哈工大《数据结构》44讲：从链表到图与排序，系统提升编码能力

很多人在入门数据结构时会遇到一个非常典型的问题书看了概念也背了一到写代码就卡住。或者说链表能写出来但遇到“如何用栈实现浏览器的前进后退”“如何用队列做任务调度”“如何判断一棵二叉树是不是平衡树”这类实际问题时脑子里一片空白。这不是因为你不够努力而是因为数据结构本质上不是一门“背诵课”而是一门“建模课”和“工程课”。它的核心不是记住哪种结构有几个指针、每种排序的时间复杂度是多少而是在面对一个问题时能够判断出它属于哪类结构、应该用什么样的组织方式去存储和访问数据、在时间和空间之间做怎样的取舍。哈尔滨工业大学的《数据结构》44讲课程正是按照这个逻辑组织起来的。它用线性表、树、图、查找与排序这五大模块把计算机科学里最常遇到的数据组织问题完整地串了一遍。这篇文章不会去罗列课程目录而是想从一个更实际的视角出发44讲到底在讲什么、每部分学到什么程度才算真正掌握以及如何把这门课的知识转化成实际编码能力。1. 为什么数据结构值得花一整门课去啃数据结构的重要性几乎所有开发者都听过但它真正解决的问题往往被低估了。程序的核心是“输入-处理-输出”而处理的前提是数据能够被组织起来。组织方式不同程序的性能表现会天差地别。举个很简单的例子在100万个元素里查找一个值用无序数组从头遍历平均需要50万次比较用哈希表平均只需要常数次操作用有序数组加二分查找大约20次比较就能完成。同一个问题因为存储结构不同性能差了上万倍。数据结构要训练的就是这种能力在动手写代码之前先想清楚数据之间的关系和操作模式然后选择最合适的存储与访问方式。哈工大这门44讲的课程以C语言为主要实现语言这一点非常关键。很多人觉得C语言麻烦没有现代语言的自动内存管理但恰恰是这种贴近底层的实现方式能把链表指针的指向、树的递归回退、图的邻接表遍历这些本质机理展现清楚。用Python或Java写链表很多内存细节被隐藏了而用C语言写一遍你才会真正理解“指针就是地址”“递归就是栈帧的压入和弹出”这些以后写任何语言都用得上的底层认知。从课程结构上看44讲对应的是计算机专业最经典的五大知识模块模块核心内容典型应用线性表顺序表、链表、栈、队列浏览记录、任务队列、表达式求值树二叉树、遍历、哈夫曼树、平衡树文件系统、编译器语法树、数据库索引图存储、遍历、最短路径、最小生成树地图导航、社交关系、网络路由查找顺序查找、二分查找、哈希查找、树表查找搜索引擎、缓存设计、数据库检索排序插入、交换、选择、归并、基数排序榜单、TopK、外部排序这五块内容不是孤立的它们是一层一层递进的。线性表是最基础的组织方式树解决的是层级关系图解决的是更复杂的网状关系查找和排序则是任何系统在实际运行中都会面对的通用操作。2. 线性表所有数据结构的地基线性表是数据结构里最基础、也最容易被轻视的模块。很多人觉得数组和链表太简单了背一背定义就跳过结果学到图和查找的时候才发现各种吃力。线性表是整个44讲的地基尤其是链表和栈它们的思想会贯穿树、图、查找、排序的每一个部分。2.1 顺序表和链表两种截然不同的取舍顺序表本质上就是数组它是连续的内存空间支持随机访问。这意味着a[3]可以直接通过首地址加偏移量算出来时间复杂度是O(1)。但插入和删除元素时需要移动大量数据平均是O(n)。链表则相反它是离散的内存节点通过指针串联。插入和删除只需要修改指针时间复杂度是O(1)但查找某个位置的元素必须从头遍历时间复杂度是O(n)。工程上怎么选这是很多面试和实际项目里经常出现的问题。如果操作模式是“读多写少”用顺序表因为随机访问快而且缓存命中率高。如果操作模式是“频繁插入删除但很少按位置随机读取”用链表更合适。但注意这里的“适合”是理论层面的。在实际工程中因为链表节点分散存储CPU缓存的局部性远不如数组所以很多现代库在高性能场景反而倾向于用连续内存加索引的方式来模拟链表的插入删除效果。用C语言实现单链表的插入节点核心代码是这样// 文件路径linkedlist.h #ifndef LINKEDLIST_H #define LINKEDLIST_H #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 在链表头部插入新节点 Node* insertAtHead(Node *head, int data) { Node *newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { return head; // 内存分配失败 } newNode-data data; newNode-next head; return newNode; } // 遍历链表并打印 void printList(Node *head) { Node *cur head; while (cur ! NULL) { printf(%d - , cur-data); cur cur-next; } printf(NULL\n); } #endif这段代码的关键在于理解指针的重新指向顺序。先让新节点的next指向原来的头节点再把头指针指向新节点。这两步如果反了链表就断了。很多初学者在写链表时出现段错误绝大多数是因为在“当前节点已经释放但还在用它的指针”或者“修改了某个节点的next导致后续节点无法访问”。2.2 栈和队列被限制了操作的表栈和队列本质上也是线性表只是操作受限栈只允许在栈顶插入和删除队列只允许在队尾插入、队头删除。这种限制反而带来了清晰的语义。栈最重要的特征是“后进先出”正好对应函数调用的过程函数A调用函数BB执行完必须先返回A才能继续往下走。系统就是用调用栈来实现这一过程的。这也是为什么递归可以改写为显式栈的非递归版本本质上是用自己的栈模拟系统调用栈。一个很实用的例子是用栈实现简易的括号匹配校验器// 文件路径stack_match.c #include stdio.h #include stdlib.h #include stdbool.h #define MAX_SIZE 100 typedef struct { char data[MAX_SIZE]; int top; } CharStack; void initStack(CharStack *s) { s-top -1; } bool isStackEmpty(CharStack *s) { return s-top -1; } bool push(CharStack *s, char c) { if (s-top MAX_SIZE - 1) { return false; } s-data[(s-top)] c; return true; } bool pop(CharStack *s, char *c) { if (isStackEmpty(s)) { return false; } *c s-data[(s-top)--]; return true; } bool isMatching(char left, char right) { return (left ( right )) || (left [ right ]) || (left { right }); } bool checkBrackets(const char *expr) { CharStack s; initStack(s); for (int i 0; expr[i] ! \0; i) { if (expr[i] ( || expr[i] [ || expr[i] {) { push(s, expr[i]); } else if (expr[i] ) || expr[i] ] || expr[i] }) { char topChar; if (!pop(s, topChar) || !isMatching(topChar, expr[i])) { return false; } } } return isStackEmpty(s); } int main() { const char *expr1 {[()()]()}; const char *expr2 {[(])}; printf(expr1: %s\n, checkBrackets(expr1) ? 匹配 : 不匹配); printf(expr2: %s\n, checkBrackets(expr2) ? 匹配 : 不匹配); return 0; }这个例子虽然简单但它体现了一个通用思路遇到“最近关联、延迟处理、反向输出”这类场景时先想想能不能用栈。队列的特征是“先进先出”它的典型场景是任务调度、消息队列、缓冲区以及树的层序遍历。理解队列时重点不在于“队尾进、队头出”这个动作而在于“公平性”的语义谁先到谁先被处理。3. 树递归思想最好的练兵场如果线性表是数据结构的地基那么树就是递归思想最好的载体。树为什么重要因为现实世界里的很多关系都是层级的公司的组织架构、计算机的文件目录、HTML的DOM结构、程序的函数调用关系本质上都可以抽象为树。3.1 二叉树的遍历前序、中序、后序、层序二叉树是树结构里最基础也最重要的一种。每个节点最多有两个孩子但正是这个“最多两个”的限制让二叉树可以用很简洁的递归逻辑来处理。二叉树的遍历分为深度优先的三种方式和广度优先的层序遍历。前序遍历先访问根节点再访问左子树最后访问右子树。中序遍历先访问左子树再访问根节点最后访问右子树。后序遍历先访问左子树再访问右子树最后访问根节点。先记住这个顺序然后理解为什么遍历顺序重要。一个很关键的规律一棵二叉搜索树的中序遍历结果是有序的。这个知识点在面试、算法题和实际工程里都会被反复使用。因为二叉搜索树的定义就是左子树所有节点小于根节点、右子树所有节点大于根节点所以中序遍历天然把节点从小到大输出。再看表达式树。表达式树是中缀表达式的树形表示操作符在内部节点操作数在叶子节点。前序遍历得到前缀表达式中序遍历得到中缀表达式后序遍历得到后缀表达式。编译器在解析表达式时会基于这种树形结构进行求值和优化。用C语言实现二叉树的中序遍历递归版本已经非常简洁// 文件路径binary_tree.c #include stdio.h #include stdlib.h typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; TreeNode* createNode(int val) { TreeNode *node (TreeNode*)malloc(sizeof(TreeNode)); node-val val; node-left NULL; node-right NULL; return node; } void inorderTraversal(TreeNode *root) { if (root NULL) { return; } inorderTraversal(root-left); printf(%d , root-val); inorderTraversal(root-right); } void preorderTraversal(TreeNode *root) { if (root NULL) { return; } printf(%d , root-val); preorderTraversal(root-left); preorderTraversal(root-right); } void postorderTraversal(TreeNode *root) { if (root NULL) { return; } postorderTraversal(root-left); postorderTraversal(root-right); printf(%d , root-val); } int main() { // 构建如下二叉树 // 1 // / \ // 2 3 // / \ // 4 5 TreeNode *root createNode(1); root-left createNode(2); root-right createNode(3); root-left-left createNode(4); root-left-right createNode(5); printf(前序遍历: ); preorderTraversal(root); printf(\n); printf(中序遍历: ); inorderTraversal(root); printf(\n); printf(后序遍历: ); postorderTraversal(root); printf(\n); return 0; }递归版本的代码很短但最需要想清楚的是“递归的终止条件”和“访问根节点的时机”。终止条件是节点为空访问时机决定了遍历类型。能够手写递归遍历之后还要掌握非递归版本。非递归的本质是用栈来模拟系统栈前序和中序相对简单后序要复杂一些因为需要判断右子树是否已经访问过。这一部分很多人会忽略但在笔试和面试里却经常出现。3.2 从二叉树到搜索树、堆和哈夫曼树二叉树是一种形状定义二叉搜索树BST是在形状定义的基础上增加了“节点大小关系”的约束。这个约束让查找、插入、删除都变成了有方向性的操作比根节点小往左走比根节点大往右走。但二叉搜索树有一个致命的问题如果按有序序列插入节点树会退化成链表查找复杂度退化为O(n)。这就是为什么会出现平衡树比如AVL树、红黑树。它们通过旋转操作来维持树的平衡让树的高度尽量接近log2(n)。哈夫曼树则是另一个方向的优化它关注的是“带权路径长度最短”。比如在文件压缩场景中出现频率高的字符用短编码出现频率低的字符用长编码整体编码长度就能最短。哈夫曼树的构造过程本身也是贪心算法的一个经典例子。学到这里时有个常见的体会是树这个模块越往后学递归和分治的思想就越重要。很多问题比如求二叉树的最大深度、判断两棵树是否相同、验证是否是二叉搜索树本质上都是“递归处理左右子树再把结果合并”。4. 图把复杂关系建模成结构树描述的是“一对多”的层级关系但现实里还有很多“多对多”的网状关系。朋友圈里的好友关系、城市之间的公路网络、网页之间的超链接这些都不是树能表达的需要用图。4.1 图的存储邻接矩阵与邻接表图的存储方式主要有两种。邻接矩阵用二维数组表示顶点之间的关系优点是判断两个顶点是否相邻只需要O(1)时间缺点是空间占用是O(n^2)对于稀疏图非常浪费。邻接表用“数组链表”的方式只存储实际存在的边空间上更省但判断两个顶点是否相邻需要遍历链表。这两种方式的取舍在工程里反映为如果图比较稠密用邻接矩阵如果图比较稀疏用邻接表。地图路径规划里的图通常都非常稀疏一个城市不会和所有其他城市都有直接道路所以实际应用中邻接表是主流。4.2 深度优先搜索与广度优先搜索图的遍历是整个图论算法的基础最核心的是深度优先搜索DFS和广度优先搜索BFS。DFS的思路是“一条路走到黑走不通再回头”对应到代码上就是递归或显式栈。BFS的思路是“从起点一层一层向外扩散”用队列实现。一个经典的BFS应用是求无权图中的最短路径也就是“最少经过几条边能到达目标顶点”。社交网络里的“好友推荐”和游戏里的“最短步数”都属于这类问题。用邻接表实现BFS核心代码结构如下// 文件路径graph_bfs.c #include stdio.h #include stdlib.h #include stdbool.h #define MAX_VERTICES 100 #define QUEUE_SIZE 100 typedef struct AdjNode { int vertex; struct AdjNode *next; } AdjNode; typedef struct Graph { AdjNode *adjLists[MAX_VERTICES]; int numVertices; } Graph; typedef struct { int items[QUEUE_SIZE]; int front; int rear; } Queue; void initGraph(Graph *graph, int vertices) { graph-numVertices vertices; for (int i 0; i vertices; i) { graph-adjLists[i] NULL; } } void addEdge(Graph *graph, int src, int dest) { AdjNode *newNode (AdjNode*)malloc(sizeof(AdjNode)); newNode-vertex dest; newNode-next graph-adjLists[src]; graph-adjLists[src] newNode; } void initQueue(Queue *q) { q-front -1; q-rear -1; } bool isQueueEmpty(Queue *q) { return q-front -1; } void enqueue(Queue *q, int value) { if (q-rear QUEUE_SIZE - 1) { return; } if (q-front -1) { q-front 0; } q-rear; q-items[q-rear] value; } int dequeue(Queue *q) { if (isQueueEmpty(q)) { return -1; } int item q-items[q-front]; q-front; if (q-front q-rear) { q-front -1; q-rear -1; } return item; } void bfs(Graph *graph, int startVertex) { bool visited[MAX_VERTICES] {false}; Queue q; initQueue(q); visited[startVertex] true; enqueue(q, startVertex); while (!isQueueEmpty(q)) { int current dequeue(q); printf(%d , current); AdjNode *adj graph-adjLists[current]; while (adj ! NULL) { if (!visited[adj-vertex]) { visited[adj-vertex] true; enqueue(q, adj-vertex); } adj adj-next; } } } int main() { Graph graph; initGraph(graph, 6); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 3); addEdge(graph, 1, 4); addEdge(graph, 2, 4); addEdge(graph, 3, 5); addEdge(graph, 4, 5); printf(从顶点0开始的BFS遍历: ); bfs(graph, 0); printf(\n); return 0; }这段代码的关键在于入队一个顶点后立刻标记为已访问而不是出队时才标记。这样做可以避免同一个顶点被多次入队。图这一章的内容远不止遍历还包括最短路径Dijkstra、Floyd、最小生成树Prim、Kruskal、拓扑排序和关键路径。但无论算法多么复杂它们都建立在DFS和BFS这两种遍历方式之上。先熟练掌握DFS和BFS的代码模板再套用到不同场景中学习曲线会平缓很多。5. 查找与排序性能优化绕不开的基本功查找和排序是数据结构里最贴近“工程实用”的两个模块。几乎任何业务系统都可以看作是“数据的增删改查”加上“结果的排序展示”。这两个模块的学习目标非常明确理解每种算法的原理能够分析时间复杂度和空间复杂度并且知道在什么场景下选什么算法。5.1 查找从二分查找、哈希表到树表查找查找问题本质上是在问“怎么在一堆数据里快速找到目标”。最简单的是顺序查找适合数据量小或者数据无序的场景时间复杂度O(n)。如果数据有序可以用二分查找时间复杂度降为O(logn)但前提是底层存储支持随机访问也就是数组。链表上做二分查找是很低效的。二分查找的代码实现虽然只有十几行但边界条件非常容易出错。看看这个正确的写法// 文件路径binary_search.c #include stdio.h int binarySearch(int arr[], int left, int right, int target) { while (left right) { int mid left (right - left) / 2; // 防止(leftright)溢出 if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return -1; // 未找到 } int main() { int arr[] {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; int n sizeof(arr) / sizeof(arr[0]); int target 7; int index binarySearch(arr, 0, n - 1, target); if (index ! -1) { printf(找到目标 %d下标为 %d\n, target, index); } else { printf(未找到目标 %d\n, target); } return 0; }要注意三点循环条件是left right而不是left rightmid的计算用left (right - left) / 2而不是(left right) / 2这样可以防止大整数溢出更新边界时是mid 1和mid - 1而不是mid否则可能死循环。哈希表散列表是另一种完全不同的查找方案它的思路是“通过关键字直接计算出存储位置”理想情况下时间复杂度是O(1)。哈希表最核心的问题是哈希冲突常见解决方案是开放定址法和链地址法。实际应用中多数语言的标准库实现采用的是链地址法的变体。C语言的课程里通常会要求手动实现哈希表这个过程能帮助理解散列函数设计、负载因子和扩容机制。树表查找则包括二叉搜索树、平衡二叉树和B树。B树和B树是数据库索引和文件系统的底层结构在大规模数据场景中非常关键。硬盘上的数据读写远比内存慢B树通过“多路”结构降低了树的高度从而减少了访问硬盘的次数。5.2 排序理解每一种算法背后的规律排序算法是数据结构课程里最“卷”的部分因为算法很多而且每种都有适用的场景和优缺点。初学者接触到的主要排序算法可以分为几类类别算法平均时间复杂度核心思想插入排序直接插入、希尔排序O(n^2)、O(n^1.3)把无序区元素插入到有序区交换排序冒泡排序、快速排序O(n^2)、O(nlogn)通过交换逆序元素完成排序选择排序简单选择、堆排序O(n^2)、O(nlogn)每次选最小/最大放到正确位置归并排序二路归并O(nlogn)分治合并两个有序序列基数排序分配式排序O(d*(nr))按位分配和收集这里要记住一个重要结论在基于比较的排序算法中时间复杂度的下限是O(nlogn)。这个结论适用于任何排序算法所以看到理论上比O(nlogn)更快的通用比较排序不用怀疑那一定不成立。快速排序是实际应用最广泛的排序算法之一它采用分治策略选择基准元素把序列分成“小于基准”和“大于等于基准”两部分然后递归处理。一个标准的快速排序实现如下// 文件路径quick_sort.c #include stdio.h 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); } } void printArray(int arr[], int size) { for (int i 0; i size; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {10, 7, 8, 9, 1, 5}; int n sizeof(arr) / sizeof(arr[0]); printf(排序前: ); printArray(arr, n); quickSort(arr, 0, n - 1); printf(排序后: ); printArray(arr, n); return 0; }快速排序的平均时间复杂度是O(nlogn)但在最坏情况下比如序列已经有序时会退化为O(n^2)。所以实际工程中通常会对基准选择做优化比如“三者取中法”或者随机选择基准减少退化的概率。这些排序算法的学习是有方法论的先按类别理解思想再写代码最后对比时间复杂度和空间复杂度。不要试图一次全部背下来而是要结合表格和代码逐类击破。6. 一套完整的综合实验把五大模块串起来在44讲的课程里实验题目通常不会只考单一知识点而是会把多个模块组合起来。很多同学在单独学每一章时都觉得自己会了一到综合实验就不知道从何下手。这里给出一个典型的综合任务设计思路以及它是如何串联线性表、树、图、查找和排序的。任务描述读入一组单词统计每个单词的出现频率然后按频率降序输出前K个高频单词。功能拆解如下子任务用到的数据结构/算法目的读入并切分单词线性表、字符串处理基础数据录入统计频率哈希表或二叉搜索树查找模块的实践按频率排序堆排序或快速排序排序模块的实践输出前K个堆/优先队列堆数据结构的进阶应用这个任务看起来简单但完整实现它你需要掌握哈希表的冲突处理、二叉树的插入和遍历、堆的构造与调整、排序算法的选择。把一个大的任务拆解成多个小的子任务然后为每个子任务选择合适的数据结构和算法这正是数据结构这门课真正的考核目标。如果有余力可以在这个任务上继续扩展用字符串的前缀树Trie来组织单词用哈夫曼编码来压缩结果文件。每扩展一步都会复习到一个新的知识点而且能直观感受到不同数据结构带来的性能差异。7. 常见误区与排查思路数据结构的学习过程中有一些高频问题这里整理一下避开这些坑能节省大量时间。问题现象可能原因排查方式解决方案链表操作时程序崩溃访问了NULL指针或已释放内存检查每次指针解引用前是否为NULL在插入/删除节点时先判断节点是否存在递归遍历树时栈溢出树深度太深或递归终止条件写错打印递归深度检查base case确认nodeNULL时返回对极端场景改用非递归二分查找死循环边界更新错误用最小用例走读使用left right循环更新为mid1或mid-1快速排序在有序数据上性能极慢选到了最差基准点打印每次选择的基准元素使用随机基准或三者取中哈希表查找效率严重下降冲突率过高负载因子过大统计链表平均长度扩容并重新散列或调整散列函数BFS结果和预期不一致顶点重复入队打印每次入队和出队的顶点入队时立刻标记visited图的最短路径结果错误边的权重处理有问题单步调试松弛操作检查初始化时是否把起点设为0其他点设为无穷大学习数据结构时还有一种常见的心理误区觉得非递归一定比递归高级于是强行把所有递归改成非递归。这个观念不对。递归的优势是代码简洁、语义清晰劣势是容易栈溢出而且函数调用有开销。实际项目的做法是深度不确定或可能很大的场景优先使用显式栈的非递归深度可控、代码可读性优先的场景用递归没有问题。还有不少人会陷入“算法题刷得越多越好”的误区忽略了把原理吃透。数据结构这门课的核心不是题库训练而是建立“抽象的结构感”看到一个需求能在脑海里浮现出它对应的结构形态和操作模型。8. 学习路径与实战建议回到开头的问题哈工大这套44讲的课程怎么用才能发挥最大价值第一遍学习建议跟着视频课的顺序走线性表、栈、队列、树、图、查找、排序保证不跳章节。每个模块听完后一定要动手写代码。数据结构是工科课不是文科课光看视频和书是绝对不够的。书上的伪代码只是思路用C语言完整写出来编译运行通过才是真正的掌握。第二遍学习建议“倒着学”。先看查找和排序遇到不懂的结构再回看前面的章节。比如学到哈希表发现不理解“链地址法”就回到链表那一节补一补。这种逆向方式能让你带着问题去学效率更高。同时要配合经典的《数据结构C语言版》教材。视频课和教材之间是互补关系视频课帮你理解思路教材提供更严谨的定义和更完整的代码实现。很多高校用的是严蔚敏老师的版本如果觉得教材代码抽象可以配合其他讲解更细致的资料。关于刷题推荐在课程进行到一半时再开始。学完线性表和树之后就可以在在线评测系统上练习以下类型的题目链表反转、括号匹配、二叉树遍历、二叉树最大深度、图的BFS/DFS模板题。这些题目能直接巩固课程知识同时为以后算法面试打基础。每道题做完后不要只看通过与否要追问自己这个解法用了什么数据结构为什么要这样选时间复杂度是多少还能不能优化从更长的时间维度看数据结构不是学一遍就结束的。工作几年后你会发现数据库的B树、操作系统里的LRU缓存淘汰、网络协议里的滑动窗口底层都是你在这门课里学过的结构。第二遍、第三遍学习时能读懂更多细节也更能体会到“数据结构是程序设计的基石”这句话的分量。9. 课程重点脉络速查把44讲的内容浓缩成一张速查表方便复习时快速定位模块核心知识点需要达到的掌握程度顺序表随机访问、插入删除的移动能实现动态扩容的数组链表头插、尾插、删除、反转能处理指针的边界和内存释放栈后进先出、表达式求值能用栈实现括号匹配和进制转换队列先进先出、循环队列能实现循环队列理解队空队满判断二叉树先序/中序/后序/层序遍历能手写递归和非递归版本二叉搜索树查找、插入、删除理解删除节点的三种情况堆大顶堆、小顶堆、堆排序能实现向上调整和向下调整哈夫曼树构造过程、编码能实现贪心构造和编码解码图存储、DFS、BFS、最短路径能根据场景选择存储结构查找顺序、二分、哈希、树表能分析平均查找长度排序9种基本排序算法能手写快排和归并理解稳定性这张表非常适合期末复习时使用。对着每一项如果能不看书就讲出思路、写出关键代码那这门课的知识就算真正学到手了。学习数据结构最忌讳的事情就是停留在“听懂”的层面。听懂只是起点真正难的是从听到写、从写到用。写不出来说明还有一个环节没打通能写出来但说不清为什么说明还没有形成系统认知。这两层都需要刻意训练。如果你的目标是应付期末考试建议先抓“必考代码题”把链表、二叉树遍历、快排、BFS/DFS这些基础代码反复写到熟。如果你的目标是考研或校招面试那还要在这个基础上多做综合题把数据结构与算法、程序设计放在一起交叉练习。无论是哪种目标这门44讲的课程都值得你认真对待因为它讲的不是某个冷门技巧而是所有程序设计的通用语言。