UNSW COMP2521 Data Structures and Algorithms 是 CS 专业大二的核心课程，也是大多数学生第一次系统接触 C 语言指针操作和算法复杂度分析的课程。
很多同学在 COMP1511 里学过 C，却在 COMP2521 的链表和树操作上翻车——因为这门课考察的不只是"写出来"，而是"写对 + 写高效 + 能证明为什么高效"。
COMP2521 课程结构
| 组成部分 | 权重 | 说明 |
|---|---|---|
| Assignment 1（链表/树实现） | 20–25% | C 实现，Autotest 评分 |
| Assignment 2（图算法） | 20–25% | C 实现，BFS/DFS/Dijkstra |
| Lab Exercises | 10% | 每周 Lab，当场或次日提交 |
| Final Exam | 40–45% | 笔试，代码题+分析题 |
第一部分：C 指针与内存管理——最大难点
1.1 指针基础回顾
int x = 10;
int *p = &x; // p 存储 x 的地址
printf("%d\n", x); // 10（变量值）
printf("%p\n", p); // x 的内存地址（如 0x7fff5...)
printf("%d\n", *p); // 10（解引用，访问地址处的值）
*p = 20; // 通过指针修改 x 的值
printf("%d\n", x); // 20
1.2 动态内存分配（malloc / free）
// ✅ 正确的动态分配模式
int *arr = malloc(n * sizeof(int));
if (arr == NULL) {
fprintf(stderr, "malloc failed\n");
exit(1);
}
// 使用数组...
arr[0] = 1;
arr[1] = 2;
// 用完必须 free！否则内存泄漏
free(arr);
arr = NULL; // 好习惯：free 后置 NULL，防止野指针
1.3 链表节点的定义与基本操作
typedef struct node {
int value;
struct node *next;
} Node;
// 创建新节点
Node *newNode(int val) {
Node *n = malloc(sizeof(Node));
assert(n != NULL);
n->value = val;
n->next = NULL;
return n;
}
// 在链表头部插入
Node *insertFront(Node *head, int val) {
Node *n = newNode(val);
n->next = head;
return n; // 返回新的头节点
}
最常见的 Segmentation Fault 原因：
- 对 NULL 指针解引用（
(*null_ptr).field） - free 之后继续访问（野指针）
- 递归没有 base case，栈溢出
1.4 调试工具
# 使用 valgrind 检测内存问题（Linux/CSE 服务器）
valgrind --leak-check=full ./your_program
# 用 AddressSanitizer 编译（更快）
gcc -fsanitize=address -g -o program program.c
./program
第二部分：树（Trees）
2.1 二叉搜索树（BST）基本操作
BST 性质：对任意节点，左子树所有值 < 节点值 < 右子树所有值。
typedef struct bstNode {
int value;
struct bstNode *left;
struct bstNode *right;
} BST;
// BST 插入（递归）
BST *bstInsert(BST *t, int val) {
if (t == NULL) {
// 创建新节点
BST *new = malloc(sizeof(BST));
new->value = val;
new->left = new->right = NULL;
return new;
}
if (val < t->value)
t->left = bstInsert(t->left, val);
else if (val > t->value)
t->right = bstInsert(t->right, val);
// val == t->value：不插入重复值
return t;
}
// 中序遍历（Inorder）→ 输出排好序的结果
void inorder(BST *t) {
if (t == NULL) return;
inorder(t->left);
printf("%d ", t->value);
inorder(t->right);
}
2.2 AVL 树——自平衡 BST
AVL 树通过旋转保持平衡（任意节点左右子树高度差 ≤ 1）。
旋转类型：
- Left Rotation（右子树过重）
- Right Rotation（左子树过重）
- Left-Right Rotation（左-右双旋）
- Right-Left Rotation（右-左双旋）
高度计算：
int height(BST *t) {
if (t == NULL) return -1;
int lh = height(t->left);
int rh = height(t->right);
return 1 + (lh > rh ? lh : rh);
}
int balanceFactor(BST *t) {
return height(t->left) - height(t->right);
}
考试关键：会判断什么时候需要旋转，以及旋转后树的结构——手画一遍比记公式有效。
第三部分：图算法
3.1 图的两种表示
// 邻接矩阵（稠密图，V² 空间）
int adj[MAX_V][MAX_V] = {0};
adj[u][v] = 1; // 无向图：adj[v][u] = 1 也要设
// 邻接链表（稀疏图，更省空间）
typedef struct adjNode {
int dest;
struct adjNode *next;
} AdjNode;
AdjNode *graph[MAX_V]; // graph[v] 是 v 的邻居链表
3.2 BFS（广度优先搜索）
BFS 用于：最短路径（无权图）、层级遍历
void bfs(int graph[][MAX_V], int n, int start) {
int visited[MAX_V] = {0};
int queue[MAX_V];
int front = 0, rear = 0;
queue[rear++] = start;
visited[start] = 1;
while (front < rear) {
int v = queue[front++];
printf("%d ", v);
for (int u = 0; u < n; u++) {
if (graph[v][u] && !visited[u]) {
queue[rear++] = u;
visited[u] = 1;
}
}
}
}
3.3 DFS（深度优先搜索）
DFS 用于：连通性检测、拓扑排序、环检测
void dfs(int graph[][MAX_V], int visited[], int v) {
visited[v] = 1;
printf("%d ", v);
for (int u = 0; u < MAX_V; u++) {
if (graph[v][u] && !visited[u]) {
dfs(graph, visited, u);
}
}
}
3.4 Dijkstra 最短路径
// 简化版 Dijkstra（邻接矩阵，适合考试）
void dijkstra(int graph[][MAX_V], int n, int src) {
int dist[MAX_V], visited[MAX_V];
for (int i = 0; i < n; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[src] = 0;
for (int count = 0; count < n - 1; count++) {
// 找未访问中距离最小的节点 u
int u = -1;
for (int v = 0; v < n; v++)
if (!visited[v] && (u == -1 || dist[v] < dist[u]))
u = v;
visited[u] = 1;
// 更新邻居距离
for (int v = 0; v < n; v++) {
if (graph[u][v] && !visited[v] &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
第四部分：复杂度分析
4.1 常见操作时间复杂度
| 数据结构 | 查找 | 插入 | 删除 |
|---|---|---|---|
| 数组（有序） | O(log n) | O(n) | O(n) |
| 链表 | O(n) | O(1)（头部） | O(n) |
| BST（平均） | O(log n) | O(log n) | O(log n) |
| BST（最差/退化） | O(n) | O(n) | O(n) |
| AVL 树 | O(log n) | O(log n) | O(log n) |
| 哈希表（平均） | O(1) | O(1) | O(1) |
4.2 排序算法复杂度
| 算法 | Best | Average | Worst | 稳定性 |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | ✅ |
| Insertion Sort | O(n) | O(n²) | O(n²) | ✅ |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | ✅ |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | ❌ |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | ❌ |
4.3 主定理（Master Theorem）
对于递推 T(n) = aT(n/b) + f(n)：
- 若 f(n) = O(n^log_b(a) - ε)：T(n) = Θ(n^log_b(a))
- 若 f(n) = Θ(n^log_b(a))：T(n) = Θ(n^log_b(a) · log n)
- 若 f(n) = Ω(n^log_b(a) + ε)：T(n) = Θ(f(n))
实际例子：
- 归并排序：T(n) = 2T(n/2) + O(n) → a=2, b=2, log₂2=1 → Case 2 → O(n log n)
- 二分查找：T(n) = T(n/2) + O(1) → a=1, b=2, log₂1=0 → Case 2 → O(log n)
COMP2521 期末考试题型
| 题型 | 分值比例 | 备考重点 |
|---|---|---|
| 手写 C 代码（链表/树操作） | 30–40% | 熟练写 BST 插入/删除 |
| 图算法（BFS/DFS/Dijkstra 追踪） | 20–25% | 手画执行过程 |
| 复杂度分析 | 15–20% | Big-O 推导+主定理 |
| 概念问答（为什么用AVL而非BST） | 15% | 优缺点对比 |
考试技巧：图算法题通常要求你手工追踪执行过程（画出每步的状态），而不是写代码——这比写代码更考察理解。
需要辅导？
COMP2521 的 Assignment 调试（Segmentation Fault 定位）和期末考前的算法追踪练习是最多同学需要帮助的环节。我们的 UNSW CS 导师大多数都考过 COMP2521，熟悉 Autotest 的评分规则。
相关资源：
