数据结构第四章串

🤖 Assistant

# 📜 第四章 串（String）

## 🌟 基本概念
### 🎯 串是什么？
🔹 **定义**：串是由零个或多个字符组成的**有限序列**（线性表的特例，元素类型固定为字符）  
🔹 **关键术语**：  
  - **子串**：串中任意连续字符组成的子序列  
  - **主串**：包含子串的原始串  
  - **字符位置**：字符在序列中的序号（从1开始）  
  - **串相等**：长度相同且对应位置字符完全相同  

🔸 **示例对比**：  
```text
主串 S = "HelloWorld"
子串 T = "lloWo"
空串 = ""
空格串 = "   "（包含3个空格）

🏗️ 串的存储结构

📌 顺序存储结构（定长）

#define MAXLEN 255
typedef struct {
    char ch[MAXLEN];  // 存储字符的数组
    int length;       // 当前串长度
} HString;

🔸 特点：

预分配固定长度空间
可能截断超长字符串（需处理溢出问题）

📌 堆分配存储（动态扩展）

typedef struct {
    char *ch;   // 动态分配首地址
    int length; // 实际长度
} DString;

// 初始化示例
DString S;
S.ch = (char*)malloc(100 * sizeof(char)); 
S.length = 0;

🔹 优势：可动态调整内存大小（realloc实现扩容）

📌 链式存储（块链结构）

#define CHUNKSIZE 4  // 每个节点存4字符
typedef struct Chunk {
    char ch[CHUNKSIZE];
    struct Chunk *next;
} Chunk;

typedef struct {
    Chunk *head, *tail;  // 头尾指针
    int curlen;          // 当前总长度
} LString;

🔸 特点：

存储密度 = 实际字符数 / 总分配空间
适合超大文本存储（如小说内容）

🔍 串的基本操作

1. 求串长（StrLength）

1
2
3

int StrLength(DString S) {
    return S.length;  // O(1)
}

2. 串比较（StrCompare）

int StrCompare(DString S, DString T) {
    for(int i=0; i<S.length && i<T.length; i++){
        if(S.ch[i] != T.ch[i]) 
            return S.ch[i]-T.ch[i];
    }
    return S.length - T.length; // 前缀相同则比较长度
}

3. 串连接（Concat）

DString Concat(DString S, DString T) {
    DString newStr;
    newStr.ch = (char*)malloc((S.length + T.length) * sizeof(char));
    // 复制S的内容
    for(int i=0; i<S.length; i++) newStr.ch[i] = S.ch[i];
    // 追加T的内容
    for(int i=0; i<T.length; i++) newStr.ch[S.length+i] = T.ch[i];
    newStr.length = S.length + T.length;
    return newStr;  // 时间复杂度 O(n+m)
}

⚔️ 模式匹配算法

🛠️ BF算法（暴力匹配）

int Index_BF(DString S, DString T) {
    int i=0, j=0;
    while(i < S.length && j < T.length) {
        if(S.ch[i] == T.ch[j]) { i++; j++; }
        else { i = i - j + 1; j = 0; }  // i回溯
    }
    return (j >= T.length) ? (i - T.length) : -1;
}

🔸 时间复杂度：O(n×m)（最坏情况）
🔹 示例流程：
主串 ABABCABCAC，模式串 ABCAC
BF算法示例

🎯 KMP算法（改进版）

核心思想：利用已匹配信息避免回溯

// 关键：构建next数组
void get_next(DString T, int next[]) {
    int i=0, j=-1;
    next[0] = -1;
    while(i < T.length-1) {
        if(j==-1 || T.ch[i]==T.ch[j]) {
            i++; j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

// KMP主算法
int Index_KMP(DString S, DString T) {
    int i=0, j=0;
    int next[T.length];
    get_next(T, next);
    while(i < S.length && j < T.length) {
        if(j==-1 || S.ch[i]==T.ch[j]) {i++; j++;}
        else j = next[j];  // j回退，i不回溯
    }
    return (j >= T.length) ? (i - T.length) : -1;
}

🔹 性能飞跃：时间复杂度 → O(n+m)
🔸 next数组计算示例：模式串 ABCDABD
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|———|—-|—-|—-|—-|—-|—-|—-|
| 字符 | A | B | C | D | A | B | D |
| next | -1| 0 | 0 | 0 | 0 | 1 | 2 |

📊 模式匹配算法对比

算法	时间复杂度	空间复杂度	优点	缺点
BF算法	O(n×m)	O(1)	实现简单	效率低，回溯多
KMP算法	O(n+m)	O(m)	无回溯，效率高	需要预处理next数组

🚀 实际应用场景

文本编辑器：快速查找/替换关键词
搜索引擎：网页内容的关键词匹配
生物信息：DNA序列模式匹配
代码解析：XML/JSON等格式校验
数据压缩：LZ77等压缩算法基于字符串匹配

🧠 思维导图总结

graph TD
    A[串] --> B[基本概念]
    A --> C[存储结构]
    A --> D[基本操作]
    A --> E[模式匹配]
    
    B --> F[空串/空格串]
    B --> G[子串/主串]
    
    C --> H[顺序存储]
    C --> I[堆分配]
    C --> J[链式存储]
    
    D --> K[连接]
    D --> L[比较]
    D --> M[求子串]
    
    E --> N[BF算法]
    E --> O[KMP算法]
    O --> P[next数组]

📜 扩展知识

1. KMP优化：nextval数组

void get_nextval(DString T, int nextval[]) {
    int i=0, j=-1;
    nextval[0] = -1;
    while(i < T.length-1) {
        if(j==-1 || T.ch[i] == T.ch[j]) {
            i++; j++;
            // 新增优化判断
            if(T.ch[i] != T.ch[j]) nextval[i] = j;
            else nextval[i] = nextval[j];
        } else {
            j = nextval[j];
        }
    }
}