当前位置：首页 > news >正文

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

news 2024/11/27 5:37:02

一、顺序存储结构

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

定长顺序存储：

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

堆分配存储：

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

二、链式存储结构

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

单链表存储：

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

块链存储：

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

三、其他存储方式

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

四、实现示例

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

顺序存储实现：

#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;
}

链式存储实现：

#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;
}