第一部份 结构化程式设计与问题解决 2
第1章 结构化程式设计复习 2
1.1问题解决与程式设计 3
1.1-1何谓问题解决 3
1.1-2解决问题的工具 4
1.1-3何谓好的解题法 5
1.2程式设计问题摘要 7
1.2-1透过由上而下设计的模组化 8
1.2-2易修改性 11
1.2-3使用者介面 14
1.2-4防错的程式设计 15
1.2-5格局 23
1.2-6除错 30
1.3摘要 33
1.4注意事项 33
习题 34
专题 35
第2章 高阶PASCAL复习 38
2.1档案 39
2.1-1一般档案 42
2.1-2文字档案 53
2.2指标 61
2.3有关PASCAL的一些补充说明 75
2.4注意事项 77
2.5摘要 78
习题 79
专题 82
第3章 链结串列 83
3.1链结串列之程式设计 84
3.1-1从链结串列中删除一个特定节点 85
3.1-2将节点插入特定位置 87
3.1-3有序链结列之插入与删除程序 89
3.1-4虚拟首节点 99
3.1-5记忆体管理 101
3.1-6自档案中存取链结串列 105
3.2个案研究:存货管理 110
3.2-1存货问题之描述 110
3.2-2存货问题的解题法 111
3.2-3解题法之由上而下设计 112
3.2-4由下而上地发展程式 129
3.2-5程式之最后改良 132
3.3摘要 155
3.4注意事项 156
习题 156
专题 158
第二部份 递回——镜 162
第4章 递回简介 162
4.1递回解题法 163
重要概念 165
4.1-1阶乘 165
4.1-2字串反向印出 172
4.2计算 184
4.2-1整数的乘冪 184
4.2-2兔子的繁殖 188
4.3排列组合 191
4.3-1史波克先生的难题 191
4.3-2疯狂的科学家 193
4.4搜寻 195
4.4-1寻找阵列中最大的元素 195
4.4-2二元搜寻 196
4.4-3寻找阵列中第k小的元素 202
4.5递回与效率 205
4.6注意事项 207
4.7摘要 207
习题 207
第5章 以递回当解题工具 212
5.1问题处理 213
5.1-1汉诺塔 213
5.1-2排序 219
5.2定义 235
5.2-1基本文法 236
5.2-2两种简单的语言 238
5.2-3算术表示式 240
5.2-4更复杂的算术表示式 252
5.3递回与数学归纳法之关系 260
5.3-1递回阶乘函数之正确性 261
5.3-2汉诺塔的解题代价 262
5.4摘要 264
5.5注意事项 265
习题 265
第三部份 资料抽象化作为问题解决工具——墙 270
第6章 资料抽象化 270
6.1简介 271
6.2抽象资料型态 275
6.3 ADT的制作——资料结构 279
6.4以ADT发展程式的实例 285
6.5 ADT堆叠的制作 290
6.5-1 ADT堆叠的循序结构 291
6.5-2 ADT堆叠的链结结构 295
6.5-3不同结构方式间的转换 299
6.6摘要 301
6.7注意事项 301
习题 302
专题 304
第7章 堆叠 306
7.1再谈ADT堆叠 307
7.2 ADT堆叠的两种简单应用 309
7.3堆叠的复杂应用 312
7.3-1算术表示式 312
7.3-2圆形搜寻 326
7.4堆叠与递回之关系 345
7.5 ADT堆叠的衍化:可巡行堆叠 351
7.5-1运用双链结串列的结构 354
7.6摘要 361
7.7注意事项 362
习题 362
专题 364
第8章 队列 366
8.1 ADT队列 367
8.2 ADT队列的制作 367
8.2-1链结结构的ADT队列 368
8.2-2循序结构的ADT队列 371
8.3 ADT队列的应用 376
8.4位置导向的ADT总结 391
8.5摘要 393
8.6注意事项 393
习题 393
专题 395
第9章 ADT表格:线性与非线性结构 398
9.1 ADT表格 400
9.2保持整体观念 404
9.3线性结构:以资料串列制作ADT表格 405
9.3-1情境A:无特定顺序地插入与巡行 407
9.3-2情境B:有序情况下巡行 408
9.3-3情境C:有序情况下巡行与查索 410
9.3-4情境D:有序情况下巡行、插入与删除 412
9.4二元树 416
9.4-1制作 419
9.4-2巡行 420
9.4-3满树与完全树 426
9.5非线性结构:以二元搜寻树制作之ADT表格 432
9.6二元树的插入及删除操作 437
9.7二元搜寻树演算法之效率 443
9.8二元搜寻树结构之细节 445
9.9摘要 459
9.10注意事项 459
习题 460
第10章 ADT表格的演变 465
10.1 ADT优先队列 466
10.1-1完全树的循序表示 469
10.1-2锥叠 470
10.1-3以锥叠制作优先队列 470
10.2个案研究:录影带存货管理系统之改良 478
10.2-1修改先前的程式 480
10.2-2增加新的功能 494
10.3以多种结构管理资料 501
10.3-1观念 501
10.3-2双链结串列 504
10.4摘要 508
10.5注意事项 508
习题 508
专题 510
第四部份 资料管理之高级技巧 514
第11章 高阶ADT表格结构 514
11.1平衡搜寻树 515
11.2 AVL树 517
11.3 2-3树 519
11.3-1 2-3树的插入操作 525
11.3-2 2-3树的删除操作 530
11.4杂凑 538
11.5优良杂凑函数的要件 545
11.6注意事项 548
11.7摘要 548
习题 548
专题 551
第12章 外部记忆体资料的管理 552
12.1外部记忆体概观 553
12.2外部档案资料的排序 556
12.3外部表格的搜寻 563
12.3-1外部表格的索引 566
12.3-2外部杂凑 569
12.3-3 B-树 573
12.3-4巡行 582
12.3-5多重索引 584
12.4摘要 585
12.5注意事项 585
习题 586
专题 588
第13章 排序演算法比较 589
13.1如何分析演算法 590
13.1-1大小等级分析 591
13.1-2 Big O的观念 593
13.1-3保持整体观念 594
13.2四种排序演算法之比较 595
13.2-1插入排序 595
13.2-2快速排序 596
13.2-3合并排序 597
13.2-4锥叠排序 598
13.3摘要 603
13.4注意事项 603
习题 604