数据结构

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

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

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

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

本书编写人员均为一线项目研发人员且又都是一线老师，对高职高专学生教学有自己的教学方法和理念。本书以“工作场景导入－知识讲解－回到工作场景－应用实践”为主线编写，通过具体案例引出问题，以解决工作场景为中心展开内容。每一章中都涵盖了完成工作过程所需的实施和具体操作过程，最后回到工作场景解决问题，同时每章都有配套的“应用实践”项目练习，让学生有思考和扩展的空间，达到学以致用的教学目的，突出实用性和操作性。全书共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. 输水管线工程风险管理 [张勇 党亥生 著]
2. 民用航空飞机标准线路施工 [主编　王志敏　陈明]
3. 不息的水脉—大运河讲谈录 [赵珩　著]
4. 实用运筹学 [主编　邢育红　于晋臣]
5. 三峡梯级电站水资源决策支持系统研究与开发 [姚华明 潘红忠 汤正]
6. 海南黎族民俗文化鉴赏 [庞国华　著]
7. 石墨烯在太赫兹及中红外频段电磁器件设计中的应用 [李艳秀 庄华伟 著]
8. 电子技术（第二版） [主编 覃爱娜 李飞]
9. 办公自动化高级应用 [陈萍 朱晓玉]
10. 信息处理技术员考试32小时通关 [薛大龙]
11. 电子产品设计案例教程（微课版）—基于嘉立创EDA（专业版） [王静 莫志宏 陈学昌 丁红]
12. C程序设计实践教程 [刘卫国]
13. C程序设计（慕课版） [刘卫国]
14. Web技术开发教程（基于.NET开源MVC框架） [王合闯 韩红玲 王青正 陈海蕊]
15. 商务英语翻译教程（笔译）（第四版） [主编 王军平]
16. 智慧零售技术与应用 [洪旭 著]
17. 建设工程法规实务 [主编 余滢]
18. 商务秘书理论与实务（第三版） [主编 张同钦]
19. 程序设计基础实践教程（C/C++语言版） [张桂芬 葛丽娜]
20. C++案例项目精讲 [主编 杨国兴]
21. 劳动争议处理实务 [主编 王秀卿 罗静]
22. 工程数学 [主编 郭立娟 王海]
23. 语音识别理论与实践 [主编　莫宏伟]
24. 信息系统项目管理师章节习题与考点特训（第二版） [主编 薛大龙]
25. 武术基础教程 [主编 李代勇 谢志民]
26. 计算机网络实训教程 [主编 张浩军 赵玉娟]
27. 画法几何与机械制图习题集（多学时） [主编 赵军]
28. HCIA-Datacom认证题库分类精讲 [主 编 韩立刚]
29. SwiftUI完全开发 [李智威 著]
30. 网络规划设计师备考一本通 [夏杰 编著]