本书全面介绍了数据结构的基础内容，帮助学生深入了解软件工程的思想和技术。学生还可以通过对一些高级编程概念（如接口、抽象和封装）的了解，为进一步深入学习高级编程知识打下坚实的基础。本书观点清晰明了、语言风格鲜明独特，深入浅出地介绍了一些高级主题。 本书特色： ◆介绍了多个库包，可用于简化编程流程，使学生可以专注于高层次理论问题的研究，避免了C语言编程的繁琐细节； ◆详细讨论了递归编程的用法，包括大量难度各异的编程示例和练习，如简单的递归函数，分析双人游戏的最小最大(minimax)策略，等等； ◆帮助读者培养编写健壮、可重用代码的良好编程习惯 。 第Ⅰ部分 预备知识 1 第1章 ANSI C概述 1 1.1 什么是C 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.2.6 函数定义 7 1.3 变量、值和类型 7 1.3.1 变量 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.4 类型转换 17 1.4.5 赋值运算符 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.2 函数定义和原型 30 1.6.3 函数调用过程的机制 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 指针 44 2.3.1 把地址当作数值 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.2.3 递归跳跃的信任 134 4.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 计算复杂度 230 7.2.1 大O符号 230 7.2.2 大O的标准简化 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.1.3 堆栈和袖珍计算器 259 8.2 定义堆栈的ADT 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.9 链表缓冲区的计算复杂度 328 9.5.10 双向链表 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.1 仿真与模型 356 10.3.2 排队模型 356 10.3.3 离散时间 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 迭代器 396 11.6.1 使用迭代器 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.1 描述树的术语 439 13.1.2 树的递归特性 439 13.1.3 用C语言表示家谱树 440 13.2 二叉搜索树 441 13.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 设计多态迭代器 544 15.4.1 泛化迭代器函数的原型 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.2 对象、类和方法 616 17.1.3 类层次结构与继承 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 Java中的预定义类 637 17.4.1 String类 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 2.1 注释 4 1.2.2 库包含 5 1.2.3 程序级定义 5 1.2.4 函数原型 5 1.2.5 main程序 6 1.2.6 函数定义 7 1.3 变量、值和类型 7 1.3.1 变量 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.4 类型转换 17 1.4.5 赋值运算符 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.2 函数定义和原型 30 1.6.3 函数调用过程的机制 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 指针 44 2.3.1 把地址当作数值 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.2.3 递归跳跃的信任 134 4.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 计算复杂度 230 7.2.1 大O符号 230 7.2.2 大O的标准简化 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.1.3 堆栈和袖珍计算器 259 8.2 定义堆栈的ADT 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.9 链表缓冲区的计算复杂度 328 9.5.10 双向链表 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.1 仿真与模型 356 10.3.2 排队模型 356 10.3.3 离散时间 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 迭代器 396 11.6.1 使用迭代器 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.1 描述树的术语 439 13.1.2 树的递归特性 439 13.1.3 用C语言表示家谱树 440 13.2 二叉搜索树 441 13.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 设计多态迭代器 544 15.4.1 泛化迭代器函数的原型 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.2 对象、类和方法 616 17.1.3 类层次结构与继承 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 Java中的预定义类 637 17.4.1 String类 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