C++数据抽象和问题求解

第1章 数据抽象：墙 11.1 面向对象的概念 21.1.1 面向对象分析与设计 21.1.2 面向对象解决方案的特征 31.2 获得更好的解决方案 41.2.1 内聚 51.2.2 耦合 51.3 规范 61.3.1 操作契约 71.3.2 特殊情况 81.3.3 抽象 91.3.4 信息隐藏 101.3.5 最小且完整的接口 111.4 抽象数据类型 121.4.1 设计ADT 14

第1章 数据抽象：墙 11.1 面向对象的概念 21.1.1 面向对象分析与设计 21.1.2 面向对象解决方案的特征 31.2 获得更好的解决方案 41.2.1 内聚 51.2.2 耦合 51.3 规范 61.3.1 操作契约 71.3.2 特殊情况 81.3.3 抽象 91.3.4 信息隐藏 101.3.5 最小且完整的接口 111.4 抽象数据类型 121.4.1 设计ADT 141.4.2 涉及其他ADT的ADT 171.5 ADT包 181.5.1 确定行为 181.5.2 指定数据和操作 191.5.3 ADT的模板接口 221.5.4 使用ADT包 24C 片段1 C 类 29C1.1 待解决的问题 30C1.1.1 私有数据字段 31C1.1.2 构造函数和析构函数 32C1.1.3 方法 32C1.1.4 防止编译错误 33C1.2 实现解决方案 34C1.3 模板 35C1.4 继承 37C1.4.1 基类和派生类 38C1.4.2 重写基类方法 40C1.5 虚方法和抽象类 42C1.5.1 虚方法 42C1.5.2 抽象类 43第2章 递归：镜子 452.1 递归解决方案 462.2 返回值的递归 482.2.1 递归值函数：n的阶乘 492.2.2 箱式跟踪 522.3 执行动作的递归 552.4 递归与数组 622.4.1 逆置数组项 632.4.2 折半查找 642.4.3 查找数组中的最大值 682.4.4 查找数组中第k个最小值 692.5 组织数据 712.6 更多示例 752.6.1 Fibonacci数列(兔子繁殖) 752.6.2 组织游行队伍 782.6.3 从n个事物中选出k个 792.7 递归和效率 81第3章 基于数组的实现 913.1 办法 923.1.1 核心方法 933.1.2 使用大小固定的数组 933.2 ADT包的基于数组的实现 943.2.1 头文件 953.2.2 定义核心方法 963.2.3 测试核心方法 983.2.4 实现更多方法 1013.2.5 删除项的方法 1033.2.6 测试 1063.3 在实现中使用递归 1073.3.1 getIndexOf方法 1073.3.2 getFrequencyOf方法 108C 片段2 指针、多态和内存分配 113C2.1 变量的内存分配和方法的前期绑定 114C2.2 需要解决的问题 115C2.3 指针与程序的自由存储 116C2.3.1 释放内存 118C2.3.2 避免内存泄漏 119C2.3.3 避免悬挂指针 122C2.4 虚方法和多态 124C2.5 数组的动态分配 126第4章 基于链表的实现 1294.1 预备知识 1304.2 ADT包的基于链表的实现 1334.2.1 头文件 1344.2.2 定义核心方法 1354.2.3 实现更多方法 1384.3 在基于链表的实现中使用递归 1434.4 测试多个ADT实现 1454.5 比较基于数组的实现和基于链表的实现 148第5章 作为问题求解技术的递归 1555.1 定义语言 1565.1.1 语法知识基础 1565.1.2 两种简单的语言 1585.2 代数表达式 1605.2.1 代数表达式的类型 1605.2.2 前缀表达式 1625.2.3 后缀表达式 1665.2.4 完全括号化表达式 1685.3 回溯 1685.3.1 查找航线 1685.3.2 八皇后问题 1735.4 递归和数学归纳法的关系 1795.4.1 递归阶乘函数的正确性 1795.4.2 Hanoi塔的工作量 180第6章 栈 1896.1 ADT栈 1906.1.1 在设计解决方案期间开发ADT 1906.1.2 ADT栈的规范 1926.2 栈的简单应用 1976.2.1 检查括号匹配 1976.2.2 识别语言中的字符串 1996.3 栈在代数表达式中的应用 2006.3.1 计算后缀表达式 2016.3.2 中缀表达式与后缀表达式的等价转换 2026.4 使用栈查找航班图 2056.5 栈和递归的关系 212C 片段3 异常 221C3.1 背景知识 222C3.2 断言 223C3.3 抛出异常 224C3.4 处理异常 227C3.4.1 多个catch块 228C3.4.2 未捕获的异常 229C3.5 程序员定义的异常类 232第7章 实现ADT栈 2357.1 基于数组的实现 2367.2 基于链表的实现 2397.3 在实现中使用异常 243第8章 列表 2478.1 指定ADT列表 2488.2 使用列表操作 2528.3 ADT列表的模板接口 255第9章 实现列表 2599.1 基于数组的ADT列表实现 2609.1.1 头文件 2619.1.2 实现文件 2629.2 基于链表的ADT列表实现 2669.2.1 头文件 2669.2.2 实现文件 2689.2.3 在LinkedList的方法中使用递归 2759.3 两种实现的比较 279第10章 算法的效率 28310.1 什么是好的解决方案 28410.2 测量算法的效率 28510.2.1 算法的执行时间 28610.2.2 算法增长率 28710.2.3 分析与大O表示法 28810.2.4 正确分析问题 29110.2.5 查找算法的效率 293第11章 排序算法及其效率 29911.1 基本排序算法 30011.1.1 选择排序 30011.1.2 起泡排序 30311.1.3 插入排序 30511.2 较快排序算法 30711.2.1 归并排序 30711.2.2 快速排序 31211.2.3 基数排序 31911.3 各种排序算法的比较 321C 片段4 类关系和重用 325C4.1 回顾继承 326C4.1.1 类的公有、私有和受保护部分 331C4.1.2 公有、私有和受保护继承 332C4.1.3 is-a和as-a关系 333C4.2 包含：has-a关系 334C4.3 回顾抽象基类 335第12章 有序表及其实现 33912.1 指定ADT有序表 34012.1.1 ADT有序表的模板接口 34212.1.2 使用有序表的操作 34312.2 基于链表的实现 34412.2.1 头文件 34412.2.2 实现文件 34512.2.3 基于链表的实现的效率 34812.3 使用ADT列表的实现 34812.3.1 包含 34912.3.2 公有继承 35212.3.3 私有继承 356第13章 队列和优先队列 36313.1 ADT队列 36413.2 ADT队列的简单应用 36713.2.1 读取字符串 36713.2.2 识别回文 36813.3 ADT优先队列 36913.4 应用：模拟 37113.5 面向位置和面向值的ADT 379第14章 队列和优先队列的实现 38714.1 ADT队列的实现 38814.1.1 使用ADT列表的实现 38814.1.2 基于链表的实现 39014.1.3 基于数组的实现 39414.1.4 比较实现 39914.2 ADT优先队列的实现 400C 片段5 运算符重载和友元访问 405C5.1 重载运算符 406C5.1.1 重载=进行赋值 408C5.1.2 重载 进行连接 410C5.2 友元访问和的重载 411第15章 树 41515.1 术语 41615.1.1 树的类型 41715.1.2 树的高度 41915.1.3 满二叉树、完全二叉树和平衡二叉树 42115.1.4 二叉树的最大和最小高度 42215.2 ADT二叉树 42515.2.1 二叉树的遍历 42515.2.2 二叉树的操作 42815.2.3 ADT二叉树的模板接口 43015.3 ADT二叉查找树 43215.3.1 二叉查找树的操作 43315.3.2 查找二叉查找树 43415.3.3 创建二叉查找树 43515.3.4 遍历二叉查找树 43715.3.5 二叉查找树操作的效率 437第16章 树的实现 44316.1 二叉树中的节点 44416.1.1 基于数组的表示 44416.1.2 基于链表的表示 44616.2 ADT二叉树基于链表的实现 44716.2.1 头文件 44716.2.2 实现 45016.3 ADT二叉查找树基于链表的实现 45816.3.1 ADT二叉查找树操作的算法 45816.3.2 BinarySearchTree类 46916.4 在文件中保存二叉查找树 47116.5 树排序 47416.6 一般树 474C 片段6 迭代器 479C6.1 迭代器 480C6.1.1 常见的迭代器操作 481C6.1.2 使用迭代器操作 482C6.1.3 实现迭代器 483C6.2 迭代器的高级功能 485第17章 堆 48917.1 ADT堆 49017.2 堆的基于数组的实现 49317.2.1 基于数组的堆操作的算法 49417.2.2 实现 49817.3 ADT优先队列的堆实现 50217.4 堆排序 504第18章 字典及其实现 51118.1 ADT字典 51218.2 可能的实现 51718.2.1 ADT字典的基于数组的有序实现 51918.2.2 ADT字典的二叉查找树实现 52118.3 选择实现 52318.4 散列 52918.4.1 散列函数 53218.4.2 解决冲突 53418.4.3 散列的效率 53918.4.4 如何确立散列函数 54218.4.5 字典遍历：散列的低效操作 54318.4.6 使用散列和分离链实现ADT字典 544第19章 平衡查找树 55119.1 平衡查找树 55219.2 2-3树 55319.2.1 遍历2-3树 55519.2.2 查找2-3树 55619.2.3 在2-3树中插入数据 55819.2.4 从2-3树中删除数据 56219.3 2-3-4树 56719.3.1 查找和遍历2-3-4树 56919.3.2 在2-3-4树中插入数据 56919.3.3 从2-3-4树中删除数据 57219.4 红-黑树 57319.4.1 查找和遍历红-黑树 57519.4.2 红-黑树的插入和删除 57519.5 AVL树 577第20章 图 58320.1 术语 58420.2 将图作为ADT 58720.3 图的遍历 59120.3.1 深度优先查找 59220.3.2 广度优先查找 59320.4 图的应用 59520.4.1 拓扑排序 59520.4.2 生成树 59820.4.3 最小生成树 60020.4.4 最短路径 60320.4.5 回路 60620.4.6 一些复杂问题 608第21章 外部存储中的数据处理 61521.1 了解外部存储 61621.2 排序外部文件的数据 61821.3 外部字典 62421.3.1 确定外部文件的索引 62621.3.2 外部散列 62921.3.3 B-树 63221.3.4 遍历 63921.3.5 多索引 640C 片段7 标准模板库 647C7.1 STL容器 648C7.1.1 STL容器适配器 649C7.1.2 顺序容器 650C7.1.3 关联容器 654C7.2 STL算法 657附录A 回顾C 基础 659附录B 编程中的重要主题 697附录C 统一建模语言 719　　附录D 软件生命周期 727附录E 数学归纳法 733附录F 算法验证 737附录G C 文件基础 741附录H C 头文件和标准函数 751附录I C 文档系统 755附录J ASCII字符代码 757附录K 针对Java编程人员的C 知识 759附录L 针对Python编程人员的C 知识 767

这本经典、畅销的数据结构教材详细介绍了数据抽象的基础知识，强调作为面向对象方法基础原理的规范和实施之间的区别。书中使用的软件工程原则和概念以及UML图便于增强学生的理解。本书特点◆　详细介绍了数据抽象，强调规范和实现之间的区别◆　广泛介绍了各种面向对象的编程技术◆　重点是核心的数据结构，而不是非必要的C 语言语法◆　说明了类和ADT在问题解决过程中的作用◆　诠释了ADT的主要应用，如查找航班图、事件驱动的模拟和八皇后问题◆　大部分章节中的例子都使用了标准模板库(STL)◆　介绍了递归◆　附录中提供了基本的C 语法，以帮助学生从其他语言转换为C