数据结构

平台课+ 模块课 搭建专业群课程

实例驱动+ 项目同步 优化内容 新颖实用

教材+ 案例+ 实战素材 立体化资源相结合

数据结构是计算机程序设计的重要基础，也是计算机等电子信息类相关专业的一门重要专业基础课程，为系统软件和应用软件的设计与开发提供必要的基础知识和方法，既为后续课程奠定理论基础，还可以提高学生分析问题和解决问题的能力。

本书编写人员均为一线项目研发人员且又都是一线老师，对高职高专学生教学有自己的教学方法和理念。本书以“工作场景导入－知识讲解－回到工作场景－应用实践”为主线编写，通过具体案例引出问题，以解决工作场景为中心展开内容。每一章中都涵盖了完成工作过程所需的实施和具体操作过程，最后回到工作场景解决问题，同时每章都有配套的“应用实践”项目练习，让学生有思考和扩展的空间，达到学以致用的教学目的，突出实用性和操作性。全书共9章，主要包括绪论、线性表、栈和队列、串、数组及广义表、树、图、查找以及排序，内容安排上将数据结构的经典算法与实际工作场景相结合，让同学们轻松、快速地掌握这些算法，为将来走上工作岗位打下坚实的基础。书中各章的案例均有实现代码，且已调试通过。

本书由许绘香、段明义任主编，负责全书的统稿、修改、定稿工作，赵喜玲、陈迎松、吴海燕任副主编，苏玉教授主审。主要编写人员分工如下：赵喜玲、吴海燕编写了第1、3、4、5章，段明义、陈迎松编写了第6、7章和附录一、附录二，许绘香编写了第2、8、9章。参考本书编写工作的还有：曹敏、杜永强、单国全、刘艳等，他们在本书的案例编码及代码调试过程中做了大量工作。另外还要感谢苏玉教授对本书提出了非常宝贵的意见，特别是书中内容的编排、案例选取、难易程度的把握等。本书得到了中国水利水电出版社相关领导的大力支持和策划团队的用心指导，在此深表感谢。

本书既可作为高职高专院校和培养应用型人才的普通本科院校计算机类或电子信息类及相关专业的教材，也可作为计算机应用人员和工程技术人员的参考书。

编者

2014年5月

第1章 绪论 1
1.1 数据结构的课程地位及研究内容 1
1.2 基本概念和术语 4
1.3 算法的描述和分析 8
1.3.1 算法 8
1.3.2 算法的设计要求 9
1.3.3 算法度量及分析 9
1.4 应用实践：学生管理系统登录模块设计 11
小结 13
习题一 13
第2章 线性表 15
2.1 工作场景导入 15
2.2 线性表的逻辑结构 16
2.3 线性表的顺序存储及运算实现 17
2.3.1 线性表的顺序存储 17
2.3.2 顺序表上基本运算的实现 18
2.4 线性表的链式存储结构 22
2.4.1 单链表及其基本运算 23
2.4.2 循环链表 32
2.4.3 双向链表 33
2.5 顺序表与链表的比较 35
2.6 回到工作场景 35
2.7 应用实践：一元多项式的表示及相加 39
小结 43
习题二 44
第3章 栈和队列 46
3.1 工作场景导入 46
3.2 栈 47
3.2.1 栈的定义及基本运算 47
3.2.2 栈的表示和实现 48
3.2.3 栈的简单应用 52
3.3 队列 58
3.3.1 队列的概念 58
3.3.2 队列的顺序存储表示 59
3.3.3 队列的链式存储表示 61
3.4 队列的应用 63
3.5 回到工作场景 64
3.6 应用实践 69
3.6.1 嵌入式系统中断模拟设计 69
3.6.2 学生舞会舞伴配对系统设计 72
小结 75
习题三 75
第4章 串 78
4.1 工作场景导入 78
4.2 串及其类型定义 79
4.2.1 串的基本概念 79
4.2.2 串的基本运算 79
4.3 串的存储结构及基本操作的实现 80
4.3.1 串的定长顺序存储 80
4.3.2 串的堆分配存储表示 82
4.3.3 串的链式存储结构 82
4.4 串的模式匹配及算法 83
4.4.1 简单的模式匹配 83
4.4.2 KMP算法 85
4.5 串操作应用举例 87
4.6 回到工作场景 89
4.7 应用实践：学生管理系统家庭情况
模块设计 91
小结 92
习题四 92
第5章 数组 94
5.1 工作场景导入 94
5.2 多维数组 95
5.2.1 数组的定义和操作 95
5.2.2 数组的内存映像 95
5.3 特殊矩阵的压缩存储 97
5.3.1 对称矩阵 97
5.3.2 三角矩阵 98
5.3.3 对角矩阵 99
5.4 稀疏矩阵 100
5.4.1 稀疏矩阵的三元组表存储 100
5.4.2 稀疏矩阵的十字链表存储 103
5.5 广义表 104
5.5.1 广义表的定义和基本运算 104
5.5.2 广义表的存储 105
5.6 回到工作场景 106
5.7 应用实践：矩阵运算的设计与实现 108
小结 111
习题五 111
第6章 树和二叉树 114
6.1 工作场景导入 114
6.2 基本术语 115
6.2.1 树的定义 115
6.2.2 与树有关的基本术语 115
6.2.3 树的表示方法 116
6.3 二叉树 117
6.3.1 二叉树的概念和基本操作 117
6.3.2 二叉树的性质 119
6.3.3 二叉树的存储结构 120
6.4 二叉树的遍历 122
6.4.1 二叉树的遍历方法及递归实现 123
6.4.2 二叉树遍历的非递归实现 125
6.4.3 由遍历序列恢复二叉树 126
6.4.4 二叉树遍历的应用 127
6.5 线索二叉树 128
6.6 树和森林 131
6.6.1 树的存储结构 131
6.6.2 树、森林与二叉树的转换 134
6.6.3 树和森林的遍历 136
6.7 哈夫曼树及其应用 137
6.7.1 最优二叉树——哈夫曼树 137
6.7.2 哈夫曼树的应用 139
6.8 回到工作场景 141
6.9 应用实践：利用二叉树遍历实现学生
成绩排序模块设计 144
小结 146
习题六 146
第7章 图 149
7.1 工作场景导入 149
7.2 图的基本概念 150
7.3 图的存储结构 154
7.3.1 邻接矩阵 154
7.3.2 邻接表和逆邻接表 156
7.4 图的遍历 158
7.4.1 深度优先搜索 159
7.4.2 广度优先搜索 160
7.5 图的应用 161
7.5.1 最小生成树 161
7.5.2 最短路径 165
7.5.3 拓扑排序 170
7.5.4 关键路径 172
7.6 回到工作场景 175
7.7 应用实践：城市网络中最短路径
的设计 179
小结 182
习题七 182
第8章 查找 186
8.1 工作场景导入 186
8.2 查找的基本概念 187
8.3 静态查找表 188
8.3.1 顺序查找 188
8.3.2 有序表的查找 189
8.3.3 索引顺序表的查找 192
8.4 动态查找 194
8.4.1 二叉排序树 194
8.4.2 平衡二叉树 199
8.4.3 B-树和B+树 202
8.5 哈希表 207
8.5.1 哈希表的基本概念 207
8.5.2 哈希函数的构造方法 208
8.5.3 哈希冲突解决方法 209
8.5.4 哈希表的查找分析 211
8.6 回到工作场景 213
8.7 应用实践：利用哈希查找实现数据
快速查询 214
小结 217
习题八 218
第9章 排序 220
9.1 工作场景导入 220
9.2 排序的基本概念 221
9.3 插入排序 222
9.3.1 直接插入排序 222
9.3.2 折半插入排序 223
9.3.3 希尔排序 224
9.4 交换排序 225
9.4.1 冒泡排序 226
9.4.2 快速排序 227
9.5 选择排序 229
9.5.1 简单选择排序 229
9.5.2 堆排序 230
9.6 归并排序 233
9.7 各种排序方法比较 234
9.8 回到工作场景 235
9.9 应用实践：内部排序的综合应用 237
小结 241
习题九 242
附录一 C语言常用语法提要 243
附录二 类C语言语法 248
参考文献 251

