《数据结构与程序设计——C语言(第二版)》 - 清华大学出版社第五事业部

目    录
第1章  编程原则	1
1.1  引言	1
1.2  Life游戏	3
1.2.1  Life游戏规则	3
1.2.2  示例	3
1.2.3  解决方案	5
1.2.4  Life游戏主程序	5
1.3  编程风格	9
1.3.1  命名	9
1.3.2  文档及其格式	10
1.3.3  程序的细化和模块化	11
1.3.4  小节练习	13
1.4  编码、测试及进一步细化	15
1.4.1  占位程序	15
1.4.2  计算相邻元胞的数目	16
1.4.3  输入和输出	17
1.4.4  驱动程序	20
1.4.5  程序的跟踪	21
1.4.6  测试程序的原则	22
1.4.7  小节练习	24
1.4.8  编程项目	24
1.5  注意事项	25
1.6  复习题	26
1.7  参考文献	26
1.7.1  C语言	26
1.7.2  编程原则	27
1.7.3  Life游戏	27
第2章  软件工程介绍	28
2.1  程序维护	28
2.1.1  Life程序回顾	28
2.1.2  关于Life程序的新起点和新方法	30
2.1.3  小节练习	31
2.1.4  编程项目	32
2.2  算法研究：Life程序的第二个版本	32
2.2.1  列表：数据结构的说明	32
2.2.2  主程序	35
2.2.3  信息隐藏	38
2.2.4  细化：子程序的开发	38
2.2.5  算法的验证	41
2.2.6  小节练习	43
2.3  编码	43
2.3.1  列表函数	44
2.3.2  错误处理	45
2.3.3  演示和测试	46
2.3.4  小节练习	49
2.3.5  编程项目	50
2.4  Life函数的编码	50
2.4.1  Vivify函数	50
2.4.2  AddNeighbors函数	51
2.4.3  混合函数	52
2.4.4  初始化	52
2.4.5  编程项目	53
2.5  程序分析与比较	53
2.5.1  语句数	53
2.5.2  比较	54
2.5.3  时间和空间的平衡	55
2.5.4  小节练习	55
2.5.5  编程项目	55
2.6  总结和展望	55
2.6.1  Life 游戏	56
2.6.2  程序设计	57
2.6.3  C语言	58
2.6.4  编程项目	59
2.7  注意事项	60
2.8  复习题	61
2.9  参考文献	61
2.9.1  软件工程	61
2.9.2  算法验证	62
2.9.3  问题解决	62
第3章  堆栈和递归	63
3.1  堆栈	63
3.1.1  引言	63
3.1.2  第一个示例：线性颠倒	64
3.1.3  信息隐藏	65
3.1.4  堆栈的说明	65
3.1.5  堆栈的实现	67
3.1.6  链接堆栈	69
3.1.7  小节练习	72
3.1.8  编程项目	73
3.2  递归	74
3.2.1  子程序的堆栈图解	74
3.2.2  子程序调用树	74
3.2.3  阶乘：一个递归定义	76
3.2.4  分而治之：汉诺(HANOI)塔	77
3.2.5  小节练习	82
3.2.6  编程项目	82
3.3  回溯：推迟工作	83
3.3.1  解决8王后难题	83
3.3.2  示例：4王后	84
3.3.3  回溯	85
3.3.4  细化：选择数据结构	86
3.3.5  回溯分析	88
3.3.6  小节练习	89
3.3.7  编程项目	90
3.4  递归法则	90
3.4.1  设计递归算法	90
3.4.2  递归如何工作	91
3.4.3  尾部递归	94
3.4.4  何时不使用递归	96
3.4.5  指南和总结	100
3.4.6  小节练习	100
3.5  注意事项	101
3.6  复习题	102
3.7  参考文献	103
第4章  队列和链表	104
4.1  定义	104
4.2  队列的实现	107
4.3  C语言中的环形队列	110
4.3.1  小节练习	112
4.3.2  编程项目	113
4.4  队列的应用：模拟	114
4.4.1  引言	114
4.4.2  机场的模拟	114
4.4.3  主程序	116
4.4.4  模拟的步骤	118
4.4.5  伪随机数	121
4.4.6  示例结果	123
4.4.7  编程项目	125
4.5  指针和链表	126
4.5.1  引言和综述	126
4.5.2  指针和C语言中的动态内存	128
4.5.3  链表基础	132
4.5.4  小节练习	133
4.6  链接队列	134
4.6.1  小节练习	136
4.6.2  编程项目	137
4.7  应用：多项式算术	137
4.7.1  项目的目的	137
4.7.2  主程序	138
4.7.3  数据结构及其实现	142
4.7.4  读取和写出多项式	143
4.7.5  多项式加法	145
4.7.6  完成项目	147
4.7.7  小节练习	147
4.7.8  编程项目	148
4.8  抽象数据类型及其实现	149
4.8.1  引言	149
4.8.2  通用定义	150
4.8.3  数据说明的细化	152
4.8.4  小节练习	153
4.9  注意事项	153
4.10  复习题	154
4.11  参考文献	154

