程序设计抽象思想 C语言描述PDF电子书下载

第Ⅰ部分 预备知识 1

第1章 ANSI C概述 1

1.1 什么是C 1

目录 1

1.2 C程序的结构 3

1.2.1 注释 4

1.2.2 库包含 5

1.2.3 程序级定义 5

1.2.4 函数原型 5

1.2.5 main程序 6

1.3 变量、值和类型 7

1.3.1 变量 7

1.2.6 函数定义 7

1.3.2 命名规则 8

1.3.3 局部变量和全局变量 9

1.3.4 数据类型的概念 9

1.3.5 整数类型 9

1.3.6 浮点类型 10

1.3.7 文本类型 11

1.3.8 布尔类型 12

1.3.9 简单的输入与输出 12

1.4 表达式 14

1.4.1 优先级与结合性 14

1.4.2 表达式中的类型混合 15

1.4.3 整数除法和求余运算符 16

1.4.5 赋值运算符 17

1.4.4 类型转换 17

1.4.6 递增与递减运算符 19

1.4.7 布尔运算符 20

1.5 语句 22

1.5.1 简单语句 22

1.5.2 块 22

1.5.3 if语句 23

1.5.4 switch语句 23

1.5.5 while语句 25

1.5.6 for语句 28

1.6 函数 29

1.6.1 返回函数结果 29

1.6.3 函数调用过程的机制 30

1.6.2 函数定义和原型 30

1.6.4 逐步求精 31

1.7 小结 31

1.8 复习题 32

1.9 编程练习 33

第2章 C的数据类型 38

2.1 枚举类型 38

2.1.1 枚举类型的内部表示 39

2.1.2 标量类型 40

2.1.3 理解typedef 41

2.2 数据和内存 41

2.2.1 位、字节、字 42

2.2.2 内存地址 42

2.3.1 把地址当作数值 44

2.3 指针 44

2.3.2 声明指针变量 45

2.3.3 基本的指针运算 45

2.3.4 特殊指针NULL 47

2.3.5 通过引用传递参数 48

2.4 数组 51

2.4.1 声明数组 51

2.4.2 数组选择 52

2.4.3 有效空间和已分配空间 53

2.4.4 作为参数传递数组 54

2.4.5 初始化数组 56

2.4.6 多维数组 57

2.5 指针和数组 59

2.5.1 指针运算 60

2.5.2 指针的自加和自减 62

2.5.3 指针和数组的关系 62

2.6 记录 64

2.6.1 定义一种新的结构类型 65

2.6.2 声明结构变量 66

2.6.3 记录选择 66

2.6.4 初始化纪录 66

2.6.5 记录的指针 67

2.7 动态分配 68

2.7.1 类型void 68

2.7.2 应对内存限制 70

2.7.3 动态数组 71

2.7.4 动态记录 72

2.8 小结 73

2.9 复习题 74

2.10 编程练习 76

第3章 库和接口 83

3.1 接口的概念 83

3.1.1 接口和实现 84

3.1.2 包和抽象 84

3.1.3 良好的接口设计规则 85

3.2 随机数字 85

3.2.1 random.h接口的结构 86

3.2.2 构建客户程序 89

3.2.3 有关随机数字的ANSI函数 91

3.2.4 实现random.c 93

3.3 字符串 96

3.3.1 字符串的底层表示 96

3.3.2 数据类型string 97

3.3.3 ANSI字符串库 98

3.3.4 接口strlib.h 102

3.4 标准的I/O库 108

3.4.1 数据文件 108

3.4.2 在C中使用文件 109

3.4.3 标准文件 110

3.4.4 字符I/O 110

3.4.5 从输入文件中重读字符 111

3.4.6 更新文件 112

3.4.7 面向行的I/O 113

3.4.8 格式化的I/O 114

3.4.9 scanf函数 115

3.5 其他ANSI库 116

3.6 小结 118

3.7 复习题 118

3.8 编程练习 120

