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