C语言数据结构-串-块链串-实现块链串的子串查找操作

绝地灬酷狼 2022-11-16 05:41 270阅读 0赞

# 块链串 #

块链串定义如下：

#define BLOCK_SIZE 4    // 可由用户定义的块大小
    #define BLS_BLANK '#'   // 用于空白处的补齐字符
    
    typedef struct _block {
        char ch[BLOCK_SIZE];    //块的数据域
        struct _block *next;    //块的指针域
    } Block;
    
    typedef struct {
        Block *head;        // 串的头指针
        Block *tail;        // 串的尾指针
        int len;            // 串的当前长度
    } BLString;
    
    //字符串初始化函数：
    void blstr_init(BLString *T) {
        T->len = 0;
        T->head = NULL;
        T->tail = NULL;
    }

这些定义已包含在头文件 dsstring.h 中，请实现块链串的子串查找操作：

bool blstr_substr(BLString src, int pos, int len, BLString *sub);

*  src为要查找的字符串  
    pos为子串开始的下标  
    len为子串的长度  
    sub在函数调用运行前指向一个已经初始化好的空串，在函数返回时，sub指向串src从第pos个字符起长度为len的子串  
    函数查找成功返回true，参数不正确返回 false

提供代码

#include <stdlib.h>
    #include <stdio.h>
    #include "dsstring.h" // 请不要删除，否则检查不通过
    
    bool blstr_substr(BLString src, int pos, int len, BLString *sub) {
    
    
    }

**参考代码**

#include <stdio.h>
    #include <stdlib.h>
    // #include "dsstring.h" // 请不要删除，否则检查不通过
    #include <assert.h>
    #include <stdbool.h>
    #include <string.h>
    
    #define BLOCK_SIZE 4   // 可由用户定义的块大小
    #define BLS_BLANK '#'  // 用于空白处的补齐字符
    
    typedef struct _block {
        char ch[BLOCK_SIZE];  //块的数据域
        struct _block* next;  //块的指针域
    } Block;
    
    typedef struct {
        Block* head;  // 串的头指针
        Block* tail;  // 串的尾指针
        int len;      // 串的当前长度
    } BLString;
    
    //字符串初始化函数：
    void blstr_init(BLString* T) {
        T->len = 0;
        T->head = NULL;
        T->tail = NULL;
    }
    
    BLString* blstr_myinit(BLString* str, int length) {
        if (str == NULL) {
            str = (BLString*)malloc(sizeof(BLString));
            assert(str);
        }
        blstr_init(str);
        // 分配空间
        str->len = length;
        if (length == 0) return str;
        int blk = length / BLOCK_SIZE;
        // int offset = length % BLOCK_SIZE;
        str->head = (Block*)malloc(sizeof(Block));
        memset(str->head->ch, BLS_BLANK, sizeof(char) * BLOCK_SIZE);
        str->head->next = NULL;
        str->tail = str->head;
        Block* cnt = str->head;
        for (int i = 0; i < blk; i++) {
            Block* p = (Block*)malloc(sizeof(Block));
            memset(p->ch, BLS_BLANK, sizeof(char) * BLOCK_SIZE);
            p->next = NULL;
            cnt->next = p;
            cnt = cnt->next;
        }
        str->tail = cnt;
        return str;
    }
    
    bool blstr_substr(BLString src, int pos, int len, BLString* sub) {
        if (len == 0) return false;
            if (pos > src.len) return false;
        if (len + pos > src.len) len = src.len - pos;
        blstr_myinit(sub, len);
        Block* cnt = src.head, * cnt1 = sub->head;
        int offset = pos % BLOCK_SIZE, offset1 = 0;
        for (int i = 0; i < pos / BLOCK_SIZE; i++) cnt = cnt->next;
        while (len-- && cnt->ch[offset] != BLS_BLANK) {
            cnt1->ch[offset1++] = cnt->ch[offset++];
            if (offset == BLOCK_SIZE) {
                offset = 0;
                cnt = cnt->next;
            }
            if (offset1 == BLOCK_SIZE) {
                offset1 = 0;
                cnt1 = cnt1->next;
            }
        }
        return true;
    }
    
    
    void blstr_free(BLString* str) {
        if (!str) return;
        Block* p = str->head;
        while (p) {
            Block* next = p->next;
            free(p);
            p = next;
        }
        free(str);
    }
    
    bool char2blstr(const char* src, BLString** dst) {
        if (!src || (src && !*src)) false;
        if (*dst) blstr_free(*dst);
        int length = strlen(src);
        *dst = blstr_myinit(*dst, length);
        Block* cnt = (*dst)->head;
        int offset = 0;
        const char* c = src;
        while (*c) {
            cnt->ch[offset++] = *c;
            if (offset == BLOCK_SIZE) {
                offset = 0;
                cnt = cnt->next;
            }
            c++;
        }
    }
    
    void blstr_print(BLString* str) {
        if (!str) return;
        Block* cnt = str->head;
        int offset = 0;
        while (cnt->ch[offset] != '\0' && cnt->ch[offset] != BLS_BLANK) {
            putchar(cnt->ch[offset]);
            offset++;
            if (offset == BLOCK_SIZE) {
                offset = 0;
                cnt = cnt->next;
            }
        }
    }
    
    int main() {
        BLString* str = NULL, * dst = (BLString*)malloc(sizeof(BLString));
        assert(dst);
        char buf[512] = "Hey man!!01234567890987654321";
        // scanf("%s", buf);
        char2blstr(buf, &str);
        blstr_substr(*str, 8, 8, dst);
        blstr_print(str);
        puts("");
        blstr_print(dst);
        return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221022/83ccd8b9388f4a348137d94362422299.png