C 语言数据结构与算法
C 语言数据结构与算法
数据结构与算法是程序设计的核心基础,本教程用 C 语言实现常用数据结构与经典算法,深入理解底层实现原理。
本教程包含
- 基础篇:环境搭建、算法基础、数据结构基本概念
- 线性结构:数组、单链表、双向链表、循环链表、栈、队列
- 树与图:二叉树、遍历、图、最短路径
- 算法篇:排序、查找、递归与经典算法
为什么用 C 学习
1. C 贴近硬件,理解指针与内存
2. 亲手实现,理解数据结构本质
3. 面试手写代码常用 C/Java
4. 高性能系统编程的基础学习方法
1. 先理解概念与复杂度
2. 画图理解结构
3. 动手实现 + 测试
4. 分析时间/空间复杂度C 语言环境搭建
C 语言环境搭建
搭建 C 语言开发环境:编译器 + 编辑器。
安装编译器
# Linux
sudo apt install gcc # Debian/Ubuntu
sudo dnf install gcc # Fedora
# macOS
xcode-select --install # 或安装 CLT
# Windows
# 推荐 MinGW-w64 或 MSYS2,或直接装 VS Code + WSL验证编译器
gcc --version
# gcc (GCC) 13.x.x第一个 C 程序
// hello.c
#include <stdio.h>
int main(void) {
printf("Hello, C!
");
return 0;
}编译运行
# 编译
gcc hello.c -o hello
# 运行
./hello
# 调试模式
gcc -g hello.c -o hello # 带调试信息
gcc -Wall hello.c -o hello # 显示警告
# 直接编译运行一步
gcc hello.c -o hello && ./helloIDE 推荐
VS Code: C/C++ 扩展(微软官方)
CLion: JetBrains C/C++ IDE(收费)
Code::Blocks: 轻量免费常用命令速查
gcc file.c -o out 编译
gdb ./out 调试
make 使用 Makefile 构建
valgrind ./out 内存检查(检测泄漏)算法基础
算法基础
算法的基本概念、复杂度分析与设计思想。
什么是算法
算法 = 解决特定问题的有限步骤集合
特征: 有穷性、确定性、可行性、输入、输出
评价标准: 正确性 + 效率(时间/空间)时间复杂度
大 O 表示法: 描述算法随数据规模增长的趋势
O(1) 常数(数组访问)
O(log n) 对数(二分查找)
O(n) 线性(遍历)
O(n log n) 线性对数(快排/归并)
O(n²) 平方(冒泡/选择)
O(2^n) 指数(暴力组合)
// 例子
int sum(int n) { // O(n)
int s = 0;
for (int i = 1; i <= n; i++) s += i;
return s;
}
// 简化: 常量、低阶项忽略
// O(2n+5) → O(n)
// O(n²+n) → O(n²)空间复杂度
额外使用的内存量
O(1): 只用了常量变量
O(n): 用了与输入规模成比例的额外空间
// 归并排序需要 O(n) 额外空间
// 原地排序(快排)只需 O(log n) 栈空间算法设计思想
分治法: 拆分子问题(归并、快排、二分)
动态规划: 重叠子问题+最优子结构(背包、LCS)
贪心: 每步局部最优(哈夫曼、最小生成树)
回溯: 试探+回退(八皇后、数独)
递归: 函数调用自身(树的遍历)复杂度分析练习
// 双重循环 → O(n²)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
sum += a[i][j];
// 每次减半 → O(log n)
while (n > 1) n /= 2;数据结构基本概念
数据结构基本概念
数据结构的定义、分类与 C 语言中的实现基础。
什么是数据结构
数据结构 = 数据的组织方式 + 操作方式
逻辑结构(抽象):
线性: 数组、链表、栈、队列
树形: 二叉树、堆
图形: 图
物理存储(实现):
顺序存储: 连续内存(数组)
链式存储: 指针连接(链表)抽象数据类型(ADT)
ADT = 数据对象 + 操作集合
例: 栈 ADT
数据: 元素序列(先进后出)
操作: push(压入)、pop(弹出)、top(栈顶)、isEmpty
C 中用 struct + 函数实现 ADTC 语言中的基础
// 结构体定义节点
struct Node {
int data;
struct Node *next; // 指针
};
// typedef 简化
typedef struct Node Node;
// 动态内存
Node *p = (Node *)malloc(sizeof(Node));
free(p); // 释放数据结构的操作
增: 插入元素
删: 删除元素
查: 查找/访问
改: 更新元素
遍历: 访问所有元素
不同结构在不同操作上有不同复杂度:
数组: 随机访问 O(1), 插入删除 O(n)
链表: 插入删除 O(1)(有指针), 随机访问 O(n)选型原则
频繁随机访问 → 数组
频繁插入删除 → 链表
后进先出 → 栈
先进先出 → 队列
层级关系 → 树
多对多关系 → 图数据结构 - 数组
数据结构 - 数组
数组是最基础的顺序存储结构,连续内存,随机访问。
数组特性
连续内存空间
下标从 0 开始
随机访问 O(1): 地址 = 基址 + 下标 × 元素大小
插入/删除 O(n)(需移动元素)C 语言数组操作
#include <stdio.h>
int main(void) {
// 定义与初始化
int arr[5] = {1, 2, 3, 4, 5};
int n = 5;
// 访问
printf("%d
", arr[2]); // 3
// 遍历
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
// 尾部插入
int newValue = 6;
arr[n] = newValue; // 需预留空间
n++;
// 指定位置插入(需移动)
int pos = 2, val = 99;
for (int i = n; i > pos; i--) {
arr[i] = arr[i - 1]; // 后移
}
arr[pos] = val;
n++;
// 删除指定位置(前移)
int delPos = 2;
for (int i = delPos; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
n--;
return 0;
}动态数组
#include <stdlib.h>
// 动态分配
int *arr = (int *)malloc(10 * sizeof(int));
if (arr == NULL) { /* 分配失败 */ }
// 扩容
arr = (int *)realloc(arr, 20 * sizeof(int));
// 释放
free(arr);二维数组
int matrix[3][4]; // 3行4列
int *flat = (int *)malloc(3*4*sizeof(int));
// 访问 matrix[i][j] = flat[i*4 + j]优缺点
优点: 随机访问快、缓存友好、空间紧凑
缺点: 大小固定(静态)、插入删除慢、可能浪费空间数据结构 - 链表
数据结构 - 链表
链表通过指针连接节点,插入删除高效,是动态数据结构的基石。
单链表结构
头节点 → 节点1 → 节点2 → ... → NULL
每个节点: 数据 + next 指针C 实现单链表
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
// 创建节点
Node *createNode(int data) {
Node *n = (Node *)malloc(sizeof(Node));
n->data = data;
n->next = NULL;
return n;
}
// 头部插入
Node *insertHead(Node *head, int data) {
Node *n = createNode(data);
n->next = head; // 新节点指向原头
return n; // 新节点成为头
}
// 尾部插入
Node *insertTail(Node *head, int data) {
Node *n = createNode(data);
if (head == NULL) return n;
Node *p = head;
while (p->next != NULL) p = p->next; // 找尾
p->next = n;
return head;
}
// 删除指定值
Node *deleteNode(Node *head, int target) {
if (head == NULL) return NULL;
if (head->data == target) { // 删除头
Node *tmp = head;
head = head->next;
free(tmp);
return head;
}
Node *p = head;
while (p->next != NULL && p->next->data != target) {
p = p->next;
}
if (p->next != NULL) { // 找到
Node *tmp = p->next;
p->next = tmp->next;
free(tmp);
}
return head;
}
// 查找
Node *search(Node *head, int target) {
for (Node *p = head; p != NULL; p = p->next) {
if (p->data == target) return p;
}
return NULL;
}
// 遍历打印
void printList(Node *head) {
for (Node *p = head; p != NULL; p = p->next) {
printf("%d -> ", p->data);
}
printf("NULL
");
}
// 释放
void freeList(Node *head) {
Node *p = head;
while (p != NULL) {
Node *tmp = p;
p = p->next;
free(tmp);
}
}复杂度
插入(有指针): O(1)
删除(有指针): O(1)
查找/访问: O(n)(需遍历)优缺点
优点: 动态大小、插入删除快
缺点: 不能随机访问、额外指针空间、缓存不友好数据结构 - 双向链表
数据结构 - 双向链表
双向链表每个节点有前驱和后继指针,可双向遍历。
结构
NULL ← 节点1 ⇄ 节点2 ⇄ 节点3 → NULL
prev data next
C 实现
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *prev; // 前驱
struct Node *next; // 后继
} Node;
Node *createNode(int data) {
Node *n = (Node *)malloc(sizeof(Node));
n->data = data;
n->prev = NULL;
n->next = NULL;
return n;
}
// 头部插入
Node *insertHead(Node *head, int data) {
Node *n = createNode(data);
if (head != NULL) head->prev = n;
n->next = head;
return n;
}
// 尾部插入
Node *insertTail(Node *head, int data) {
Node *n = createNode(data);
if (head == NULL) return n;
Node *p = head;
while (p->next != NULL) p = p->next;
p->next = n;
n->prev = p;
return head;
}
// 删除节点(已知指针,O(1))
Node *deleteNode(Node *head, Node *target) {
if (target == NULL) return head;
if (target == head) {
head = head->next;
if (head) head->prev = NULL;
} else {
target->prev->next = target->next;
if (target->next) target->next->prev = target->prev;
}
free(target);
return head;
}
// 正向遍历
void printForward(Node *head) {
for (Node *p = head; p; p = p->next) {
printf("%d ⇄ ", p->data);
}
printf("NULL
");
}
// 反向遍历
void printBackward(Node *head) {
if (!head) return;
Node *p = head;
while (p->next) p = p->next; // 到尾
for (; p; p = p->prev) {
printf("%d ⇄ ", p->data);
}
printf("NULL
");
}优势
双向遍历(向前/向后)
删除已知节点 O(1)(无需找前驱)
实现 LRU 缓存等复杂结构的基础代价
每个节点多一个指针(空间+)
插入删除需维护两个指针(逻辑复杂)数据结构 - 循环链表
数据结构 - 循环链表
循环链表尾部指向头部,形成环,适合环形数据处理。
结构
节点1 → 节点2 → 节点3 → 节点4
↑ ↓
└──────── 回到节点1 ←────┘
尾节点的 next 指向头(而非 NULL)C 实现(单循环链表)
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
// 创建(指向自己,空环)
Node *createNode(int data) {
Node *n = (Node *)malloc(sizeof(Node));
n->data = data;
n->next = n; // 自环
return n;
}
// 尾部插入(在头前插,保持头不变)
Node *insertTail(Node *head, int data) {
Node *n = createNode(data);
if (head == NULL) return n;
// 找到尾(尾的 next 是 head)
Node *p = head;
while (p->next != head) p = p->next;
p->next = n;
n->next = head;
return head;
}
// 遍历(从 head 出发,回到 head 结束)
void printList(Node *head) {
if (head == NULL) return;
Node *p = head;
do {
printf("%d -> ", p->data);
p = p->next;
} while (p != head);
printf("(回到头)
");
}
// 约瑟夫环问题(经典应用)
// n 个人围一圈,报数 m,每报到 m 的人出圈
int josephus(int n, int m) {
int survivor = 0;
for (int i = 2; i <= n; i++) {
survivor = (survivor + m) % i;
}
return survivor + 1; // 1-based
}应用
约瑟夫环问题
循环队列/缓冲区
操作系统进程轮转调度
游戏回合制注意
遍历结束条件: p->next == head(而非 NULL)
小心死循环(操作前先判空/判环)数据结构 - 栈
数据结构 - 栈
栈是后进先出(LIFO)的线性结构,用于函数调用、表达式求值、撤销操作。
栈的基本操作
push(压栈): 放入栈顶
pop(弹栈): 取出栈顶
top/peek: 查看栈顶(不取出)
isEmpty: 是否为空
size: 元素个数
后进先出: 最后放入的先取出数组实现(顺序栈)
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
typedef struct {
int data[MAX];
int top; // 栈顶索引(-1为空)
} Stack;
void init(Stack *s) { s->top = -1; }
int isEmpty(Stack *s) { return s->top == -1; }
int isFull(Stack *s) { return s->top == MAX - 1; }
void push(Stack *s, int val) {
if (isFull(s)) { printf("栈满
"); return; }
s->data[++s->top] = val;
}
int pop(Stack *s) {
if (isEmpty(s)) { printf("栈空
"); return -1; }
return s->data[s->top--];
}
int top(Stack *s) {
if (isEmpty(s)) return -1;
return s->data[s->top];
}
int main(void) {
Stack s;
init(&s);
push(&s, 10);
push(&s, 20);
push(&s, 30);
printf("%d
", pop(&s)); // 30
printf("%d
", pop(&s)); // 20
printf("%d
", top(&s)); // 10
return 0;
}链表实现(链式栈)
typedef struct Node { int data; struct Node *next; } Node;
// push: 头插
Node *push(Node *top, int val) {
Node *n = (Node *)malloc(sizeof(Node));
n->data = val;
n->next = top;
return n;
}
// pop: 取头
int pop(Node **top) {
if (*top == NULL) return -1;
Node *tmp = *top;
int val = tmp->data;
*top = tmp->next;
free(tmp);
return val;
}应用场景
函数调用栈(递归)
表达式求值(中缀转后缀)
括号匹配
浏览器后退
撤销/重做数据结构 - 队列
数据结构 - 队列
队列是先进先出(FIFO)的线性结构,用于任务调度、缓冲、BFS。
队列操作
enqueue(入队): 队尾加入
dequeue(出队): 队头取出
front: 查看队头
isEmpty
先进先出: 先入队的先出队数组实现(循环队列)
#include <stdio.h>
#define MAX 100
typedef struct {
int data[MAX];
int front; // 队头(出队位置)
int rear; // 队尾(入队位置)
int count; // 元素个数
} Queue;
void init(Queue *q) {
q->front = 0;
q->rear = 0;
q->count = 0;
}
int isEmpty(Queue *q) { return q->count == 0; }
int isFull(Queue *q) { return q->count == MAX; }
void enqueue(Queue *q, int val) {
if (isFull(q)) { printf("队满
"); return; }
q->data[q->rear] = val;
q->rear = (q->rear + 1) % MAX; // 循环
q->count++;
}
int dequeue(Queue *q) {
if (isEmpty(q)) { printf("队空
"); return -1; }
int val = q->data[q->front];
q->front = (q->front + 1) % MAX;
q->count--;
return val;
}
int main(void) {
Queue q;
init(&q);
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
printf("%d
", dequeue(&q)); // 1
printf("%d
", dequeue(&q)); // 2
printf("%d
", dequeue(&q)); // 3
return 0;
}链表实现(链式队列)
typedef struct Node { int data; struct Node *next; } Node;
typedef struct { Node *front; Node *rear; } Queue;
void enqueue(Queue *q, int val) {
Node *n = (Node *)malloc(sizeof(Node));
n->data = val; n->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = n;
} else {
q->rear->next = n;
q->rear = n;
}
}
int dequeue(Queue *q) {
if (q->front == NULL) return -1;
Node *tmp = q->front;
int val = tmp->data;
q->front = q->front->next;
if (q->front == NULL) q->rear = NULL;
free(tmp);
return val;
}应用
BFS 广度优先搜索
任务调度、消息队列
打印缓冲、I/O 缓冲
操作系统就绪队列数据结构 - 二叉树
数据结构 - 二叉树
二叉树是最重要的树形结构,每个节点最多两个子节点,是搜索、堆、表达式树的基础。
二叉树结构
1
/ 2 3
/ \ 4 5 6
节点: 数据 + 左孩子 + 右孩子
满二叉树: 每层都满
完全二叉树: 除最后一层外都满,从左排列C 实现
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
Node *createNode(int data) {
Node *n = (Node *)malloc(sizeof(Node));
n->data = data;
n->left = NULL;
n->right = NULL;
return n;
}
// 前序遍历: 根 → 左 → 右
void preorder(Node *root) {
if (root == NULL) return;
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
// 中序遍历: 左 → 根 → 右
void inorder(Node *root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
// 后序遍历: 左 → 右 → 根
void postorder(Node *root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
// 树的高度
int height(Node *root) {
if (root == NULL) return 0;
int l = height(root->left);
int r = height(root->right);
return (l > r ? l : r) + 1;
}
// 节点数
int countNodes(Node *root) {
if (root == NULL) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
int main(void) {
// 构建示例树
Node *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
preorder(root); printf("
"); // 1 2 4 5 3
inorder(root); printf("
"); // 4 2 5 1 3
postorder(root); printf("
"); // 4 5 2 3 1
printf("高度: %d
", height(root)); // 3
printf("节点数: %d
", countNodes(root)); // 5
return 0;
}层序遍历(队列)
// 用队列逐层输出
// 1 → 2 3 → 4 5应用
二叉搜索树(BST)、堆
表达式树
哈夫曼树(压缩)
文件系统目录数据结构 - 二叉树遍历
数据结构 - 二叉树遍历
深入二叉树遍历:递归与非递归实现,层序遍历。
递归遍历回顾
前序: 根-左-右 中序: 左-根-右 后序: 左-右-根
三种递归实现结构相同,只是 printf 位置不同非递归前序遍历(栈)
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int data; struct Node *left, *right; } Node;
typedef struct Stack { Node *data[100]; int top; } Stack;
void push(Stack *s, Node *n) { s->data[++s->top] = n; }
Node *pop(Stack *s) { return s->data[s->top--]; }
int isEmpty(Stack *s) { return s->top == -1; }
void preorder_iter(Node *root) {
if (root == NULL) return;
Stack s = {.top = -1};
push(&s, root);
while (!isEmpty(&s)) {
Node *cur = pop(&s);
printf("%d ", cur->data);
// 先压右再压左(左先出)
if (cur->right) push(&s, cur->right);
if (cur->left) push(&s, cur->left);
}
printf("
");
}非递归中序遍历
void inorder_iter(Node *root) {
Stack s = {.top = -1};
Node *cur = root;
while (cur != NULL || !isEmpty(&s)) {
// 沿左子树一路压栈
while (cur != NULL) {
push(&s, cur);
cur = cur->left;
}
// 弹出访问,转向右子树
cur = pop(&s);
printf("%d ", cur->data);
cur = cur->right;
}
printf("
");
}层序遍历(队列)
typedef struct Queue { Node *data[100]; int front, rear; } Queue;
void enqueue(Queue *q, Node *n) {
q->data[q->rear++] = n;
}
Node *dequeue(Queue *q) { return q->data[q->front++]; }
void levelOrder(Node *root) {
if (root == NULL) return;
Queue q = {0, 0};
enqueue(&q, root);
while (q.front < q.rear) {
Node *cur = dequeue(&q);
printf("%d ", cur->data);
if (cur->left) enqueue(&q, cur->left);
if (cur->right) enqueue(&q, cur->right);
}
printf("
");
}遍历应用
中序 + 前序/后序 → 重建二叉树
前序: 复制树
后序: 释放树(先子后父)
层序: 求最小深度、判断完全二叉树数据结构 - 图
数据结构 - 图
图是最灵活的数据结构,表示多对多关系:网络、社交、地图。
图的基本概念
顶点(Vertex): 图的节点
边(Edge): 顶点间的连接
有向图: 边有方向(单向)
无向图: 边无方向
权值: 边的代价(距离等)
度: 顶点的边数
路径: 顶点序列
连通: 任意两点可达存储方式
1. 邻接矩阵: N×N 数组
优点: 查询 O(1) 缺点: 空间 O(n²)
2. 邻接表: 每个顶点一个链表
优点: 空间省 缺点: 查询 O(度数)邻接矩阵实现
#include <stdio.h>
#include <string.h>
#define MAX 100
int graph[MAX][MAX]; // graph[i][j] = 1 有边
// 添加无向边
void addEdge(int u, int v) {
graph[u][v] = 1;
graph[v][u] = 1; // 无向
}
// 添加有向边
void addDirectedEdge(int u, int v) {
graph[u][v] = 1;
}
// 输出
void printGraph(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", graph[i][j]);
}
printf("
");
}
}邻接表实现
typedef struct EdgeNode {
int vertex;
struct EdgeNode *next;
} EdgeNode;
typedef struct {
EdgeNode *head; // 每个顶点的边链表
} Vertex;
Vertex vertices[MAX];
void addEdge(int u, int v) {
EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->vertex = v;
e->next = vertices[u].head;
vertices[u].head = e; // 头插
}图的遍历
DFS(深度优先): 栈/递归,一条路走到底
BFS(广度优先): 队列,逐层扩散
// 用于: 连通性判断、路径搜索、拓扑排序应用
社交网络、地图导航(最短路径)
网络拓扑、依赖关系(拓扑排序)
推荐系统(二部图)
状态空间搜索数据结构 - 最短路径
数据结构 - 最短路径
图论经典问题:求两点间最短路径,核心算法是 Dijkstra 和 Floyd。
Dijkstra 算法(单源最短路径)
适用: 非负权值图
思想: 贪心,每次选距离最近未访问顶点
复杂度: O(V²)(朴素) / O(E log V)(堆优化)
#include <stdio.h>
#include <limits.h>
#define MAX 100
#define INF INT_MAX
int graph[MAX][MAX];
int dist[MAX]; // 到源点距离
int visited[MAX]; // 是否已确定
void dijkstra(int src, int n) {
// 初始化
for (int i = 0; i < n; i++) {
dist[i] = INF;
visited[i] = 0;
}
dist[src] = 0;
for (int count = 0; count < n - 1; count++) {
// 找未访问中距离最小的
int u = -1, minDist = INF;
for (int i = 0; i < n; i++) {
if (!visited[i] && dist[i] < minDist) {
minDist = dist[i];
u = i;
}
}
if (u == -1) break;
visited[u] = 1;
// 更新邻居
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v]
&& dist[u] != INF
&& dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
int main(void) {
int n = 5;
// 初始化图(0表示无边)
graph[0][1] = 10; graph[0][2] = 3;
graph[1][2] = 1; graph[1][3] = 2;
graph[2][1] = 4; graph[2][3] = 8;
graph[3][4] = 7; graph[2][4] = 2;
dijkstra(0, n);
for (int i = 0; i < n; i++) {
printf("0→%d: %d
", i, dist[i]);
}
return 0;
}Floyd 算法(全源最短路径)
适用: 所有顶点对,允许负权(无负环)
思想: 动态规划,三重循环
复杂度: O(V³)
void floyd(int n) {
// dist 初始化为 graph(无边为 INF)
for (int k = 0; k < n; k++) { // 中转点
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != INF && dist[k][j] != INF
&& dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}算法选择
单源 + 非负权: Dijkstra(O(E log V)最优)
单源 + 负权: Bellman-Ford
全源 + 小图: Floyd(O(V³))
全源 + 稀疏: 多次 Dijkstra应用
地图导航、网络路由(OSPF)
游戏寻路
社交距离分析排序算法
排序算法
排序是最基础的算法问题,掌握常见排序的实现与复杂度。
排序算法总览
算法 平均 最坏 空间 稳定性
冒泡排序 O(n²) O(n²) O(1) 稳定
选择排序 O(n²) O(n²) O(1) 不稳定
插入排序 O(n²) O(n²) O(1) 稳定
希尔排序 O(n^1.3) - O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(n²) O(logn) 不稳定
堆排序 O(nlogn) O(nlogn) O(1) 不稳定快速排序(最常用)
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a; *a = *b; *b = t;
}
// 分区: 选基准,小的在左大的在右
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选最后一个为基准
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main(void) {
int arr[] = {9, 4, 7, 2, 5, 1, 8, 3, 6};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}归并排序(稳定 O(nlogn))
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1, n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}C 库函数 qsort
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b; // 升序
}
qsort(arr, n, sizeof(int), cmp);查找算法
查找算法
顺序查找、二分查找与哈希查找,理解不同场景的选择。
顺序查找(O(n))
int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) return i;
}
return -1; // 未找到
}
// 适用: 无序数据,小规模二分查找(O(log n))
// 前提: 有序数组
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防溢出
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// 递归版
int binarySearchRec(int arr[], int left, int right, int target) {
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target)
return binarySearchRec(arr, mid + 1, right, target);
return binarySearchRec(arr, left, mid - 1, target);
}
// C 库: bsearch
#include <stdlib.h>
int *result = (int *)bsearch(&target, arr, n, sizeof(int), cmp);哈希查找(O(1) 平均)
// 哈希表: 通过哈希函数直接定位
// 简单实现(取模)
#define SIZE 101
typedef struct {
int key;
int value;
int occupied; // 是否占用
} HashEntry;
HashEntry table[SIZE];
int hash(int key) { return key % SIZE; }
// 线性探测解决冲突
void insert(int key, int value) {
int idx = hash(key);
while (table[idx].occupied) {
idx = (idx + 1) % SIZE; // 线性探测
}
table[idx].key = key;
table[idx].value = value;
table[idx].occupied = 1;
}
int search(int key) {
int idx = hash(key);
int start = idx;
while (table[idx].occupied) {
if (table[idx].key == key) return table[idx].value;
idx = (idx + 1) % SIZE;
if (idx == start) break; // 回到起点
}
return -1; // 未找到
}查找场景选择
无序小数据: 顺序查找
有序静态: 二分查找
频繁增删+查找: 哈希表 / 二叉搜索树
需要有序遍历: 二叉搜索树递归算法
递归算法
递归是函数调用自身的编程技巧,天然适合树形与分治问题。
递归三要素
1. 基准条件(终止条件)
2. 递归调用(规模缩小)
3. 结果组合
// 阶乘
int factorial(int n) {
if (n <= 1) return 1; // 基准
return n * factorial(n - 1); // 递归
}
// 斐波那契
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}递归 vs 迭代
递归: 代码简洁、表达清晰
栈开销大,深度过大栈溢出
迭代: 无栈开销,性能好
代码可能更复杂
// 斐波那契迭代版(性能好)
int fib_iter(int n) {
if (n <= 1) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int t = a + b;
a = b;
b = t;
}
return b;
}经典递归: 汉诺塔
void hanoi(int n, char from, char aux, char to) {
if (n == 1) {
printf("%c → %c
", from, to);
return;
}
hanoi(n - 1, from, to, aux); // 移 n-1 到辅助
printf("%c → %c
", from, to); // 移最大盘
hanoi(n - 1, aux, from, to); // 移 n-1 到目标
}
// hanoi(3, 'A', 'B', 'C');
// A → C, A → B, C → B, A → C, B → A, B → C, A → C递归应用
树的遍历、图的 DFS
分治算法(归并、快排)
回溯(八皇后、迷宫)
动态规划的 memo 实现尾递归优化
// 尾递归: 递归调用是最后一步
int factorialTail(int n, int acc) {
if (n <= 1) return acc;
return factorialTail(n - 1, n * acc); // 尾调用
}
// C 编译器可能优化为循环(减少栈)经典算法: 二分与回溯
经典算法:二分与回溯
二分搜索的变体应用与回溯算法的典型问题。
二分搜索变体
// 找第一个 ≥ target 的位置(下界)
int lowerBound(int arr[], int n, int target) {
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
// 找第一个 > target 的位置(上界)
int upperBound(int arr[], int n, int target) {
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) left = mid + 1;
else right = mid;
}
return left;
}
// 浮点二分(求平方根)
double sqrtBinary(double x) {
double lo = 0, hi = x, mid;
for (int i = 0; i < 100; i++) { // 迭代100次足够
mid = (lo + hi) / 2;
if (mid * mid < x) lo = mid;
else hi = mid;
}
return (lo + hi) / 2;
}回溯: 八皇后
#include <stdio.h>
#define N 8
int count = 0;
// 检查 (row, col) 是否安全
int isSafe(int board[N][N], int row, int col) {
int i, j;
// 检查列
for (i = 0; i < row; i++)
if (board[i][col]) return 0;
// 检查左上对角线
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j]) return 0;
// 检查右上对角线
for (i = row, j = col; i >= 0 && j < N; i--, j++)
if (board[i][j]) return 0;
return 1;
}
void solve(int board[N][N], int row) {
if (row == N) { // 所有行都放好
count++;
return;
}
for (int col = 0; col < N; col++) {
if (isSafe(board, row, col)) {
board[row][col] = 1; // 尝试
solve(board, row + 1); // 递归
board[row][col] = 0; // 回溯
}
}
}
// 调用 solve(board, 0) → count = 92回溯模板
void backtrack(参数) {
if (满足结束条件) { 记录结果; return; }
for (选择 in 所有可能) {
做出选择;
backtrack(新参数); // 递归
撤销选择; // 回溯
}
}应用
八皇后、数独、全排列
组合/子集生成
迷宫求解、正则匹配
AI 博弈搜索(剪枝)经典算法: 动态规划
经典算法:动态规划
动态规划(DP)解决最优子结构与重叠子问题,是面试与算法竞赛重点。
DP 特征
最优子结构: 大问题最优解包含子问题最优解
重叠子问题: 子问题被重复计算(用表存储)
步骤:
1. 定义状态 dp[i]
2. 状态转移方程
3. 初始化
4. 遍历计算
5. 返回结果例1: 斐波那契(记忆化)
#include <stdio.h>
int fib_dp(int n) {
if (n <= 1) return n;
int dp[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 转移方程
}
return dp[n];
}
// O(n) 替代 O(2^n)例2: 爬楼梯
// 每次爬1或2阶,到 n 阶有多少种方法
// dp[i] = dp[i-1] + dp[i-2]
int climbStairs(int n) {
if (n <= 2) return n;
int dp[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}例3: 最长公共子序列(LCS)
// dp[i][j]: 前i个与前j个的LCS长度
// if a[i]==b[j]: dp[i][j] = dp[i-1][j-1] + 1
// else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
int lcs(char *a, int m, char *b, int n) {
int dp[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (a[i-1] == b[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = dp[i-1][j] > dp[i][j-1]
? dp[i-1][j] : dp[i][j-1];
}
}
}
return dp[m][n];
}例4: 0-1 背包
// n 件物品,重量 w[i],价值 v[i],背包容量 C
// dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i])
int knapsack(int w[], int v[], int n, int C) {
int dp[n + 1][C + 1];
for (int i = 0; i <= n; i++) {
for (int c = 0; c <= C; c++) {
if (i == 0 || c == 0) {
dp[i][c] = 0;
} else if (w[i-1] <= c) {
int notTake = dp[i-1][c];
int take = dp[i-1][c-w[i-1]] + v[i-1];
dp[i][c] = notTake > take ? notTake : take;
} else {
dp[i][c] = dp[i-1][c];
}
}
}
return dp[n][C];
}应用
最短路径(Floyd)、编辑距离
背包系列、股票买卖
最长递增子序列、回文子串
路径计数(机器人走格子)数据结构与算法总结
数据结构与算法总结
恭喜完成本教程!系统回顾并给出学习路径。
数据结构总览
线性:
数组 随机访问快,插入删除慢
链表 插入删除快,访问慢
栈 LIFO: 函数调用/撤销
队列 FIFO: 调度/缓冲
树形:
二叉树 层次关系,遍历三序
(二叉搜索树/堆/哈夫曼 为进阶)
图形:
邻接矩阵/邻接表
DFS/BFS 遍历,最短路径算法总览
排序: 快排(常用)/归并(稳定)/堆排
查找: 二分(有序)/哈希(快速)
递归: 树遍历/分治/回溯
动态规划: 最优子结构问题
图算法: Dijkstra/Floyd/DFS/BFS复杂度记忆要点
O(1): 数组访问、栈操作、哈希查找
O(log n): 二分、平衡树查找
O(n): 遍历、线性查找
O(n log n): 快排/归并/堆排
O(n²): 冒泡/选择/插入、Floyd
O(2^n): 暴力递归(斐波那契未优化)解题思路框架
1. 理解问题,画图示例
2. 暴力解法 → 分析瓶颈
3. 选择合适数据结构优化
4. 考虑算法思想(分治/DP/贪心)
5. 分析复杂度
6. 边界与测试用例进阶学习路径
1. 二叉搜索树、AVL、红黑树
2. 堆(优先队列)与堆排序
3. 哈希表完整实现与冲突处理
4. 图论进阶:拓扑排序、最小生成树
5. 字符串算法:KMP、Trie
6. 算法竞赛:LeetCode/HackerRank 每日刷题C 语言实现建议
1. 画图理解指针关系(尤其链表)
2. 每次操作后检查内存泄漏(free)
3. 用 assert 验证关键假设
4. 边界条件: 空表/单元素/满表
5. 写完用 valgrind 检查内存数据结构与算法需要大量练习才能融会贯通。建议每学完一种结构,亲手实现并测试,再刷对应 LeetCode 题目巩固。
第 1 / 20 节