数据结构：串（ Bunch）及其实现

什么是串？

串（String）是由零个或多个字符组成的有限序列，比如 "hello" 就是一个串。串是编程中非常常见的数据结构，常用于处理文本数据。

串的特点：

顺序存储：串中的字符是连续存储的，类似于数组。
链式存储：串中的字符也可以通过链表的方式存储，每个节点存储一个字符。
常用操作：包括插入、删除、查找、替换等。

串的存储方式

1. 顺序存储

顺序存储是用数组来存储串中的字符。数组的每个元素存储一个字符，字符之间是连续存储的。

优点：

访问速度快，可以通过下标直接访问任意字符。
实现简单。

缺点：

插入和删除操作需要移动大量字符，效率低。
数组大小固定，不适合动态变化的串。

C 语言实现：

#include <stdio.h>
#include <string.h>#define MAX_SIZE 100  // 串的最大长度// 定义顺序存储的串
typedef struct {char data[MAX_SIZE];  // 存储字符的数组int length;           // 串的长度
} SeqString;// 初始化串
void InitString(SeqString *s, const char *str) {strcpy(s->data, str);  // 复制字符串到数组中s->length = strlen(str);  // 设置串的长度
}// 插入字符
int InsertString(SeqString *s, int pos, const char *str) {if (pos < 0 || pos > s->length || s->length + strlen(str) > MAX_SIZE) {return -1;  // 插入位置不合法或空间不足}// 将插入位置后的字符往后移动for (int i = s->length - 1; i >= pos; i--) {s->data[i + strlen(str)] = s->data[i];}// 插入新字符for (int i = 0; i < strlen(str); i++) {s->data[pos + i] = str[i];}s->length += strlen(str);  // 更新串的长度return 0;
}// 删除字符
int DeleteString(SeqString *s, int pos, int len) {if (pos < 0 || pos + len > s->length) {return -1;  // 删除位置不合法}// 将删除位置后的字符往前移动for (int i = pos + len; i < s->length; i++) {s->data[i - len] = s->data[i];}s->length -= len;  // 更新串的长度return 0;
}// 查找子串
int FindString(SeqString *s, const char *str) {for (int i = 0; i <= s->length - strlen(str); i++) {int j = 0;while (j < strlen(str) && s->data[i + j] == str[j]) {j++;}if (j == strlen(str)) {return i;  // 找到子串，返回起始位置}}return -1;  // 未找到子串
}// 打印串
void PrintString(SeqString *s) {printf("串内容：%s\n", s->data);
}int main() {SeqString s;InitString(&s, "hello");  // 初始化串PrintString(&s);          // 打印串InsertString(&s, 5, " world");  // 在位置 5 插入 " world"PrintString(&s);                // 打印串DeleteString(&s, 5, 6);  // 从位置 5 删除 6 个字符PrintString(&s);         // 打印串int index = FindString(&s, "llo");  // 查找子串 "llo"if (index != -1) {printf("找到子串，起始位置：%d\n", index);} else {printf("未找到子串\n");}return 0;
}

2. 链式存储

链式存储是用链表来存储串中的字符。每个节点存储一个字符，节点之间通过指针连接。

优点：

插入和删除操作效率高，不需要移动大量字符。
适合动态变化的串。

缺点：

访问速度慢，需要从头开始遍历。
内存开销大，每个节点需要额外存储指针。

C 语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义链式存储的串节点
typedef struct Node {char data;           // 存储字符struct Node *next;   // 指向下一个节点的指针
} Node;// 定义链式存储的串
typedef struct {Node *head;  // 头指针int length;  // 串的长度
} LinkString;// 初始化串
void InitString(LinkString *s, const char *str) {s->head = NULL;s->length = 0;// 从后往前插入字符，保证顺序正确for (int i = strlen(str) - 1; i >= 0; i--) {Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = str[i];newNode->next = s->head;s->head = newNode;s->length++;}
}// 插入字符
int InsertString(LinkString *s, int pos, const char *str) {if (pos < 0 || pos > s->length) {return -1;  // 插入位置不合法}// 找到插入位置的前一个节点Node *prev = NULL;Node *current = s->head;for (int i = 0; i < pos; i++) {prev = current;current = current->next;}// 插入新字符for (int i = 0; i < strlen(str); i++) {Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = str[i];newNode->next = current;if (prev == NULL) {s->head = newNode;  // 插入到头部} else {prev->next = newNode;}prev = newNode;s->length++;}return 0;
}// 删除字符
int DeleteString(LinkString *s, int pos, int len) {if (pos < 0 || pos + len > s->length) {return -1;  // 删除位置不合法}// 找到删除位置的前一个节点Node *prev = NULL;Node *current = s->head;for (int i = 0; i < pos; i++) {prev = current;current = current->next;}// 删除字符for (int i = 0; i < len; i++) {Node *temp = current;current = current->next;free(temp);s->length--;}if (prev == NULL) {s->head = current;  // 删除的是头节点} else {prev->next = current;}return 0;
}// 查找子串
int FindString(LinkString *s, const char *str) {Node *current = s->head;int index = 0;while (current != NULL) {Node *temp = current;int i = 0;while (temp != NULL && i < strlen(str) {if (temp->data != str[i]) {break;}temp = temp->next;i++;}if (i == strlen(str)) {return index;  // 找到子串，返回起始位置}current = current->next;index++;}return -1;  // 未找到子串
}// 打印串
void PrintString(LinkString *s) {Node *current = s->head;printf("串内容：");while (current != NULL) {printf("%c", current->data);current = current->next;}printf("\n");
}int main() {LinkString s;InitString(&s, "hello");  // 初始化串PrintString(&s);          // 打印串InsertString(&s, 5, " world");  // 在位置 5 插入 " world"PrintString(&s);                // 打印串DeleteString(&s, 5, 6);  // 从位置 5 删除 6 个字符PrintString(&s);         // 打印串int index = FindString(&s, "llo");  // 查找子串 "llo"if (index != -1) {printf("找到子串，起始位置：%d\n", index);} else {printf("未找到子串\n");}return 0;
}