数据结构 （12）串的存储实现

一、顺序存储结构

       顺序存储结构是用一组连续的存储单元来存储串中的字符序列。这种存储方式类似于线性表的顺序存储结构，但串的存储对象仅限于字符。顺序存储结构又可以分为定长顺序存储和堆分配存储两种方式。

1. 定长顺序存储：

   • 使用静态数组存储（定长，提前开辟内存空间）字符串。
   • 为每个串变量分配一个固定长度的存储区，即定长数组。
   • 串的实际长度可以在预定义长度的范围内随意，但超出预定义长度的串值会被舍弃，称为“截断”。

2. 堆分配存储：

   • 使用动态数组存储字符串。
   • 串的存储空间在程序运行时根据串的实际长度动态分配。
   • 这种方式可以克服定长顺序存储中串长受限的问题。

二、链式存储结构

       链式存储结构是通过链表来存储串的每个字符。每个结点存储一个或多个字符，同时包括一个指向下一个结点的指针。链式存储结构便于进行插入和删除操作，但不如顺序存储结构那样方便于随机访问。

1. 单链表存储：

   • 每个节点存储一个字符，但这种方式存在较大的空间浪费。
   • 为了提高空间利用率，可以每个节点存储多个字符，最后一个节点若未被占满，可用“#”或其他非串值字符补全。

2. 块链存储：

   • 类似于线性表的链式存储结构，但每个节点称为“块”，可以存储多个字符。
   • 这种方式结合了顺序存储和链式存储的优点，既便于进行插入和删除操作，又提高了空间利用率。

三、其他存储方式

       除了顺序存储和链式存储外，还有一些其他的串存储方式，如紧缩存储和非紧缩存储等。紧缩存储是指每个存储单元中存放多个字符，以提高存储密度；而非紧缩存储则是一个存储单元中只存放一个字符。

四、实现示例

     以下是使用C语言实现的顺序存储和链式存储的简单示例：

1. 顺序存储实现：

   #include <stdio.h>
   #include <string.h>#define MAXSIZE 255
   typedef struct {char ch[MAXSIZE];int length;
   } SString;int main() {SString str1, str2;strcpy(str1.ch, "Hello, World!");str1.length = strlen(str1.ch);strcpy(str2.ch, "C Programming");str2.length = strlen(str2.ch);// 串连接操作strcat(str1.ch, " ");strcat(str1.ch, str2.ch);str1.length = strlen(str1.ch);printf("The concatenated string is: %s\n", str1.ch);return 0;
   }

2. 链式存储实现：

   #include <stdio.h>
   #include <stdlib.h>#define CHUNKSIZE 80
   typedef struct chunk {char ch[CHUNKSIZE];struct chunk *next;
   } chunk;typedef struct {chunk *head, *tail;
   } LinkStrNode;int main() {LinkStrNode str;str.head = str.tail = NULL;char input[100];printf("Input the string: ");scanf("%s", input);// 构造链表存储字符串chunk *current = NULL;for (int i = 0; input[i] != '\0'; i++) {chunk *new_chunk = (chunk *)malloc(sizeof(chunk));new_chunk->ch[0] = input[i];new_chunk->ch[1] = '\0'; // 字符串结尾new_chunk->next = NULL;if (str.tail == NULL) {str.head = str.tail = new_chunk;} else {str.tail->next = new_chunk;str.tail = new_chunk;}}// 输出链表存储的字符串current = str.head;while (current != NULL) {printf("%s", current->ch);current = current->next;}printf("\n");// 释放链表内存current = str.head;while (current != NULL) {chunk *temp = current;current = current->next;free(temp);}return 0;
   }

五、总结

       串的存储实现方式多种多样，每种方式都有其优点和缺点。在实际应用中，需要根据具体的需求和场景选择合适的存储方式。顺序存储结构适用于串长固定且操作频繁的场景；链式存储结构则适用于串长变化较大且需要频繁进行插入和删除操作的场景。

 结语  

傻瓜用嘴说话

聪明人用脑袋说话

智慧的人用心说话

！！！