第1章 绪论 1
1.1数据结构的发展概况 2
1.2数据结构的研究对象 3
1.3数据结构的基本概念 5
数据结构 5
抽象数据类型 10
1.4算法描述及算法分析 13
算法概念 13
算法描述 15
算法分析 18
1.5思考练习与算法设计 24
第2章 线性表 29
2.1线性表的逻辑结构 30
线性表的定义 30
线性表的抽象数据类型定义 30
2.2线性表的顺序存储结构及操作实现 32
顺序表的定义 32
顺序表的操作实现 33
2.3线性表链式存储结构及操作实现 37
单链表的定义 37
单链表的操作实现 39
循环链表的定义 44
循环链表的操作实现 45
2.4线性表两种存储结构的比较 47
结构特点的比较 47
存储空间的比较 48
操作时间的比较 48
2.5综合举例 48
2.6思考练习与算法设计 55
第3章 特殊线性表—栈、队列和串 60
3.1栈 61
栈的逻辑结构 61
栈的顺序存储结构及操作实现 62
栈的链式存储结构及操作实现 67
栈的两种存储结构比较 70
3.2队列 71
队列的逻辑结构 71
队列的顺序存储结构及操作实现 72
队列的链式存储结构及操作实现 76
队列的两种存储结构比较 80
3.3串 80
串的逻辑结构 81
串的顺序存储结构及操作实现 83
串的动态存储结构及操作实现 88
串的模式匹配 89
3.4综合举例 94
3.5思考练习与算法设计 101
第4章 广义线性表——数组和广义表 105
4.1数组 106
数组的逻辑结构 1106
数组的顺序存储结构及操作实现 107
4.2矩阵的压缩存储 110
特殊矩阵的压缩存储 111
稀疏矩阵的压缩存储 114
4.3广义表 123
广义表的逻辑结构 123
广义表的链式存储结构及操作实现 126
4.4综合举例 130
4.5思考练习与算法设计 140
第5章 树和二叉树 144
5.1树的逻辑结构 145
树的定义 145
树的抽象数据类型定义 148
树的遍历 149
5.2树的存储结构及操作实现 150
双亲表示法 150
孩子表示法 152
双亲孩子表示法 154
孩子兄弟表示法 156
5.3二叉树的逻辑结构 158
二叉树的定义 159
二叉树的抽象数据类型定义 163
二叉树的遍历 165
5.4二叉树的存储结构及操作实现 166
完全二叉树顺序表 166
链式存储结构 168
线索链表 172
5.5树和森林与二叉树的转换 177
树与二叉树的转换 177
森林与二叉树的转换 179
5.6哈夫曼树及其应用 181
哈夫曼树的定义 181
哈夫曼树的存储表示与实现 183
哈夫曼编码的定义 186
哈夫曼编码的存储表示与实现 187
5.7综合举例 189
5.8思考练习与算法设计 201
第6章 图 208
6.1图的逻辑结构 209
图的定义 209
图的抽象数据类型定义 212
图的遍历 214
6.2图的存储结构及操作实现 217
邻接矩阵 217
邻接表 220
十字链表 224
邻接多重表 225
图的存储结构比较 226
6.3图的连通性 227
无向图的连通性 227
生成树和生成森林 228
6.4最小生成树 230
MST性质 231
普里姆算法 231
克鲁斯卡尔算法 234
6.5最短路径 236
某个源点到其他顶点的最短路径 237
每对顶点之间的最短路径 239
6.6拓扑排序 241
AOV网 241
拓扑排序 242
6.7关键路径 244
AOE网 244
关键路径 245
6.8综合举例 249
6.9思考练习与算法设计 256
第7章 查找 263
7.1概述 264
查找的基本概念 264
查找的性能分析 265
7.2静态查找表 265
顺序查找 266
折半查找 267
分块查找 269
7.3动态查找表 271
二叉排序树 271
平衡二叉树 277
B_树 282
7.4哈希表 289
哈希表的基本概念 289
哈希函数的设计 290
冲突的处理 293
哈希表的查找及其性能分析 295
7.5综合举例 299
7.6思考练习与算法设计 305
第8章 排序 311
8.1概述 312
排序的基本概念 312
排序的性能分析 313
8.2插入排序 313
直接插入排序 313
希尔排序 315
8.3交换排序 317
冒泡排序 317
快速排序 318
8.4选择排序 321
简单选择排序 321
堆排序 323
8.5归并排序 328
二路归并排序 328
归并排序的递归实现 329
8.6各种排序方法比较 330
8.7综合举例 333
8.8思考练习与算法设计 336
附录A 数据结构类型定义 342