第1章 绪论 1
1．1 数据结构的基本概念 1
1．2 抽象数据类型的表示与实现 4
1．3 算法设计与描述 6
1．3．1 算法 6
1．3．2 算法描述 7
1．4 算法的性能分析与度量 7
1．4．1 算法的性能标准 7
1．5 算法分析应用举例 8
1．4．2 算法的时间复杂度与空间复杂度 8
习题一 11
第2章 线性表 12
2．1 线性表的逻辑结构 12
2．1．1 线性表的定义 12
2．1．2 线性表的逻辑结构 12
2．1．3 线性表的基本运算 13
2．1．4 线性表的ADT描述 14
2．2 线性表的顺序存储 15
2．2．1 线性表的顺序存储结构 15
2．2．2 顺序存储结构线性表运算的实现 16
2．3．1 线性表的链式存储结构 20
2．3 线性表的链式存储 20
2．3．2 线性表链式存储结构的操作及实现算法 21
2．3．3 静态链表 26
2．3．4 线性表实现方法的比较 29
2．4 循环链表 29
2．5 双向链表 32
2．6 程序举例 34
2．6．1 一元多项式的表示 34
2．6．2 一元多项式的加法运算 35
习题二 36
3．1 栈 39
第3章 栈、队列和串 39
3．1．1 栈的基本操作 40
3．1．2 栈存储结构 41
3．1．3 栈的应用举例 46
3．2 队列 48
3．2．1 队列的基本操作 49
3．2．2 队列的存储结构 50
3．2．3 队列应用 53
3．3 串 54
3．3．1 串的概念 54
3．3．2 串的基本操作 55
3．3．3 串的存储结构 56
3．3．4 串的模式匹配算法 59
3．3．5 串的应用举例 63
习题三 64
第4章 数组和广义表 68
4．1 数组的定义及其操作 68
4．1．1 数组的定义 68
4．1．2 数组的存储结构 69
4．2 特殊矩阵的压缩存储 70
4．2．1 对称矩阵的压缩存储 70
4．2．2 稀疏矩阵的压缩存储 71
4．3．1 广义表的定义 75
4．3 广义表 75
4．3．2 广义表的操作 76
4．3．3 广义表的存储结构 78
4．4 程序举例 80
4．4．1 稀疏矩阵的三元组表建立十字链表及其运算 80
4．4．2 广义表的应用——n元表达式的表示 83
习题四 85
第5章 树与二叉树 89
5．1 树的定义与存储 89
5．1．1 树的定义和基本术语 90
5．1．3 树的存储结构 92
5．1．2 树的基本操作 92
5．2 二叉树的定义与主要特性 95
5．2．1 二叉树的定义和基本术语 96
5．2．2 二叉树的存储结构 102
5．3 二叉树的遍历和二叉树的线索化 104
5．3．1 二叉树的遍历 104
5．3．2 线索二叉树 108
5．4 树、森林与二叉树的转换 111
5．4．1 树转换成二叉树 111
5．4．2 森林转换成二叉树 112
5．4．5 森林的遍历 113
5．4．4 树的遍历 113
5．4．3 二叉树转换为森林 113
5．5 Huffman树及其应用 114
5．5．1 Huffman树 114
5．5．2 Huffman树的应用 118
5．6 程序举例 119
习题五 121
第6章 图 124
6．1 基本概念 124
6．1．1 图的定义和术语 124
6．1．2 图的基本操作 128
6．2 图的存储结构 129
6．2．1 邻接矩阵存储方法 130
6．2．2 邻接表存储方法 133
6．2．3 十字链表存储方法 135
6．2．4邻接多重表存储方法 137
6．2．5 图的边表存储结构 138
6．3 图的遍历及其应用 139
6．3．1 深度优先搜索 140
6．3．2 广度优先搜索 141
6．3．3 图的遍历应用 142
6．4 图的最小生成树 149
6．4．1 普里姆算法 149
6．4．2 克鲁斯卡尔算法 151
6．5 最短路径 153
6．5．1 单源点最短路径 153
6．5．2 每一对顶点之间的最短路径 157
6．5．3 传递闭包 159
6．6 拓扑排序 160
6．7 关键路径 164
6．8 图的应用举例 167
6．8．1 求图的中心顶点 167
6．8．2 一个智力问题求解 169
习题六 170
7．1 排序的概念 172
第7章 内部排序 172
7．2．1 直接插入排序 174
7．2 三种简单排序算法 174
7．2．2 冒泡排序 176
7．2．3 简单选择排序 178
7．3 希尔排序 179
7．4 快速排序 181
7．5 堆排序 186
7．6 归并排序 191
7．7 基数排序 194
7．8 各种内部排序方法的比较 197
7．9．1 荷兰国旗问题 198
7．9 排序算法的应用举例 198
7．9．2 多路归并的实现 200
习题七 202
第8章 查找 204
8．1 查找的概念 204
8．2 线性表的查找 205
8．2．1 顺序查找 205
8．2．2 折半查找 206
8．2．3 有序表的其他查找方法 210
8．3．1 二叉排序树的定义 213
8．3 二叉排序树 213
8．3．2 BST树上的查找 214
8．3．3 BST树的插入和删除 216
8．4 平衡二叉树 220
8．4．1 平衡二叉树的定义 220
8．4．2 平衡化旋转 221
8．4．3 AVL树的插入和删除 226
8．5 算法应用与程序举例 228
习题八 230
9．1．1 散列表 232
9．1 散列表与散列方法 232
第9章 散列和索引技术 232
9．1．2 散列函数 234
9．1．3 冲突处理方法 236
9．1．4 散列表的操作 240
9．2 线性索引 242
9．2．1 顺序索引表 242
9．2．2 分块查找 243
9．3 树形索引 245
9．3．1 B-树 245
习题九 251
9．3．2 B+树 253
9．4 算法应用举例及其程序设计 255
第10章 文件管理与外部排序 259
10．1 文件与外排序的概念 259
10．1．1 关于文件的一些概念 259
10．1．2 有关文件的操作 260
10．1．3 外部存储设备 261
10．1．4 外排序的概念 263
10．2 文件的组织方式 264
10．2．1 顺序文件 264
10．2．2 索引文件 265
10．2．4 多关键字文件 270
10．2．3 散列文件 270
10．3 外排序简单方法 272
10．3．1 外排序的简单方法 273
10．3．2 外排序的时间分析 274
10．4 多路归并排序 275
10．4．1 多路归并 276
10．4．2 多路平衡归并排序 279
10．4．3 多步归并排序 280
10．5 置换选择 282
10．6 最佳归并树 285
习题十 286