数据结构从理论到代码：手写链表、二叉树、哈希表与调试实战

简介：这份PDF是山东大学《数据结构》课程内容整理，面向计算机专业本（专）科生、考研与期末复习者，帮助快速建立从数据组织到算法分析的知识框架。资源共1个文件，为PDF格式，压缩包大小仅324KB，轻量便携，可直接在电脑或手机上阅读。内容从第一章绪论切入，系统讲解数据、数据元素、数据项、数据对象等基础概念，辨析集合、线性、树形、网状四类逻辑结构，并介绍顺序、链式、散列、索引四种存储结构；第二章重点阐述线性表的定义、顺序表与链式表的表示和实现，涵盖初始化、插入、删除、查找等典型操作的算法思路与时间复杂度分析，配有C语言描述，能帮助将抽象概念落实到具体编码实现。已有113人学习浏览，适合在听课或看书后用来梳理重点、查漏补缺，也可作为考前快速回顾的浓缩讲义，对备考山东大学及相关院校计算机专业具有直接参考价值。

1. 为什么把「山东大学-数据结构.pdf」从头翻到尾，还是写不出能过笔试的数据结构代码

我最早是从同事的移动硬盘里翻到这份讲义，文件名就叫「山东大学-数据结构.pdf」，封面没什么花哨，章节体例接近常见的数据结构 C 语言版教材，但多了一些山东大学软件学院的历年例题标记。这些年审过不少校招简历，也带过实验室新人，发现一个重复率极高的现象：能把这份 PDF 从头翻到尾的人，能背出二叉树三种遍历顺序，能画出哈希冲突链，但真让他们十分钟内手写一个最小栈，或者解释为什么有序数组中二分查找比单链表快，立刻卡住。

问题不在讲义，在阅读方式。数据结构讲义负责“描述结构”，工程里真正的任务发生在“制造结构”和“操作结构”里。看懂一段定义，和写完不报错的实现，中间隔着边界条件、内存布局和编译器的报错。下面这套路线把「山东大学-数据结构.pdf」当作一份知识目录，沿着理论、实现、排错、应用四层走下来，每一步都留下能直接运行的代码和操作步骤，保证看完一个知识点，当天就能在自己编辑器里把它跑起来。

2. 拆解「山东大学-数据结构.pdf」中的核心抽象：逻辑结构、复杂度与选型

数据结构课放在大学二三年级，地位有点尴尬：没有算法那么多数学推导，又没有工程课那么多框架可调。多数人翻 PDF 时只看到“数组、链表、栈、队列”这些名词，没意识到每一章其实在回答两个问题：数据怎么组织，操作怎么收费。这两个问题一旦在脑子里立住，后面实现、面试甚至系统设计都会顺很多。

2.1 四类逻辑结构在写代码时的具体区别

教材喜欢把逻辑结构分成集合、线性、树形、图状四类，读 PDF 时逐字看不如画一遍。按写代码的角度重新分类：

• 集合结构对应编程语言里的set，核心操作是唯一性和成员判断；
• 线性结构对应数组和链表，强调“位置”和“顺序”，所以才有遍历、头部插入、尾部插入的说法；
• 树形结构强调层级和祖先关系，天然适合表达文件目录、表达式求值和决策路径；
• 图状结构的重点在两个顶点之间的关系，最短路径、连通分量都围绕边展开。

画过之后会得到一个真正的结论：同一批数据，逻辑结构不同，能做的操作集完全不同。例如 10 万个键值对要按键序输出，用哈希结构根本做不到；要根据学号精确查人，用二叉搜索树和用哈希表的次数不是一个量级。讲义反复强调“逻辑结构与存储结构分离”，落到开发里就是先回答“我怎么用这批数据”，再决定“内存里怎么摆”。

# 同一个数据集合，集合结构与线性结构的表达能力不同 s = {3, 1, 4, 1, 5} # 集合结构自动去重 arr = [3, 1, 4, 1, 5] # 线性结构保留全部元素和顺序 print(len(s)) # 4，集合只关心唯一性 print(arr.count(1)) # 2，线性结构可以统计重复次数

这段代码展示集合没有“重复”语义，线性结构才能统计频次。做数据建模时第一问就该是：我到底需不需要重复、顺序和索引。这三个需求直接决定结构选型，也决定后面接口怎么设计。

2.2 时间复杂度不只是计算题，它直接决定 API 选型