1. Linux系统管理（openEuler版） [主编 许兴鹍 黄君羡]
2. Web前端开发从学到用完美实践 [阮晓龙 冯顺磊 编著]
3. 用英语讲中国故事（全视频 彩色版）上、下册 [主编　谢亮亮　汪洋]
4. 新时代大学生美育教育 [穆林 刘苍劲 彭圣芳]
5. 电子商务英语 [丁文毅 严慧]
6. 智能可穿戴项目化教程 [曾文波 陈赵云]
7. 视觉设计解析与实战教程 [姜春磊　杨晓]
8. 电子产品制图与制版案例教程 [邹莉莉　苏文斌　贺小艳]
9. 设计新维度：CMF元素与创新产品设计 [彭小鹏]
10. 园林树木识别与应用 [主编 张玉泉]
11. 文本信息处理与应用 [主编　何黎松　姚香秀]
12. 工业机器人编程及应用（第二版） [主编 向艳芳 胡月霞]
13. C语言程序设计（第二版） [主编 刘祖珉 赵仕波]
14. 数据分析与应用 [主编　孙伟　王兰芹]
15. Linux操作系统配置与管理项目化教程（第二版） [主编 白玉羚 刘金明 闫 淼]
16. Ansys SpaceClaim直接建模与仿真指南 [蔡宜时 编著]
17. 基于大数据的智慧农业管理平台关键技术研究与实践 [周永福 著]
18. 健美运动 [戴显岩]
19. Python程序开发基础（AI+微课版） [赵艳莉　曾鑫]
20. 大学生心理困境突围之路 [张珏 著]
21. 机器学习基础与实践 [主编　李晓峰　胥文婷　李云波]
22. 大模型应用实战 DeepSeek＋即梦AI＋剪映重塑创作 [丁红　杨彦彦　丁丁　编著]
23. HarmonyOS从入门到精通 [陈赵云　周永福　杨　浪]
24. 用英语发现世界：欧美文化篇 [李小丽　张薇　编著]
25. 大学体育教程 [戴显岩]
26. 新一代信息技术 [李佼辉 任雪冬]
27. 轨道交通类专门用途英语教程 [李德华主编 商晔副主编]
28. 建设工程项目团队知识异质性对团队绩效的影响研究 [胡可]
29. 新时代元阳梯田 云南现代化高原立体灌区 前世 今生 未来 [云南省水利水电勘测设计研究院 ]
30. 网络工程师章节习题与考点特训（适配第6版考纲） [夏杰 编著]