第Ⅱ部分 递归和算法分析 127

第4章 递归入门 127

4.1 一个简单的递归示例 128

4.2 阶乘函数 129

4.2.1 Fact的递归公式 130

4.2.2 追踪递归过程 130

4.3 费波那契函数 134

4.2.3 递归跳跃的信任 134

4.3.1 计算费波那契序列 135

4.3.2 增进实现递归的信心 136

4.3.3 递归实现的效率 137

4.3.4 不应该责备递归 138

4.4 其他递归示例 139

4.4.1 探测回文 139

4.4.2 二分查找 142

4.4.3 交互递归 143

4.5 以递归的方式思考 144

4.5.1 保持整体观 145

4.5.2 避免常见的错误 145

4.6 小结 146

4.7 复习题 147

4.8 编程练习 149

第5章 递归过程 152

5.1 汉诺塔 152

5.1.1 分解问题 153

5.1.2 寻找递归策略 153

5.1.3 验证递归策略 155

5.1.4 解决方案的编码 156

5.1.5 追踪递归过程 156

5.2 产生排列 160

5.3 递归在绘图中的应用 162

5.3.1 图形库 162

5.3.2 电脑艺术示例 165

5.3.3 不规则碎片形 169

5.4 小结 173

5.5 复习题 174

5.6 编程练习 175

第6章 回溯算法 183

6.1 用递归回溯解决迷宫问题 183

6.1.1 右手规则 183

6.1.2 寻找递归方法 184

6.1.3 识别简单情景 185

6.1.4 编写迷宫解决方案算法 186

6.1.5 确信解决方案可以正确运行 190

6.2 回溯与游戏 192

6.2.1 拿子游戏 193

6.2.2 常规化的双人游戏程序 199

6.2.3 最小最大策略 200

6.2.4 实现最小最大化算法 202

6.2.5 在具体的游戏中采用常规策略 204

6.3 小结 216

6.4 复习题 217

6.5 编程练习 218

第7章 算法分析 225

7.1 排序问题 225

7.1.1 选择排序算法 226

7.1.2 性能的经验度量 227

7.1.3 分析选择排序的性能 228

7.2.2 大O的标准简化 230

7.2.1 大O符号 230

7.2 计算复杂度 230

7.2.3 排序算法的计算复杂度 231

7.2.4 根据代码结构预测计算复杂度 232

7.2.5 最差情况复杂度与平均情况复杂度 233

7.2.6 大O的正式定义 233

7.3 递归帮助 235

7.3.1 分治策略的威力 235

7.3.2 合并两个数组 236

7.3.3 合并排序算法 237

7.3.4 合并排序的计算复杂度 239

7.3.5 比较N2和NlogN的性能 240

7.4 标准复杂度类型 241

7.5 快速排序算法 242

7.5.1 分割数组 244

7.5.2 分析快速排序的性能 246

7.6 数学归纳法 247

7.7 小结 250

7.8 复习题 250

7.9 编程练习 252

第Ⅲ部分 数据抽象 257

第8章 抽象数据类型 257

8.1 堆栈 258

8.1.1 基本的堆栈比喻 258

8.1.2 堆栈和函数调用 258

8.2 定义堆栈的ADT 259

8.1.3 堆栈和袖珍计算器 259

8.2.1 定义堆栈抽象的类型 260

8.2.2 不透明类型 261

8.2.3 定义stack.h接口 262

8.3 在应用程序中使用堆栈 265

8.4 实现堆栈抽象 269

8.4.1 定义具体类型 269

8.4.2 实现堆栈操作 269

8.4.3 不透明类型的优点 271

8.4.4 改进stack.c的实现 272

8.5 定义扫描器ADT 273

8.5.1 封装状态的危险 274

8.5.2 抽象数据类型作为封装状态的替代 274

8.5.3 实现扫描器抽象 279

8.6 小结 283

8.7 复习题 284

8.8 编程练习 285

第9章 效率与ADT 297

