这里主要说四大模块：线性表（顺序表与链表的存储实现、操作及对比）、栈（LIFO特性、顺序/链式实现及表达式求值应用）、队列（FIFO特性、循环队列解决假溢出问题）和串（BF/KMP模式匹配算法）。文档通过C语言代码示例、时间复杂度分析、对比表格和真题解析，重点突出线性结构的存储原理、基本操作实现（如链表插入删除、栈的括号匹配）以及典型应用场景（如递归调用、BFS算法），比较重要的知识点：
-
线性表
-
顺序表（数组存储，快速访问但插入删除慢）
-
链表（指针链接，动态内存分配，插入删除快）
-
包含单链表、循环链表和双向链表等变体
-
栈
-
后进先出（LIFO）结构
-
顺序栈和链栈两种实现
-
典型应用：函数调用、表达式求值、括号匹配
-
队列
-
先进先出（FIFO）结构
-
重点掌握循环队列解决"假溢出"问题
-
链队列的实现方式
-
串
-
字符串的存储结构
-
基础的模式匹配算法（BF算法）
-
（部分教材包含）KMP算法思想
知识拓扑
知识点介绍
1. 线性表
1.1 基本概念与逻辑结构
定义：线性表是由n（n≥0）个相同类型数据元素构成的有限序列，记作（a₁,a₂,...,aₙ）。其中：
-
元素个数n称为表长
-
n=0时称为空表
-
存在唯一"第一个"和"最后一个"元素
重要特性：
-
元素类型相同
-
元素具有序偶关系
-
每个元素最多有一个直接前驱和一个直接后继
// 抽象数据类型（ADT）标准定义
ADT List {数据对象：D = {aᵢ | aᵢ ∈ ElemSet, i=1,2,...,n, n≥0}数据关系：R = {<aᵢ₋₁,aᵢ> | aᵢ₋₁,aᵢ ∈ D, i=2,...,n}基本操作：InitList(&L); // 构造空线性表DestroyList(&L); // 销毁线性表ListEmpty(L); // 判空ListLength(L); // 求表长GetElem(L,i,&e); // 按位查找LocateElem(L,e); // 按值查找ListInsert(&L,i,e); // 插入元素ListDelete(&L,i,&e); // 删除元素
} ADT List
1.2 顺序存储结构详解
物理结构：用一组地址连续的存储单元依次存放线性表的元素
存储特点：
-
逻辑上相邻的元素物理位置也相邻
-
随机存取特性（通过首地址+偏移量直接访问）
-
需要预分配固定大小的存储空间
元素位置公式：
LOC(aᵢ) = LOC(a₁) + (i-1)*sizeof(ElemType)
插入操作算法分析：
#define MAXSIZE 100 // 顺序表最大容量
typedef struct {ElemType data[MAXSIZE]; // 存储空间基址int length; // 当前长度
} SqList;
Status ListInsert(SqList &L, int i, ElemType e) {// 在顺序表L的第i个位置插入新元素eif (i<1 || i>L.length+1) return ERROR; // 位置不合法if (L.length >= MAXSIZE) return ERROR; // 存储空间已满for (int j=L.length; j>=i; j--)L.data[j] = L.data[j-1]; // 插入位置及之后的元素后移L.data[i-1] = e; // 放入新元素L.length++; // 表长增1return OK;
}
时间复杂度分析：
最好情况（表尾插入）：O(1)
最坏情况（表头插入）：O(n)
平均情况：Σ(i=1→n+1) pᵢ(n-i+1) = n/2 → O(n)
1.3 链式存储结构详解
结点结构：
typedef struct LNode { // 结点类型定义ElemType data; // 数据域struct LNode *next; // 指针域
} LNode, *LinkList;
头结点作用：
-
统一空表和非空表的处理
-
方便首元结点的插入/删除操作
-
使链表操作参数统一
单链表创建（尾插法）：
void CreateList_R(LinkList &L, int n) {L = (LinkList)malloc(sizeof(LNode)); // 创建头结点L->next = NULL;LNode *r = L; // 尾指针初始化for (int i=0; i<n; ++i) {LNode *p = (LNode*)malloc(sizeof(LNode));scanf("%d", &p->data); // 输入元素值p->next = NULL;r->next = p; // 插入到表尾r = p; // 更新尾指针}
}
双向链表优势：
-
可双向遍历
-
删除操作更高效（无需定位前驱）
typedef struct DuLNode {ElemType data;struct DuLNode *prior;struct DuLNode *next;
} DuLNode, *DuLinkList;
1.4 应用场景对比分析
| 对比维度 | 顺序表 | 链表 |
|---|---|---|
| 存储密度 | 100% | <100%（需存储指针） |
| 访问方式 | 随机访问（O(1)） | 顺序访问（O(n)） |
| 插入/删除 | 平均移动n/2个元素（O(n)） | 修改指针（O(1)） |
| 空间分配 | 静态分配（可能浪费/溢出） | 动态分配（按需申请） |
| 典型应用 | 数据量固定、查询频繁的场景 | 数据量变化大、频繁增删的场景 |
2. 栈
2.1 栈的定义与特性
后进先出（LIFO）原理：
-
限定仅在表尾（栈顶）进行插入和删除操作
-
栈底固定，栈顶动态变化
数学性质：卡特兰数（Catalan number）计算合法的出栈顺序数：
Cₙ = (1/(n+1)) * C(2n,n)
2.2 两种实现方式对比
顺序栈定义：
#define STACK_INIT_SIZE 100
typedef struct {SElemType *base; // 栈底指针SElemType *top; // 栈顶指针int stacksize; // 当前分配空间
} SqStack;
链栈优势：
-
无需考虑栈满情况
-
多栈共享存储空间更方便
2.3 栈的经典应用场景
递归调用实现：
// 阶乘函数的递归实现
int Factorial(int n) {if (n==0) return 1;else return n * Factorial(n-1);
}
系统使用调用栈存储：
返回地址
参数传递
局部变量
表达式求值算法：
中缀表达式：3*(4+5)/2 转换步骤： 1. 初始化操作数栈和运算符栈 2. 遇到数字直接入操作数栈 3. 遇到运算符与栈顶比较优先级... 最终结果：3 4 5 + * 2 /
（后续章节内容因篇幅限制暂略，完整版包含所有章节的详细实现和真题解析）
5. 知识图谱
6. 真题破解
2023年真题：设计算法判断链表是否中心对称
bool isSymmetrical(LinkList L) {// 1. 使用快慢指针找到中点LNode *slow = L->next, *fast = L->next;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}// 2. 反转后半部分链表LNode *pre = NULL, *cur = slow;while (cur) {LNode *temp = cur->next;cur->next = pre;pre = cur;cur = temp;}// 3. 前后半部分比较LNode *p1 = L->next, *p2 = pre;while (p2) {if (p1->data != p2->data) return false;p1 = p1->next;p2 = p2->next;}return true;
}