数据结构：串（ 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;
}串的常用算法
1. 模式匹配算法
模式匹配是串的一个重要操作，用于查找子串在主串中的位置。常见的算法有：
-
朴素算法：逐个字符比较，时间复杂度为 O(n*m)。
-
KMP 算法：通过预处理模式串，减少比较次数，时间复杂度为 O(n+m)。
串的使用场景
-
文本编辑器：用于处理文本的插入、删除、查找等操作。
-
搜索引擎：用于匹配关键词和网页内容。
-
编译器：用于解析源代码中的字符串。
应用实例：文本编辑器
文本编辑器可以用串来实现：
-
插入文本：在指定位置插入字符串。
-
删除文本：删除指定位置的字符串。
-
查找文本：查找指定的关键词。
-
替换文本：将指定的字符串替换为另一个字符串。
总结
串是一种非常重要的数据结构，常用于处理文本数据。顺序存储和链式存储各有优缺点，适合不同的场景。通过学习串的基本操作和常用算法，你可以更好地解决实际问题。希望通过这篇文章，你能轻松掌握串的相关知识！