数据结构与算法——串

块链串

前言

​ 在学习串的存储结构时我们知道，顺序存储的方式往往会导致越界的问题出现，然而当我们采用链式存储结构动态分配内存时，如果仅仅是每一个结点只对应一个字符，就会导致很大的一部分空间被浪费。因此，我们使用块链串的概念来完善串的链式存储结构。

什么是块链串

​ 简单来说，块链串就是将链表中的结点定义成一个数组，实现一个结点可以存储多个字符。而具体存储多少个字符，则要依据实际的情况做出选择。

块链串的结构定义

1
2
3
4
5
6
7
8
9
10
11
12
 typedef struct _clock
{
  char ch[BLOCK_SIZE];	//用于存放字符串的数组  
  struct _block *next;	//用于链接的指针
} Block;

typedef struct
{
  Block *head;	//指向块链串的头结点
  Block *tail;	//始终指向块链串的尾结点
  int len;	//记录块链串的总长度
}BLString;

块链串的初始化

1
2
3
4
5
6
void blstr_init(BLString *T)
{
    T ->len = 0;
    T ->head = NULL;
    T ->tail = NULL;
}

块链串的SubString(BLString src, int pos, int len， BLString *sub,)函数

​ 该函数的作用是，用Sub返回串S中第pos个字符起长度为len的子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
int blstr_substr(BLString src, int pos, int len, BLString *sub)
{
    int i, j, k, count;
    Block *p, *r;
    
    //是否满足题目条件的判断
    //原串是否为空
    if(src.head == NULL && src.tail == NULL && src.len == 0)
        return false;
    //pos的位置是否正确
    if(len <= 0 || pos < 0 || pos > src.len - 1)
        return false;

    //使指针p移动到pos的位置上
    for(count = 1, p = src.head; pos > count*BLOCK_SIZE; p = p->next, count++);

    //初始化指针r
    r = sub->head;
    //i用于控制存入的变量个数
    i = 0;
    //j用于控制r中的数组切换
    j = 0;
    //k用于控制src中的数组的切换
    k = (pos % BLOCK_SIZE);  
    
    //如果pos之后的字符串不足len个，则返回src在pos之后的所有字符
    if(pos + len > src.len)
        len = src.len -pos;

    while(i < len)
    {
        if(!r)
        {
            r = (Block*)malloc(sizeof(Block));
            if(!r)
                return false;
            r->next = NULL;

            //解决第一次(*sub).head的初始化，使他指向r的以一个块
            if(!sub->head)
                sub->head = sub->tail = r;
            //保证(*sub).tail始终指向r的末尾块
            else
            {
                sub-> tail -> next = r;
            }
        }

        //开始将pos之后len长度的字符串输入到r中
        while(i < len)
        {
            r->ch[j] = p->ch[k];
            j = (1 + j) % BLOCK_SIZE;
            k = (1 + k) % BLOCK_SIZE;
            i++;

            //控制p中的数组切换
            if(!k)
                p = p->next;
            //控制r中的数组切换
            if(!j)
            {
                r = r->next;
                break;  //返回到上一级循环，给r重新分配一个BLOCK，并且调整tail指针的位置
            }
        }
    }

    sub->len = len;

    //将r中最后一个BLOCK中没有字符的部分用 '#'补齐
    count = (len - 1) % BLOCK_SIZE + 1;
    while(count < BLOCK_SIZE)
    {
        sub->tail->ch[count] = '#';
        count ++;
    }
    
    return true;
}

​

  • 由上述代码，总体的结构是一个大的循环，循环的作用是给sub创建一个新的结点。循环结构的特别之处在于加入条件区别了sub的初始化和之后的链接。
  • 块链串的其他操作函数，之后遇到时在具体介绍吧！