第5章  通用列表	156
5.1  列表说明	156
5.2  列表的实现	158
5.2.1  连续实现	158
5.2.2  简单的链接实现	159
5.2.3  变更：保持当前位置	163
5.2.4  双向链表	164
5.2.5  实现的比较	166
5.2.6  小节练习	167
5.2.7  编程项目	168
5.3  字符串	168
5.4  应用：文本编辑器	170
5.4.1  说明	171
5.4.2  实现	171
5.4.3　编程项目	178
5.5  数组中的链表	178
5.5.1  方法	179
5.5.2  操作：空间管理	180
5.5.3  其他操作	183
5.5.4  链表的变化	184
5.5.5  小节练习	184
5.6  排列	186
5.6.1  思想	187
5.6.2  细化	187
5.6.3  通用函数	188
5.6.4  数据结构：优化	188
5.6.5  最终的程序	189
5.6.6  编程项目	191
5.7  注意事项	191
5.8  复习题	192
5.9  参考文献	192
第6章  搜索	193
6.1  搜索：介绍及其表示	193
6.1.1  键	193
6.1.2  分析	193
6.1.3  外部搜索和内部搜索	194
6.1.4  C语言实现	194
6.1.5  参数	194
6.2  顺序搜索	195
6.2.1  算法及函数	195
6.2.2  算法分析	196
6.2.3  测试	197
6.2.4  小节练习	199
6.2.5  编程项目	200
6.3  寄物处：项目	201
6.3.1  介绍和说明	201
6.3.2  演示及测试程序	203
6.3.3  编程项目	205
6.4  二叉搜索	206
6.4.1  算法研究	207
6.4.2  忽略版本	208
6.4.3  识别等式	210
6.4.4  小节练习	211
6.4.5  编程项目	212
6.5  比较树	212
6.5.1  分析n=10的情况	213
6.5.2  算法推广	215
6.5.3  方法的比较	218
6.5.4  普遍关系	219
6.5.5  小节练习	220
6.5.6  编程项目	220
6.6  下限	220
6.6.1  优化程序	220
6.6.2  任意搜索算法	221
6.6.3  观察2-树	221
6.6.4  搜索下限	223
6.6.5  其他的搜索算法	223
6.6.6  小节练习	224
6.6.7  编程项目	224
6.7  渐近线	224
6.7.1  介绍	224
6.7.2  Big-O表示法	225
6.7.3  Big-O表示法的不精确性	227
6.7.4  通用函数的排序	228
6.7.5  小节练习	229
6.7.6  编程项目	229
6.8  注意事项	229
6.9  复习题	230
6.10  参考文献	230
第7章  排序	232
7.1  介绍和符号	232
7.2  插入排序	233
7.2.1  顺序列表	233
7.2.2  通常的插入排序	234
7.2.3  链接版本	236
7.2.4  分析	237
7.2.5  小节练习	238
7.2.6  编程项目	239
7.3  选择排序	240
7.3.1  算法	240
7.3.2  连续实现	241
7.3.3  分析	242
7.3.4  比较	243
7.3.5  小节练习	243
7.3.6  编程项目	244
7.4  希尔排序	244
7.4.1  小节练习	246
7.4.2  编程项目	246
7.5  下限	246
7.5.1  小节练习	248
7.5.2  编程项目	248
7.6  “分而治之”排序	249
7.6.1  主要思想	249
7.6.2  示例	250
7.6.3  小节练习	253
7.7  链表的归并排序	254
7.7.1  函数	254
7.7.2  合并分析	256
7.7.3  小节练习	258
7.7.4  编程项目	259
7.8  连续列表的快速排序	260
7.8.1  主函数	260
7.8.2  列表的划分	261
7.8.3  快速排序分析	263
7.8.4  快速排序的平均情形分析	265
7.8.5  与归并排序的比较	266
7.8.6  小节练习	267
7.8.7  编程项目	269
7.9  堆和堆排序	269
7.9.1  2-树的列表	269
7.9.2  堆排序	271
7.9.3  堆排序分析	273
7.9.4  优先级队列	274
7.9.5  小节练习	275
7.9.6  编程项目	276
7.10  回顾：方法的比较	276
7.10.1  使用的存储空间	276
7.10.2  计算机时间	276
7.10.3  编程量	276
7.10.4  统计分析	277
7.10.5  实验测试	277
7.10.6  小节练习	277
7.11  注意事项	279
7.12  复习题	279
7.13  参考文献	280
第8章  表和信息检索	282
8.1  引言：突破lg n障碍	282
8.2  矩形数组	283
8.2.1  行优先和列优先顺序	283
8.2.2  下标矩形数组	283
8.2.3  访问表	284
8.2.4  小节练习	284
8.3  各种形状的表	285
8.3.1  三角表	285
8.3.2  不规则表	286
8.3.3  反向表	287
8.3.4  小节练习	288
8.3.5  编程项目	289
8.4  表：一种新的抽象数据类型	289
8.4.1  函数	289
8.4.2  抽象数据类型	290
8.4.3  实现	290
8.4.4  比较	291
8.5  应用：基数排序	291
8.5.1  思想	292
8.5.2  实现	292
8.5.3  分析	295
8.5.4  小节练习	295
8.5.5  编程项目	295
8.6  散列	296
8.6.1  稀疏表	296
8.6.2  选择散列函数	297
8.6.3  利用开放寻址的解决方案	299
8.6.4  冲突的链式解决方案	303
8.6.5  小节练习	305
8.6.6  编程项目	306
8.7  散列分析	307
8.7.1  一个数学娱乐问题的分析	307
8.7.2  计数搜索次数	307
8.7.3  链式方式的分析	308
8.7.4  开放寻址方式的分析	308
8.7.5  理论比较	309
8.7.6  经验比较	310
8.7.7  小节练习	311
8.7.8  编程项目	312
8.8  总结：方法的比较	312
8.9  应用：回顾Life游戏	312
8.9.1  算法的选择	313
8.9.2  数据结构的声明	313
8.9.3  主程序	314
8.9.4  函数	315
8.9.5  编程项目	318
8.10  注意事项	319
8.11  复习题	319
8.12  参考文献	320

