数据结构 线性表
具有相同数据类型的n个数据元素的有限序列
元素具有相同数据类型
元素之间具有顺序关系（除首尾元素外，每个元素有且仅有一个直接前驱和一个直接后继）
元素个数有限
1. 顺序表（顺序存储）
顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素。
特点：
逻辑上相邻的元素物理位置也相邻
随机访问（通过下标直接访问）
插入/删除需要移动大量元素
#define MAX_SIZE 100 // 最大容量
typedef struct {
int data[MAX_SIZE]; // 存储数组
int length; // 当前长度
} SeqList;
// 初始化
void InitList(SeqList *L) {
L->length = 0;
}
// 插入操作
int ListInsert(SeqList *L, int pos, int elem) {
if (pos < 1 || pos > L->length + 1 || L->length >= MAX_SIZE) {
return 0; // 插入失败
}
for (int i = L->length; i >= pos; i--) {
L->data[i] = L->data[i-1];
}
L->data[pos-1] = elem;
L->length++;
return 1; // 插入成功
}
// 删除操作
int ListDelete(SeqList *L, int pos, int *elem) {
if (pos < 1 || pos > L->length) {
return 0; // 删除失败
}
*elem = L->data[pos-1];
for (int i = pos; i < L->length; i++) {
L->data[i-1] = L->data[i];
}
L->length--;
return 1; // 删除成功
}- 顺序表适用场景：
- 需要频繁访问元素
- 元素数量变化不大
- 已知大致元素数量
2. 链表（链式存储）
链表是用一组任意的存储单元存储线性表的数据元素，通过指针连接元素。
特点：
逻辑上相邻的元素物理位置不一定相邻
插入/删除不需要移动元素
不支持随机访问
typedef struct LNode {
int data; // 数据域
struct LNode *next; // 指针域
} LNode, *LinkList;
// 头插法建立链表
void CreateListHead(LinkList *L, int n) {
*L = (LinkList)malloc(sizeof(LNode));
(*L)->next = NULL;
for (int i = 0; i < n; i++) {
LNode *p = (LNode*)malloc(sizeof(LNode));
p->data = i+1;
p->next = (*L)->next;
(*L)->next = p;
}
}
// 插入操作
int ListInsert(LinkList *L, int pos, int elem) {
LNode *p = *L;
int j = 0;
while (p && j < pos-1) {
p = p->next;
j++;
}
if (!p || j > pos-1) return 0;
LNode *s = (LNode*)malloc(sizeof(LNode));
s->data = elem;
s->next = p->next;
p->next = s;
return 1;
}
// 删除操作
int ListDelete(LinkList *L, int pos, int *elem) {
LNode *p = *L;
int j = 0;
while (p->next && j < pos-1) {
p = p->next;
j++;
}
if (!(p->next) || j > pos-1) return 0;
LNode *q = p->next;
*elem = q->data;
p->next = q->next;
free(q);
return 1;
}链表适用场景：
需要频繁插入/删除
元素数量变化大
无法预估元素数量
线性表的常见操作
| 操作 | 顺序表 | 链表 |
|---|---|---|
| 访问元素 | O(1) | O(n) |
| 插入/删除 | O(n) | O(1) [已知位置] |
| 查找元素 | O(n) | O(n) |
| 空间分配 | 静态/动态数组 | 动态分配 |
线性表的变种
双向链表：每个节点包含前驱和后继指针
循环链表：尾节点指向头节点
静态链表：用数组实现的链表（游标实现）
栈和队列：受限的线性表（只能在端点操作）
线性表是数据结构的基础，理解它对学习更复杂的数据结构非常重要。
数组
数组实现的线性表适用于：
需要频繁随机访问的场景
元素数量相对固定的情况
// 定义数组
int array[MAX_SIZE];
int length = 0; // 当前长度
// 获取元素
function get(i):
if i < 0 OR i ≥ length:
return error
return array[i]
// 插入元素
function insert(i, e):
if length == MAX_SIZE:
return error // 数组已满
if i < 0 OR i > length:
return error // 位置不合法
// 将i及之后的元素后移
for j = length-1 downto i:
array[j+1] = array[j]
array[i] = e
length++
// 删除元素
function delete(i):
if i < 0 OR i ≥ length:
return error
// 将i之后的元素前移
for j = i to length-2:
array[j] = array[j+1]
length--
树状数组
（又称二叉索引树）是一种高效实现前缀和查询与单点更新的数据结构
核心思想
利用二进制表示中最低位的1来构建层次结构，每个节点存储特定区间的和。
基本操作原理
lowbit计算：
x & -x，获取x的二进制表示中最低位的1例如：6 (110) 的lowbit是 2 (10)
更新操作：
修改一个元素时，需要更新所有包含该元素的区间
通过不断加上lowbit值向上更新
查询操作：
查询前缀和时，通过不断减去lowbit值向下累加
class FenwickTree {
private:
vector<int> tree;
int lowbit(int x) {
return x & -x;
}
public:
FenwickTree(int size) : tree(size + 1, 0) {}
// 单点更新：位置i增加val
void update(int i, int val) {
while (i < tree.size()) {
tree[i] += val;
i += lowbit(i);
}
}
// 查询前缀和：[1..i]的和
int query(int i) {
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= lowbit(i);
}
return sum;
}
// 区间查询：[i..j]的和
int rangeQuery(int i, int j) {
return query(j) - query(i - 1);
}
};树状数组常用于：
计算逆序对数量
实时统计前缀和
解决某些计数问题
配合离散化处理大数据集
字符串:(KMP 字典树 AC自动机 BM 后缀数组)
KMP: 高效的字符串匹配算法 (在主字符串 中 找 模式串 出现的 位置)
KMP算法特别适用于：
在长文本中反复搜索同一模式串
需要高效字符串匹配的场景（如文本编辑器、IDE的查找功能）
作为其他算法的基础组件（如字符串周期性问题）
主串(text): "ABABDABACDABABCABAB"
模式串(pattern): "ABABCABAB"
构建next数组：[0, 0, 1, 2, 0, 1, 2, 3, 4]
匹配过程：
在text[10]处找到完整匹配字典树:用于高效地存储和检索字符串集合。它也被称为前缀树或单词查找树。
基本概念
字典树的核心特点：
每个节点代表一个字符串的字符
从根节点到某一节点的路径上的字符连接起来，构成该节点对应的字符串
根节点对应空字符串
通常在节点中用标志位标记字符串的结束
字典树的节点通常包含：
子节点指针（通常用数组或哈希表实现）
是否是单词结尾的标志
可能的附加数据（如词频等）
应用场景
自动补全系统：如搜索引擎的搜索建议
拼写检查：快速判断单词是否存在
IP路由：最长前缀匹配
单词游戏：如Boggle、Scrabble等
输入法：中文输入法的候选词推荐
AC自动机:
AC自动机是一种多模式串匹配算法，可以同时查找多个模式串在文本中的所有出现位置。结合了字典树（Trie）和KMP算法的思想，是字符串匹配领域的重要算法。
核心思想
构建字典树：将所有模式串构建成一棵字典树
添加失败指针：类似于KMP的next数组，实现匹配失败时的跳转
多模式匹配：在文本串上进行高效扫描，同时匹配所有模式串
AC自动机包含三个核心部分：
Trie树结构：存储所有模式串
失败指针（fail指针）：匹配失败时的跳转指针
输出表：记录每个节点代表的完整模式串
BM BM算法是一种高效的字符串匹配算法 实际应用中通常比KMP算法表现更好
核心思想
BM算法采用两种启发式规则来跳过不必要的比较：
坏字符规则（Bad Character Rule）：从右向左比较，遇到不匹配字符时根据预处理的坏字符表滑动模式串
好后缀规则（Good Suffix Rule）：当发现部分匹配时，根据已匹配的后缀信息滑动模式串
应用场景
文本编辑器的查找功能
病毒扫描中的特征码匹配
生物信息学中的DNA序列匹配
大文本中的关键词搜索
后缀数组
后缀数组是一种强大的字符串处理数据结构，能够高效解决多种字符串问题。它是后缀树的空间优化替代方案，在实际应用中更为常用
基本概念
后缀数组是一个包含字符串所有后缀的按字典序排序的数组，存储的是这些后缀的起始索引。
对于长度为n的字符串S，其后缀数组SA是一个[0..n-1]的排列，满足：
S[SA[0]..] < S[SA[1]..] < ... < S[SA[n-1]..]
示例
字符串S = "banana"（长度n=6）
索引 后缀
0 banana
1 anana
2 nana
3 ana
4 na
5 a
排序后得到后缀数组SA = [5, 3, 1, 0, 4, 2]2025年6月13日 23点21分