C程序设计的抽象思维PDF电子书下载

第一部分 预备知识第1章 ANSI C概述 2

1.1 什么是C 2

1.2 C程序的结构 4

1.2.1 注释 5

1.2.2 包含的库文件 5

1.2.3 程序级的定义 6

1.2.4 函数原型 6

1.2.5 主程序 6

1.2.6 函数定义 7

1.3 变量、值和类型 8

1.3.1 变量 8

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 表达式 13

1.4.1 优先级与结合性 14

1.4.2 表达式中的类型混合 15

1.4.3 整数除法和求余运算 15

1.4.4 类型转换 16

1.4.5 赋值运算符 16

1.4.6 递增与递减运算符 17

1.4.7 布尔运算符 18

1.5 语句 20

1.5.1 简单语句 20

1.5.2 块 20

1.5.3 if语句 21

1.5.4 switch语句 21

1.5.5 while语句 23

1.5.6 for语句 25

1.6 函数 26

1.6.1 返回函数结果 27

1.6.2 函数定义和原型 27

1.6.3 函数调用过程的机制 28

1.6.4 逐步求精 28

1.7 总结 28

1.8 复习题 29

1.9 编程练习 30

第2章 C的数据类型 34

2.1 枚举类型 34

2.1.1 枚举类型的内部表示 35

2.1.2 标量类型 36

2.1.3 理解typedef 36

2.2 数据和内存 37

2.2.1 位、字节、字 37

2.2.2 内存地址 38

2.3 指针 39

2.3.1 把地址当作数值 40

2.3.2 声明指针变量 40

2.3.3 基本的指针运算 41

2.3.4 特殊指针NULL 43

2.3.5 传递引用 43

2.4 数组 46

2.4.1 声明数组 46

2.4.2 数组选择 47

2.4.3 分配的空间和利用的空间 48

2.4.4 把数组作为参数 48

2.4.5 初始化数组 51

2.4.6 多维数组 52

2.5 指针和数组 53

2.5.1 指针运算 54

2.5.2 指针的自加和自减 56

2.5.3 指针和数组的关系 56

2.6 记录 58

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

2.6.2 声明结构变量 59

2.6.3 记录选择 59

2.6.4 初始化纪录 59

2.6.5 记录的指针 60

2.7 动态分配 61

2.7.1 类型void＊ 61

2.7.2 对内存限制的处理 62

2.7.3 动态数组 63

2.7.4 动态记录 64

2.8 总结 65

2.9 复习题 66

2.10 编程练习 68

第3章 库和接口 74

3.1 接口的概念 74

3.1.1 接口和实现 75

3.1.2 包和抽象 75

3.1.3 良好的接口设计规则 76

3.2 随机数字 76

3.2.1 random.h接口的结构 77

3.2.2 构造一个客户程序 80

3.2.3 ANSI中有关随机数字的函数 82

3.2.4 实现random.c 83

3.3 字符串 86

3.3.1 字符的底层表示 86

3.3.2 数据类型string 88

3.3.3 ANSI字符串库 89

3.3.4 接口strlib.h 92

3.4 标准的I/O库 98

3.4.1 数据文件 98

3.4.2 在C中使用文件 99

3.4.3 标准文件 100

3.4.4 字符I/O 100

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

3.4.6 更新文件 102

3.4.7 面向行的I/O 103

3.4.8 格式化的I/O 103

3.4.9 scanf函数 104

3.5 其他ANSI库 105

3.6 总结 107

3.7 复习题 107

3.8 编程练习 109

第二部分 递归和算法分析第4章 递归入门 116

4.1 一个简单的递归示例 116

4.2 阶乘函数 118

4.2.1 Fact的递归公式 118

4.2.2 追踪递归过程 119

4.2.3 递归跳跃的信任 122

4.3 费波那契函数 123

4.3.1 计算费波那契序列 123

4.3.2 增进实现递归的信心 125

4.3.3 递归实现的效率 125

4.3.4 不应该责备递归 126

4.4 其他递归示例 127

4.4.1 探测回文 128

4.4.2 二分查找 130

4.4.3 交互递归 131

4.5 递归的思考 133

4.5.1 保持整体观 133

4.5.2 避免常见的陷阱 133

4.6 总结 134

4.7 复习题 135

4.8 编程练习 137

第5章 递归过程 140

5.1 汉诺塔 140

5.1.1 分解问题 141

5.1.2 寻找递归策略 142

5.1.3 证实递归策略 143

5.1.4 编码解决方案 144

5.1.5 追踪递归过程 144

5.2 产生排列 148

5.3 递归的绘图应用 150

5.3.1 绘图库 150

