出版日期:2014-10
ISBN:9787302376573
作者:邓锐,赵莉,朱清妍
作者简介
本书依据高职学生学习的特点，经过长期高职教学实践成型。全书包括数据结构与算法、线性表、栈和队列、串、递归、树、图、查找和内排序9部分内容，剔除了数组、矩阵、广义表、外排序和文件等内容，并将较难的内容编排到了“知识与技能扩展”部分，以供读者作为选修内容学习。同时，对于实际工作中应用较少的知识点（如线段树、并查集等）进行了精简。
全书紧紧围绕9部分内容，精心设计了9个有趣的“大话”形式的开场白，旨在通过轻快的类比，帮助学生宏观理解对应的知识点。同时，每章均精选了相对应的经典案例，借助这些案例的讲解和分析，使学生在解决问题的过程中逐步掌握结构设计与算法，并提高学生的通识素养和专业兴趣。
本书可作为高职学院和中职学校计算机相关专业的数据结构和算法教程，同时也可作为程序设计开发者和爱好者的学习参考用书。
书籍目录
第1 章 数据结构与算法 ............................................................................................... 1
开场白 ..........................................................................................................................1
1.1 案例提出——高斯的巧妙解题 .........................................................................2
1.2 知识点学习 .........................................................................................................3
1.2.1 数据结构 ................................................................................................3
1.2.2 算法 ......................................................................................................12
1.2.3 数据结构+ 算法= 程序 ......................................................................17
1.3 案例问题解决 ...................................................................................................17
1.3.1 1787 年高斯算法——比较算法优劣 .................................................17
1.3.2 2014 年高斯算法——比较结构优劣 .................................................18
1.4 知识与技能扩展 ...............................................................................................18
课后习题 ....................................................................................................................19
上机实战 ....................................................................................................................20
第2 章 线性表 ............................................................................................................. 22
开场白 ........................................................................................................................22
2.1 案例提出——约瑟夫与海盗 ...........................................................................23
2.2 知识点学习 .......................................................................................................23
2.2.1 线性表 ..................................................................................................23
2.2.2 线性表的顺序存储结构 ......................................................................25
2.2.3 线性表的链式存储结构 ......................................................................30
2.2.4 静态链表 ..............................................................................................42
2.3 案例问题解决 ...................................................................................................42
2.3.1 用顺序表解决约瑟夫问题 ..................................................................43
2.3.2 用循环链表解决约瑟夫问题 ..............................................................44
2.4 知识与技能扩展 ...............................................................................................47
课后习题 ....................................................................................................................48
上机实战 ....................................................................................................................48
数据结构案例教程（C/C++ 版）
IV
第3 章 栈和队列 ......................................................................................................... 50
开场白 ........................................................................................................................50
3.1 案例提出——迷宫问题 ...................................................................................51
3.2 知识点学习 .......................................................................................................52
3.2.1 栈 ..........................................................................................................52
3.2.2 队列 ......................................................................................................63
3.3 案例问题解决 ...................................................................................................71
3.3.1 用栈来解决迷宫问题 ..........................................................................71
3.3.2 用队列来解决迷宫问题 ......................................................................75
3.4 知识与技能扩展 ...............................................................................................79
课后习题 ....................................................................................................................80
上机实战 ....................................................................................................................81
第4 章 串 ...................................................................................................................... 83
开场白 ........................................................................................................................83
4.1 案例提出——埃特巴什码 ...............................................................................84
4.2 知识点学习 .......................................................................................................85
4.2.1 串的基本概念 ......................................................................................85
4.2.2 串的存储结构 ......................................................................................86
4.2.3 串的模式匹配 ....................................................................................100
4.3 案例问题解决 .................................................................................................102
4.3.1 顺序结构埃特巴什码 ........................................................................102
4.3.2 链式结构埃特巴什码 ........................................................................105
4.4 知识与技能扩展——KMP 算法 ...................................................................109
课后习题 ..................................................................................................................112
上机实战 ..................................................................................................................113
第5 章 递归 ................................................................................................................ 115
开场白 ......................................................................................................................115
5.1 案例提出——验证黄金分割 .........................................................................116
5.2 知识点学习 .....................................................................................................117
5.2.1 什么是递归 ........................................................................................117
5.2.2 递归调用的过程 ................................................................................120
5.2.3 递归算法的设计 ................................................................................120
5.3 案例问题解决——验证黄金分割 .................................................................122
5.4 知识与技能扩展——递归转换 .....................................................................123
课后习题 ..................................................................................................................125
上机实战 ..................................................................................................................126
第6 章 树 .................................................................................................................... 128
开场白 ......................................................................................................................128
目 录
V
6.1 案例提出——高效的电文编译 .....................................................................129
6.2 知识点学习 .....................................................................................................129
6.2.1 树的基本概念 ....................................................................................129
6.2.2 二叉树 ................................................................................................136
6.2.3 哈夫曼树 ............................................................................................153
6.3 案例问题解决 .................................................................................................158
6.4 知识与技能扩展——二叉树遍历非递归算法 .............................................162
课后习题 ..................................................................................................................169
上机实战 ..................................................................................................................170
第7 章 图 .................................................................................................................... 172
开场白 ......................................................................................................................172
7.1 案例提出——道路畅通与伤员急救问题的解决 .........................................173
7.2 知识点学习 .....................................................................................................175
7.2.1 图的基本概念 ....................................................................................175
7.2.2 图的存储结构 ....................................................................................177
7.2.3 图的遍历 ............................................................................................183
7.2.4 最小生成树 ........................................................................................187
7.2.5 有向无环图及其应用 ........................................................................191
7.2.6 单源最短路径——迪杰斯特拉算法 ................................................197
7.3 案例问题解决 .................................................................................................201
7.3.1 省政府“畅通工程”——普里姆算法 ............................................201
7.3.2 伤员急需运送——迪杰斯特拉算法 ................................................203
7.4 知识与技能扩展——弗洛伊德算法 .............................................................205
课后习题 ..................................................................................................................207
上机实战 ..................................................................................................................208
第8 章 查找 ................................................................................................................ 210
开场白 ......................................................................................................................210
8.1 案例提出——词典中查找单词 .....................................................................211
8.2 知识点学习 .....................................................................................................211
8.2.1 查找的基本概念 ................................................................................211
8.2.2 线性表的查找 ....................................................................................212
8.2.3 树表查找——二叉排序树 ................................................................218
8.3 案例问题解决 .................................................................................................226
8.4 知识与技能扩展——哈希表查找 .................................................................227
课后习题 ..................................................................................................................231
上机实战 ..................................................................................................................232
第9 章 内排序 ........................................................................................................... 234
开场白 ......................................................................................................................234
数据结构案例教程（C/C++ 版）
VI
9.1 案例提出——光棍节的排序活动 .................................................................235
9.2 知识点学习 .....................................................................................................236
9.2.1 排序的基本概念 ................................................................................236
9.2.2 插入排序 ............................................................................................237
9.2.3 交换排序 ............................................................................................240
9.2.4 选择排序 ............................................................................................244
9.2.5 归并排序 ............................................................................................249
9.2.6 基数排序 ............................................................................................252
9.3 案例问题解决 .................................................................................................253
9.4 知识与技能扩展——各种内排序方法的比较和选择 .................................256
课后习题 ..................................................................................................................257
上机实战 ..................................................................................................................258
参考文献 ........................................................................................................................ 260