数据结构从理论到代码：手写链表、二叉树、哈希表与调试实战-北京尧图网络

简介这份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) 问题需要优化时换用分段结构。操作底层是动态数组底层是链表按下标访问O(1)O(n)头部插入/删除O(n)O(1)尾部插入/删除O(1)扩容摊还O(1)带尾指针按值查找O(n)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, capacity16): 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 Nonewhile的终止条件是“槽位为空”或“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 localsbt输出调用栈能立刻看到崩溃发生在哪个函数、哪一行。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(fn{n}, elapsed{elapsed:.6f}s)如果理论复杂度是 O(n log n)四组成绩的耗时比约 1:10:130:1700。用这个比例去对照自己的复杂度推导能发现是否无意中写了 O(n²)。数据规模翻倍后耗时翻四倍说明已经退化该回去调整结构而不是继续堆机器资源。5.2 用复杂度复盘表对齐预期与实测每次写完数据结构习题都做一张小表格记录三列算法名称、理论复杂度、输入规模在多少时耗时开始失控。常用的几个公共模板算法或结构平均时间复杂度最坏场景实测中第一次耗时跳变的 n数组冒泡排序O(n²)逆序输入n 到 8000 左右开始明显发慢二叉查找树查找O(log n)有序输入树高接近 n 时退化为 O(n)线性探测哈希表O(1)装载因子超过 0.7装载因子到 0.75 以后吞吐明显下降最后衡量数据结构有没有学扎实标准不是页码里记了多少笔记而是换一个新问题能不能直接选对结构。比如“求滑动窗口最大值”第一反应是单调队列“20 亿个元素中选前 100”第一反应是堆这就是讲义刻进脑子里的直觉。检验的时候不要再看 PDF 目录直接打开编辑器给刚才的代码加一组最坏的输入看看谁先扛不住。本文还有配套的精品资源点击获取

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

相关推荐

ComfyUI云端GPU部署全攻略：从选卡到工作流调优

嵌入式衣物护理机选购指南与热门机型测评

OpenClaw架构解析：LLM与工具调用的工程实践

更多资讯

基于SpringBoot与微信小程序的离校管理系统设计与实现

SpringBoot智慧社区系统开发实战与优化

Win11输入法图标消失？从TSF框架到ctfmon.exe的完整排查指南

Spring Security核心架构与生产实践指南

Babel 插件 transform-exponentiation-operator：将 ES2016 指数运算符编译为 ES5

ESP32-P4 USB Host实战：从鼠标枚举到HID协议深度解析

今日更新

校园网认证计费模式详解：AAA与代拨架构、原理及排障

Spring Boot+Vue垃圾分类毕设：分层、权限与排错实战

把 Cline 的 Base URL 改到 TaoToken 之后，DeepSeek 仍能修调试配置

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？