# c-exam-project

**Repository Path**: dinqb/c-exam-project

## Basic Information

- **Project Name**: c-exam-project
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-05-09
- **Last Updated**: 2026-05-26

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# C语言数据结构与算法考试复习项目

> 本项目覆盖 C 语言考研/期末考试的高频考点，包含完整中文注释与考试填空标注。

## 📁 项目结构

```
c-exam-project/
├── datastructure/          # 数据结构（8个文件）
├── algorithm/              # 算法
│   ├── sort/              # 8种排序算法
│   └── search/            # 2种查找算法
├── advanced/              # 高级算法
│   ├── dp/                # 动态规划（3个文件）
│   ├── greedy/            # 贪心算法（2个文件）
│   ├── divide/            # 分治法（1个文件）
│   └── backtrack/         # 回溯法（2个文件）
├── pattern/               # 设计模式
│   ├── creational/        # 创建型（4个文件）
│   ├── structural/         # 结构型（5个文件）
│   └── behavioral/        # 行为型（6个文件）
└── README.md              # 本文档
```

## 🗂️ 考试要点速查

### 📌 数据结构（8个文件）

| 文件 | 考点 | 难度 |
|------|------|------|
| `array.c` | 顺序表插入/删除、动态扩容、时间复杂度 | ⭐ |
| `linked_list.c` | 单链表操作、快慢指针、反转、合并 | ⭐⭐ |
| `stack.c` | 顺序栈/链栈、括号匹配、后缀表达式求值 | ⭐⭐ |
| `queue.c` | 循环队列、链式队列、BFS模板、约瑟夫问题 | ⭐⭐ |
| `binary_tree.c` | 遍历（前/中/后/层序）、建树、BST | ⭐⭐⭐ |
| `heap.c` | 大/小顶堆、heapify、堆排序、Top-K | ⭐⭐⭐ |
| `hash_table.c` | 哈希函数、线性探测、链地址法、二次探测 | ⭐⭐⭐ |
| `graph.c` | DFS/BFS、Dijkstra、拓扑排序、并查集 | ⭐⭐⭐ |

### 📌 排序算法（8个文件）

| 算法 | 平均 | 最坏 | 空间 | 稳定 | 适用场景 |
|------|------|------|------|------|---------|
| 冒泡排序 | O(n²) | O(n²) | O(1) | ✅ | 教学、基本理解 |
| 选择排序 | O(n²) | O(n²) | O(1) | ❌ | 小规模数据 |
| 插入排序 | O(n²) | O(n²) | O(1) | ✅ | 接近有序数据 |
| 希尔排序 | O(n^1.3) | O(n²) | O(1) | ❌ | 中等规模数据 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | ✅ | 外部排序、链表排序 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ❌ | 大规模通用排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ❌ | Top-K、优先级队列 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | ✅ | 范围有限的整数 |

### 📌 查找算法（2个文件）

| 算法 | 时间复杂度 | 适用场景 |
|------|-----------|---------|
| 二分查找 | O(log n) | 有序数组、边界查找 |
| 插值查找 | O(log log n) | 均匀分布的数值数据 |

### 📌 高级算法（8个文件）

| 算法 | 题目 | 状态转移 |
|------|------|---------|
| 动态规划 | 0-1背包、完全背包 | dp[j]=max(dp[j],dp[j-w]+v) |
| 动态规划 | LIS（最长递增子序列） | dp[i]=1+max(dp[j]) |
| 动态规划 | 编辑距离 | dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+cost) |
| 贪心 | 哈夫曼编码 | 选两个最小权值合并 |
| 贪心 | 活动选择 | 选结束时间最早的活动 |
| 分治 | 归并排序进阶 | 逆序对数统计 |
| 回溯 | N皇后 | isValid(row,col)剪枝 |
| 回溯 | 子集和/全排列 | 选/不选、used[]去重 |

### 📌 设计模式（15个文件）

**创建型（4个）：** 单例、工厂方法、抽象工厂、建造者

**结构型（5个）：** 适配器、装饰器、代理、组合、桥接

**行为型（6个）：** 策略、观察者、命令、模板方法、状态、迭代器

## 🔧 编译与运行

```bash
# 编译单个文件
gcc -o output source.c

# 编译并运行
gcc -o test source.c && ./test

# 排序算法示例
gcc -o bubble_sort algorithm/sort/bubble_sort.c && ./bubble_sort

# 数据结构示例
gcc -o linked_list datastructure/linked_list.c && ./linked_list

# 设计模式示例
gcc -o singleton pattern/creational/singleton.c -lpthread && ./singleton
```

## 📚 使用说明

1. **VSCode 打开项目根目录**：`code c-exam-project/`
2. **安装 C 扩展**：Microsoft C/C++ 插件（必装）
3. **每个 `.c` 文件可独立编译运行**，建议先运行查看输出，再阅读代码
4. **考试复习**：按模块逐一阅读，重点关注注释中的【考试填空位置】

## ⚠️ 考试注意事项

- 循环队列的**队空/队满判断**是高频填空题
- 快排的**基准选择**和**最坏情况**是高频分析题
- 二分查找**必须用** `low + (high-low)/2` 防止溢出
- 动态规划的**状态转移方程**必须能独立写出
- 设计模式注意**每个模式的关键词**：代理（控制访问）、装饰器（动态增强）、观察者（一对多通知）

## 📄 License

MIT License - 可自由使用于学习与教学