数据结构

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

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

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

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

本书编写人员均为一线项目研发人员且又都是一线老师，对高职高专学生教学有自己的教学方法和理念。本书以“工作场景导入－知识讲解－回到工作场景－应用实践”为主线编写，通过具体案例引出问题，以解决工作场景为中心展开内容。每一章中都涵盖了完成工作过程所需的实施和具体操作过程，最后回到工作场景解决问题，同时每章都有配套的“应用实践”项目练习，让学生有思考和扩展的空间，达到学以致用的教学目的，突出实用性和操作性。全书共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. 外贸英语从入门到实战：53种实战场景秒变谈判高手 [张乐 廖熠 编著]
9. Linux系统管理（openEuler版） [主编 许兴鹍 黄君羡]
10. Python程序设计项目化教程（基于AI） [主编 禹晨 赵金考 王宏斌]
11. 可编程控制器应用项目化教程（三菱FX系列） [主编 姜文雍 李东方]
12. 全球英文电影精选：看电影学英文 [张颖　编译]
13. Python程序设计与网络爬虫 [黄海辉 彭新东]
14. 实体店创业分析实务 [燕艳 陈文冬 编著]
15. 中国对欧盟OFDI效率与风险的多维度实证评估—基于KK-SFA模型与PCF-聚类分析方法 [黄健钧 著]
16. 生成式人工智能素养 [邱有春　罗明全]
17. 系统分析师考试32小时通关（适配第2版考纲） [薛大龙　邹月平]
18. Ansys DesignModeler参数化特征建模与仿真指南 [蔡宜时 编著]
19. 浙江省山区县共富工坊建设的现状与对策 [徐骏骅 著]
20. 计算机网络技术及应用（第3版） [主编 刘永华 陈瑶]
21. 北京冬奥精神传承和发展研究 [顾春雨 邹新娴 等 著]
22. 汽车营销理论与实务（第三版） [主编 赵培全]
23. 人工智能基础与实践 [禹晨 赵金考 王宏斌 李璐]
24. 系统分析师5天修炼（适配第2版考纲） [施游 邹汉斌 黄少年 主编]
25. 线性代数（第二版） [惠小健 贺艳琴 夏斌湖]
26. 微控制器系统设计（STM32版） [主编 杨凌]
27. 机械原理与机械设计作业集（第二版） [主编 田亚平 李爱姣]
28. 高剑父的现代国画研究 [陈水兴　著]
29. 用英语介绍中国江河湖海 [庞彦杰　李静　赵娟　刘桂杰　编]
30. 大学生创新创业基础（第2版） [主编 姜国权 方邡]