数据结构简明教程

第1章绪论 1
学习目标 1
1.1常用术语 1
1.2算法描述 10
1.3算法评价 12
本章小结 18
习题一 18
第2章集合 23
学习目标 23
2.1集合的定义和运算 23
2.1.1集合的定义 23
2.1.2集合的抽象数据类型 23
2.1.3集合运算举例 24
2.2集合的顺序存储结构和
操作实现 25
2.3集合的链接存储结构和
操作实现 33
本章小结 39
习题二 40
第3章线性表 42
学习目标 42
3.1线性表的定义和抽象数据类型 42
3.1.1线性表的定义 42
3.1.2线性表的抽象数据类型 43
3.2线性表的顺序存储结构和
操作实现 44
3.3线性表的链接存储结构和
操作实现 49
3.4线性表的其他链接存储结构 51
3.5广义表 54
3.5.1广义表的定义 54
3.5.2广义表的存储结构 56
3.5.3广义表的运算 57
本章小结 59
习题三 60
第4章栈和队列 62
学习目标 62
4.1栈 62
4.1.1栈的定义 62
4.1.2栈的抽象数据类型 63
4.2栈的顺序存储结构和操作实现 63
4.3栈的链接存储结构和操作实现 67
4.4栈的简单应用举例 70
4.5栈与递归 74
4.6队列 82
4.6.1队列的定义 82
4.6.2队列的抽象数据类型 82
4.6.3队列的顺序存储结构和
操作实现 83
4.6.4队列的链接存储结构和
操作实现 87
本章小结 90
习题四 91
第5章树和二叉树 94
学习目标 94
5.1树的概念 94
5.1.1树的定义 94
5.1.2树的表示 95
5.1.3树的基本术语 95
5.1.4树的性质 96
5.2二叉树 97
5.2.1二叉树的定义 97
5.2.2二叉树的性质 98
5.2.3二叉树的抽象数据类型 100
5.2.4二叉树的存储结构 101
5.3二叉树的遍历 103
5.4二叉树的其他运算 107
5.5二叉搜索树 112
5.5.1二叉搜索树的定义 112
5.5.2二叉搜索树的抽象数据类型 113
5.5.3二叉搜索树的运算 113
5.6堆 119
5.6.1堆的定义 119
5.6.2堆的抽象数据类型 119
5.6.3堆的存储结构 120
5.6.4堆的运算 121
本章小结 125
习题五 126
第6章图 130
学习目标 130
6.1图的概念 130
6.1.1图的定义 130
6.1.2图的基本术语 131
6.2图的存储结构 133
6.2.1邻接矩阵 133
6.2.2邻接表 135
6.2.3边集数组 138
6.3图的遍历 139
6.3.1深度优先搜索遍历 139
6.3.2广度优先搜索遍历 141
6.3.3非连通图的遍历 143
6.4图的生成树和最小生成树 144
6.4.1生成树的概念 144
6.4.2克鲁斯卡尔算法 146
6.5拓扑排序 148
本章小结 153
习题六 154
第7章查找 157
学习目标 157
7.1查找的基本概念 157
7.2顺序表查找 158
7.2.1顺序查找 159
7.2.2二分查找 160
7.3索引查找 163
7.3.1索引的概念 163
7.3.2索引查找算法 166
7.4散列查找 168
7.4.1散列的概念 168
7.4.2散列函数 169
7.4.3处理冲突的方法 171
7.4.4散列表的运算 175
7.5B树查找 179
7.5.1B_树的定义 179
7.5.2B_树查找 180
7.5.3B_树的插入 182
7.5.4B_树的删除 183
本章小结 186
习题七 187
第8章排序 190
学习目标 190
8.1排序的基本概念 190
8.2插入排序 191
8.3选择排序 193
8.3.1直接选择排序 193
8.3.2堆排序 195
8.4交换排序 198
8.4.1气泡排序 198
8.4.2快速排序 200
8.5归并排序 203
8.6外排序 206
本章小结 213
习题八 214
附录部分习题解答 217
参考书目 226