数据结构高频考点全解析：从链表到图的代码实战与复习指南

1. 数据结构到底在考什么：一张全景图帮你定优先级

先说实话，数据结构这门课，大部分人在学的时候是懵的。学的时候觉得每个知识点都像一座孤岛，链表是链表、树是树、图是图，好像谁也挨不上谁。等到期末复习、考研冲刺或者校招面试刷题的时候，才突然发现真正高频的考点其实高度集中，而且它们背后的逻辑是能串成一条线的。

这篇文章不是教材的复读机，而是把数据结构里最核心的高频考点拎出来，配上可以直接抄走的代码示例和踩坑心得。不管你是期末复习、准备408考研，还是秋招面试前突击，下面这一套东西吃透，应付绝大多数场景足够了。

先说清楚一个底层认知：数据结构研究的是"数据怎么组织、怎么存、怎么操作"。细分下来就是三件事——逻辑结构（数据元素之间什么关系）、存储结构（在内存里怎么摆）、基本操作（增删改查排序查找）。你会发现，所有的数据结构，本质都是在回答这三个问题中的某一个。

接下来我从学习顺序和考点优先级两个维度，把整个知识体系摊开来看。

我的建议是：先线性后非线性，先简单后复杂。数组链表、栈队列这些线性结构搞不透，树和图基本学不踏实，因为树的遍历本质是用栈/队列的思想，图的遍历本质是树的遍历的推广。

另外提醒一句，语法层面的东西不要死抠。数据结构考的是思路，不是语言特性。下面的代码示例我统一用C语言写，因为408和严蔚敏教材就是C语言为底子，但你在面试中用Java、Python写同一个思路，完全没问题。

2. 链表与线性表：手撕代码的第一道坎，也是送分题

链表为什么是面试常客？因为它在内存里是零散存储的，全靠指针串起来，这就天然容易出错。一个next指错，整个链就断了。但链表题目的套路又是高度模板化的，练熟了就是送分题。

2.1 反转链表：迭代和递归两个版本都必须会

反转链表是链表题里最经典的一道，几乎每个面试官都会问。我先贴迭代版本，这是最直观的思路：用三个指针，pre、cur、next，把每个节点的next指向前一个节点。

struct ListNode { int val; struct ListNode *next; }; // 迭代反转 struct ListNode* reverseList_iter(struct ListNode* head) { struct ListNode *pre = NULL; struct ListNode *cur = head; while (cur != NULL) { struct ListNode *next = cur->next; // 保存下一个节点 cur->next = pre; // 反转指针 pre = cur; // pre 后移 cur = next; // cur 后移 } return pre; // 新的头节点 } // 递归反转 struct ListNode* reverseList_rec(struct ListNode* head) { if (head == NULL || head->next == NULL) { return head; } struct ListNode *newHead = reverseList_rec(head->next); head->next->next = head; // 把当前节点的下一个节点指向当前节点 head->next = NULL; return newHead; }

递归版本第一次看可能会绕。拆开看的话，它的逻辑是：先反转后续的链表，得到newHead，然后让当前节点的下一个节点（head->next）的next指向当前节点。比如1 -> 2 -> 3 -> NULL，先反转2 -> 3得到3 -> 2，然后让2->next = 1，1->next = NULL，最终就是3 -> 2 -> 1。边界条件就是空链表和单节点链表，直接返回本身。

2.2 快慢指针：判环、找中间节点、找倒数第k个，一个模板全解决

快慢指针的思想特别简单：一个指针每次走两步（快指针），一个指针每次走一步（慢指针）。如果链表里有环，快慢指针最终会在环里相遇；如果想找中间节点，快指针到终点时慢指针刚好在中间。

