可运行版本 · C++
每个文件均可独立编译运行（g++ 文件名.cpp -o out && ./out），带 main 测试用例。
文件一览
| 序号 | 内容 | 文件 |
|---|---|---|
| 01 | 线性表 | 01_线性表.cpp |
| 02 | 栈与队列 | 02_栈与队列.cpp |
| 03 | 二叉树 | 03_二叉树.cpp |
| 04 | 排序算法 | 04_排序算法.cpp |
| 05 | 串匹配与查找 | 05_串匹配与查找.cpp |
| 06 | 图算法 | 06_图算法.cpp |
01 线性表
cpp
/*
* ============================================================
* 408 考研数据结构 —— 线性表 (可运行 C++ 版)
* 文件: 01_线性表.cpp
* 编译: g++ 01_线性表.cpp -o test && ./test
* ============================================================
*
* 覆盖内容:
* 1. 顺序表: 初始化、插入、删除
* 2. 单链表: 尾插法建表、链表逆置
* 3. ★ 2010 真题: 循环左移 (三次逆置法)
* 4. ★ 2011 真题: 两有序数组求中位数
* 5. ★ 2013 真题: 摩尔投票法求主元素
*
* C++ 特性: 使用引用 & 传参，简化指针操作
* ============================================================
*/
#include <cstdio>
#include <cstdlib>
#define MaxSize 50
typedef int ElemType;
/* ========== 一、顺序表 ========== */
typedef struct {
ElemType data[MaxSize];
int length;
} SqList;
/* 初始化 */
void InitList(SqList &L) {
L.length = 0;
}
/* 插入: 在第 i 个位置(1-based)插入元素 e */
bool ListInsert(SqList &L, int i, ElemType e) {
if (i < 1 || i > L.length + 1 || L.length >= MaxSize)
return false;
for (int j = L.length; j >= i; j--) // 后移腾位
L.data[j] = L.data[j - 1];
L.data[i - 1] = e; // 位序 i 对应下标 i-1
L.length++;
return true;
}
/* 删除: 删除第 i 个位置的元素, 用 e 带回 */
bool ListDelete(SqList &L, int i, ElemType &e) {
if (i < 1 || i > L.length)
return false;
e = L.data[i - 1];
for (int j = i; j < L.length; j++) // 前移填充
L.data[j - 1] = L.data[j];
L.length--;
return true;
}
/* 打印顺序表 */
void PrintSqList(SqList L) {
printf("[ ");
for (int i = 0; i < L.length; i++)
printf("%d ", L.data[i]);
printf("]\n");
}
/* ========== 二、单链表 ========== */
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
/* 尾插法建表: 数据顺序与输入一致 */
LinkList CreateList_Tail(int arr[], int n) {
LinkList L = (LinkList)malloc(sizeof(LNode)); // 创建头结点
L->next = NULL;
LNode *r = L; // r 始终指向表尾
for (int i = 0; i < n; i++) {
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = arr[i];
r->next = s; // 新结点接到表尾
r = s; // r 后移
}
r->next = NULL; // 尾结点 next 置空
return L;
}
/* 链表原地逆置: 头插法逆置, O(n)/O(1) */
void ReverseList(LinkList &L) {
LNode *p = L->next; // p: 工作指针
LNode *r; // r: 保存 p 的后继
L->next = NULL; // 头结点断开，变空表
while (p != NULL) {
r = p->next; // 1. 保存后继
p->next = L->next; // 2. 头插: p 指向当前第一个
L->next = p; // 3. 头结点指向 p
p = r; // 4. 前进到下一个
}
}
/* 打印链表 */
void PrintList(LinkList L) {
LNode *p = L->next;
printf("Head->");
while (p) {
printf("%d->", p->data);
p = p->next;
}
printf("NULL\n");
}
/* ========== 三、真题算法 ========== */
/*
* ★ 2010 真题: 数组循环左移 p 位
* 三次逆置法, 时间 O(n), 空间 O(1)
*/
void Reverse(int a[], int left, int right) {
while (left < right) {
int temp = a[left];
a[left] = a[right];
a[right] = temp;
left++;
right--;
}
}
void LeftShift(int a[], int n, int p) {
p %= n; // 防止 p >= n
Reverse(a, 0, p - 1); // 步骤1: 逆置前 p 个
Reverse(a, p, n - 1); // 步骤2: 逆置后 n-p 个
Reverse(a, 0, n - 1); // 步骤3: 整体逆置
}
/*
* ★ 2011 真题: 两等长有序数组求中位数
* 双指针归并计数, O(n)
*/
int FindMedian(int A[], int B[], int n) {
int ia = 0, ib = 0; // 两个数组的指针
int last = 0; // 记录每次选中的较小值
for (int count = 0; count < n; count++) {
if (ia < n && (ib >= n || A[ia] <= B[ib]))
last = A[ia++]; // A 的当前元素较小(或 B 已用完)
else
last = B[ib++]; // B 的当前元素较小(或 A 已用完)
}
return last; // 第 n 个就是中位数
}
/*
* ★ 2013 真题: 摩尔投票法找主元素
* 第一遍: 候选者计数, 归零换人
* 第二遍: 验证候选者出现次数是否 > n/2
*/
int FindMainElement(int A[], int n) {
int candidate = A[0];
int count = 1;
// 第一遍: 寻找候选者
for (int i = 1; i < n; i++) {
if (A[i] == candidate) {
count++;
} else {
count--;
if (count == 0) {
candidate = A[i];
count = 1;
}
}
}
// 第二遍: 验证
count = 0;
for (int i = 0; i < n; i++)
if (A[i] == candidate) count++;
return (count > n / 2) ? candidate : -1;
}
/* ========== main 演示 ========== */
int main() {
printf("===== 线性表 C++ 可运行版 =====\n\n");
/* --- 顺序表 --- */
SqList L;
InitList(L);
ListInsert(L, 1, 10);
ListInsert(L, 2, 20);
ListInsert(L, 3, 30);
printf("顺序表: ");
PrintSqList(L);
/* --- 单链表 --- */
int d[] = {3, 1, 4, 1, 5};
LinkList LL = CreateList_Tail(d, 5);
printf("链表: ");
PrintList(LL);
ReverseList(LL);
printf("逆置: ");
PrintList(LL);
/* --- 2010: 循环左移 --- */
printf("\n--- 2010 真题 ---\n");
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7};
LeftShift(arr, 8, 3);
printf("循环左移3: ");
for (int i = 0; i < 8; i++) printf("%d ", arr[i]);
printf("\n");
/* --- 2011: 中位数 --- */
printf("\n--- 2011 真题 ---\n");
int A[] = {1, 3, 5, 7, 9};
int B[] = {2, 4, 6, 8, 10};
printf("中位数: %d\n", FindMedian(A, B, 5));
/* --- 2013: 主元素 --- */
printf("\n--- 2013 真题 ---\n");
int C[] = {0, 5, 5, 3, 5, 1, 5, 5};
printf("主元素: %d\n", FindMainElement(C, 8));
return 0;
}02 栈与队列
cpp
/*
* ============================================================
* 408 考研数据结构 —— 栈与队列 (可运行 C++ 版)
* 文件: 02_栈与队列.cpp
* 编译: g++ 02_栈与队列.cpp -o test && ./test
* ============================================================
*
* 覆盖内容:
* 1. 顺序栈: 初始化/进栈/出栈/判空
* 2. 循环队列 (牺牲一个单元法)
* 3. ★ 括号匹配算法
* 4. ★ 后缀表达式求值
* ============================================================
*/
#include <cstdio>
#define MaxSize 50
typedef int ElemType;
/* ========== 一、顺序栈 ========== */
typedef struct {
ElemType data[MaxSize];
int top; // 栈顶指针, 初始 -1
} SqStack;
void InitStack(SqStack &S) {
S.top = -1;
}
bool StackEmpty(SqStack S) {
return S.top == -1;
}
/* 进栈: 先移指针再存数据 */
bool Push(SqStack &S, ElemType x) {
if (S.top == MaxSize - 1)
return false; // 栈满
S.data[++S.top] = x;
return true;
}
/* 出栈: 先取数据再移指针 */
bool Pop(SqStack &S, ElemType &x) {
if (S.top == -1)
return false; // 栈空
x = S.data[S.top--];
return true;
}
/* ========== 二、循环队列 (牺牲一个单元法) ========== */
typedef struct {
ElemType data[MaxSize];
int front, rear;
} SqQueue;
void InitQueue(SqQueue &Q) {
Q.front = Q.rear = 0;
}
bool QueueEmpty(SqQueue Q) {
return Q.front == Q.rear;
}
/* 入队: rear 的下一个是 front 就满了 */
bool EnQueue(SqQueue &Q, ElemType x) {
if ((Q.rear + 1) % MaxSize == Q.front)
return false; // 队满
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize;
return true;
}
/* 出队: 从 front 端取 */
bool DeQueue(SqQueue &Q, ElemType &x) {
if (Q.front == Q.rear)
return false; // 队空
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return true;
}
/* ========== 三、栈的应用 ========== */
/*
* ★ 括号匹配
* 左括号入栈, 右括号检查栈顶是否对称
* 最终栈必须为空
*/
bool BracketMatch(const char *str) {
SqStack S;
InitStack(S);
for (int i = 0; str[i] != '\0'; i++) {
char ch = str[i];
// 遇到左括号: 入栈
if (ch == '(' || ch == '[' || ch == '{') {
Push(S, ch);
}
// 遇到右括号: 检查配对
else if (ch == ')' || ch == ']' || ch == '}') {
if (StackEmpty(S))
return false; // 没有左括号可配
ElemType top;
Pop(S, top);
if (ch == ')' && top != '(') return false;
if (ch == ']' && top != '[') return false;
if (ch == '}' && top != '{') return false;
}
}
return StackEmpty(S); // 栈空则全部匹配
}
/*
* ★ 后缀表达式求值 (操作数为个位数, 简化演示)
* 规则: 数字入栈, 遇运算符弹两个计算后压回
* 注意: 先弹出的是右操作数!
*/
int EvalPostfix(const char *expr) {
SqStack S;
InitStack(S);
ElemType a, b, result;
for (int i = 0; expr[i] != '\0'; i++) {
if (expr[i] >= '0' && expr[i] <= '9') {
Push(S, expr[i] - '0'); // 数字字符转整数入栈
} else if (expr[i] == ' ') {
continue; // 跳过空格
} else {
Pop(S, b); // 先弹出的是右操作数
Pop(S, a); // 再弹出左操作数
switch (expr[i]) {
case '+': result = a + b; break;
case '-': result = a - b; break;
case '*': result = a * b; break;
case '/': result = a / b; break;
default: result = 0;
}
Push(S, result);
}
}
Pop(S, result);
return result;
}
/* ========== main 演示 ========== */
int main() {
printf("===== 栈与队列 C++ 可运行版 =====\n\n");
/* --- 顺序栈基础 --- */
printf("--- 顺序栈 ---\n");
SqStack S;
InitStack(S);
Push(S, 10);
Push(S, 20);
Push(S, 30);
ElemType val;
Pop(S, val);
printf("弹出: %d\n", val); // 30
/* --- 循环队列 --- */
printf("\n--- 循环队列 ---\n");
SqQueue Q;
InitQueue(Q);
EnQueue(Q, 1);
EnQueue(Q, 2);
EnQueue(Q, 3);
DeQueue(Q, val);
printf("出队: %d\n", val); // 1
/* --- 括号匹配 --- */
printf("\n--- 括号匹配 ---\n");
printf("\"(a+b)*[c-d]\" 匹配? %s\n",
BracketMatch("(a+b)*[c-d]") ? "是" : "否");
printf("\"(a+b]*c\" 匹配? %s\n",
BracketMatch("(a+b]*c") ? "是" : "否");
/* --- 后缀表达式 --- */
printf("\n--- 后缀表达式求值 ---\n");
printf("\"34+5*\" = %d (即(3+4)*5)\n", EvalPostfix("34+5*"));
printf("\"512+4*+3-\" = %d (即5+(1+2)*4-3)\n", EvalPostfix("512+4*+3-"));
return 0;
}03 二叉树
cpp
/*
* ============================================================
* 408 考研数据结构 —— 二叉树 (可运行 C++ 版)
* 文件: 03_二叉树.cpp
* 编译: g++ 03_二叉树.cpp -o test && ./test
* ============================================================
*
* 覆盖内容:
* 1. 二叉链表存储与手工建树
* 2. 先序/中序/后序 递归遍历
* 3. ★ 中序非递归遍历 (栈实现)
* 4. ★ 层序遍历 (队列实现, BFS 原型)
* 5. 求深度 / 统计叶子
* 6. ★ 2014 真题: 求 WPL (带权路径长度)
*
* 测试树:
* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
* ============================================================
*/
#include <cstdio>
#include <cstdlib>
typedef int ElemType;
/* ---- 二叉链表定义 ---- */
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
/* 创建新结点 */
BiTNode *NewNode(ElemType val) {
BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));
p->data = val;
p->lchild = p->rchild = NULL;
return p;
}
/* ========== 一、递归遍历 ========== */
void PreOrder(BiTree T) {
if (T != NULL) {
printf("%d ", T->data); // 先访问根
PreOrder(T->lchild); // 再左
PreOrder(T->rchild); // 再右
}
}
void InOrder(BiTree T) {
if (T != NULL) {
InOrder(T->lchild); // 先左
printf("%d ", T->data); // 再根
InOrder(T->rchild); // 再右
}
}
void PostOrder(BiTree T) {
if (T != NULL) {
PostOrder(T->lchild); // 先左
PostOrder(T->rchild); // 再右
printf("%d ", T->data); // 最后根
}
}
/* ========== 二、中序非递归 (栈实现, 考研大题重点) ========== */
/*
* 思路:
* 1. 从当前结点一路向左走到底, 沿途入栈
* 2. 走到空了, 弹栈访问
* 3. 转向右子树, 重复步骤 1
*/
void InOrderNonRecursive(BiTree T) {
BiTNode *stack[50];
int top = -1;
BiTNode *p = T;
while (p != NULL || top != -1) {
if (p != NULL) {
stack[++top] = p; // 入栈
p = p->lchild; // 一路向左
} else {
p = stack[top--]; // 弹栈
printf("%d ", p->data); // 访问
p = p->rchild; // 转向右子树
}
}
}
/* ========== 三、层序遍历 (队列实现) ========== */
void LevelOrder(BiTree T) {
if (T == NULL) return;
BiTNode *queue[50];
int front = 0, rear = 0;
queue[rear++] = T; // 根入队
while (front != rear) {
BiTNode *p = queue[front++]; // 出队
printf("%d ", p->data); // 访问
if (p->lchild != NULL)
queue[rear++] = p->lchild; // 左孩子入队
if (p->rchild != NULL)
queue[rear++] = p->rchild; // 右孩子入队
}
}
/* ========== 四、常用操作 ========== */
/* 求深度: max(左深, 右深) + 1 */
int TreeDepth(BiTree T) {
if (T == NULL) return 0;
int ld = TreeDepth(T->lchild);
int rd = TreeDepth(T->rchild);
return (ld > rd ? ld : rd) + 1;
}
/* 统计叶子: 左右孩子都空就是叶子 */
int CountLeaves(BiTree T) {
if (T == NULL) return 0;
if (T->lchild == NULL && T->rchild == NULL)
return 1;
return CountLeaves(T->lchild) + CountLeaves(T->rchild);
}
/* ========== 五、2014 真题: 求 WPL ========== */
/*
* WPL = 所有叶子的 (权值 × 深度) 之和
* 叶子结点: 返回 weight * depth
* 非叶子: 递归左右求和
*/
int CalcWPL(BiTree T, int depth) {
if (T == NULL) return 0;
if (T->lchild == NULL && T->rchild == NULL)
return T->data * depth; // 叶子: 权值 × 深度
return CalcWPL(T->lchild, depth + 1)
+ CalcWPL(T->rchild, depth + 1);
}
/* ========== main 演示 ========== */
int main() {
printf("===== 二叉树 C++ 可运行版 =====\n\n");
/* 手工建树 */
BiTNode *n1 = NewNode(1), *n2 = NewNode(2), *n3 = NewNode(3);
BiTNode *n4 = NewNode(4), *n5 = NewNode(5);
BiTNode *n6 = NewNode(6), *n7 = NewNode(7);
n1->lchild = n2; n1->rchild = n3;
n2->lchild = n4; n2->rchild = n5;
n3->lchild = n6; n3->rchild = n7;
printf("先序: "); PreOrder(n1); printf("\n");
printf("中序: "); InOrder(n1); printf("\n");
printf("后序: "); PostOrder(n1); printf("\n");
printf("中序非递归: "); InOrderNonRecursive(n1); printf("\n");
printf("层序: "); LevelOrder(n1); printf("\n");
printf("\n深度 = %d\n", TreeDepth(n1));
printf("叶子数 = %d\n", CountLeaves(n1));
printf("WPL = %d\n", CalcWPL(n1, 0));
return 0;
}04 排序算法
cpp
/*
* ============================================================
* 408 考研数据结构 —— 八大排序 (可运行 C++ 版)
* 文件: 04_排序算法.cpp
* 编译: g++ 04_排序算法.cpp -o test && ./test
* ============================================================
*
* 包含全部 8 种考纲排序算法:
* 1. 直接插入排序 5. 快速排序
* 2. 折半插入排序 6. 简单选择排序
* 3. 希尔排序 7. 堆排序 (下标从1)
* 4. 冒泡排序 8. 归并排序
* ============================================================
*/
#include <cstdio>
/* 工具函数 */
void PrintArr(int A[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", A[i]);
printf("\n");
}
void CopyArr(int src[], int dst[], int n) {
for (int i = 0; i < n; i++)
dst[i] = src[i];
}
void swap(int &a, int &b) {
int t = a; a = b; b = t;
}
/* ===========================================
* 1. 直接插入排序
* 稳定, 最好 O(n), 最坏/平均 O(n^2)
* =========================================== */
void InsertSort(int A[], int n) {
for (int i = 1; i < n; i++) {
int temp = A[i];
int j;
for (j = i - 1; j >= 0 && temp < A[j]; j--)
A[j + 1] = A[j]; // 比 temp 大的后移
A[j + 1] = temp; // 插入到正确位置
}
}
/* ===========================================
* 2. 折半插入排序
* 稳定, 比较次数减少但移动不变, O(n^2)
* =========================================== */
void BinaryInsertSort(int A[], int n) {
for (int i = 1; i < n; i++) {
int temp = A[i];
int low = 0, high = i - 1;
// 折半查找插入位置
while (low <= high) {
int mid = (low + high) / 2;
if (A[mid] > temp)
high = mid - 1;
else
low = mid + 1;
}
// high+1 就是插入位置, 后移 [high+1, i-1]
for (int j = i - 1; j >= high + 1; j--)
A[j + 1] = A[j];
A[high + 1] = temp;
}
}
/* ===========================================
* 3. 希尔排序
* 不稳定, 约 O(n^1.3)
* =========================================== */
void ShellSort(int A[], int n) {
for (int dk = n / 2; dk >= 1; dk /= 2) { // 增量递减
for (int i = dk; i < n; i++) { // 对每组做插排
if (A[i] < A[i - dk]) {
int temp = A[i];
int j;
for (j = i - dk; j >= 0 && temp < A[j]; j -= dk)
A[j + dk] = A[j];
A[j + dk] = temp;
}
}
}
}
/* ===========================================
* 4. 冒泡排序
* 稳定, 最好 O(n), 最坏 O(n^2)
* =========================================== */
void BubbleSort(int A[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = n - 1; j > i; j--) {
if (A[j - 1] > A[j]) {
swap(A[j - 1], A[j]);
swapped = true;
}
}
if (!swapped) return; // 本趟无交换, 已有序
}
}
/* ===========================================
* 5. 快速排序
* 不稳定, 平均 O(nlogn), 最坏 O(n^2)
* =========================================== */
int Partition(int A[], int low, int high) {
int pivot = A[low]; // 取第一个作为枢轴
while (low < high) {
while (low < high && A[high] >= pivot)
high--; // 从右找小的
A[low] = A[high];
while (low < high && A[low] <= pivot)
low++; // 从左找大的
A[high] = A[low];
}
A[low] = pivot; // 枢轴就位
return low;
}
void QuickSort(int A[], int low, int high) {
if (low < high) {
int pos = Partition(A, low, high);
QuickSort(A, low, pos - 1); // 左半递归
QuickSort(A, pos + 1, high); // 右半递归
}
}
/* ===========================================
* 6. 简单选择排序
* 不稳定, 时间始终 O(n^2)
* =========================================== */
void SelectSort(int A[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++)
if (A[j] < A[min]) min = j;
if (min != i)
swap(A[i], A[min]);
}
}
/* ===========================================
* 7. 堆排序 (大顶堆, 下标从 1, A[0] 作暂存)
* 不稳定, O(nlogn), 空间 O(1)
* =========================================== */
void AdjustDown(int A[], int k, int len) {
A[0] = A[k]; // 暂存要调整的结点
for (int i = 2 * k; i <= len; i *= 2) {
if (i < len && A[i] < A[i + 1])
i++; // 找较大的孩子
if (A[0] >= A[i])
break; // 到位
A[k] = A[i]; // 大孩子上浮
k = i;
}
A[k] = A[0]; // 放到最终位置
}
void HeapSort(int A[], int len) {
// 建初始大顶堆
for (int i = len / 2; i > 0; i--)
AdjustDown(A, i, len);
// 排序: 不断交换堆顶与末尾, 再调整
for (int i = len; i > 1; i--) {
swap(A[1], A[i]); // 堆顶与末尾交换
AdjustDown(A, 1, i - 1); // 调整剩余
}
}
/* ===========================================
* 8. 归并排序
* 稳定, O(nlogn), 空间 O(n)
* =========================================== */
int B_merge[50]; // 辅助数组
void Merge(int A[], int low, int mid, int high) {
// 复制到辅助数组
for (int k = low; k <= high; k++)
B_merge[k] = A[k];
// 归并: 两路合一
int i = low, j = mid + 1, k = low;
while (i <= mid && j <= high) {
if (B_merge[i] <= B_merge[j])
A[k++] = B_merge[i++];
else
A[k++] = B_merge[j++];
}
while (i <= mid) A[k++] = B_merge[i++];
while (j <= high) A[k++] = B_merge[j++];
}
void MergeSort(int A[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
MergeSort(A, low, mid); // 排左半
MergeSort(A, mid + 1, high); // 排右半
Merge(A, low, mid, high); // 合并
}
}
/* ========== main: 全部排序对比 ========== */
int main() {
printf("===== 八大排序 C++ 可运行版 =====\n");
int original[] = {49, 38, 65, 97, 76, 13, 27, 49};
int n = 8, A[8];
printf("原始数组: ");
PrintArr(original, n);
printf("\n");
CopyArr(original, A, n); InsertSort(A, n);
printf("直接插入: "); PrintArr(A, n);
CopyArr(original, A, n); BinaryInsertSort(A, n);
printf("折半插入: "); PrintArr(A, n);
CopyArr(original, A, n); ShellSort(A, n);
printf("希尔排序: "); PrintArr(A, n);
CopyArr(original, A, n); BubbleSort(A, n);
printf("冒泡排序: "); PrintArr(A, n);
CopyArr(original, A, n); QuickSort(A, 0, n - 1);
printf("快速排序: "); PrintArr(A, n);
CopyArr(original, A, n); SelectSort(A, n);
printf("选择排序: "); PrintArr(A, n);
CopyArr(original, A, n); MergeSort(A, 0, n - 1);
printf("归并排序: "); PrintArr(A, n);
/* 堆排序: A[0] 暂存, 数据从 A[1] 开始 */
printf("\n--- 堆排序 (下标从1) ---\n");
int H[] = {0, 49, 38, 65, 97, 76, 13, 27, 49};
printf("排序前: ");
for (int i = 1; i <= 8; i++) printf("%d ", H[i]);
printf("\n");
HeapSort(H, 8);
printf("排序后: ");
for (int i = 1; i <= 8; i++) printf("%d ", H[i]);
printf("\n");
return 0;
}05 串匹配与查找
cpp
/*
* ============================================================
* 408 考研数据结构 —— KMP 与查找 (可运行 C++ 版)
* 文件: 05_串匹配与查找.cpp
* 编译: g++ 05_串匹配与查找.cpp -o test && ./test
* ============================================================
*
* 覆盖内容:
* 1. ★ KMP: get_next 求 next 数组 (1-based, 教材风格)
* 2. ★ KMP: get_nextval 求 nextval 数组
* 3. ★ KMP: Index_KMP 主匹配函数
* 4. 折半查找 (非递归)
* ============================================================
*/
#include <cstdio>
#include <cstring>
/* ========== KMP 算法 (1-based, 教材风格) ========== */
/*
* get_next: 求模式串 T 的 next 数组
*
* next[j] 含义: 当 T[j] 与主串失配时, j 应回退到 next[j]
* 手算提示: next[1]=0, next[2]=1, 从第3位开始找最长公共前后缀+1
*/
void get_next(char T[], int Tlen, int next[]) {
int i = 1, j = 0;
next[1] = 0;
while (i < Tlen) {
if (j == 0 || T[i] == T[j]) {
++i;
++j;
next[i] = j;
} else {
j = next[j]; // 回退
}
}
}
/*
* get_nextval: next 的优化版
*
* 当 T[i] == T[next[i]] 时, 回退后仍会失配
* 所以直接继承 nextval[next[i]]
*/
void get_nextval(char T[], int Tlen, int nextval[]) {
int i = 1, j = 0;
nextval[1] = 0;
while (i < Tlen) {
if (j == 0 || T[i] == T[j]) {
++i;
++j;
if (T[i] != T[j])
nextval[i] = j; // 不等, 正常赋值
else
nextval[i] = nextval[j]; // 相等, 继承优化
} else {
j = nextval[j];
}
}
}
/*
* KMP 主匹配: 在 S 中查找 T 第一次出现的位置 (1-based)
* 主串不回溯, 模式串利用 next 跳转
*/
int Index_KMP(char S[], int Slen, char T[], int Tlen, int next[]) {
int i = 1, j = 1;
while (i <= Slen && j <= Tlen) {
if (j == 0 || S[i] == T[j]) {
++i;
++j;
} else {
j = next[j]; // 模式串回退
}
}
if (j > Tlen)
return i - Tlen; // 匹配成功, 返回起始位置
else
return 0; // 未找到
}
/* ========== 折半查找 ========== */
/*
* 有序数组中查找 key, 找到返回下标, 找不到返回 -1
* 时间 O(logn)
*/
int BinarySearch(int A[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (A[mid] == key)
return mid;
else if (A[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1; // 未找到
}
/* ========== main 演示 ========== */
int main() {
printf("===== KMP 与查找 C++ 可运行版 =====\n\n");
/* --- KMP 演示 ---
* 教材风格: 下标从 1 开始, ch[0] 用 '#' 占位
*/
char S[] = "#aababaabaabcac"; // 主串, 14 个有效字符
char T[] = "#abaabcac"; // 模式串, 8 个有效字符
int Slen = 14, Tlen = 8;
int next[20], nextval[20];
get_next(T, Tlen, next);
get_nextval(T, Tlen, nextval);
printf("模式串 T = \"abaabcac\"\n");
printf("位序: ");
for (int i = 1; i <= Tlen; i++) printf("%d ", i);
printf("\n字符: ");
for (int i = 1; i <= Tlen; i++) printf("%c ", T[i]);
printf("\nnext: ");
for (int i = 1; i <= Tlen; i++) printf("%d ", next[i]);
printf("\nnextval: ");
for (int i = 1; i <= Tlen; i++) printf("%d ", nextval[i]);
printf("\n\n");
int pos = Index_KMP(S, Slen, T, Tlen, next);
printf("主串 S = \"aababaabaabcac\"\n");
printf("匹配位置 = %d\n\n", pos);
/* --- 折半查找 --- */
printf("--- 折半查找 ---\n");
int arr[] = {7, 10, 13, 16, 19, 29, 32, 33, 37, 41, 43};
int n = 11;
printf("有序数组: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
printf("查找 33 -> 下标 %d\n", BinarySearch(arr, n, 33));
printf("查找 20 -> %s\n",
BinarySearch(arr, n, 20) == -1 ? "未找到" : "找到");
return 0;
}06 图算法
cpp
/*
* ============================================================
* 408 考研数据结构 —— 图算法 (可运行 C++ 版)
* 文件: 06_图算法.cpp
* 编译: g++ 06_图算法.cpp -o test && ./test
* ============================================================
*
* 覆盖内容:
* 1. 邻接矩阵存储图
* 2. ★ DFS 深度优先遍历 (递归)
* 3. ★ BFS 广度优先遍历 (队列)
* 4. ★ Dijkstra 最短路径
* 5. ★ 拓扑排序
* ============================================================
*/
#include <cstdio>
#include <cstdlib>
#define MaxV 20
#define INF 999999
/* ========== 邻接矩阵存储 ========== */
typedef struct {
int vex[MaxV];
int Edge[MaxV][MaxV];
int vexnum, arcnum;
} MGraph;
bool visited[MaxV]; // 访问标记数组
/* 初始化图 */
void InitGraph(MGraph &G, int n) {
G.vexnum = n;
G.arcnum = 0;
for (int i = 0; i < n; i++) {
G.vex[i] = i;
for (int j = 0; j < n; j++)
G.Edge[i][j] = (i == j) ? 0 : INF;
}
}
/* 添加无向边 */
void AddEdge(MGraph &G, int u, int v, int w) {
G.Edge[u][v] = w;
G.Edge[v][u] = w;
G.arcnum++;
}
/* ========== DFS 深度优先遍历 ========== */
/*
* 递归: 访问 v, 标记, 遍历邻居递归
*/
void DFS(MGraph &G, int v) {
printf("%d ", v);
visited[v] = true;
for (int w = 0; w < G.vexnum; w++) {
if (G.Edge[v][w] != 0 && G.Edge[v][w] != INF && !visited[w])
DFS(G, w);
}
}
void DFSTraverse(MGraph &G) {
for (int i = 0; i < G.vexnum; i++)
visited[i] = false;
for (int i = 0; i < G.vexnum; i++)
if (!visited[i]) DFS(G, i);
}
/* ========== BFS 广度优先遍历 ========== */
/*
* 队列: 源点入队标记, 出队遍历邻居, 未访问的入队
*/
void BFS(MGraph &G, int v) {
int queue[MaxV];
int front = 0, rear = 0;
printf("%d ", v);
visited[v] = true;
queue[rear++] = v;
while (front != rear) {
int u = queue[front++]; // 出队
for (int w = 0; w < G.vexnum; w++) {
if (G.Edge[u][w] != 0 && G.Edge[u][w] != INF && !visited[w]) {
printf("%d ", w);
visited[w] = true;
queue[rear++] = w;
}
}
}
}
void BFSTraverse(MGraph &G) {
for (int i = 0; i < G.vexnum; i++)
visited[i] = false;
for (int i = 0; i < G.vexnum; i++)
if (!visited[i]) BFS(G, i);
}
/* ========== Dijkstra 最短路径 ========== */
/*
* 从源点 src 到其余各点的最短距离
* dist[i]: 源到 i 的当前最短距离
* path[i]: i 的前驱 (用于输出路径)
* fin[i]: i 是否已确定最短路
*/
void Dijkstra(MGraph &G, int src) {
int dist[MaxV], path[MaxV];
bool fin[MaxV];
// 初始化
for (int i = 0; i < G.vexnum; i++) {
dist[i] = G.Edge[src][i];
fin[i] = false;
path[i] = (dist[i] < INF) ? src : -1;
}
dist[src] = 0;
fin[src] = true;
// 循环 n-1 次
for (int i = 0; i < G.vexnum - 1; i++) {
// 找未确定的最近顶点
int minDist = INF, u = -1;
for (int j = 0; j < G.vexnum; j++) {
if (!fin[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
if (u == -1) break; // 不连通
fin[u] = true;
// 松弛操作: 用 u 更新其邻居
for (int j = 0; j < G.vexnum; j++) {
if (!fin[j] && G.Edge[u][j] < INF
&& dist[u] + G.Edge[u][j] < dist[j]) {
dist[j] = dist[u] + G.Edge[u][j];
path[j] = u;
}
}
}
// 输出结果
printf("Dijkstra (源点 %d):\n", src);
for (int i = 0; i < G.vexnum; i++) {
if (dist[i] >= INF)
printf(" 到 %d: 不可达\n", i);
else
printf(" 到 %d: 距离 = %d, 前驱 = %d\n", i, dist[i], path[i]);
}
}
/* ========== 拓扑排序 ========== */
/*
* 1. 统计入度
* 2. 入度为 0 的入栈
* 3. 弹出→输出→邻居入度-1→新入度0则入栈
* 4. 若输出数 < 顶点数, 有环
*/
int TopologicalSort(MGraph &G) {
int indegree[MaxV] = {0};
int stack[MaxV], top = -1;
int count = 0;
// 统计入度
for (int j = 0; j < G.vexnum; j++)
for (int i = 0; i < G.vexnum; i++)
if (G.Edge[i][j] != 0 && G.Edge[i][j] != INF)
indegree[j]++;
// 入度为 0 的入栈
for (int i = 0; i < G.vexnum; i++)
if (indegree[i] == 0)
stack[++top] = i;
printf("拓扑序列: ");
while (top != -1) {
int v = stack[top--]; // 出栈
printf("%d ", v);
count++;
for (int j = 0; j < G.vexnum; j++) {
if (G.Edge[v][j] != 0 && G.Edge[v][j] != INF) {
indegree[j]--;
if (indegree[j] == 0)
stack[++top] = j;
}
}
}
printf("\n");
if (count < G.vexnum) {
printf("存在环, 拓扑排序失败!\n");
return 0;
}
return 1;
}
/* ========== main 演示 ========== */
int main() {
printf("===== 图算法 C++ 可运行版 =====\n\n");
/* 无向图:
* 0---1---3
* | |
* 2---4
*/
MGraph G;
InitGraph(G, 5);
AddEdge(G, 0, 1, 1);
AddEdge(G, 0, 2, 1);
AddEdge(G, 1, 3, 1);
AddEdge(G, 1, 4, 1);
AddEdge(G, 2, 4, 1);
printf("DFS: ");
DFSTraverse(G);
printf("\n");
printf("BFS: ");
BFSTraverse(G);
printf("\n\n");
/* 带权有向图:
* 0--(1)-->1--(3)-->3
* | |
* (6) (2)
* v v
* 2--(1)-->4
*/
MGraph G2;
InitGraph(G2, 5);
G2.Edge[0][1] = 1;
G2.Edge[0][2] = 6;
G2.Edge[1][3] = 3;
G2.Edge[1][4] = 2;
G2.Edge[2][4] = 1;
Dijkstra(G2, 0);
printf("\n");
printf("--- 拓扑排序 ---\n");
TopologicalSort(G2);
return 0;
}