数据结构

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

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

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

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

本书编写人员均为一线项目研发人员且又都是一线老师，对高职高专学生教学有自己的教学方法和理念。本书以“工作场景导入－知识讲解－回到工作场景－应用实践”为主线编写，通过具体案例引出问题，以解决工作场景为中心展开内容。每一章中都涵盖了完成工作过程所需的实施和具体操作过程，最后回到工作场景解决问题，同时每章都有配套的“应用实践”项目练习，让学生有思考和扩展的空间，达到学以致用的教学目的，突出实用性和操作性。全书共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. 信息技术基础（麒麟操作系统+WPS Office） [主编　芮雪　蒋莉　王亮亮]
2. Office高级应用项目式教程（第2版） [主编 李观金 张倩文 黎夏克 ]
3. 巧用翻译学英语：英汉互译500例 [王学文 著]
4. 高等教育多维评价体系构建与高质量发展研究 [张妍 著]
5. 系统规划与管理师章节习题与考点特训（第二版） [主编 薛大龙]
6. 计算机操作系统实践指导（openEuler版） [主编 秦光 曾陈萍 岳付强]
7. 信息系统管理工程师真题及模考卷精析（适用机考） [主 编 薛大龙 程 刚 上官绪]
8. 航海类院校体育教育教学研究 [张利超 李宁 著]
9. 新时代背景下我国职业教育产教融合长效机制建设研究 [王玉贤 著]
10. 电路分析 [主编 李飞 毛先柏]
11. 信息系统管理工程师（适用第2版大纲）一站通关 [指尖疯　编著]
12. 传统山水画论解读与实践 [陈钠 著]
13. 网络工程师备考一本通（适配第6版考纲） [夏杰 编著]
14. 陈孝云的职教理想与情怀 [祝吉太 江传瑞 张义廷 著]
15. 地方本科院校电子信息学科课程思政案例集 [王甫]
16. Excel数据处理与分析（第二版） [主编 张志明 邹 蕾]
17. 网络工程师5天修炼（适配第6版考纲） [主编　朱小平 施游]
18. 仓储管理实务（第二版） [周宁武 编著]
19. 基于AE与C#的地理信息系统二次开发 [李小根 贾艳昌 乔翠平 姜彤 ]
20. 2023年长沙市文化和旅游业发展报告 [主编 陈莉]
21. 舞台化妆造型设计 [主编 刘思彤 张 涛 张忆雨]
22. 产教融合视角高校体育专业实践教学体系构建研究 [杨柳青 叶华兵 著]
23. 知识图谱及应用案例 [张善文 黄文准 于长青 陈明淑]
24. Python程序设计案例教程（微课版） [主编　石利平　田辉平　余以胜]
25. 皓月繁星：青少年儿童心理成长手册 [主　编　林赞歌 副主编　杜志南]
26. 材料力学 [章宝华 赵新胜 徐斌]
27. 系统集成项目管理工程师考试32小时通关（第3版） [主编　薛大龙 副主编　上官绪阳]
28. 软考论文高分特训与范文10篇——系统分析师（第二版） [薛大龙 邹月平 施游]
29. 黄河海勃湾水利枢纽防凌安全运行 [王战领 王丛发 范瑜彬 著]
30. 大学生心理健康教育 [方雄 著]