资料结构与问题解法PDF电子书下载

第一部份 结构化程式设计与问题解决 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