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

一、顺序存储结构

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

定长顺序存储：

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

堆分配存储：

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

二、链式存储结构

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

单链表存储：

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

块链存储：

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

三、其他存储方式

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

四、实现示例

以下是使用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;
}