讲义的每章前面都有大段复杂度推导，很多人跳过去，到树与图那里就吃亏。复杂度不是考试题，它是在没有压测环境时估算程序极限的工具。读代码时把三句话刻在脑子里：循环嵌套看层数，递归看递推式，容器操作看底层实现。

最容易误判的例子是 Python 的list.pop(0)。底层是数组，弹出头部后所有元素要整体左移，复杂度 O(n)；而list.pop()是 O(1)。第一次写队列的人往往会用append加pop(0)，数据一多就暴露抖动。改用collections.deque后两端都是 O(1)，JavaScript 里的Array.shift()也有同样的 O(n) 问题，需要优化时换用分段结构。

表格背后的选择不靠“背下来”，要看数据流的访问模式。日志追加业务选数组尾部；倒排索引高频拼接片段，用链表减少内存搬移；Redis 的列表之所以用双向链表，也是因为要同时支持头尾弹出。复杂度只告诉你量级，不告诉你常数，所以定位到具体场景后还要加参数评估，这就引出选型的下一步。

2.3 线性表选型：数组还是链表，不看掌握程度看访问模式

这是线上问题里最常被问到的选择之一，实际答案早就写在访问模式里。

顺序访问为主就选数组。理由有三：内存连续，CPU 缓存预取命中率高；按下标定位是 O(1)；内置动态数组都针对尾部操作做了深度优化。随机插入、删除频繁且数据量大的场景，才把链表纳入考虑。

需要注意，链表不是“高级”的代名词，它的用武之地常在“对象之间互相引用”的模型里。操作系统里的进程链表、内存管理里的空闲链表，选用链表的根本原因是结点可以离散分布，结点与结点之间通过指针保持关系，这更贴近“一个进程指向另一个进程”的真实世界。这一点在文件系统、虚拟内存的实现里反复出现，也是讲义到后期还要回讲链表的原因：不是因为它快，而是因为它能表达关系。

2.3.1 C 语言语境下的选型补充

在 C 语言代码里选数组还是链表，还有一个容易忽视的维护成本。数组的扩容是一次memmove或重新realloc，会搬运全部数据；链表插入只要改两个指针，但每次分配结点都有一次malloc。实际工程里很少单看复杂度选型，而是把“分配次数”也当成隐性成本：高频插入且数据量稳定，链表更划算；数据量大但只在尾部追加，数组更划算。这个维度在面试聊到vector与list的区别时，常被当作加分的补充点。

3. 用最小可运行代码把线性表、二叉树和哈希表落地

把讲义里的定义变成代码，最大的障碍是选择不合适的例子。太小的例子看不出结构的作用，太大的例子又淹没在业务逻辑里。下面四个实现是我复习这块内容时常用的“最小模型”，每个都能单独编译运行，后面附参数说明和容易出错的位置。

3.1 用 C 实现带头结点的单链表，插入时先接后继再改前驱

单链表是入门第一课，也是后续 LRU 缓存、OS 任务队列的基础。教科书一般用不带头结点的版本，面试笔试里带头结点的写法更省心：头结点不存业务数据，插入、删除代码不需要单独处理“删除的是第一个结点”这种分支。

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; // 在结点 prev 的后面插入一个新结点，值记为 val int insert_after(Node *prev, int val) { if (prev == NULL) { return -1; // 前驱为空，拒绝写入 } Node *new_node = (Node *)malloc(sizeof(Node)); if (new_node == NULL) { return -2; // 内存分配失败 } new_node->data = val; new_node->next = prev->next; // 先让新结点接住原先的后继 prev->next = new_node; // 再让前驱指向新结点 return 0; } int main(void) { Node head = {0, NULL}; // 头结点不参与业务数据存储 for (int i = 1; i <= 3; i++) { insert_after(&head, i); } for (Node *p = head.next; p != NULL; p = p->next) { printf("%d ", p->data); } return 0; }

代码里最容易写反的是两行指针操作，如果先执行prev->next = new_node，后面的new_node->next = prev->next拿到的就是新结点自己，链表形成环。必须先让新结点接住原来的后继，再让前驱指向新结点。insert_after返回 -1 和 -2 两个错误码，分别对应空指针和malloc失败，调用侧可以根据返回值回滚或打印错误，这个习惯在工程里比只返回 0 更稳定。

3.2 用 Python 实现最小栈，O(1) 取最小值靠“辅助栈同步”

最小栈是面试高频题，要求push、pop、top、get_min四种操作都是 O(1)。常见实现是维护一个辅助栈，栈顶永远保存当前主栈的最小值。

