第一章 绪论/l 1.1 问题求解/1 1.1.1问题/2 1.1.2问题的分析/2 1.1.3算法的选择/3 1.1.4解的精化/4 1.2 数据结构/4 1.3 算法/6 l.3.1算法的设计/6 1.3.2算法的分析/7 1.4 抽象数据类型/9 1.5 程序设计方法和语言/11 小结/12 习题/12第二章 C++与面向对象初步/13 2.1 C++语言对c的基本扩充/13 2.1.1注释/13 2.1.2函数原型说明/14 2.1.3引用和引用参数/14 2.1.4重载/16 2.1.5缺省参数/16 2.1.6变量说明/17 2.1.7输入和输出/17 2.1.8动态存储分配/17 2.1.9类型定义/18 2.1.10强制类型转换/18 2.2 对象和类/18 2.3 类的界面描述和实现/22 2.3.1类的数据域/24 2.3.2对象的行为——成员函数/24 2.3.3运算符作为成员函数/25 2.3.4用构造函数进行实例的初始化/27 2.4 普通运算符和普通函数/31 2.4.1普通运算符/31 2.4.2普通函数/33 2.4.3输入和输出/33 2.5 类的合成、继承和多态性/36 2.5.1合成/36 2.5.2继承/38 2.5.3多态性/39 小结/40 习题/42第三章 字符串二—数据封装技术/44 3.1 C语言的字符和字符串/44 3.2 字符串数据抽象的描述和实现/46 3.2.1字符串类的定义/47 3.2.2构造函数的定义/49 3.2.3析构函数/52 3.2.4基本成员函数的实现/53 3.2.5比较运算符/57 3.2.6串连接/59 3.2.7输入和输出/60 3.3子串/62 3.4 模式匹配/67 3.4.1简单字符串匹配/69 3.4.2 Knuth-Mords-Pratt模式匹配算法/72 3.4.3 Bovermore符串匹配算法/76 小结/80 习题/80第四章 向量——类的重用技术/83 4.1 模板类/84 4.2 向量的实现/86 4.3 定界向量和枚举向量——继承方式的重用/90 4.3.1定界向量/90 4.3.2枚举向量/94 4.4 排序向量和矩阵——舍成方式的重用/96 4.4.1排序向量和二分法检索/96 4.4.2矩阵/100 4.5 向量遍历器/103 4.5.1遍历器的抽象/103 4.5.2向量遍历器/105 4.6 向量的排序一模板函数/110 4.6.1插入排序/110 4.6.2起泡排序/112 4.6.3选择排序/113 4.6.4快速排序算法/114 4.7 继承和多态的若干讨论/l16 4.7.1父类与子类/116 4.7.2静态类型和动态类型/117 4.7.3框架和框架类/118 4.7.4遮蔽和虚函数/118 4.7.5虚遮蔽和非虚遮蔽/119 4.7.6两类继承/120 4.7.7多态的主要形式/121 4.7.8参数多态性——归约/121 4.7.9切割问题/123小结/125习题/125第五章 动态数据结构一链表/128 5.1 单链表的定义/128 5.1.1表类/128 5.1.2链类/130 5.2 单链表的实现/131 5.2.I链类的实现/131 5.2.2表类的实现/133 5.3 表遍历器/136 5.3.1表遍历器类/136 5.3.2表遍历器类的实现/138 5.4 表的应用：多项式处理/142 5.4.1项类/143 5.4.2多项式类/145 5.5 排序表“/148 5.5.1排序表类/148 5.5.2排序表类的实现/148 5.5.3排序表的应用——表插入排序/149 5.6 其他链表/150 5.6.1 自组织表/150 5.6.2双端表/152 5.6-3循环表/154 5.6.4双链表/155 5.7 可利用空间表/155小结/157习题/159第六章 栈和队列/161 6.1 抽象类栈和队列161 6.2 栈的实现/162 6.2.1栈的向量实现/163 6.2.2栈的链表实现/165 6.3栈的应用——表达式计算/167 6.3.1、后缀表达式的求值/167 6.3.2中缀表达式到后缀表达式 的转换/170 6.4 队列的实现/172 6.4.1队列的向量实现/172 6.4.2队列的链表实现/174 6.5 队列的应用——农夫过河问题/177小结/181习题/181第七章 树和二叉树/184 7.1 基本概念/185 7.1.1树/185 7.1.2二叉树/187 7.1.3树与二叉树的关系/190 7.2 二叉树的实现/191 7.2.1二叉树结点类/191 7.2.2基本二叉树类/193 7.2.3可构造二叉树类/195 7.3 二叉树的周游/197 7.3.1周游的递归实现/197 7.3.2通过遍历器实现周游/199 7.3.3前序周游器类/199 7.3.4中序周游器类/202 7.3.5后序周游器类/203 7.3.6层次周游算法(按宽度方向周游)/205 7.4 二叉树的向量表示/207 7.4.1二叉树向量表示的一种基本方法/207 7.4.2记录结构信息的二叉树向量表示/208 7.5 二叉排序树/209 7.6 平衡的二叉排序树/214 7.6.1AVL树上的操作/215 7.6.2AVL树的设计与实现/218 7.7 二叉树的应用——哈夫曼树/225小、结/228习题/228第八章 优先队列/23l 8.1 优先队列的抽象/231 8.2 堆/234 8.3 堆排序/238 8.4 斜堆/240 8.5 离散事件模拟/244 8.5.1模拟类的结构/246 8.5.2冰淇淋店的模拟/248 8.5.3随机数/251小结/253习题/253第九章 集合与字典/256 9.1 集合及其运算/256 9.1.1集合运算/257 9.1.2集合类/258 9.2 位向量集合/259 9.2.1位向量/260 9.2.2位向量集合/266 9.2.3字符集合/269 9.2.4字符集类的应用——将字符串分解为单词/270 9.3 集合的表实现/273 9.4 关联与字典/275 9.5 字典的关联表实现/278 9.6 字典的应用/281 9.6.1稀疏矩阵/281 9.6.2排序字典/284 9.6.3索引的实现/285小结/287习题/289 第十章散列结构/291 10.1散列结构/291 10.2散列函数/295 10.3开地址散列向量/297 10.4桶散列——用桶解决碰撞/300 IO.4.桶散列的抽象模板类/301 10.4.2用树作为桶的实现/302 10.4.3桶散列结构操作时间的分析/304lO.5桶散列结构的遍历器/30510.6用散列表实现集合/307 10.6.1应用——拼写检查器/30910.7用桶散列表实现字典/311小结/313习题/314第十一章 图/316 11.1 基本概念/316 11.2 图的邻接矩阵表示和Warshall算法/318 11.2.1图的邻接矩阵表示/318 Il.2.2图结点的可达性问题/318 11.3 邻接表方式的图表示和深度优先搜索/320 11.3.1邻接表表示中的结点类/321 11.3.2用深度优先方式求解可达性问题/322 11.4 带权图的矩阵表示和Floyd算法/324 11.4.1带权图的邻接矩阵/325 11.4.2带权图最短路径问题Floyd算法/325 11.5 带权图的邻接表表示与Dijkstra算法/327 11.5.1带权图的邻接表表示/327 11.5.2从一个结点出发的最短路径和Dijkstra算法/328 11.6 连通性、带权连通无向图与最小生成树/330 11.7有限自动机/333 11.8拓扑排序}/336小结/338习题/339第十二章 文件/342 12.1 外存、文件及其问题/342 12.1.1外存储器的特点与信息组织/342 12.1.2文件基本结构和操作/344 12.1.3文件与字典/345 12.1.4文件组织/346 12.2 C++的字符流文件及其操作/347 12.3 归并排序/352 12.4 文件的随机访问/356 12.5 文件索引结构/359 12.5.1索引向量/359 12.5.2树形索引结构/360 12.5.3 B树/361 12.5.4 B+树/364 12.6 树索引文件的实现/367小结/369习题/369附录/371 附录A 主要抽象数据类及其相互关系/371 附录B Borland C++集成开发环境使用入门/375 附录C“多叉路口的交通管理系统”上机报告/387
· · · · · · (收起)