// 判断链表是否有环：快慢指针相遇则说明有环 int hasCycle(struct ListNode *head) { struct ListNode *fast = head; struct ListNode *slow = head; while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; if (fast == slow) { return 1; // 有环 } } return 0; // 无环 } // 找中间节点：快指针到终点时，慢指针就是中间位置 struct ListNode* findMiddle(struct ListNode* head) { struct ListNode *fast = head; struct ListNode *slow = head; while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; } return slow; }

这里的核心是说，为什么快指针每次走两步而不是三步四步？两个原因。一是时间复杂度，快慢指针都在O(n)内完成，步幅不影响量级；二是步幅太大可能跳过某些判断条件，而且快指针可能直接空指针越界，要处理的边界条件变多。两步是最自然的折中。

2.3 有序链表的合并：注意虚拟头节点的用法

合并两个有序链表，有个小技巧特别值得说一下：虚拟头节点（dummy node）。它的作用是不用单独处理"谁是新链表的头节点"这个问题，最后只需要返回dummy->next即可。

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { struct ListNode dummy; // 虚拟头节点，栈上分配，不用手动free struct ListNode *tail = &dummy; dummy.next = NULL; while (l1 != NULL && l2 != NULL) { if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } // 把剩余部分接上 tail->next = (l1 != NULL) ? l1 : l2; return dummy.next; }

有一个小坑需要提醒：如果虚拟头节点是用malloc动态分配的，记得在返回前free掉；像上面这样在栈上定义一个dummy变量就不用管，函数结束自动释放。这个细节很多人在面试的时候会忽略，导致虽然代码逻辑对，但是被面试官追问内存管理时露怯。

2.4 链表实操的几个常见坑

• 空指针检查一定要做。访问cur->next之前，先确认cur不是NULL。比如找倒数第k个节点，k的合法性要判断。
• 反转链表时，中间变量next用来保存cur的下一个节点，这个变量不能省，否则反转完cur->next指向pre后，原来后面的节点就找不到了。
• 循环链表题目里，如果题目没有明说是否有环，先想清楚快指针是否会野指针越界。

我自己的经验是：链表题的边界条件，无外乎"空链表""单节点""两个节点""链表有环""k值越界"这几种。每次写完代码，先把这几种情况在心里过一遍，基本能挡住90%的bug。

3. 栈与队列：括号匹配、单调栈和双栈模拟一个都别落下

栈和队列其实是线性表的两种受限版本。栈只能在栈顶插入删除（后进先出），队列只能队尾插入队头删除（先进先出）。说起来简单，但它们在算法题里非常能打。

3.1 括号匹配：用数组模拟栈，比调用库函数更稳

括号匹配是栈最经典的应用。遇到左括号入栈，遇到右括号出栈检查是否匹配。

#include <stdio.h> #include <string.h> // 用数组模拟栈 int isValid(char *s) { int len = strlen(s); char stack[len]; int top = -1; // 栈空标志 for (int i = 0; i < len; i++) { if (s[i] == '(' || s[i] == '[' || s[i] == '{') { stack[++top] = s[i]; } else { if (top == -1) return 0; // 没有左括号匹配，非法 char left = stack[top--]; if (!((left == '(' && s[i] == ')') || (left == '[' && s[i] == ']') || (left == '{' && s[i] == '}'))) { return 0; // 类型不匹配 } } } return top == -1; // 栈空才合法 }

为什么用数组模拟栈而不是直接调用系统栈或者标准库？因为在很多笔试平台、考研手写代码的场景下，你可能没有完整的标准库可用，而且数组模拟栈是数据结构课的基础功，考察的就是你能不能手写一个栈。top从-1开始，入栈是stack[++top] = x，出栈是x = stack[top--]，这两个操作写熟了，数组栈就彻底拿下了。

3.2 单调栈：下一个更大元素的万能套路

单调栈是个进阶内容，但理解之后特别实用。它解决的核心问题一般是：数组里每个元素的下一个更大（或更小）的元素是谁，或者每个元素左边第一个比它大（或小）的元素是谁。

以"每日温度"为例，给定一个每日温度的数组，返回一个数组，每个位置表示要等几天才能等到更暖和的温度。这是典型的找下一个更大元素的距离。

#include <stdlib.h> // temperatures: 温度数组 // returnSize: 返回数组长度 int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) { *returnSize = temperaturesSize; int* result = (int*)calloc(temperaturesSize, sizeof(int)); int* stack = (int*)malloc(temperaturesSize * sizeof(int)); // 栈里存下标 int top = -1; for (int i = 0; i < temperaturesSize; i++) { // 栈非空且当前温度大于栈顶下标对应的温度 while (top >= 0 && temperatures[i] > temperatures[stack[top]]) { int idx = stack[top--]; result[idx] = i - idx; // 天数差 } stack[++top] = i; // 当前下标入栈 } // 栈里剩余元素说明后面没有更高温度，result[]已经是0，不用处理 free(stack); return result; }

单调栈的精髓在于"单调"。栈里存的下标，对应的温度是严格递减的（从栈底到栈顶）。每来一个新元素，就把栈里所有小于它的元素弹出，因为对于那些元素来说，当前元素就是它们的"下一个更大元素"。我当年学这个套路的时候，最大的卡点是搞不清栈里应该存值还是存下标——答案是存下标，因为你要算距离差，没有下标这个信息就算不出来。

3.3 用两个栈实现队列：经典中的经典

这道题面试频率很高，思路不复杂但值得动手写一遍：一个栈in负责入队，一个栈out负责出队。入队直接压入in；出队时如果out为空，把in里所有元素倒进out（逆序），然后从out弹栈。

typedef struct { int in[100]; int inTop; int out[100]; int outTop; } MyQueue; MyQueue* myQueueCreate() { MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue)); q->inTop = -1; q->outTop = -1; return q; } void myQueuePush(MyQueue* obj, int x) { obj->in[++obj->inTop] = x; } // 确保out栈不为空后弹出 int myQueuePop(MyQueue* obj) { if (obj->outTop == -1) { while (obj->inTop >= 0) { obj->out[++obj->outTop] = obj->in[obj->inTop--]; } } return obj->out[obj->outTop--]; } int myQueuePeek(MyQueue* obj) { if (obj->outTop == -1) { while (obj->inTop >= 0) { obj->out[++obj->outTop] = obj->in[obj->inTop--]; } } return obj->out[obj->outTop]; }