9.1 编辑器缓冲区的概念 297

9.2 定义缓冲区抽象 298

9.2.1 接口buffer.h中的函数 299

9.2.2 为编辑器应用程序编写代码 301

9.3 用数组实现编辑器 303

9.3.1 定义具体类型 303

9.3.2 实现缓冲区的操作 304

9.3.3 数组实现的计算复杂度 308

9.4 用堆栈实现编辑器 309

9.4.1 定义基于堆栈的缓冲区的具体结构 310

9.4.2 实现缓冲区的操作 310

9.4.3 比较计算复杂度 313

9.5 用链表实现编辑器 313

9.5.1 链表的概念 314

9.5.2 设计链表数据结构 314

9.5.3 使用链表表示缓冲区 316

9.5.4 链表缓冲区中的插入 317

9.5.5 链表缓冲区中的删除 320

9.5.6 链表表示中的光标移动 321

9.5.7 链表的习惯用法 323

9.5.8 完成缓冲区实现 324

9.5.10 双向链表 328

9.5.9 链表缓冲区的计算复杂度 328

9.5.11 时间-空间的权衡 329

9.6 小结 329

9.7 复习题 330

9.8 编程练习 331

第10章 线性结构 337

10.1 堆栈回顾 337

10.2 队列 344

10.2.1 接口queue.h的结构 344

10.2.2 基于数组的队列实现 347

10.2.3 队列的链表实现 351

10.3 使用队列的仿真 355

10.3.3 离散时间 356

10.3.2 排队模型 356

10.3.1 仿真与模型 356

10.3.4 仿真时间中的事件 357

10.3.5 实现仿真 357

10.4 小结 364

10.5 复习题 365

10.6 编程练习 366

第11章 符号表 371

11.1 定义符号表抽象 371

11.1.1 选择值和键的类型 372

11.1.2 表示未定义项 373

11.1.3 符号表接口的初始版本 373

11.2 散列 375

11.2.1 实现散列表策略 375

11.2.2 选择散列函数 380

11.2.3 确定桶的数量 381

11.3 初级接口的限制 382

11.4 使用函数作为数据 384

11.4.1 通用绘图函数 384

11.4.2 声明函数指针与函数类 385

11.4.3 实现PlotFunction 386

11.4.4 qsort函数 387

11.5 映射函数 391

11.5.1 映射符号表中的所有项 391

11.5.2 实现MapSymbolTable 394

11.5.3 向回调函数传递客户数据 395

11.6.1 使用迭代器 396

11.6 迭代器 396

11.6.2 定义迭代器接口 397

11.6.3 实现针对符号表的迭代器抽象 398

11.7 命令分派表 401

11.8 小结 404

11.9 复习题 405

11.10 编程练习 406

第Ⅳ部分 递归数据 411

第12章 递归链表 411

12.1 链表的递归表述 412

12.2 定义抽象链表类型 413

12.2.1 不变类型 416

12.2.2 操纵链表结构的函数 417

12.2.3 连接多个链表 419

12.2.4 不变类型间的内部共享 421

12.3 使用链表表示大整数 422

12.3.1 bigint.h接口 423

12.3.2 表示类型bigIntADT 425

12.3.3 实现bigint包 426

12.3.4 使用bigint.h包 430

12.4 小结 432

12.5 复习题 433

12.6 编程练习 434

第13章 树 438

13.1 家谱树 438

13.1.2 树的递归特性 439

13.1.1 描述树的术语 439

13.1.3 用C语言表示家谱树 440

13.2 二叉搜索树 441

1 3.2.1 使用二叉搜索树的底层动机 442

13.2.2 在二叉搜索树中查找节点 443

13.2.3 在二叉搜索树中插入新节点 444

13.2.4 树的遍历 447

13.3 平衡树 449

13.3.1 树的平衡策略 450

13.3.2 举例说明AVL的思想 451

13.3.3 单旋转 452

13.3.4 双旋转 454

13.3.5 实现AVL算法 455

