承德网站建设步骤,网站报价系统,wordpress 商品模板,二级网站建设 管理思路第四部分、字符串#xff0c;数据结构中的串存储结构 串存储结构#xff0c;也就是存储字符串的数据结构。
很明显#xff0c;字符串之间的逻辑关系也是“一对一”#xff0c;用线性表的思维不难想出#xff0c;串存储结构也有顺序存储和链式存储。
提到字符串#xff…第四部分、字符串数据结构中的串存储结构 串存储结构也就是存储字符串的数据结构。
很明显字符串之间的逻辑关系也是“一对一”用线性表的思维不难想出串存储结构也有顺序存储和链式存储。
提到字符串常做的操作就是串之间的匹配因为本章给初学者介绍 2 种串的模式匹配算法BF 算法和 KMP 算法。
三、串的堆分配存储结构
串的堆分配存储其具体实现方式是采用动态数组存储字符串。 通常编程语言会将程序占有的内存空间分成多个不同的区域程序包含的数据会被分门别类并存储到对应的区域。拿 C 语言来说程序会将内存分为 4 个区域分别为堆区、栈区、数据区和代码区其中的堆区是本节所关注的。 与其他区域不同堆区的内存空间需要程序员手动使用 malloc 函数申请并且在不用后要手动通过 free 函数将其释放。 C 语言中使用 malloc 函数最多的场景是给数组分配空间这类数组称为动态数组。例如 char * a (char*)malloc(5*sizeof(char)); 此行代码创建了一个动态数组 a通过使用 malloc 申请了 5 个 char 类型大小的堆存储空间。动态数组相比普通数组静态数组的优势是长度可变换句话说根据需要动态数组可额外申请更多的堆空间使用 relloc 函数 a (char*)realloc(a, 10*sizeof(char)); 通过使用这行代码之前具有 5 个 char 型存储空间的动态数组其容量扩大为可存储 10 个 char 型数据。 下面给大家举一个完整的示例以便对串的堆分配存储有更清楚地认识。该程序可实现将两个串data.bian 和 cheng.net合并为一个串 #include stdio.h #include stdlib.h #include string.h int main() { char * a1 NULL; char * a2 NULL; a1 (char*)malloc(10 * sizeof(char)); strcpy(a1, data.bian);//将字符串data.bian复制给a1 a2 (char*)malloc(10 * sizeof(char)); strcpy(a2, cheng.net); int lengthA1 strlen(a1);//a1串的长度 int lengthA2 strlen(a2);//a2串的长度 //尝试将合并的串存储在 a1 中如果 a1 空间不够则用realloc动态申请 if (lengthA1 lengthA1 lengthA2) { a1 (char*)realloc(a1, (lengthA1 lengthA21) * sizeof(char)); } //合并两个串到 a1 中 for (int i lengthA1; i lengthA1 lengthA2; i) { a1[i] a2[i - lengthA1]; } //串的末尾要添加 \0避免出错 a1[lengthA1 lengthA2] \0; printf(%s, a1); //用完动态数组要立即释放 free(a1); free(a2); return 0; } 程序运行结果 data.biancheng.net 注意程序中给 a1 和 a2 赋值时使用了 strcpy 复制函数。这里不能直接用 a1 data.biancheng程序编译会出错报错信息为 没有 malloc 的空间不能 free。因为 strcpy 函数是将字符串复制到申请的存储空间中而直接赋值是字符串存储在别的内存空间本身是一个常量放在数据区中更改了指针 a1 和 a2 的指向也就是说之前动态申请的存储空间虽然申请了结果还没用呢就丢了。 四、串的块链存储结构 串的块链存储指的是使用链表结构存储字符串。 本节实现串的块链存储使用的是无头节点的单链表。当然根据实际需要你也可以自行决定所用链表的结构双链表还是单链表有无头节点。 我们知道单链表中的 单 强调的仅仅是链表各个节点只能有一个指针并没有限制数据域中存储数据的具体个数。因此在设计链表节点的结构时可以令各节点存储多个数据。 例如图 1 所示是用链表存储字符串 shujujiegou该链表各个节点中可存储 1 个字符 图 1 各节点仅存储 1 个数据元素的链表
同样图 2 设置的链表各节点可存储 4 个字符 图 2 各节点可存储 4 个数据元素的链表
从图 2 可以看到使用链表存储字符串其最后一个节点的数据域不一定会被字符串全部占满对于这种情况通常会用 # 或其他特殊字符能与字符串区分开就行将最后一个节点填满。 初学者可能会问使用块链结构存储字符串时怎样确定链表中节点存储数据的个数呢 链表各节点存储数据个数的多少可参考以下几个因素
串的长度和存储空间的大小若串包含数据量很大且链表申请的存储空间有限此时应尽可能的让各节点存储更多的数据提高空间的利用率每多一个节点就要多申请一个指针域的空间反之如果串不是特别长或者存储空间足够就需要再结合其他因素综合考虑程序实现的功能如果实际场景中需要对存储的串做大量的插入或删除操作则应尽可能减少各节点存储数据的数量反之就需要再结合其他因素。
以上两点仅是目前想到影响节点存储数据个数的因素在实际场景中还需结合实现环境综合分析。 这里给出一个实现串的块链存储的 C 语言程序以加深初学者对此字符串存储方式的认识 #includestdio.h #includestdlib.h #includestring.h #define linkNum 3//全局设置链表中节点存储数据的个数 typedef struct Link { char a[linkNum]; //数据域可存放 linkNum 个数据 struct Link * next; //代表指针域指向直接后继元素 }link; // nk为节点名每个节点都是一个 link 结构体 link * initLink(link * head, char * str); void displayLink(link * head); int main() { link * head NULL; head initLink(head, data.biancheng.net); displayLink(head); return 0; } //初始化链表其中head为头指针str为存储的字符串 link * initLink(link * head, char * str) { int length strlen(str); //根据字符串的长度计算出链表中使用节点的个数 int num length/linkNum; if (length%linkNum) { num; } //创建并初始化首元节点 head (link*)malloc(sizeof(link)); head-next NULL; link *temp head; //初始化链表 for (int i 0; inum; i) { int j 0; for (; jlinkNum; j) { if (i*linkNum j length) { temp-a[j] str[i*linkNum j]; } else temp-a[j] #; } if (i*linkNum j length) { link * newlink (link*)malloc(sizeof(link)); newlink-next NULL; temp-next newlink; temp newlink; } } return head; } //输出链表 void displayLink(link * head) { link * temp head; while (temp) { for (int i 0; i linkNum; i) { printf(%c, temp-a[i]); } temp temp-next; } } 程序输出结果为 data.biancheng.net
