数据结构（第二版）

目录
第1章绪论1
1.1问题的分析1
1.1.1系统与结构1
1.1.2抽象与模型3
1.1.3数据结构与算法4
1.2数据结构的相关概念4
1.2.1基本概念5
1.2.2数据的逻辑结构6
1.2.3数据的存储结构8
1.3数据类型与抽象数据类型9
1.3.1数据类型9
1.3.2抽象数据类型9
1.3.3抽象数据类型实现11
1.4算法和算法分析11
1.4.1算法特性11
1.4.2算法描述12
1.4.3算法性能分析与度量14
1.5本章小结17
习题18
第2章线性表20
2.1线性表的定义20
2.2线性表的问题案例20
2.3线性表的抽象数据类型21
2.4顺序表及基本操作24
2.4.1线性表的顺序存储24
2.4.2顺序表的实现24
2.5顺序查找28
2.5.1静态查找表28
2.5.2顺序查找算法29
2.6线性表的链式存储结构及基本操作31
2.6.1线性表的链式存储31
2.6.2单链表的实现32
2.6.3其他形式的链表38
2.7线性表的其他存储方法40
2.7.1顺序存储与链式存储的比较40
2.7.2静态链表41
2.7.3间接寻址存储41
2.8问题案例分析与实现42
2.9本章小结46
习题47
第3章栈、队列和串49
3.1栈49
3.1.1栈的逻辑结构49
3.1.2栈的问题案例51
3.1.3栈的顺序存储结构及基本操作52
3.1.4栈的链式存储结构及基本操作55
3.1.5顺序栈和链栈的比较57
3.1.6案例求解57
3.2队列62
3.2.1队列的逻辑结构62
3.2.2队列的顺序存储结构及实现64
3.2.3队列的链式存储结构及实现67
3.2.4循环队列和链队的比较70
3.2.5队列的应用70
3.3串71
3.3.1串的逻辑结构71
3.3.2串的存储结构73
3.3.3模式匹配算法75
3.4本章小结80习题81
第4章哈希表83
4.1哈希表的概念83
4.2哈希表的问题案例83
4.3哈希表的构建84
4.4常用的哈希函数84
4.5处理冲突的方法86
4.6哈希表的查找分析88
4.7问题案例分析与实现944.8
本章小结105习题105
第5章递归与广义表107
5.1递归107
5.1.1递归的基本概念107
5.1.2递归的问题案例108
5.1.3递归函数及其执行过程108
5.1.4递归与分治109
5.1.5迭代和递归111
5.2广义线性表112
5.2.1数组的定义112
5.2.2数组的顺序存储114
5.3矩阵的压缩存储116
5.3.1特殊矩阵的压缩存储116
5.3.2稀疏矩阵的压缩存储118
5.3.3稀疏矩阵的运算121
5.4广义表130
5.4.1广义表的逻辑结构131
5.4.2广义表的问题案例131
5.4.3广义表的抽象数据类型132
5.4.4广义表的存储133
5.4.5广义表的实现135
5.5本章小结139
习题139
第6章二叉树和树141
6.1树的定义和基本术语141
6.1.1树的定义141
6.1.2树的基本术语142
6.2二叉树的相关定义143
6.2.1二叉树的概念和性质143
6.2.2二叉树的问题案例145
6.2.3二叉树的抽象数据类型和特殊的二叉树145
6.3二叉树的存储结构与实现152
6.3.1二叉树的存储结构152
6.3.2二叉树的基本操作及实现155
6.4二叉树的遍历161
6.4.1二叉树的遍历方法及递归实现161
6.4.2二叉树遍历的非递归实现166
6.4.3由遍历序列恢复二叉树170
6.4.4不用栈的二叉树遍历的非递归方法171
6.5线索二叉树172
6.5.1线索二叉树的定义及其结构172
6.5.2线索二叉树的基本操作及实现174
6.6二叉树的应用178
6.6.1二叉树遍历的应用178
6.6.2*优二叉树―哈夫曼树179
6.6.3查找与二叉树185
6.6.4二叉排序树188
6.6.5平衡二叉树194
6.7树的操作与存储199
6.7.1树的基本操作199
6.7.2树的存储结构203
6.8树、森林与二叉树的转换206
6.8.1树转换为二叉树206
6.8.2森林转换为二叉树207
6.8.3二叉树转换为树和森林208
6.9树和森林的遍历208
6.9.1树的遍历208
6.9.2森林的遍历209
6.10树的应用209
6.10.1判定树210
6.10.2集合的表示211
6.10.3求关系等价类问题213
6.11B-树和B+树214
6.12本章小结219
习题220
第7章图222
7.1图的基本概念222
7.1.1图的定义222
7.1.2图的基本术语223
7.2图的问题案例225
7.3图的抽象数据类型225
7.4图的存储结构及操作228
7.4.1邻接矩阵228
7.4.2邻接表231
7.4.3十字链表234
7.4.4邻接多重表237
7.5图的遍历238
7.5.1深度优先搜索238
7.5.2广度优先搜索240
7.6图的连通性241
7.6.1无向图的连通性242
7.6.2有向图的连通性242
7.6.3生成树和生成森林243
7.6.4关结点和重连通分量245
7.7*小生成树248
7.7.1*小生成树的基本概念248
7.7.2构造*小生成树的Prim算法249
7.7.3构造*小生成树的Kruskal算法251
7.8*短路径253
7.8.1从一个源点到其他各点的*短路径253
7.8.2每一对顶点之间的*短路径257
7.9有向无环图及其应用259
7.9.1有向无环图的概念259
7.9.2AOV网与拓扑排序259
7.9.3AOE网与关键路径263
7.10本章小结269
习题270
第8章排序273
8.1基本概念273
8.2插入排序274
8.2.1直接插入排序274
8.2.2折半插入排序276
8.2.3表插入排序277
8.2.4希尔排序281
8.3交换排序282
8.3.1冒泡排序282
8.3.2快速排序283
8.4选择排序287
8.4.1简单选择排序287
8.4.2树形选择排序288
8.4.3堆排序291
8.5归并排序294
8.6基数排序296
8.6.1多关键字排序296
8.6.2链式基数排序297
8.7各种内部排序算法的比较301
8.8本章小结302
习题302
参考文献304