13.4 为二叉搜索树定义通用接口 458

13.4.1 允许客户定义节点结构 462

13.4.2 泛化键的类型 465

13.4.3 删除节点 465

13.4.4 实现二叉搜索树包 467

13.4.5 使用二叉树实现symtab.h接口 472

13.5 小结 474

13.6 复习题 474

13.7 编程练习 477

第14章 表达式树 484

14.1 解释器概述 484

14.2 表达式的抽象结构 487

14.2.1 表达式的递归定义 487

14.2.2 歧义性 488

14.2.3 表达式树 489

14.2.4 定义表达式的抽象接口 490

14.3 定义具体表达式类型 494

14.3.1 联合类型 494

14.3.2 用带标记联合表示表达式 496

14.3.3 可视化具体表示 498

14.3.4 实现构造器和选择器函数 500

14.4 分析表达式 502

14.4.1 语法分析和语法 502

14.4.2 不考虑优先级的语法分析 503

14.4.3 在语法分析器中加入优先级 507

14.5 计算表达式 509

14.6 小结 511

14.7 复习题 512

14.8 编程练习 513

第15章 集合 525

15.1 作为数学抽象的集合 525

15.1.1 成员资格 526

15.1.2 集合运算 526

15.1.3 集合恒等式 527

15.2 设计集合接口 529

15.2.1 定义元素类型 529

15.2.2 编写set.h接口 531

15.2.3 字符集合 534

15.2.4 使用指针集合来避免重复 535

15.3 实现集合包 537

15.4.1 泛化迭代器函数的原型 544

15.4 设计多态迭代器 544

15.4.2 在迭代器中实现多态性 545

15.4.3 导出聚集类型 546

15.4.4 编码迭代器包 550

15.4.5 foreach的习惯用法 554

15.5 提高整数集合的效率 554

15.5.1 特征向量 555

15.5.2 压缩的位数组 555

15.5.3 位运算符 556

15.5.4 使用位运算符实现特征向量 559

15.5.5 实现高级集合操作 561

15.5.6 使用混合实现 561

15.6 小结 561

15.7 复习题 563

15.8 编程练习 565

第16章 图 570

16.1 图的结构 570

16.1.1 有向图和无向图 572

16.1.2 路径和环 573

16.1.3 连通性 573

16.2 图的实现策略 574

16.2.1 使用邻接列表表示连接 575

16.2.2 使用邻接矩阵表示连接 578

16.3 扩展图抽象 581

16.3.1 将数据与节点和图关联 581

16.3.2 显式弧 581

16.3.3 迭代和图 582

16.3.4 分层抽象 583

16.3.5 基于集合的图接口 584

16.4 图的遍历 592

16.4.1 深度优先遍历 593

16.4.2 广度优先搜索 595

16.5 寻找最短路径 597

16.6 小结 604

16.7 复习题 605

16.8 编程练习 607

第17章 展望Java 614

17.1 面向对象范式 614

17.1.1 面向对象编程的历史 615

17.1.3 类层次结构与继承 616

17.1.2 对象、类和方法 616

17.2 Java简介 618

17.2.1 Web结构 618

17.2.2 applet 619

17.2.3 执行Java applet 623

17.3 Java结构 624

17.3.1 Java的语法 625

17.3.2 Java中的原子类型 626

17.3.3 定义一个新类 626

17.3.4 构造器方法 628

17.3.5 this关键字 628

17.3.6 定义方法 629

17.3.7 定义子类 631

17.4.1 String类 637

17.4 Java中的预定义类 637

17.4.2 Hashtable类 638

17.4.3 原子类型的对象包装器 641

17.4.4 Vector类 641

17.4.5 Stack类 643

17.5 创建交互式applet的工具 644

17.5.1 组件与容器 644

17.5.2 action方法 645

17.5.3 用于绘制简单图形的applet 646

17.5.4 更进一步 654

17.6 小结 654

17.8 复习题 654

17.9 编程练习 656