5.3.2 电脑艺术示例 152

5.3.3 不规则碎片形 155

5.4 总结 159

5.5 复习题 160

5.6 编程练习 161

第6章 回溯算法 168

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

6.1.1 右手规则 168

6.1.2 寻找递归方法 169

6.1.3 识别简单情景 170

6.1.4 迷宫解决方案算法编码 171

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

6.2 回溯与对策 176

6.2.1 拿子游戏 177

6.2.2 一般化的双人游戏程序 183

6.2.3 最小最大策略 184

6.2.4 实现最小最大化算法 185

6.2.5 在具体的游戏中采用一般化策略 187

6.3 总结 199

6.4 复习题 199

6.5 编程练习 200

第7章 算法分析 206

7.1 排序问题 206

7.1.1 选择排序算法 207

7.1.2 性能的经验度量 208

7.1.3 分析选择排序的性能 209

7.2 计算复杂度 210

7.2.1 大O符号 210

7.2.2 大O的标准简化 211

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

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

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

7.2.6 大O的正式定义 214

7.3 递归帮助 215

7.3.1 分治策略的威力 215

7.3.2 合并两个数组 216

7.3.3 合并排序算法 216

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

7.3.5 比较N2和NlogN的性能 219

7.4 标准复杂度类型 220

7.5 快速排序算法 221

7.5.1 分割数组 223

7.5.2 分析快速排序的性能 225

7.6 数学归纳法 225

7.7 总结 227

7.8 复习题 228

7.9 编程练习 230

第三部分 数据抽象第8章 抽象数据类型 236

8.1 栈 236

8.1.1 栈的基本概念 237

8.1.2 栈和函数调用 237

8.1.3 栈和袖珍计算器 237

8.2 定义栈的ADT 238

8.2.1 定义栈抽象的类型 238

8.2.2 不透明类型 240

8.2.3 定义stack.h接口 240

8.3 在应用中使用栈 244

8.4 实现栈抽象 247

8.4.1 定义具体类型 247

8.4.2 实现栈操作 247

8.4.3 不透明类型的优点 249

8.4.4 改进stack.c的实现 250

8.5 定义一个scannerADT 251

8.5.1 封装状态的危险 252

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

8.5.3 实现扫描器抽象 256

8.6 总结 261

8.7 复习题 262

8.8 编程练习 263

第9章 效率与ADT 273

9.1 编辑器缓冲区的概念 273

9.2 定义缓冲区抽象 274

9.2.1 接口buffer.h中的函数 275

9.2.2 为编辑器应用编写代码 277

9.3 用数组实现编辑器 279

9.3.1 定义具体类型 279

9.3.2 实现缓冲区的操作 280

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

9.4 用栈实现编辑器 284

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

9.4.2 实现缓冲区的操作 284

9.4.3 比较计算复杂度 287

9.5 用链表实现编辑器 288

9.5.1 链表的概念 288

9.5.2 设计链表数据结构 289

9.5.3 使用链表表示缓冲区 290

9.5.4 链表缓冲区中的插入 291

9.5.5 链表缓冲区中的删除 292

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

9.5.7 链表的习惯用法 295

9.5.8 完成缓冲区实现 296

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

9.5.10 双向链表 300

9.5.11 时间-空间的权衡 300

9.6 总结 301

9.7 复习题 301

9.8 编程练习 302

第10章 线性结构 307

10.1 栈回顾 307

10.2 队列 313

10.2.1 接口queue.h的结构 313

10.2.2 基于数组的队列实现 316

10.2.3 队列的链表实现 320

10.3 使用队列的仿真 324

10.3.1 仿真与模型 324

10.3.2 排队模型 324

10.3.3 离散时间 325

10.3.4 仿真时间中的事件 325

10.3.5 实现仿真 325

10.4 总结 331

10.5 复习题 332

10.6 编程练习 333

第11章 符号表 338

11.1 定义符号表抽象 338

11.1.1 选择值和键的类型 339

11.1.2 表示未定义项 340

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

11.2 散列 342

11.2.1 实现散列表策略 342

11.2.2 选择散列函数 347

11.2.3 确定桶的数量 348

11.3 初级接口的限制 348

11.4 使用函数作为数据 350

11.4.1 一个一般测绘函数 351

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

11.4.3 实现PlotFunction 352

11.4.4 qsort函数 352

11.5 映射函数 356

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

11.5.2 实现MapSymbolTable 359

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

11.6 迭代器 361

11.6.1 使用迭代器 361

11.6.2 定义迭代器接口 362

11.6.3 实现符号表的迭代器抽象 363

11.7 命令分派表 366

