第1章 绪论 1
1．1 什么是数据结构 2
1．2 抽象数据类型及面向对象概念 4
1．2．1 数据类型 4
1．2．2 数据抽象与抽象数据类型（ADTs:Abstract Data Types） 4
1．2．3 面向对象的概念 5
1．2．4 用于描述数据结构的语言 7
1．3 数据结构的抽象层次 7
1．4．1 C++的函数特征 9
*1．4 用C++描述面向对象程序 9
1．4．2 C++的数据声明 10
1．4．3 C++的作用域 11
1．4．4 C++的类 11
1．4．5 C++中的对象 13
1．4．6 C++的输入输出 13
1．4．7 C++中的函数 15
1．4．8 C++中的参数传递 15
1．4．9 C++中的函数名重载和操作符重载 16
1．4．10 C++中的动态存储分配 17
1．4．11 友元（friend）函数 18
1．4．12 内联（inline）函数 18
1．4．13 结构（struct）与类 18
1．4．14 联合（Union）与类 19
1．5 算法定义 19
1．6 模板（template） 20
1．7．1 算法的性能标准 23
1．7 性能分析与度量 23
*1．7．2 算法的后期测试 24
1．7．3 算法的事前估计 26
1．7．4 空间复杂度度量 26
1．7．5 时间复杂度度量 27
1．7．6 时间复杂度的渐进表示法 31
1．7．7 渐进的空间复杂度 34
习题 34
2．1．1 在C++中数组的定义和初始化 37
第2章 数组 37
2．1 作为抽象数据类型的数组 37
2．1．2 作为抽象数据类型的数组 38
2．1．3 数组的顺序存储方式 40
2．2 顺序表 42
2．2．1 顺序表的定义和特点 43
2．2．2 顺序表的类定义 43
2．2．3 顺序表的查找、插入和删除 45
2．2．4 作为抽象数据类型，使用顺序表的事例 47
*2．3 多项式抽象数据类型 47
2．3．1 多项式抽象数据类型 48
2．3．2 多项式的表示 49
2．3．3 多项式的相加 51
2．4 稀疏矩阵 53
2．4．1 稀疏矩阵的抽象数据类型 53
2．4．2 稀疏矩阵的压缩表示 53
*2．4．3 稀疏矩阵的转置 54
*2．4．4 稀疏矩阵相乘 57
2．5 字符串 59
2．5．1 字符串抽象数据类型和类定义 59
2．5．2 字符串操作的实现 61
2．5．3 字符串的模式匹配 63
*2．5．4 模式匹配的改进算法——KMP（D.E.Knuth -J.H.Morris—V.R.Pratt）算法 64
习题 68
第3章 链表 71
3．1 单链表（Singly Linked List） 71
3．1．1 单链表的结构 71
3．1．2 单链表的类定义 72
3．1．3 单链表中的插入与删除 73
3．3．4 带表头结点的单链表 75
3．3．5 用模板定义的单链表类 76
3．3．6 单链表的游标（Iterator）类 79
3．3．7 静态链表 81
3．2．1 循环链表的类定义 82
3．2 循环链表 82
3．2．2 用循环链表求解约瑟夫问题 83
*3．3 多项式及其相加 84
3．3．1 多项式的类定义 84
3．3．2 多项式的加法 85
3．4 双向链表 87
3．5 稀疏矩阵 92
3．5．1 稀疏矩阵的类定义 92
3．5．2 稀疏矩阵的建立 94
3．5．3 删除稀疏矩阵 95
3．6 C++中的虚函数和动态联编 96
3．6．1 C++中的继承（inheritance） 96
3．6．2 基类与派生类对象指针的转换 97
3．6．3 虚函数（virtual function） 99
3．6．4 纯虚函数和抽象基类 99
3．6．5 多态性（polymorphism）和动态联编 99
习题 101
4．1．1 栈的抽象数据类型 103
第4章 栈和队列 103
4．1 栈 103
4．1．2 栈抽象数据类型的顺序存储表示与实现——顺序栈 104
4．1．3 栈抽象数据类型的链接存储表示——链式栈 106
*4．2 表达式的计算（Expression Evaluation） 107
4．2．1 表达式 107
4．2．2 应用后缀表示计算表达式的值 108
4．2．3 中缀表达式转换为后缀表达式 111
4．3 队列 113
4．3．1 队列的抽象数据类型 113
4．3．2 队列的顺序存储表示——循环队列 114
4．3．3 队列的链接存储表示——链式队列 116
4．3．4 队列的应用举例—打印二项展开式（a+b）j的系数 118
4．4 优先级队列（Priority Queue） 119
4．4．1 优先级队列的定义 119
4．4．2 优先级队列的存储表示和实现 120
*4．5 事件驱动模拟（Event-Driven Simulation） 121
习题 130
第5章 递归（RECURVE） 132
5．1 递归的概念 132
5．2 迷宫问题 135
5．3 递归过程与递归工作栈 138
*5．4 利用栈实现的迷宫问题非递归解法 142
5．5 广义表（General Lists） 145
5．5．1 广义表的概念 146
5．5．2 广义表的表示及操作 147
5．5．3 广义表存储结构的实现 149
5．5．4 广义表的访问算法 151
5．5．5 广义表的递归算法 153
*5．5．6 三元多项式的表示 159
习题 161
6．1．2 树的术语 163
6．1．1 树的定义 163
6．1 树与森林的概念 163
第6章 树与森林 163
6．1．3 树的抽象数据类型 164
6．2 二叉树（Binary Tree） 165
6．2．1 二叉树的定义 165
6．2．2 二叉树的性质 166
6．2．3 二叉树的抽象数据类型 167
6．3．1 数组表示 168
6．3 二叉树的表示 168
6．3．2 链表存储表示 169
6．4 二叉树遍历（Binary Tree Traversal） 172
6．4．1 中序遍历（Inorder Traversal） 173
6．4．2 前序遍历（preorder Traversal） 173
6．4．3 后序遍历（Postorder Traversal） 174
6．4．4 应用二叉树遍历的事例 175
*6．4．5 二叉树遍历的游标类（Tree Iterator） 177
6．5．1 线索（Thread） 182
*6．5 线索化二叉树（Threaded Binary Tree） 182
*6．4．6 不用栈的二叉树中序遍历算法 182
6．5．2 中序线索化二叉树 183
6．5．3 前序与后序的线索化二叉树 188
6．6 堆（Heap） 189
6．6．1 堆的定义 190
6．6．1 堆的建立 191
6．6．3 堆的插入与删除 192
6．7 树与森林 194
6．7．1 树的存储表示 194
6．7．2 森林与二叉树的转换 199
6．7．3 树的遍历 200
6．7．4 森林的遍历 202
*6．8 二叉树的计数 203
6．9 霍夫曼树（Huffman Tree） 206
6．9．1 路径长度（Path Length） 206
6．9．2 霍夫曼树 207
9．9．3 霍夫曼编码 209
习题 210
第7章 集合与搜索 212
7．1 集合及其表示 212
7．1．1 集合基本概念 212
7．1．2 以集合为基础的抽象数据类型 213
7．1．3 用位向量实现集合抽象数据类型 213
7．1．4 用有序链表实现集合的抽象数据类型 215
7．2 等价类和并查集 219
7．2．1 等价关系与等价类 219
7．2．2 确定等价类的链表方法 220
7．2．3 并查集 222
7．3 静态搜索结构 227
7．3．1 搜索的概念 227
7．3．2 静态搜索结构 228
7．3．3 顺序搜索 229
7．3．4 基于有序顺序表的折半搜索 231
*7．3．5 基于有序顺序表的斐波那契搜索和插值搜索 234
7．4 二叉搜索树 235
7．4．1 定义 235
7．4．2 二叉搜索树上的搜索 237
7．4．3 二叉搜索树的插入 238
7．4．4 二叉搜索树的删除 239
*7．4．5 与二叉搜索树相关的中序游标类 240
*7．5 最优二叉搜索树 242
7．5．1 扩充二叉搜索树 242
7．5．2 最优二叉搜索树 243
7．6 AVL树 247
7．6．1 AVL树的定义 247
7．6．2 平衡化旋转 248
7．6．3 AVL树的插入和删除 252
7．6．4 AVL树的高度 255
习题 256
8．1．1 图的基本概念 259
8．1 图的基本概念 259
第8章 图 259
8．1．2 图的抽象数据类型 261
8．2 图的存储表示 262
8．2．1 邻接矩阵 262
8．2．2 邻接表 265
8．2．3 邻接多重表 269
8．3 图的遍历与连通性 270
8．3．1 深度优先搜索 271
8．3．2 广度优先搜索 272
8．3．3 连通分量 273
8．3．4 重连通分量 274
8．4 最小生成树 277
8．4．1 克鲁斯卡尔（Kruskal）算法 278
8．4．2 普里姆（Prim）算法 280
8．5 最短路径 283
8．5．1 边上权值非负情形的单源最短路径问题 283
*8．5．2 边上权值为任意值的单源最短路径问题 286
8．5．3 所有顶点之间的最短路径 288
8．6 活动网络 290
8．6．1 用顶点表示活动的网络 290
8．6．1 用边表示活动的网络 294
习题 298
第9章 排序 301
9．1 概述 301
9．2 插入排序 303
9．2．1 直接插入排序 303
9．2．2 折半插入排序 304
9．2．3 链表插入排序 305
9．2．4 希尔排序 307
9．3 交换排序 309
9．3．1 起泡排序 309
9．3．2 快速排序 310
9．4 选择排序 312
9．4．2 锦标赛排序 313
9．4．1 直接选择排序 313
9．4．3 堆排序 317
9．5 归并排序 318
9．5．1 归并 318
9．5．2 迭代的归并排序算法 319
9．5．3 递归的表归并排序 321
*9．6 基数排序 323
9．6．1 多关键码排序 323
9．6．2 链式基数排序 324
9．7 外排序 326
9．7．1 外排序的基本过程 326
9．7．2 k路平衡归并 329
9．7．3 初始归并段的生成 333
*9．7．4 并行操作的缓冲区处理 337
9．7．5 最佳归并树 339
习题 341
10．1．1 线性索引 344
10．1 静态索引结构 344
第10章 索引结构与散列 344
10．1．2 倒排表 346
10．1．3 m路静态搜索树 347
10．2 动态索引结构 348
10．2．1 动态的m路搜索树 348
10．2．2 B_树 350
10．2．3 B_树的插入 352
10．2．4 B_树的删除 354
10．2．5 B+树 358
*10．3 Trie树 361
10．3．1 Trie树的定义 361
10．3．2 Trie树的搜索 362
10．3．3 在Trie树上的插入和删除 363
10．4 散列（Hashing） 364
10．4．1 词典（Dictionary）的抽象数据类型 364
10．4．3 散列函数 365
10．4．2 散列表与散列方法 365
10．4．4 处理溢出的闭散列方法 369
10．4．5 处理溢出的开散列方法——链地址法 376
10．4．6 散列表分析 378
*10．5 可扩充散列 379
10．5．1 二叉Trie树 379
10．5．2 将二叉Trie树转换为目录 380
10．5．3 插入与目录扩充 383
10．5．4 删除与目录收缩 385
10．5．5 性能分析 386
习题 388
附录 实习要求与实习报告 391
实习1 栈和队列 396
实习2 串（内容：全屏幕文本编辑器） 396
实习3 树（内容：作业调度） 398
实习4 图（内容：某公园导游图） 399
实习5 查找、排序（内容：简单的职工管理系统） 399
参考文献 401