《资料结构与问题解法》

第一部份结构化程式设计与问题解决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.5ADT堆叠的制作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.5ADT堆叠的衍化：可巡行堆叠351

7.5-1运用双链结串列的结构354

7.6摘要361

7.7注意事项362

习题362

专题364

第8章队列366

8.1 ADT队列367

8.2ADT队列的制作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.1ADT优先队列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.32-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-3B-树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-2Big 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