class MinStack: def __init__(self): self.stack = [] # 主栈，保存原始数据 self.min_stack = [] # 辅助栈，栈顶保存当前最小值 def push(self, x: int) -> None: self.stack.append(x) # 辅助栈为空，或 x 不大于当前最小值，都压入辅助栈 if not self.min_stack or x <= self.min_stack[-1]: self.min_stack.append(x) def pop(self) -> None: if not self.stack: return x = self.stack.pop() # 被弹出的值正好是当前最小值，辅助栈也要弹出 if x == self.min_stack[-1]: self.min_stack.pop() def top(self) -> int: return self.stack[-1] def get_min(self) -> int: return self.min_stack[-1]

两个关键点。第一，push里用<=而不是<，为了支持重复最小值：连续压入两个相同的最小值，辅助栈里要留两份，否则弹出其中一个后，min_stack的栈顶空了，get_min会读到错误结果。第二，pop判断相等用==，比较的是数值而不是对象引用，整数场景下没问题。手写这道题时最常见错误是辅助栈不同步，主栈弹出后没有及时更新min_stack，后续get_min返回一个已经出栈的值。

3.3 二叉查找树的插入与搜索，要看清退化场景

二叉树是后面堆、AVL、红黑树的基础。二叉查找树的规则只有一条：左子树结点值小于根，右子树大于根，左右子树自身也满足这个性质。插入操作递归实现很简洁：

typedef struct BSTNode { int data; struct BSTNode *left; struct BSTNode *right; } BSTNode; // 向二叉查找树插入 key，返回新的根结点 BSTNode *bst_insert(BSTNode *root, int key) { if (root == NULL) { BSTNode *node = (BSTNode *)malloc(sizeof(BSTNode)); node->data = key; node->left = NULL; node->right = NULL; return node; } if (key < root->data) { root->left = bst_insert(root->left, key); // 进左子树 } else if (key > root->data) { root->right = bst_insert(root->right, key); // 进右子树 } // key 已存在时不做处理，维持键的唯一性 return root; }

这个写法的返回值一定要重新赋给root->left或root->right，否则新结点挂在树上后，上层的指针没有被更新，整棵树相当于没插入。时间复杂度上，平衡状态下平均 O(log n)，但最坏情况是数据有序输入，比如按 1 到 10000 的顺序插入，树退化成一条链表，查找变成 O(n)。这也是为什么工程里的二叉查找树几乎都会加平衡策略。

3.3.1 用中序遍历验证插入逻辑

调试二叉查找树最直接的方法，是插入一组乱序数据后做中序遍历，如果输出有序，树的插入逻辑就是对的。遍历函数本身也是常考题，递归三步就能写完：

def inorder(root): if root is None: return inorder(root.left) print(root.val, end=" ") inorder(root.right)

3.4 哈希表冲突处理：线性探测的代码与边界条件

哈希表是应用最广的数据结构之一，难点不在哈希函数，而在冲突处理。线性探测是开放寻址法里最简单的一种，Python 版本的实现核心如下：

class HashTable: def __init__(self, capacity=16): self.capacity = capacity self.table = [None] * capacity # 槽位，None 表示空 def _hash(self, key): return hash(key) % self.capacity def put(self, key, value): idx = self._hash(key) while self.table[idx] is not None and self.table[idx][0] != key: idx = (idx + 1) % self.capacity # 向后探测，越界回绕 self.table[idx] = (key, value) def get(self, key): idx = self._hash(key) while self.table[idx] is not None: if self.table[idx][0] == key: return self.table[idx][1] idx = (idx + 1) % self.capacity return None

while的终止条件是“槽位为空”或“key 相同”。线性探测的问题在删除时暴露：直接置None会切断后续元素的探测链，已被删除位置之后的元素在查找时会提前碰到空位而返回不存在。工程做法是引入墓碑标记（tombstone），删除时标记DELETED，查找时跳过标记，插入时优先复用。装载因子超过 0.7 时，线性探测的碰撞迅速恶化，读取时间从 O(1) 变成接近 O(n)。这个阈值来自数学推导，实践中可以直接观察：插入 10 万条数据后，对比满载前的吞吐量，差出 5 倍以上就该扩容或换用链地址法。

4. 数据结构代码调试的三个必查位置：段错误、递归溢出和哈希冲突

代码能写完还不算数，能稳定通过边界测试才算。数据结构代码大量使用指针和递归，报错信息和普通业务代码完全不一样，常见的坑集中在三个位置。

4.1 段错误先查空指针与越界写，用 gdb 看调用栈而不是乱猜

