第1章 绪论 1
1.1 数据抽象与数据结构 1
1.1.1 抽象与结构 1
1.1.2 抽象与封装 2
1.1.3 程序设计中的抽象 3
1.1.4 数据结构 5
1.2 抽象数据类型与应用程序接口 9
1.2.1 抽象数据类型 9
1.2.2 接口和实现 9
1.2.3 良好的接口设计规则 10
1.3 算法和算法分析 12
1.3.1 算法和算法描述 12
1.3.2 算法分析基础 13
1.4 数据结构与算法的描述与实现 18
1.4.1 一维数组 18
1.4.2 指针与结构体 21
习题1 27
第2章 线性数据结构 29
2.1 典型线性数据结构 29
2.1.1 线性结构的逻辑描述 29
2.1.2 线性结构的存储表示 31
2.2 顺序栈 32
2.2.1 栈的顺序表示和实现 32
2.2.2 应用举例 34
2.3 循环队列 37
2.3.1 队列的顺序表示 37
2.3.2 循环队列的实现 38
2.3.3 应用举例 41
2.4 顺序表 41
2.4.1 线性表的顺序表示与实现 41
2.4.2 一元稀疏多项式 45
2.4.3 稀疏矩阵 48
2.5 链栈与链队列 53
2.5.1 链栈 53
2.5.2 链队列 55
2.6 线性表的链式表示和实现 57
2.6.1 单链表 57
2.6.2 双向链表 64
2.6.3 循环链表 66
2.7 线性表两种存储结构的比较 69
习题2 70
第3章 排序基础 73
3.1 排序的概念与分类 73
3.1.1 排序的概念 73
3.1.2 排序的分类 74
3.2 直接插入排序 75
3.3 希尔排序 77
3.4 基数排序 80
3.4.1 多关键字排序 80
3.4.2 基数排序 81
习题3 86
第4章 哈希表 88
4.1 哈希表的概念 88
4.2 哈希函数的构造方法 89
4.2.1 直接定址法 89
4.2.2 除留余数法 90
4.2.3 数字分析法 91
4.2.4 折叠法 91
4.2.5 平方取中法 92
4.3 处理冲突的方法 93
4.3.1 链地址法 93
4.3.2 开放定址法 93
4.4 哈希表的实现 95
4.4.1 链地址哈希表的实现 95
4.4.2 开放定址哈希表的实现 97
4.5 哈希表的查找性能 100
习题4 102
第5章 递归 104
5.1 递归基础 104
5.1.1 汉诺塔问题 104
5.1.2 递归函数执行过程 105
5.2 递归与分治 108
5.2.1 分治法 108
5.2.2 折半查找 109
5.2.3 归并排序 111
5.2.4 快速排序 113
5.3 递归与迭代 116
5.3.1 迭代三要素 116
5.3.2 迭代与递归的联系与区别 119
5.4 广义表 119
5.4.1 广义表的定义 120
5.4.2 广义表的存储结构 121
5.4.3 广义表常用操作的实现 123
习题5 124
第6章 二叉树 126
6.1 二叉树的概念和性质 126
6.1.1 二叉树的定义和术语 126
6.1.2 二叉树的性质 127
6.2 二叉树的存储结构 129
6.2.1 顺序存储结构 129
6.2.2 链式存储结构 130
6.3 遍历二叉树 132
6.3.1 二叉树的递归遍历 133
6.3.2 二叉树的非递归遍历 134
6.3.3 遍历的应用 138
6.4 堆 140
6.4.1 堆的定义 140
6.4.2 基本操作的实现 141
6.4.3 堆排序 145
6.5 二叉查找树 149
6.5.1 二叉查找树的定义 149
6.5.2 二叉查找树的查找 150
6.5.3 二叉查找树的插入 151
6.5.4 二叉查找树的删除 152
6.5.5 二叉查找树的查找性能 155
6.6 平衡二叉树 155
6.6.1 平衡二叉树的定义 156
6.6.2 平衡二叉树的失衡及调整 157
6.6.3 平衡二叉树的插入 161
习题6 163
第7章 树和森林 166
7.1 树的定义 166
7.2 树的存储结构 167
7.2.1 双亲表示法 167
7.2.2 双亲孩子表示法 168
7.2.3 孩子兄弟表示法 168
7.3 树和森林的遍历 172
7.4 并查集 174
7.5 B树 179
7.5.1 B树的定义 179
7.5.2 B树的查找 180
7.5.3 B树的插入 182
7.5.4 B树的删除 184
7 5.5 B＋树 186
习题7 187
第8章 图 189
8.1 图的基本概念 189
8.1.1 图的定义 189
8.1.2 图的术语 190
8.2 图的存储结构 192
8.2.1 邻接数组 192
8.2.2 邻接表 196
8.3 图的遍历 202
8.3.1 深度优先遍历 202
8.3.2 广度优先遍历 204
8.3.3 遍历的应用 206
8.4 最小生成树 207
8.4.1 普里姆算法 207
8.4.2 克鲁斯卡尔算法 211
8.5 最短路径 213
8.6 拓扑排序 216
8.7 关键路径 218
习题8 224
参考文献 227