第9章  二叉树	321
9.1  二叉树的介绍	321
9.1.1  定义	321
9.1.2  二叉树的遍历	323
9.1.3  二叉树的链接实现	327
9.1.4  小节练习	329
9.2  二叉搜索树	331
9.2.1  顺序列表和实现	332
9.2.2  树搜索	333
9.2.3  二叉搜索树的插入	336
9.2.4  树排序	338
9.2.5  二叉搜索树的删除	339
9.2.6  小节练习	342
9.2.7  编程项目	343
9.3  构建二叉搜索树	346
9.3.1  开始构建	347
9.3.2  声明和主函数	347
9.3.3  插入节点	348
9.3.4  完成任务	349
9.3.5  评估	350
9.3.6  随机搜索树和优化	351
9.3.7  小节练习	352
9.4  高度平衡：AVL树	353
9.4.1  定义	353
9.4.2  节点的插入	354
9.4.3  节点的删除	361
9.4.4  AVL树的高度	363
9.4.5  小节练习	364
9.4.6  编程项目	365
9.5  分裂树：一个自调整数据结构	366
9.5.1  引言	366
9.5.2  分裂步骤	367
9.5.3  分裂算法	369
9.5.4  平摊算法分析：介绍	372
9.5.5  分裂的平摊分析	375
9.5.6  小节练习	379
9.5.7  编程项目	380
9.6  注意事项	380
9.7  复习题	381
9.8  参考文献	382
第10章  多路径树	384
10.1  果园、树和二叉树	384
10.1.1  树的分类	384
10.1.2  顺序树	386
10.1.3  森林和果园	387
10.1.4  形式映射	388
10.1.5  旋转	389
10.1.6  总结	389
10.1.7  小节练习	389
10.2  字典搜索树：trie	391
10.2.1  trie	391
10.2.2  键的搜索	392
10.2.3  C语言算法	392
10.2.4  trie中的插入	393
10.2.5  trie中的删除	394
10.2.6  trie的评论	395
10.2.7  小节练习	395
10.2.8  编程项目	395
10.3  外部搜索：B-树	396
10.3.1  访问时间	396
10.3.2  多路搜索树	396
10.3.3  多路平衡树	397
10.3.4  B-树的插入	397
10.3.5  C语言算法：搜索和插入	399
10.3.6  B-树中的删除	404
10.3.7  小节练习	410
10.3.8  编程项目	411
10.4  红黑树	412
10.4.1  引言	412
10.4.2  定义和分析	412
10.4.3  插入	414
10.4.4  插入的C语言表示	416
10.4.5  小节练习	419
10.4.6  编程项目	419
10.5  树结构程序：游戏中的预测	419
10.5.1  游戏树	419
10.5.2  极大极小方法	420
10.5.3  算法开发	421
10.5.4  细化	422
10.5.5  小节练习	423
10.5.6  编程项目	424
10.6  注意事项	424
10.7  复习题	425
10.8  参考文献	426
第11章  图	427
11.1  数学背景	427
11.1.1  定义和示例	427
11.1.2  无向图	428
11.1.3  有向图	428
11.2  计算机表示	429
11.3  图的遍历	432
11.3.1  方法	432
11.3.2  深度优先算法	433
11.3.3  宽度优先算法	434
11.4  拓扑排序	435
11.4.1  问题	435
11.4.2  深度优先算法	436
11.4.3  宽度优先算法	437
11.5  寻找最短路径的算法	439
11.5.1  问题	439
11.5.2  方法	440
11.5.3  示例	441
11.5.4  实现	442
11.6  作为数据结构的图	443
11.6.1  小节练习	444
11.6.2  编程项目	444
11.7  注意事项	445
11.8  复习题	445
11.9  参考文献	445
第12章  案例分析：波兰表示法	447
12.1  问题	447
12.2  思想	449
12.2.1  表达式树	449
12.2.2  波兰表示法	450
12.2.3  C语言方法	451
12.2.4  小节练习	451
12.3  波兰表达式的求值	452
12.3.1  前缀表达式的求值	452
12.3.2  C语言约定	453
12.3.3  前缀式求值的C函数	453
12.3.4  后缀表达式的求值	454
12.3.5  程序的证明：统计堆栈的入口数	455
12.3.6  后缀表达式的递归求值	458
12.3.7  小节练习	460
12.4  从中缀式转换为波兰式	461
12.4.1  小节练习	466
12.4.2  编程项目	466
12.5  交互式表达式求值程序	467
12.5.1  总体结构	467
12.5.2  数据的表示方法	469
12.5.3  初始化和辅助任务	471
12.5.4  表达式的转换	474
12.5.5  求解表达式的值	482
12.5.6  绘制表达式的图形	483
12.5.7  小节练习	485
12.5.8  编程项目	485
12.6  参考文献	485
附录A  数学方法	487
附录B  递归的消除	505
附录C  C语言介绍	528