高等学校计算机专业系列教材数据结构:抽象建模.实现与应用

前言
第1章　概论 1
1.1　引言 1
1.2　数据结构相关概念及术语 1
1.3　抽象数据类型的表示与实现 3
1.4　算法与算法分析 6
1.4.1　算法 6
1.4.2　算法分析与度量 8
1.5　小结 10
1.6　练习 10
第2章　线性表 11
2.1　引言 11
2.2　线性表的抽象数据类型 11
2.3　线性表的顺序表示与实现 15
2.3.1　顺序表的定义和特点 15
2.3.2　顺序表的存储结构 15
2.3.3　顺序表基本操作的实现与性能分析 16
2.4　线性表的链式表示与实现 19
2.4.1　单链表 20
2.4.2　其他形式的链表 24
2.5　线性表的应用举例 27
2.6　小结 31
2.7　练习 31
第3章　栈和队列 32
3.1　引言 32
3.2　栈的抽象数据类型 32
3.3　栈的顺序表示与实现 33
3.4　栈的链式表示与实现 36
3.5　栈的应用举例 37
3.5.1　逆序输出问题 37
3.5.2　*近匹配与比较问题 38
3.5.3　递归与回溯问题 43
3.6　队列的抽象数据类型 47
3.7　队列的顺序表示与实现 48
3.8　队列的链式表示与实现 50
3.9　队列的应用举例 52
3.10　小结 53
3.11　练习 53
第4章　数组、广义表和字符串 54
4.1　引言 54
4.2　数组 54
4.2.1　一维数组 54
4.2.2　二维数组 55
4.3　特殊矩阵的压缩存储 56
4.3.1　对称矩阵 56
4.3.2　对角矩阵 57
4.4　稀疏矩阵的压缩存储 57
4.4.1　稀疏矩阵的三元组表示 57
4.4.2　三元组的顺序表表示 58
4.4.3　三元组的十字链表表示 61
4.5　广义表 62
4.5.1　广义表的概念 62
4.5.2　广义表的抽象数据类型 63
4.5.3　广义表的存储结构 64
4.6　字符串 66
4.6.1　字符串的抽象数据类型 66
4.6.2　字符串的存储结构与子串定位 67
4.7　小结 68
4.8　练习 68
第5章　树和二叉树 70
5.1　引言 70
5.2　树的定义和基本术语 70
5.2.1　树的定义 70
5.2.2　树的逻辑表示 71
5.2.3　树的基本术语 72
5.2.4　树的抽象数据类型 72
5.3　二叉树 73
5.3.1　二叉树的定义 73
5.3.2　二叉树的抽象数据类型 74
5.3.3　二叉树的性质 76
5.3.4　二叉树的存储结构 77
5.3.5　二叉树的遍历 79
5.3.6　二叉树遍历算法的
应用举例 81
5.4　树和森林 85
5.4.1　树与二叉树的转换 85
5.4.2　森林与二叉树的转换 86
5.4.3　树和森林的遍历 87
5.5　霍夫曼树 88
5.5.1　霍夫曼树的定义 88
5.5.2　霍夫曼树的构造 90
5.5.3　霍夫曼编码 90
5.5.4　霍夫曼树和霍夫曼编码的算法实现 92
5.6　小结 94
5.7　练习 94
第6章　图 95
6.1　引言 95
6.2　图的定义、基本术语和抽象数据类型 95
6.3　图的存储方式 97
6.3.1　邻接矩阵 97
6.3.2　邻接表 99
6.4　图的遍历 101
6.4.1　深度优先遍历 101
6.4.2　广度优先遍历 102
6.4.3　图的遍历算法的应用举例 103
6.5　*小生成树 107
6.5.1　*小生成树的定义 107
6.5.2　普里姆算法 108
6.5.3　克鲁斯卡尔算法 111
6.6　拓扑排序与关键路径 112
6.6.1　拓扑排序 112
6.6.2　AOE网与关键路径 113
6.7　*短路径问题 116
6.7.1　单源*短路径问题 116
6.7.2　所有顶点对之间的*短路径 119
6.8　小结 121
6.9　练习 122
第7章　查找 123
7.1　引言 123
7.2　查找表的定义与抽象数据类型 123
7.3　顺序表的静态查找 124
7.3.1　顺序查找 125
7.3.2　折半查找 126
7.3.3　索引查找 129
7.4　树表的动态查找 130
7.4.1　二叉排序树 130
7.4.2　平衡二叉排序树 138
7.4.3　B-树 141
7.4.4　B 树 146
7.5　哈希表的查找 147
7.5.1　哈希表的定义 147
7.5.2　哈希函数的构造方法 148
7.5.3　处理冲突的方式 150
7.5.4　哈希表的查找 152
7.5.5　性能分析 153
7.6　小结 155
7.7　练习 156
第8章　排序 157
8.1　引言 157
8.2　排序的定义与分类 157
8.2.1　排序的定义 157
8.2.2　排序的分类 157
8.2.3　排序的数据类型 158
8.3　插入排序 158
8.3.1　直接插入排序 158
8.3.2　希尔排序 160
8.4　交换排序 162
8.4.1　简单交换排序 162
8.4.2　快速排序 164
8.5　选择排序 166
8.5.1　简单选择排序 167
8.5.2　树形选择排序 168
8.5.3　堆排序 169
8.6　归并排序 173
8.7　基数排序 175
8.7.1　多关键字的排序 175
8.7.2　基数排序的实现 176
8.8　各种内部排序方法的比较 178
8.9　小结 179
8.10　练习 179