程序设计抽象思想 C语言描述PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第Ⅰ部分 预备知识1

第1章 ANSI C概述1

1.1 什么是C1

目录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 理解typedef41

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 特殊指针NULL47

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 类型void68

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.c93

3.3 字符串96

3.3.1 字符串的底层表示96

3.3.2 数据类型string97

3.3.3 ANSI字符串库98

3.3.4 接口strlib.h102

3.4 标准的I/O库108

3.4.1 数据文件108

3.4.2 在C中使用文件109

3.4.3 标准文件110

3.4.4 字符I/O110

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

3.4.6 更新文件112

3.4.7 面向行的I/O113

3.4.8 格式化的I/O114

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 定义堆栈的ADT259

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 定义扫描器ADT273

8.5.1 封装状态的危险274

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

8.5.3 实现扫描器抽象279

8.6 小结283

8.7 复习题284

8.8 编程练习285

第9章 效率与ADT297

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 实现PlotFunction386

11.4.4 qsort函数387

11.5 映射函数391

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

11.5.2 实现MapSymbolTable394

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 表示类型bigIntADT425

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章 展望Java614

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 applet619

17.2.3 执行Java applet623

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 用于绘制简单图形的applet646

17.5.4 更进一步654

17.6 小结654

17.8 复习题654

17.9 编程练习656