这个结构里有个关键优化思路叫"懒搬运"：不是每次出队都把in里的元素倒腾到out，而是等到out栈空了再一次性搬运。这样摊还下来，每个元素最多被移动两次（入栈一次、倒腾时出栈入栈各一次），均摊时间复杂度是O(1)。这种思路在后面的很多题目里都能复用。

4. 二叉树：递归、层序、BST和最近公共祖先，刷题主力区

二叉树在整个数据结构里地位极高。树的题90%都能用递归解决，而递归的关键是想清楚三件事：终止条件是什么？单层递归要做什么？返回值是什么？这三件事想明白，大部分树题就是一马平川。

4.1 二叉树的存储结构与三种递归遍历

先写一个最基础的结构体定义，然后前、中、后序三种遍历的递归实现，代码极其简单，但你必须写到条件反射：

struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; // 前序遍历：根 -> 左 -> 右 void preorder(struct TreeNode* root) { if (root == NULL) return; printf("%d ", root->val); preorder(root->left); preorder(root->right); } // 中序遍历：左 -> 根 -> 右 void inorder(struct TreeNode* root) { if (root == NULL) return; inorder(root->left); printf("%d ", root->val); inorder(root->right); } // 后序遍历：左 -> 右 -> 根 void postorder(struct TreeNode* root) { if (root == NULL) return; postorder(root->left); postorder(root->right); printf("%d ", root->val); }

这里有一个很实用的记忆方法：前中后指的是根节点的位置。前序根在最前面，中序根在中间，后序根在最后。剩下的左和右的顺序永远是先左后右。