C 和 C++ 的链表、二叉树代码几乎都栽在段错误上。段错误的本质是进程访问了没有权限的内存，最常见原因是空指针解引用和数组越界写。很多人的第一反应是加 printf，把程序打得千疮百孔，不如直接在编译时加-g选项，再用 gdb 调：

gcc -g -o bst bst.c gdb ./bst (gdb) run (gdb) bt (gdb) frame 3 (gdb) info locals

bt输出调用栈，能立刻看到崩溃发生在哪个函数、哪一行。frame 3切到指定层，info locals查看局部变量。从崩溃点往前推两行，通常就能定位到某个指针是NULL，或者malloc返回后被误删。长期养成的习惯是：每次malloc后都判断返回值，每次解引用前都确认不是NULL。这两个检查能让段错误概率下降八成。

4.2 递归溢出要区分“深度问题”和“终止条件问题”

递归实现树的遍历和排序很直观，但函数调用栈有极限。普通开发环境下默认栈空间 8MB 左右，递归深度几万层就可能把栈打爆。遇到爆栈先分两类情况处理：

第一类，递归深度本身过大。查询树高度时二叉树已经退化，递归深度逼近结点数，这时考虑用循环加显式栈改写。第二类，终止条件写错，递归无法收敛。写递归时先写终止条件，再写递归调用，if (root == NULL) return;这样的守卫放在第一行。

4.2.1 用递归计数器判断路径是否符合预期

调试时在递归函数里加一个计数变量，可以很快判断递归路径是否符合预期：

# 检查斐波那契第 n 项时，看递归调用次数 n = 30 count = 0 def fib(k): global count count += 1 if k <= 1: return k return fib(k - 1) + fib(k - 2) fib(n) print(count) # 会超过 100 万次

同样逻辑里若出现同一子问题被反复计算，就应该用记忆化数组缓存结果。这个例子不涉及栈溢出，但已经说明：递归的“层数”不是唯一指标，调用次数也可能是指数级增长，两者都要盯。

4.3 哈希表性能下降时看装载因子，而不是只看哈希函数

哈希表变慢有两个原因：装载因子过高、哈希函数质量差。装载因子是元素个数除以槽位数，超过 0.7 后碰撞概率急剧上升。检查方法很简单，打印一下当前表的槽位和元素数：

print(f"元素数: {len(keys)}, 槽位数: {table.capacity}, 装载因子: {len(keys) / table.capacity:.2f}")

如果装载因子没超阈值但查找仍然慢，问题多半出在哈希函数上。简单取模对小整数簇友好，但对连续偶数的 key 会造成大量偶数槽空着，奇数槽挤满。可以统计每个槽的链长，标准差太大的话换一种散列方式。调试这类问题不要靠猜，给哈希表加一个统计函数，输出最长链长度和平均链长，一次就能定位瓶颈。

5. 把讲义里的数据结构结论变成可验证的本事：自测题与复杂度复盘

PDF 读了、代码写了，还需要一套方法证明自己“真会了”。除了背诵定义，我通常会做三件事：给实现配一个数据生成器，滑动压测参数，最后做一次复杂度复盘。

5.1 给实现配一个数据生成器，用它做边界输入

手写数据很难覆盖边界，生成器的作用是把数据规模从 1 推大到 10 万级别。以排序算法为例：

import random import time for n in [100, 1000, 10000, 100000]: data = [random.randint(0, 1000000) for _ in range(n)] start = time.perf_counter() data.sort() elapsed = time.perf_counter() - start print(f"n={n}, elapsed={elapsed:.6f}s")

如果理论复杂度是 O(n log n)，四组成绩的耗时比约 1:10:130:1700。用这个比例去对照自己的复杂度推导，能发现是否无意中写了 O(n²)。数据规模翻倍后耗时翻四倍，说明已经退化，该回去调整结构而不是继续堆机器资源。

5.2 用复杂度复盘表对齐预期与实测

每次写完数据结构习题，都做一张小表格记录三列：算法名称、理论复杂度、输入规模在多少时耗时开始失控。常用的几个公共模板：

最后衡量数据结构有没有学扎实，标准不是页码里记了多少笔记，而是换一个新问题能不能直接选对结构。比如“求滑动窗口最大值”第一反应是单调队列，“20 亿个元素中选前 100”第一反应是堆，这就是讲义刻进脑子里的直觉。检验的时候不要再看 PDF 目录，直接打开编辑器，给刚才的代码加一组最坏的输入，看看谁先扛不住。

本文还有配套的精品资源，点击获取