可运行版本 · C
每个文件均可独立编译运行（gcc 文件名.c -o out && ./out），带 main 测试用例，并实现了多道统考真题。建议亲手跑一遍验证边界条件。
文件一览
| 序号 | 内容 | 文件 |
|---|---|---|
| 01 | 线性表 · 顺序表 | 01_线性表_顺序表.c |
| 02 | 线性表 · 单链表 | 02_线性表_单链表.c |
| 03 | 栈与队列 | 03_栈与队列.c |
| 04 | 二叉树 | 04_二叉树.c |
| 05 | 排序算法 | 05_排序算法.c |
| 06 | 串匹配与查找 | 06_串匹配与查找.c |
| 07 | 图算法 | 07_图算法.c |
01 线性表 · 顺序表
c
/*
* ============================================================
* 408 考研数据结构 —— 顺序表 (可编译运行版)
* 文件: 01_线性表_顺序表.c
* 编译: gcc 01_线性表_顺序表.c -o sqlist && sqlist
* ============================================================
*
* 本文件包含:
* 1. 顺序表的定义与初始化
* 2. 插入、删除操作 (考研必背)
* 3. 按值/按序号查找
* 4. ★ 真题经典: 数组循环左移 p 位 (2010 年真题)
* 5. ★ 真题经典: 两个有序数组求中位数 (2011 年真题)
* 6. ★ 真题经典: 寻找主元素 (2013 年真题)
*
* 注意: 教材中数组下标一般从 0 开始, 逻辑位序从 1 开始。
* ============================================================
*/
#include <stdio.h>
#include <stdlib.h>
#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
* - 要把第 i 个及之后的元素全部后移一位
* - 时间复杂度: 最好 O(1), 最坏 O(n), 平均 O(n)
*/
int ListInsert(SqList *L, int i, ElemType e) {
if (i < 1 || i > L->length + 1) return 0;
if (L->length >= MaxSize) return 0;
int j;
for (j = L->length; j >= i; j--) /* 从最后一个元素开始后移 */
L->data[j] = L->data[j - 1];
L->data[i - 1] = e; /* 位序 i 对应下标 i-1 */
L->length++;
return 1;
}
/* 删除: 删除第 i 个位置(1-based)的元素, 用 e 带回
* - 要把第 i+1 个及之后的元素全部前移一位
*/
int ListDelete(SqList *L, int i, ElemType *e) {
if (i < 1 || i > L->length) return 0;
*e = L->data[i - 1];
int j;
for (j = i; j < L->length; j++)
L->data[j - 1] = L->data[j];
L->length--;
return 1;
}
/* 按值查找: 返回第一个等于 e 的元素的位序(1-based), 找不到返回 0 */
int LocateElem(SqList L, ElemType e) {
int i;
for (i = 0; i < L.length; i++)
if (L.data[i] == e) return i + 1;
return 0;
}
/* 打印顺序表 */
void PrintList(SqList L) {
int i;
printf("[ ");
for (i = 0; i < L.length; i++)
printf("%d ", L.data[i]);
printf("] (length=%d)\n", L.length);
}
/* ========== 408 真题经典算法 ========== */
/*
* ★ 2010 年真题: 将数组 a[0..n-1] 循环左移 p 位
* 思路: 三次逆置
* 1. 逆置 a[0..p-1]
* 2. 逆置 a[p..n-1]
* 3. 逆置 a[0..n-1]
* 时间 O(n), 空间 O(1)
*/
void Reverse(int a[], int left, int right) {
int temp;
while (left < right) {
temp = a[left];
a[left] = a[right];
a[right] = temp;
left++;
right--;
}
}
void LeftShift(int a[], int n, int p) {
p = p % n; /* 防止 p >= n 的情况 */
if (p == 0) return;
Reverse(a, 0, p - 1); /* 步骤1: 逆置前 p 个 */
Reverse(a, p, n - 1); /* 步骤2: 逆置后 n-p 个 */
Reverse(a, 0, n - 1); /* 步骤3: 整体逆置 */
}
/*
* ★ 2011 年真题: 两个等长有序序列 A,B 各含 n 个元素, 求合并后的中位数
* O(n) 解法: 双指针归并计数
* 两个指针分别指向 A 和 B 的起始位置,
* 每次移动较小者的指针, 当总共移动了 n-1 次时,
* 下一个较小者就是中位数。
*/
int FindMedian(int A[], int B[], int n) {
int ia = 0, ib = 0;
int count;
int last = 0; /* 记录上一个被选中的值 */
for (count = 0; count < n; count++) {
if (ia < n && (ib >= n || A[ia] <= B[ib])) {
last = A[ia];
ia++;
} else {
last = B[ib];
ib++;
}
}
return last; /* 第 n 个就是中位数 */
}
/*
* ★ 2013 年真题: 找主元素
* 若数组 A[0..n-1] 中有某个元素出现次数 > n/2, 则称其为主元素
* 返回主元素值, 若不存在返回 -1
*
* 经典 O(n) 做法: 摩尔投票法 (Boyer-Moore Voting)
* - 第一遍扫描: 用一个候选者 candidate 和计数器 count
* 遇到相同的 count++, 不同的 count--
* count 归零时换人。最后剩下的就是候选者。
* - 第二遍扫描: 验证候选者出现次数是否真的 > n/2
*/
int FindMainElement(int A[], int n) {
int candidate = A[0];
int count = 1;
int i;
/* 第一遍: 找候选者 */
for (i = 1; i < n; i++) {
if (A[i] == candidate)
count++;
else {
count--;
if (count == 0) {
candidate = A[i];
count = 1;
}
}
}
/* 第二遍: 验证 */
count = 0;
for (i = 0; i < n; i++)
if (A[i] == candidate) count++;
if (count > n / 2)
return candidate;
else
return -1;
}
/* ========== main: 全部演示 ========== */
int main() {
printf("===== 408 顺序表 可运行演示 =====\n\n");
/* --- 基础操作演示 --- */
SqList L;
InitList(&L);
ListInsert(&L, 1, 10);
ListInsert(&L, 2, 20);
ListInsert(&L, 3, 30);
ListInsert(&L, 2, 15); /* 在第2位插入15 */
printf("插入后: ");
PrintList(L); /* 预期: [10 15 20 30] */
ElemType del;
ListDelete(&L, 3, &del);
printf("删除第3位(值=%d)后: ", del);
PrintList(L); /* 预期: [10 15 30] */
int pos = LocateElem(L, 15);
printf("元素 15 在位序 %d\n\n", pos);
/* --- 2010: 循环左移 --- */
printf("--- 2010 真题: 循环左移 ---\n");
int arr1[] = {0, 1, 2, 3, 4, 5, 6, 7};
int n1 = 8, p = 3;
printf("原数组: ");
int i;
for (i = 0; i < n1; i++) printf("%d ", arr1[i]);
LeftShift(arr1, n1, p);
printf("\n左移 %d 位: ", p);
for (i = 0; i < n1; i++) printf("%d ", arr1[i]);
printf("\n\n");
/* --- 2011: 两有序数组求中位数 --- */
printf("--- 2011 真题: 两有序数组求中位数 ---\n");
int A[] = {1, 3, 5, 7, 9};
int B[] = {2, 4, 6, 8, 10};
int median = FindMedian(A, B, 5);
printf("A = {1,3,5,7,9}, B = {2,4,6,8,10}\n");
printf("中位数 = %d\n\n", median); /* 预期: 5 */
/* --- 2013: 主元素 --- */
printf("--- 2013 真题: 主元素 ---\n");
int C[] = {0, 5, 5, 3, 5, 1, 5, 5};
int mainElem = FindMainElement(C, 8);
printf("数组 = {0,5,5,3,5,1,5,5}\n");
printf("主元素 = %d\n\n", mainElem); /* 预期: 5 */
int D[] = {0, 5, 5, 3, 5, 1, 2, 7};
mainElem = FindMainElement(D, 8);
printf("数组 = {0,5,5,3,5,1,2,7}\n");
printf("主元素 = %d (不存在则 -1)\n", mainElem);
return 0;
}02 线性表 · 单链表
c
/*
* ============================================================
* 408 考研数据结构 —— 单链表 (可编译运行版)
* 文件: 02_线性表_单链表.c
* 编译: gcc 02_线性表_单链表.c -o linklist && linklist
* ============================================================
*
* 本文件包含:
* 1. 单链表的定义 (带头结点)
* 2. 头插法 / 尾插法建表 (两种最基本的创建方式)
* 3. 按序号 / 按值查找
* 4. 插入 / 删除结点
* 5. ★ 高频考点: 链表原地逆置 (头插法逆置)
* 6. ★ 高频考点: 快慢指针找中间结点
* 7. ★ 课后题: 删除链表中所有值为 x 的结点
* 8. ★ 课后题: 链表排序 (直接插入排序思路)
*
* 教材惯例: 单链表带头结点, 头结点不存数据,
* L->next 指向第一个真实的数据结点。
* ============================================================
*/
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
/* ---- 单链表结构体定义 ---- */
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
/* LinkList 等价于 LNode *, 用 LinkList 强调"这是整个链表" */
/* 用 LNode * 强调"这是某个结点的指针" */
/* ========== 基础操作 ========== */
/* 初始化: 创建一个空的带头结点链表 */
LinkList InitList() {
LinkList L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
return L;
}
/* 头插法建表: 每次把新结点插到头结点后面
* 结果: 数据顺序与输入顺序相反
* (考点: 常用于 "链表逆置" 的核心技巧)
*/
LinkList CreateList_Head(int arr[], int n) {
LinkList L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
int i;
for (i = 0; i < n; i++) {
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = arr[i];
s->next = L->next; /* 新结点指向原来的第一个 */
L->next = s; /* 头结点指向新结点 */
}
return L;
}
/* 尾插法建表: 每次把新结点接到表尾
* 结果: 数据顺序与输入顺序相同
* (需要一个尾指针 r 跟踪表尾)
*/
LinkList CreateList_Tail(int arr[], int n) {
LinkList L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
LNode *r = L; /* r 始终指向当前的尾结点 */
int i;
for (i = 0; i < n; i++) {
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = arr[i];
r->next = s;
r = s;
}
r->next = NULL; /* 千万别忘: 最后尾结点的 next 置空! */
return L;
}
/* 按序号查找: 返回第 i 个结点的指针 (1-based) */
LNode *GetElem(LinkList L, int i) {
if (i < 0) return NULL;
if (i == 0) return L; /* 第 0 个是头结点 */
LNode *p = L->next;
int j = 1;
while (p != NULL && j < i) {
p = p->next;
j++;
}
return p; /* 如果 i 超出长度, p 会是 NULL */
}
/* 按值查找: 返回第一个值为 e 的结点指针 */
LNode *LocateElem(LinkList L, ElemType e) {
LNode *p = L->next;
while (p != NULL && p->data != e)
p = p->next;
return p; /* 找不到返回 NULL */
}
/* 在第 i 个位置插入值为 e 的新结点 */
int ListInsert(LinkList L, int i, ElemType e) {
LNode *p = GetElem(L, i - 1); /* 找前驱 */
if (p == NULL) return 0;
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next; /* 新结点指向原第 i 个 */
p->next = s; /* 前驱指向新结点 */
return 1;
}
/* 删除第 i 个结点, 被删除的值通过 e 带回 */
int ListDelete(LinkList L, int i, ElemType *e) {
LNode *p = GetElem(L, i - 1); /* 找前驱 */
if (p == NULL || p->next == NULL) return 0;
LNode *q = p->next; /* q 指向要删除的结点 */
*e = q->data;
p->next = q->next; /* 前驱跳过被删结点 */
free(q); /* 释放空间 */
return 1;
}
/* 求表长 */
int ListLength(LinkList L) {
int len = 0;
LNode *p = L->next;
while (p != NULL) {
len++;
p = p->next;
}
return len;
}
/* 打印链表 */
void PrintList(LinkList L) {
LNode *p = L->next;
printf("Head -> ");
while (p != NULL) {
printf("%d -> ", p->data);
p = p->next;
}
printf("NULL\n");
}
/* ========== 高频考点算法 ========== */
/*
* ★ 链表原地逆置 (不申请新结点)
* 方法: 将原链表的结点逐一摘下, 用头插法重新挂到头结点后面
* 时间 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. p 前进到下一个待处理结点 */
}
}
/*
* ★ 快慢指针找中间结点
* 快指针每次走 2 步, 慢指针每次走 1 步
* 当快指针走到底时, 慢指针恰好在中间
*/
LNode *FindMiddle(LinkList L) {
LNode *slow = L->next;
LNode *fast = L->next;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
/*
* ★ 删除链表中所有值为 x 的结点
* 技巧: 用前驱指针判断后继的值
*/
void DeleteAllX(LinkList L, ElemType x) {
LNode *p = L; /* p 是当前结点的前驱 */
LNode *q;
while (p->next != NULL) {
if (p->next->data == x) {
q = p->next;
p->next = q->next;
free(q);
/* 注意: 这里不移动 p, 因为删除后 p->next 变了 */
} else {
p = p->next;
}
}
}
/*
* ★ 链表排序 (直接插入排序)
* 思路: 摘下原链头, 逐个插入到一个新的有序链表中
*/
void SortList(LinkList L) {
if (L->next == NULL || L->next->next == NULL) return;
LNode *p = L->next->next; /* 从第二个结点开始 */
L->next->next = NULL; /* 有序链表初始只有第一个结点 */
while (p != NULL) {
LNode *r = p->next; /* 保存后继 */
/* 在有序部分中找插入位置: 找到第一个 > p->data 的前驱 */
LNode *q = L;
while (q->next != NULL && q->next->data < p->data)
q = q->next;
/* 插入 */
p->next = q->next;
q->next = p;
p = r; /* 处理下一个 */
}
}
/* ========== main: 全部演示 ========== */
int main() {
printf("===== 408 单链表 可运行演示 =====\n\n");
/* 尾插法建表 */
int data[] = {3, 1, 4, 1, 5, 9, 2, 6};
LinkList L = CreateList_Tail(data, 8);
printf("尾插法建表: ");
PrintList(L);
/* 头插法建表 (验证顺序反转) */
int data2[] = {1, 2, 3};
LinkList L2 = CreateList_Head(data2, 3);
printf("头插法建表 {1,2,3}: ");
PrintList(L2); /* 预期: 3 -> 2 -> 1 */
/* 插入与删除 */
ListInsert(L, 1, 99);
printf("\n在第1位插入99: ");
PrintList(L);
ElemType del;
ListDelete(L, 1, &del);
printf("删除第1位(%d): ", del);
PrintList(L);
/* 链表逆置 */
printf("\n--- 链表逆置 ---\n");
printf("逆置前: ");
PrintList(L);
ReverseList(L);
printf("逆置后: ");
PrintList(L);
/* 快慢指针找中间 */
printf("\n--- 快慢指针找中间 ---\n");
LNode *mid = FindMiddle(L);
if (mid) printf("中间结点值 = %d\n", mid->data);
/* 删除所有值为 1 的结点 */
printf("\n--- 删除所有值为 1 的结点 ---\n");
printf("删除前: ");
PrintList(L);
DeleteAllX(L, 1);
printf("删除后: ");
PrintList(L);
/* 链表排序 */
printf("\n--- 链表排序 ---\n");
int data3[] = {5, 3, 8, 1, 2, 7};
LinkList L3 = CreateList_Tail(data3, 6);
printf("排序前: ");
PrintList(L3);
SortList(L3);
printf("排序后: ");
PrintList(L3);
return 0;
}03 栈与队列
c
/*
* ============================================================
* 408 考研数据结构 —— 栈与队列 (可编译运行版)
* 文件: 03_栈与队列.c
* 编译: gcc 03_栈与队列.c -o stack_queue && stack_queue
* ============================================================
*
* 本文件包含:
* 1. 顺序栈: 初始化 / 进栈 / 出栈 / 判空
* 2. 循环队列 (牺牲一个单元法): 初始化 / 入队 / 出队 / 判空
* 3. ★ 栈的经典应用: 括号匹配
* 4. ★ 栈的经典应用: 十进制转二进制
* 5. ★ 栈的经典应用: 后缀表达式求值
*
* 考研重点:
* - 顺序栈 top 初始为 -1, 先加后存
* - 循环队列的 3 种判空判满方案 (本文件展示最常考的牺牲一个单元法)
* ============================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxSize 50
typedef int ElemType;
/* ========== 顺序栈 ========== */
typedef struct {
ElemType data[MaxSize];
int top; /* 栈顶指针, 初始化为 -1 */
} SqStack;
void InitStack(SqStack *S) { S->top = -1; }
int StackEmpty(SqStack *S) { return S->top == -1; }
int Push(SqStack *S, ElemType x) {
if (S->top == MaxSize - 1) return 0; /* 栈满 */
S->data[++S->top] = x; /* 先加指针, 再存数据 */
return 1;
}
int Pop(SqStack *S, ElemType *x) {
if (S->top == -1) return 0; /* 栈空 */
*x = S->data[S->top--]; /* 先取数据, 再减指针 */
return 1;
}
int GetTop(SqStack *S, ElemType *x) {
if (S->top == -1) return 0;
*x = S->data[S->top]; /* 只看不取 */
return 1;
}
/* ========== 循环队列 (牺牲一个单元法) ========== */
typedef struct {
ElemType data[MaxSize];
int front, rear;
} SqQueue;
void InitQueue(SqQueue *Q) { Q->front = Q->rear = 0; }
int QueueEmpty(SqQueue *Q) { return Q->front == Q->rear; }
/* 判满: rear 的下一个位置是 front 就满了 */
int EnQueue(SqQueue *Q, ElemType x) {
if ((Q->rear + 1) % MaxSize == Q->front) return 0;
Q->data[Q->rear] = x;
Q->rear = (Q->rear + 1) % MaxSize;
return 1;
}
int DeQueue(SqQueue *Q, ElemType *x) {
if (Q->front == Q->rear) return 0;
*x = Q->data[Q->front];
Q->front = (Q->front + 1) % MaxSize;
return 1;
}
/* ========== 栈的经典应用 ========== */
/*
* ★ 括号匹配算法
* 遇到左括号入栈, 遇到右括号检查栈顶是否匹配
* 最终栈必须为空才算匹配成功
*/
int BracketMatch(const char *str) {
SqStack S;
InitStack(&S);
int i;
char ch;
for (i = 0; str[i] != '\0'; i++) {
if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
Push(&S, str[i]); /* 左括号入栈 */
} else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
if (StackEmpty(&S)) return 0; /* 没有左括号可配 */
Pop(&S, (ElemType *)&ch);
/* 检查对称性 */
if (str[i] == ')' && ch != '(') return 0;
if (str[i] == ']' && ch != '[') return 0;
if (str[i] == '}' && ch != '{') return 0;
}
}
return StackEmpty(&S); /* 最终栈为空才行 */
}
/*
* ★ 十进制转二进制
* 反复除以 2 取余入栈, 然后弹栈得到结果
*/
void DecToBin(int n) {
SqStack S;
InitStack(&S);
ElemType rem;
if (n == 0) { printf("0"); return; }
while (n > 0) {
Push(&S, n % 2);
n = n / 2;
}
while (!StackEmpty(&S)) {
Pop(&S, &rem);
printf("%d", rem);
}
}
/*
* ★ 后缀表达式求值 (操作数为个位数, 简化演示)
* 规则: 遇到数字入栈, 遇到运算符弹出两个操作数计算后压回
*/
int EvalPostfix(const char *expr) {
SqStack S;
InitStack(&S);
int i;
ElemType a, b, result;
for (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("===== 408 栈与队列 可运行演示 =====\n\n");
/* --- 顺序栈基础 --- */
printf("--- 顺序栈 ---\n");
SqStack S;
InitStack(&S);
Push(&S, 10);
Push(&S, 20);
Push(&S, 30);
ElemType val;
GetTop(&S, &val);
printf("栈顶: %d\n", val);
Pop(&S, &val);
printf("弹出: %d, 新栈顶: ", val);
GetTop(&S, &val);
printf("%d\n\n", val);
/* --- 循环队列基础 --- */
printf("--- 循环队列 ---\n");
SqQueue Q;
InitQueue(&Q);
EnQueue(&Q, 1);
EnQueue(&Q, 2);
EnQueue(&Q, 3);
DeQueue(&Q, &val);
printf("出队: %d\n", val);
DeQueue(&Q, &val);
printf("出队: %d\n\n", val);
/* --- 括号匹配 --- */
printf("--- 括号匹配 ---\n");
printf("\"(a+b)*[c-d]\" 匹配? %s\n",
BracketMatch("(a+b)*[c-d]") ? "是" : "否");
printf("\"(a+b]*c\" 匹配? %s\n",
BracketMatch("(a+b]*c") ? "是" : "否");
printf("\"((())\" 匹配? %s\n\n",
BracketMatch("((())") ? "是" : "否");
/* --- 十进制转二进制 --- */
printf("--- 十进制转二进制 ---\n");
printf("42 -> ");
DecToBin(42);
printf("\n13 -> ");
DecToBin(13);
printf("\n\n");
/* --- 后缀表达式求值 --- */
printf("--- 后缀表达式求值 ---\n");
/* "3 4 + 5 *" 即 (3+4)*5 = 35 */
int res = EvalPostfix("34+5*");
printf("后缀 \"34+5*\" = %d (即(3+4)*5)\n", res);
/* "5 1 2 + 4 * + 3 -" 即 5+((1+2)*4)-3 = 14 */
res = EvalPostfix("512+4*+3-");
printf("后缀 \"512+4*+3-\" = %d (即5+(1+2)*4-3)\n", res);
return 0;
}04 二叉树
c
/*
* ============================================================
* 408 考研数据结构 —— 二叉树 (可编译运行版)
* 文件: 04_二叉树.c
* 编译: gcc 04_二叉树.c -o btree && btree
* ============================================================
*
* 本文件包含:
* 1. 二叉链表存储结构的定义与手工建树
* 2. 先序/中序/后序 递归遍历
* 3. ★ 中序非递归遍历 (栈实现, 考研大题重点)
* 4. ★ 层序遍历 (队列实现, BFS 的原型)
* 5. ★ 求二叉树深度 (递归)
* 6. ★ 统计叶子结点个数
* 7. ★ 2014 真题: 求 WPL (带权路径长度)
* 8. ★ 判断是否是完全二叉树
*
* 手工建树说明:
* 为了让你真正运行起来看到效果, 本文件手工构造一棵树:
* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
* ============================================================
*/
#include <stdio.h>
#include <stdlib.h>
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; /* 转向右子树 */
}
}
}
/* ========== 层序遍历 (BFS, 队列实现) ========== */
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;
}
}
/* ========== 求二叉树深度 ========== */
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, 否则递归左右子树
* 注意: 这里 depth 从 0 开始 (根在第 0 层)
*/
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);
}
/* ========== 判断是否为完全二叉树 ========== */
/*
* 层序遍历,遇到空结点后不应再出现非空结点
*/
int IsComplete(BiTree T) {
if (T == NULL) return 1;
BiTNode *queue[50];
int front = 0, rear = 0;
int reachedNull = 0; /* 标记是否遇到过空 */
queue[rear++] = T;
while (front != rear) {
BiTNode *p = queue[front++];
if (p == NULL) {
reachedNull = 1;
} else {
if (reachedNull) return 0; /* 空之后又遇到非空, 不是完全二叉树 */
queue[rear++] = p->lchild; /* 即使是空也入队 */
queue[rear++] = p->rchild;
}
}
return 1;
}
/* ========== main 演示 ========== */
int main() {
printf("===== 408 二叉树 可运行演示 =====\n\n");
/* 手工建立一棵二叉树:
* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
*/
BiTNode *n1 = NewNode(1);
BiTNode *n2 = NewNode(2);
BiTNode *n3 = NewNode(3);
BiTNode *n4 = NewNode(4);
BiTNode *n5 = NewNode(5);
BiTNode *n6 = NewNode(6);
BiTNode *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("\n中序非递归: "); InOrderNonRecursive(n1); printf("\n");
printf("层序遍历: "); LevelOrder(n1); printf("\n");
printf("\n树的深度 = %d\n", TreeDepth(n1));
printf("叶子结点数 = %d\n", CountLeaves(n1));
/* WPL: 叶子是 4(深度2), 5(深度2), 6(深度2), 7(深度2) */
printf("\nWPL = %d (叶子权×深度之和)\n", CalcWPL(n1, 0));
printf("是否完全二叉树? %s\n", IsComplete(n1) ? "是" : "否");
/* 构造一棵不完全的树测试 */
BiTNode *m1 = NewNode(1);
BiTNode *m2 = NewNode(2);
BiTNode *m3 = NewNode(3);
m1->lchild = m2; m1->rchild = m3;
m3->rchild = NewNode(4); /* 右子树有右孩子, 左子树无 -> 不完全 */
printf("不完全二叉树判断? %s\n", IsComplete(m1) ? "是" : "否");
return 0;
}05 排序算法
c
/*
* ============================================================
* 408 考研数据结构 —— 排序算法全家桶 (可编译运行版)
* 文件: 05_排序算法.c
* 编译: gcc 05_排序算法.c -o sort && sort
* ============================================================
*
* 本文件一次性将 408 考纲要求的全部排序算法集齐并可运行:
* 1. 直接插入排序
* 2. 折半插入排序
* 3. 希尔排序
* 4. 冒泡排序
* 5. ★ 快速排序 (含 Partition 核心及第 k 小应用)
* 6. 简单选择排序
* 7. ★ 堆排序 (大顶堆建堆 + 排序, 下标从 1 开始)
* 8. ★ 归并排序
*
* 每个算法都带完整的测试, 一运行就能看到排序前后的对比。
*
* 注意: 堆排序中, 教材惯例 A[0] 作为暂存单元不存数据,
* 有效元素从 A[1] 到 A[n]。
* ============================================================
*/
#include <stdio.h>
#include <stdlib.h>
/* 打印数组辅助函数 */
void PrintArray(int A[], int n) {
int i;
for (i = 0; i < n; i++) printf("%d ", A[i]);
printf("\n");
}
/* 拷贝数组 (每次测试前恢复原始数据) */
void CopyArray(int src[], int dst[], int n) {
int i;
for (i = 0; i < n; i++) dst[i] = src[i];
}
/* swap */
void swap(int *a, int *b) {
int t = *a; *a = *b; *b = t;
}
/* ===========================================
* 1. 直接插入排序
* 将 A[i] 插入到前面已排好的 A[0..i-1] 中
* 最好 O(n), 最坏 O(n^2), 稳定
* =========================================== */
void InsertSort(int A[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) {
if (A[i] < A[i - 1]) {
temp = A[i];
for (j = i - 1; j >= 0 && temp < A[j]; j--)
A[j + 1] = A[j]; /* 一边找一边后移 */
A[j + 1] = temp;
}
}
}
/* ===========================================
* 2. 折半插入排序
* 查找阶段用二分, 但移动次数不变, 总体仍 O(n^2)
* =========================================== */
void BinaryInsertSort(int A[], int n) {
int i, j, low, high, mid, temp;
for (i = 1; i < n; i++) {
temp = A[i];
low = 0; high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (A[mid] > temp) high = mid - 1;
else low = mid + 1;
}
/* high+1 就是插入位置 */
for (j = i - 1; j >= high + 1; j--)
A[j + 1] = A[j];
A[high + 1] = temp;
}
}
/* ===========================================
* 3. 希尔排序
* 增量序列: dk = n/2, n/4, ..., 1
* 不稳定, 约 O(n^1.3)
* =========================================== */
void ShellSort(int A[], int n) {
int dk, i, j, temp;
for (dk = n / 2; dk >= 1; dk /= 2) {
for (i = dk; i < n; i++) {
if (A[i] < A[i - dk]) {
temp = A[i];
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) {
int i, j, flag;
for (i = 0; i < n - 1; i++) {
flag = 0;
for (j = n - 1; j > i; j--) {
if (A[j - 1] > A[j]) {
swap(&A[j - 1], &A[j]);
flag = 1;
}
}
if (flag == 0) return; /* 本趟无交换, 已经有序 */
}
}
/* ===========================================
* 5. 快速排序
* 核心: Partition 划分函数
* 平均 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) {
int i, j, min;
for (i = 0; i < n - 1; i++) {
min = i;
for (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(n), 排序 O(nlogn), 空间 O(1), 不稳定
* =========================================== */
void AdjustDown(int A[], int k, int len) {
int i;
A[0] = A[k]; /* 暂存 */
for (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 BuildMaxHeap(int A[], int len) {
int i;
for (i = len / 2; i > 0; i--) /* 从最后一个非叶结点开始 */
AdjustDown(A, i, len);
}
void HeapSort(int A[], int len) {
BuildMaxHeap(A, len); /* 建初始大顶堆 */
int i;
for (i = len; i > 1; i--) {
swap(&A[1], &A[i]); /* 堆顶(最大)与末尾交换 */
AdjustDown(A, 1, i - 1); /* 剩余元素重新调整 */
}
}
/* ===========================================
* 8. 归并排序
* 辅助数组 B 开在外面, 避免反复分配
* 时间总是 O(nlogn), 空间 O(n), 稳定
* =========================================== */
int B_merge[50]; /* 辅助数组 */
void Merge(int A[], int low, int mid, int high) {
int i, j, k;
for (k = low; k <= high; k++) B_merge[k] = A[k]; /* 复制 */
for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {
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() {
int original[] = {49, 38, 65, 97, 76, 13, 27, 49};
int n = 8;
int A[8];
printf("===== 408 八大排序 可运行演示 =====\n");
printf("原始数组: "); PrintArray(original, n);
printf("\n");
CopyArray(original, A, n);
InsertSort(A, n);
printf("直接插入: "); PrintArray(A, n);
CopyArray(original, A, n);
BinaryInsertSort(A, n);
printf("折半插入: "); PrintArray(A, n);
CopyArray(original, A, n);
ShellSort(A, n);
printf("希尔排序: "); PrintArray(A, n);
CopyArray(original, A, n);
BubbleSort(A, n);
printf("冒泡排序: "); PrintArray(A, n);
CopyArray(original, A, n);
QuickSort(A, 0, n - 1);
printf("快速排序: "); PrintArray(A, n);
CopyArray(original, A, n);
SelectSort(A, n);
printf("选择排序: "); PrintArray(A, n);
/* 堆排序: A[0] 做暂存, 数据从 A[1] 开始 */
printf("\n--- 堆排序 (下标从1开始) ---\n");
int H[] = {0, 49, 38, 65, 97, 76, 13, 27, 49}; /* H[0]不用 */
printf("排序前: ");
int i;
for (i = 1; i <= 8; i++) printf("%d ", H[i]);
printf("\n");
HeapSort(H, 8);
printf("排序后: ");
for (i = 1; i <= 8; i++) printf("%d ", H[i]);
printf("\n");
printf("\n--- 归并排序 ---\n");
CopyArray(original, A, n);
printf("排序前: "); PrintArray(A, n);
MergeSort(A, 0, n - 1);
printf("排序后: "); PrintArray(A, n);
return 0;
}06 串匹配与查找
c
/*
* ============================================================
* 408 考研数据结构 —— KMP 串匹配与查找 (可编译运行版)
* 文件: 06_串匹配与查找.c
* 编译: gcc 06_串匹配与查找.c -o kmp && kmp
* ============================================================
*
* 本文件包含:
* 1. ★ KMP 算法: get_next 求 next 数组
* 2. ★ KMP 算法: get_nextval 求 nextval 数组
* 3. ★ KMP 主匹配函数 Index_KMP
* 4. 折半查找 (非递归)
*
* 重要说明:
* 教材中字符串下标从 1 开始, ch[0] 存长度或不用。
* 本文件为了可运行性, 同时展示了:
* - 教材 1-based 风格 (考试用这个)
* - C 语言 0-based 风格 (理解用)
* ============================================================
*/
#include <stdio.h>
#include <string.h>
/* ========== 1-based KMP (严格教材风格, 用于考试) ========== */
/*
* get_next: 从模式串 T 推导出 next 数组
*
* next[j] 的含义:
* 当 T[j] 与主串失配时, j 应该回退到 next[j] 的位置
* 即模式串的前 next[j]-1 个字符已经和主串匹配好了
*
* 手算提示: 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]] 时, 即使回退到 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 开始
*/
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; /* 返回匹配位置 (1-based) */
else
return 0; /* 未找到 */
}
/* ========== 折半查找 ========== */
int BinarySearch(int A[], int n, int key) {
int low = 0, high = n - 1, mid;
while (low <= high) {
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("===== 408 KMP 串匹配与查找 可运行演示 =====\n\n");
/* --- KMP 演示 ---
* 注意: 教材风格, S[0] 和 T[0] 不用, 有效字符从下标 1 开始
* 所以我们在字符串前面加一个占位符 '#'
*/
/* 主串: "aababaabaabcac" (14 个字符) */
/* 模式串: "abaabcac" (8 个字符) */
char S[] = "#aababaabaabcac"; /* S[1]='a', S[2]='a', ... */
char T[] = "#abaabcac"; /* T[1]='a', T[2]='b', ... */
int Slen = 14, Tlen = 8;
int next[20], nextval[20];
get_next(T, Tlen, next);
get_nextval(T, Tlen, nextval);
int i;
printf("模式串 T = \"abaabcac\"\n");
printf("位序: ");
for (i = 1; i <= Tlen; i++) printf("%d ", i);
printf("\n字符: ");
for (i = 1; i <= Tlen; i++) printf("%c ", T[i]);
printf("\nnext: ");
for (i = 1; i <= Tlen; i++) printf("%d ", next[i]);
printf("\nnextval: ");
for (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");
if (pos > 0)
printf("T 在 S 中第一次出现的位置 = %d\n\n", pos);
else
printf("未找到\n\n");
/* --- 折半查找 --- */
printf("--- 折半查找 ---\n");
int arr[] = {7, 10, 13, 16, 19, 29, 32, 33, 37, 41, 43};
int n = 11;
printf("有序数组: ");
for (i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
int key = 33;
int result = BinarySearch(arr, n, key);
printf("查找 %d -> 下标 %d\n", key, result);
key = 20;
result = BinarySearch(arr, n, key);
printf("查找 %d -> %s\n", key, result == -1 ? "未找到" : "找到了");
return 0;
}07 图算法
c
/*
* ============================================================
* 408 考研数据结构 —— 图: BFS / DFS / Dijkstra (可编译运行版)
* 文件: 07_图算法.c
* 编译: gcc 07_图算法.c -o graph && graph
* ============================================================
*
* 本文件包含:
* 1. 邻接矩阵存储图
* 2. ★ DFS 深度优先遍历 (递归)
* 3. ★ BFS 广度优先遍历 (队列)
* 4. ★ Dijkstra 最短路径 (邻接矩阵)
* 5. ★ 拓扑排序 (邻接表, 选择题/大题常考)
*
* 测试图 (无向图, 5 个顶点):
* 0 --- 1 --- 3
* | |
* 2 --- 4
* ============================================================
*/
#include <stdio.h>
#include <stdlib.h>
#define MaxV 20
#define INF 999999
/* ========== 邻接矩阵存储 ========== */
typedef struct {
int vex[MaxV]; /* 顶点表 */
int Edge[MaxV][MaxV]; /* 邻接矩阵 */
int vexnum, arcnum; /* 顶点数, 边数 */
} MGraph;
int visited[MaxV]; /* 访问标记数组 */
/* 初始化图 */
void InitGraph(MGraph *G, int n) {
int i, j;
G->vexnum = n;
G->arcnum = 0;
for (i = 0; i < n; i++) {
G->vex[i] = i;
for (j = 0; j < n; j++)
G->Edge[i][j] = (i == j) ? 0 : INF;
}
}
/* 添加无向边 (权值默认为 1) */
void AddEdge(MGraph *G, int u, int v, int w) {
G->Edge[u][v] = w;
G->Edge[v][u] = w;
G->arcnum++;
}
/* ========== DFS 深度优先遍历 ========== */
/*
* 递归原理:
* 1. 访问当前顶点, 标记
* 2. 遍历邻接矩阵找未访问的邻居, 递归进去
*/
void DFS(MGraph *G, int v) {
printf("%d ", v);
visited[v] = 1;
int w;
for (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) {
int i;
for (i = 0; i < G->vexnum; i++) visited[i] = 0;
for (i = 0; i < G->vexnum; i++)
if (!visited[i]) DFS(G, i);
}
/* ========== BFS 广度优先遍历 ========== */
/*
* 队列实现:
* 1. 源点入队, 标记
* 2. 出队, 遍历邻居, 未访问的入队并标记
*/
void BFS(MGraph *G, int v) {
int queue[MaxV], front = 0, rear = 0;
printf("%d ", v);
visited[v] = 1;
queue[rear++] = v;
while (front != rear) {
int u = queue[front++];
int w;
for (w = 0; w < G->vexnum; w++) {
if (G->Edge[u][w] != 0 && G->Edge[u][w] != INF && !visited[w]) {
printf("%d ", w);
visited[w] = 1;
queue[rear++] = w;
}
}
}
}
void BFSTraverse(MGraph *G) {
int i;
for (i = 0; i < G->vexnum; i++) visited[i] = 0;
for (i = 0; i < G->vexnum; i++)
if (!visited[i]) BFS(G, i);
}
/* ========== Dijkstra 最短路径 ========== */
/*
* 从源点 src 到其余各点的最短路径
* dist[i]: 源点到 i 的当前最短距离
* path[i]: i 的前驱顶点 (用于输出路径)
* final[i]: 顶点 i 是否已经确定最短路
*/
void Dijkstra(MGraph *G, int src) {
int dist[MaxV], path[MaxV], final[MaxV];
int i, j;
/* 初始化 */
for (i = 0; i < G->vexnum; i++) {
dist[i] = G->Edge[src][i];
final[i] = 0;
path[i] = (dist[i] < INF) ? src : -1;
}
dist[src] = 0;
final[src] = 1;
/* 循环 n-1 次, 每次确定一个最短路顶点 */
for (i = 0; i < G->vexnum - 1; i++) {
int min = INF, u = -1;
/* 找未确定的最短距离顶点 */
for (j = 0; j < G->vexnum; j++) {
if (!final[j] && dist[j] < min) {
min = dist[j];
u = j;
}
}
if (u == -1) break; /* 不连通 */
final[u] = 1;
/* 用 u 更新其邻居 (松弛操作) */
for (j = 0; j < G->vexnum; j++) {
if (!final[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 (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 i, j, count = 0;
/* 统计入度 (邻接矩阵: Edge[i][j]!=0 且 !=INF 说明有边 i->j) */
for (j = 0; j < G->vexnum; j++)
for (i = 0; i < G->vexnum; i++)
if (G->Edge[i][j] != 0 && G->Edge[i][j] != INF)
indegree[j]++;
/* 入度为 0 的入栈 */
for (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 (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("===== 408 图算法 可运行演示 =====\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 ---\n");
DFSTraverse(&G);
printf("\n\n");
printf("--- BFS ---\n");
BFSTraverse(&G);
printf("\n\n");
/* 构建带权有向图测试 Dijkstra:
* 0 --(1)--> 1 --(3)--> 3
* | |
* (6) (2)
* v v
* 2 --(1)--> 4
*/
printf("--- Dijkstra ---\n");
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");
/* 拓扑排序 (有向无环图):
* 0 --> 1 --> 3
* | |
* v v
* 2 --> 4
*/
printf("--- 拓扑排序 ---\n");
TopologicalSort(&G2);
return 0;
}