还有个重要的性质：中序遍历一棵二叉搜索树得到的是有序序列，这是后面很多BST（二叉搜索树）题目的核心依据。

4.2 非递归中序遍历：用栈模拟递归

递归虽然简洁，但面试官经常让你用非递归写一遍，考察你对栈的理解程度。非递归中序遍历的核心思想是：沿着左子树一路入栈，直到左子树为空，弹出栈顶节点访问，然后转到它的右子树继续。

#include <stdio.h> #include <stdlib.h> // 非递归中序遍历 void inorderIterative(struct TreeNode* root) { struct TreeNode* stack[100]; int top = -1; struct TreeNode* cur = root; while (cur != NULL || top >= 0) { // 一路向左，全部入栈 while (cur != NULL) { stack[++top] = cur; cur = cur->left; } // 弹出栈顶并访问 cur = stack[top--]; printf("%d ", cur->val); // 转到右子树 cur = cur->right; } }

这里最难理解的就是循环终止条件cur != NULL || top >= 0。意思是：当前节点还存在，或者栈里还有节点没访问完，就继续循环。很多初学的人只写了top >= 0，导致根节点访问完就退出，右子树还没遍历。这个小细节我踩过坑，记忆特别深。

层序遍历（BFS）也要会，它依赖队列，用数组模拟队列或者直接用库里的队列都行。层序的思路是：根节点入队，每次出队一个节点，就把它的左右孩子入队，直到队列为空。

4.3 二叉搜索树：查找、插入和删除

BST的核心性质：左子树所有节点值小于根节点，右子树所有节点值大于根节点，且左右子树各自也是BST。查找和插入的代码比较好写，删除稍微复杂一点，分三种情况。

// BST查找 struct TreeNode* searchBST(struct TreeNode* root, int val) { if (root == NULL || root->val == val) { return root; } if (val < root->val) { return searchBST(root->left, val); } else { return searchBST(root->right, val); } } // BST插入（递归） struct TreeNode* insertIntoBST(struct TreeNode* root, int val) { if (root == NULL) { struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); node->val = val; node->left = node->right = NULL; return node; } if (val < root->val) { root->left = insertIntoBST(root->left, val); } else if (val > root->val) { root->right = insertIntoBST(root->right, val); } return root; }

删除节点时最难的情况是：要删除的节点既有左子树又有右子树。惯用的做法是找到右子树中的最小节点（或左子树中的最大节点），用它替换当前节点的值，然后去右子树中删除那个最小节点。这样能保证删除后仍然是BST。

4.4 最近公共祖先（LCA）：递归的漂亮体现