11.8 总结 368

11.9 复习题 369

11.10 编程练习 370

第四部分 递归数据第12章 递归列表 376

12.1 链表的递归表述 377

12.2 定义抽象链表类型 378

12.2.1 不变类型 380

12.2.2 操纵链表结构的函数 381

12.2.3 连接多个链表 383

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

12.3 使用链表表示大整数 386

12.3.1 bigint.h接口 386

12.3.2 表示类型bigIntADT 388

12.3.3 实现bigint包 389

12.3.4 使用bigint.h包 394

12.4 总结 395

12.5 复习题 396

12.6 编程练习 397

第13章 树 400

13.1 家谱树 401

13.1.1 描述树的术语 401

13.1.2 树的递归特性 401

13.1.3 用C语言表示家谱树 402

13.2 二叉搜索树 403

13.2.1 使用二叉搜索树的底层动机 403

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

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

13.2.4 树的遍历 408

13.3 平衡树 409

13.3.1 树的平衡策略 410

13.3.2 举例说明AVL的思想 411

13.3.3 单旋转 412

13.3.4 双旋转 414

13.3.5 实现AVL算法 414

13.4 为二叉搜索树定义一般化接口 418

13.4.1 允许用户定义节点结构 421

13.4.2 一般化用作键的类型 424

13.4.3 删除节点 424

13.4.4 实现二叉搜索树包 425

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

13.5 总结 432

13.6 复习题 433

13.7 编程练习 435

第14章 表达式树 442

14.1 解释器概述 443

14.2 表达式的抽象结构 445

14.2.1 表达式的递归定义 445

14.2.2 多义性 446

14.2.3 表达式树 447

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

14.3 定义具体表达式类型 451

14.3.1 联合类型 451

14.3.2 使用标记的联合表示表达式 453

14.3.3 可视化具体表示 454

14.3.4 实现构建器和选择器函数 456

14.4 语法分析表达式 458

14.4.1 语法分析和语法 458

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

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

14.5 计算表达式 464

14.6 总结 467

14.7 复习题 467

14.8 编程练习 468

第15章 集合 479

15.1 为数学抽象的集合 479

15.1.1 成员资格 480

15.1.2 集合运算 480

15.1.3 集合恒等式 481

15.2 设计集合接口 482

15.2.1 定义元素类型 483

15.2.2 编写set.h接口 484

15.2.3 字符集合 488

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

15.3 实现集合包 490

15.4 设计多态迭代器 497

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

15.4.2 在迭代器实现中加入多态性 497

15.4.3 导出聚集类型 498

15.4.4 编码迭代器包 502

15.4.5 foreach的习惯用法 506

15.5 提高整型集合的效率 506

15.5.1 特征向量 507

15.5.2 压缩的位数组 507

15.5.3 位运算符 508

15.5.4 使用位操作符实现特征向量 510

15.5.5 实现高级集合操作 512

15.5.6 使用混合实现 513

15.6 总结 513

15.7 复习题 514

15.8 编程练习 517

第16章 图 521

16.1 图的结构 521

16.1.1 有向图和无向图 523

16.1.2 路径和环 524

16.1.3 连通性 524

16.2 图的实现策略 525

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

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

16.3 扩展图抽象 532

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

16.3.2 显式弧 532

16.3.3 迭代和图 533

16.3.4 分层抽象 534

16.3.5 基于集合的图接口 534

16.4 图的遍历 543

16.4.1 深度优先遍历 543

16.4.2 广度优先搜索 545

16.5 寻找最短路径 548

16.6 总结 554

16.7 复习题 555

16.8 编程练习 556

第17章 Java的未来 563

17.1 面向对象范例 563

17.1.1 面向对象编程的历史 564

17.1.2 对象、类和方法 565

17.1.3 类层次与继承 566

17.2 Java入门 567

17.2.1 Web结构 567

17.2.2 applet 568

17.2.3 执行Java applet 572

17.3 Java的结构 573

17.3.1 Java的语法 574

17.3.2 Java中的原子类型 575

17.3.3 定义新类 575

17.3.4 构造器方法 576

17.3.5 this关键字 577

17.3.6 定义方法 577

17.3.7 定义子类 579

17.4 Java中的预定义类 586

17.4.1 String类 586

17.4.2 Hashtable类 587

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

17.4.4 Vector类 590

17.4.5 Stack类 591

17.5 创建交互applet的工具 592

17.5.1 组件与容器 592

17.5.2 action方法 593

17.5.3 用于画图形的简单applet 594

17.5.4 更进一步 602

17.6 总结 602

17.7 复习题 602

17.8 编程练习 604