目 录
第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