给定一个BST和两个节点p、q，找它们的最近公共祖先。BST的性质让这道题变得很简单：如果p和q都小于root，则LCA一定在左子树；如果都大于root，则在右子树；否则root就是分岔点。

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) { if (root == NULL) return NULL; // 两个目标值都在左子树 if (p->val < root->val && q->val < root->val) { return lowestCommonAncestor(root->left, p, q); } // 都在右子树 if (p->val > root->val && q->val > root->val) { return lowestCommonAncestor(root->right, p, q); } // 一个在左一个在右，或root就是p/q，那么root就是LCA return root; }

不是BST的普通二叉树的LCA稍微复杂一点，核心思路是：递归在左子树和右子树里找p和q，如果两边都找到了，说明当前节点是分岔点，返回当前节点；如果只在一侧找到，返回那一侧的结果；都没找到返回NULL。这个套路务必掌握，面试常考。

5. 堆：建堆为什么是O(n)，TopK问题怎么解

堆在408和面试里都是重点，但很多人对它敬而远之，因为涉及到down和up操作，代码比较绕。其实堆的本质就是用数组表示的完全二叉树，父节点一定大于（大根堆）或小于（小根堆）它的子节点。

5.1 堆的存储与核心操作

假设根节点在数组下标0开始，那么节点i的左孩子下标是2*i+1，右孩子是2*i+2，父节点是(i-1)/2。这个映射关系是堆的基础。

down操作（下沉）是堆的灵魂。以大根堆为例，如果某个节点不满足父大于子的性质，就把它和较大的子节点交换，然后继续向下调整。

// 大根堆下沉调整，n是堆的规模 void siftDown(int arr[], int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; siftDown(arr, n, largest); // 继续下沉 } }

建堆的代码也很简单：从最后一个非叶子节点开始，逐个执行siftDown。

void buildHeap(int arr[], int n) { // 最后一个非叶子节点下标是 n/2 - 1 for (int i = n / 2 - 1; i >= 0; i--) { siftDown(arr, n, i); } }

5.2 一个直觉解释：建堆为什么是O(n)

这是很多人困惑的地方。直觉上看，建堆要调整n/2个节点，每个节点最多下沉log n层，复杂度应该是O(n log n)才对，但严谨的结论是O(n)。

关键在于：越底层的节点数量越多，但它们下沉的距离越短。倒数第二层的节点有n/4个，每个最多下沉1层；倒数第三层有n/8个，每个最多下沉2层。总工作量是一个等差数列求和，最终收敛到O(n)。这个证明在408里是要求掌握的，面试里如果能说出来，绝对是加分项。

5.3 堆的两个高频应用：堆排序和TopK

堆排序的思路秒懂：建立大根堆，然后不断把堆顶（最大值）和末尾元素交换，堆规模减一，再对堆顶做siftDown，重复n-1次。

TopK问题更实用：从海量数据中找出最大的K个数。方法是维护一个大小为K的小根堆，遍历数据，如果当前元素大于堆顶（也就是K个数里最小的那个），就替换堆顶并下沉调整。这样遍历完，堆里的K个元素就是最大的K个。时间复杂度是O(n log K)，在K远小于n时非常高效。

我经常用这个例子给初学者讲，什么是数据结构的工程价值：如果数据量是1亿，想找最大的100个，全排序代价太高，小根堆方案只需要维护100个元素的堆，性能天差地别。

6. 排序算法：八大排序一张表背熟，快排归并堆排必须能手写

排序是数据结构里最"值钱"的一章，因为它在面试里出现频率极高。先看一张总表，把这八个排序算法的核心指标背熟。

6.1 快速排序：模板代码加上优化点

快排的核心是分治 + 分区（partition）。选一个基准值，把比基准小的放左边、大的放右边，然后递归处理两侧。下面是统一写法：

int partition(int arr[], int low, int high) { int pivot = arr[high]; // 选最后一个元素作为基准 int i = low - 1; // i 指向比基准小的最后一个位置 for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; // 交换 arr[i] 和 arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // 基准归位 int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; 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); } }

快排的优化有两招常被问。一个是三数取中：取low、mid、high三个位置的中间值作为基准，避免数组本身有序时每次分区极度不均匀，导致退化成O(n²)。另一个是小区间插入排序：当区间长度小于阈值（比如10~16）时，改用插入排序。插入排序在数据接近有序时效率极高，阈值以内的数据经过多轮快排已经基本有序，插入排序非常快。

6.2 归并排序：必须会写，且要会用它求逆序对

归并排序的思路也是分治：先递归排序左右两半，然后合并两个有序数组。合并过程需要额外的O(n)空间，这是它空间复杂度为O(n)的原因。

void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int 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) { if (L[i] <= R[j]) { arr[k++] = L[i++]; } else { arr[k++] = 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, right, mid + 1); // 这里故意写错一个参数，下面解释 merge(arr, left, mid, right); } }

等一下，上面这段mergeSort我是故意写错了一个参数——正确写法是mergeSort(arr, mid + 1, right)，不是mergeSort(arr, right, mid + 1)。写反参数会导致递归区间传错，程序直接栈溢出或结果全乱。这恰好是我当年踩过的一个坑：mergeSort的左半部分和右半部分调用，特别是右半部分的起始和结束位置，一定要对照着区间左闭右闭的性质来写，每次递归前先在纸上画一遍区间。

6.3 堆排序：结合上一章的siftDown直接写

堆排序的代码，建立在siftDown的基础上：

void heapSort(int arr[], int n) { buildHeap(arr, n); // 建大根堆 for (int i = n - 1; i > 0; i--) { // 堆顶（最大值）换到末尾 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; siftDown(arr, i, 0); // 堆规模变为i，从根节点下沉调整 } }

堆排序的排序过程结合图看特别清晰：每次把堆顶最大值放到数组尾部，尾部元素到了堆顶，然后下沉，再取下一个最大值。如此反复，数组从后往前逐渐有序。

稳定性是排序里常考的概念。稳定意味着相等元素的相对位置不改变。快排、选择排序、堆排序都是不稳定的，归并、插入、冒泡、基数排序是稳定的。判断依据就看"跨距离交换"是否发生——如果排序过程中存在长距离跳跃交换，稳定性就被破坏了。这个判断标准比死记硬背靠谱得多。

7. 图的DFS/BFS、拓扑排序和最短路径：从模板到应用

图是数据结构里"天花板"级别的章节，但也别怕，真题里考的无非就那几板斧：邻接表和邻接矩阵的存储、DFS/BFS遍历、拓扑排序、Dijkstra最短路径。把这些模板吃透，图的部分就能稳住。

7.1 邻接矩阵 vs 邻接表：怎么选

图的存储是图论的基础。邻接矩阵是一个二维数组，arr[i][j] = 1表示i到j有边；邻接表则是每个节点维护一个链表，只存与自己相连的节点编号。

面试里如果题目没有明确说明是稠密图还是稀疏图，默认情况下用邻接表更稳妥，因为空间开销小，遍历邻接点也高效。

7.2 DFS和BFS模板

DFS（深度优先）在树上就是前序遍历的思路，先访问当前节点，然后递归访问相邻节点。BFS（广度优先）依赖队列，一层一层往外扩。

#include <stdbool.h> #include <string.h> #define MAXN 100 // 邻接表节点 struct Edge { int to; struct Edge* next; }; struct Edge* head[MAXN]; // head[i] 指向节点i的第一个邻边 bool visited[MAXN]; // DFS void dfs(int u) { visited[u] = true; for (struct Edge* e = head[u]; e != NULL; e = e->next) { int v = e->to; if (!visited[v]) { dfs(v); } } } // BFS：用数组模拟队列 void bfs(int start, int n) { int queue[MAXN]; int front = 0, rear = 0; memset(visited, 0, sizeof(visited)); visited[start] = true; queue[rear++] = start; while (front < rear) { int u = queue[front++]; for (struct Edge* e = head[u]; e != NULL; e = e->next) { int v = e->to; if (!visited[v]) { visited[v] = true; queue[rear++] = v; } } } }

DFS天然适合搜索所有路径、判断连通性、求连通分量；BFS天然适合求无权图的最短路径，因为BFS第一次访问到某个节点的层数，就是该节点到起点的最短距离。这个性质在网格类题目里特别常用。

7.3 拓扑排序：Kahn算法

拓扑排序针对有向无环图（DAG），解决的问题是"谁先谁后"：比如课程安排中有些课有先修课，求一个合法的选课顺序。

void topologicalSort(int n) { int indegree[MAXN]; memset(indegree, 0, sizeof(indegree)); // 计算每个节点的入度 for (int u = 0; u < n; u++) { for (struct Edge* e = head[u]; e != NULL; e = e->next) { indegree[e->to]++; } } // 入度为0的节点入队 int queue[MAXN]; int front = 0, rear = 0; for (int i = 0; i < n; i++) { if (indegree[i] == 0) { queue[rear++] = i; } } int count = 0; while (front < rear) { int u = queue[front++]; printf("%d ", u); count++; for (struct Edge* e = head[u]; e != NULL; e = e->next) { int v = e->to; indegree[v]--; if (indegree[v] == 0) { queue[rear++] = v; } } } // 如果count < n，说明图中有环，不存在拓扑排序 if (count != n) { printf("图中存在环，无法完成拓扑排序\n"); } }

Kahn算法的核心是不断删除入度为0的节点，每删除一个节点，它指向的节点入度减一。最后如果所有节点都被删除，说明图是DAG；否则说明有环。拓扑排序的结果不唯一，因为可能有多个入度为0的节点，选择顺序不同导致结果不同。

7.4 Dijkstra最短路径：朴素的O(n²)版本必须会写

Dijkstra算法解决的是单源最短路径问题，前提是图中没有负权边。核心思想是贪心：每次从未确定最短距离的节点中选距离最小的，然后用它去松弛其他节点。

#define INF 0x3f3f3f3f // dist[i]表示起点到i的最短距离，初始化为INF int dist[MAXN]; bool used[MAXN]; void dijkstra(int start, int n) { memset(dist, 0x3f, sizeof(dist)); memset(used, 0, sizeof(used)); dist[start] = 0; for (int i = 0; i < n; i++) { // 找出未确定最短路径且dist最小的节点 int u = -1, minDist = INF; for (int j = 0; j < n; j++) { if (!used[j] && dist[j] < minDist) { minDist = dist[j]; u = j; } } if (u == -1) break; used[u] = true; // 用u松弛相邻节点 for (struct Edge* e = head[u]; e != NULL; e = e->next) { int v = e->to; if (!used[v] && dist[u] + 1 < dist[v]) { dist[v] = dist[u] + 1; } } } }

这里的边权我简化成了1，实际题目里每个Edge结构体要带一个weight字段，松弛的时候用dist[u] + weight。学过优先队列优化版本（堆优化O(E log V)）当然更好，但朴素版本是地基，408笔试和手写代码场景基本考这个。

8. 哈希表与查找：链地址法、开放寻址和工程里的实际选择

哈希表（散列表）是查找章节的重点。它能在平均O(1)时间内完成查找、插入和删除，靠的就是哈希函数把key映射到数组下标。但这个映射不是完美的，两个不同的key可能映射到同一个位置，这就是哈希冲突。

8.1 链地址法：最常用的冲突解决方案

链地址法就是每个哈希桶（bucket）后面挂一个链表，冲突的元素直接挂到同一个桶的链表后面。查找时先算出桶下标，再在链表里顺序查找。

#define TABLE_SIZE 100 typedef struct HashNode { int key; int value; struct HashNode* next; } HashNode; typedef struct { HashNode* buckets[TABLE_SIZE]; } HashMap; // 简单的哈希函数：取模 int hashFunc(int key) { // 负数处理：确保下标非负 return (key % TABLE_SIZE + TABLE_SIZE) % TABLE_SIZE; } void put(HashMap* map, int key, int value) { int index = hashFunc(key); HashNode* node = map->buckets[index]; while (node != NULL) { if (node->key == key) { node->value = value; // 更新值 return; } node = node->next; } // 头插法插入新节点 HashNode* newNode = (HashNode*)malloc(sizeof(HashNode)); newNode->key = key; newNode->value = value; newNode->next = map->buckets[index]; map->buckets[index] = newNode; } int get(HashMap* map, int key) { int index = hashFunc(key); HashNode* node = map->buckets[index]; while (node != NULL) { if (node->key == key) { return node->value; } node = node->next; } return -1; // 没找到 }

注意哈希函数里取模那里我加了两次TABLE_SIZE，这是为了处理key为负数的情况。C语言的取模运算对于负数返回负值，直接当下标会越界。这个细节如果你没处理，输入里有负key的时候程序会直接崩掉，属于面试中的隐藏红牌。

8.2 开放寻址法：线性探测

链地址法是"冲突了就在桶后面加节点"，开放寻址法是"冲突了就往后找空位置"。线性探测就是依次往后查，arr[(hash(key) + i) % size]，直到找到空位或者遇到目标key。这种方法不需要额外的链表节点，内存利用率更高，但删除元素比较麻烦——不能直接置空，否则会断掉探测链，通常被面试官追问时才会涉及。

8.3 负载因子和扩容：工程里为什么hashmap要"长大"

负载因子 = 元素个数 / 桶数量。负载因子越大，冲突越多，查找性能越差。工程实现里一般设定一个阈值（比如0.75），超过就触发扩容——重新分配一个更大的数组，把所有元素重新哈希到新数组里。

扩容看起来简单，其实代价很高，因为数组长度变了，哈希函数里的取模除数变了，所有元素的位置都可能变。这也是为什么很多语言实现里，HashMap扩容时性能会有一次明显的抖动。为什么扩容后要重新哈希而不是直接拷贝？因为哈希结果依赖数组大小，直接原样搬过去，查询时算出的下标对不上，数据就"丢了"。

哈希表的工程价值怎么强调都不过分：从数据库索引到缓存系统、从编译器符号表到编程语言本身的对象字典，到处都有它的影子。所以面试里问HashMap底层原理的频率极高，链地址法、负载因子、扩容、红黑树优化这几个关键词都要能讲明白。

9. 我的复习建议：学习顺序、手写代码的方法和面试表达

最后这一部分，分享一些个人经验。数据结构的学习，最忌讳的是"看懂了但写不出来"。看懂和能写之间差了至少十遍手写练习。我的亲身感受是，代码是唯一能检验你是否真的理解某个数据结构的方法——你能把反转链表完整写出来，说明你真的掌握了指针操作；你只能口头说"用三个指针"而写不出来，说明还是没到位。

第一，学习顺序不要乱。先吃透线性表，再啃栈和队列，然后是二叉树、堆、排序，最后是图和哈希。树这块要单独多花时间，因为它的递归思想贯穿后续几乎所有高级内容。图和排序是综合应用，前面的基础不牢，后面容易崩。

第二，核心代码要反复手写。我推荐大家把下面这一个清单里的算法，每个都写到"闭着眼睛能写出来"的程度，至少写五遍：链表反转、快慢指针判环、括号匹配、二叉树三种递归遍历、非递归中序遍历、BST插入和删除、堆的下沉和堆排序、快排的partition、归并排序的merge、拓扑排序的Kahn算法、Dijkstra朴素版、链地址法哈希表。这个清单基本覆盖了笔试手写代码的80%考题。

第三，写代码之前先开口说思路。面试官通常更看重你的思维过程。我的习惯是先说：这个问题可以用什么数据结构解决，时间复杂度和空间复杂度大概是怎样的，然后写代码。写的时候边写边说，每一步在干什么。万一中间写错了，思路是对的，面试官依然会给分。

第四，故意在草稿纸上画图。链表题画链表，树题画树，图题画图。画图不是为了好看，是为了防止指针操作漏掉边界。画一遍，每个指针指向哪里一目了然，空指针、环、头节点这些坑都能提前规避。

最后再分享一个查漏补缺的小技巧：拿到一个数据结构知识点，先问自己三个问题——它解决什么问题？它比替代方案好在哪？它的短板和代价是什么？比如链表对比数组，好在哪里（插入删除O(1)），坏在哪里（随机访问O(n)）。答得上这三个问题，说明这个知识点你是真的理解了，而不是背下来的。

数据结构这门课，说难也难，说容易也容易。难是因为它要求你同时具备抽象思维和代码落地能力；容易是因为高频考点就那么集中，核心代码就那么几段。把上面这些扎实过一遍，不管是期末、考研还是面试，在这个方向的底气都会完全不一样。