数据结构 第2版PDF电子书下载

第1章　绪论 1

1-1　数据结构的概念 1

1-1-1 为什么要学习数据结构 1

1-1-2　相关概念和术语 4

1-1-3　数据结构课程的内容 6

1-2　数据类型和抽象数据类型 7

1-2-1　数据类型 7

1-2-2　抽象数据类型 8

1-3　算法和算法分析 9

1-3-1　算法特性 9

1-3-2　算法描述 9

1-3-3　算法性能分析与度量 10

习题 11

第2章　线性表 13

2-1　线性表的逻辑结构 13

2-1-1　线性表的定义 13

2-1-2　线性表的基本操作 13

2-2　线性表的顺序存储及运算实现 14

2-2-1　顺序表 14

2-2-2　顺序表上基本运算的实现 16

2-2-3　顺序表应用举例 19

2-3　线性表的链式存储和运算实现 22

2-3-1 单链表 22

2-3-2　单链表上基本运算的实现 24

2-3-3　循环链表 30

2-3-4　双向链表 31

2-3-5 静态链表 32

2-3-6　单链表应用举例 34

2-4　顺序表和链表的比较 36

习题 37

第3章　栈和队列 39

3-1 栈 39

3-1-1　栈的定义及基本运算 39

3-1-2　栈的存储实现和运算实现 40

3-2　栈的应用举例 43

3-3 队列 53

3-3-1 队列的定义及基本运算 53

3-3-2　队列的存储实现及运算实现 54

3-4　队列应用举例 59

习题 62

第4章 串 63

4-1　串及其基本运算 63

4-1-1 串的基本概念 63

4-1-2　串的基本运算 63

4-2 串的定长顺序存储及基本运算 64

4-2-1 串的定长顺序存储 64

4-2-2　定长顺序串的基本运算 65

4-2-3　模式匹配 66

4-3 串的堆存储结构 72

4-3-1 串名的存储映像 72

4-3-2　堆存储结构 74

4-3-3　基于堆结构的串的基本运算实现 74

习题 76

第5章　数组和广义表 77

5-1　多维数组 77

5-1-1　数组的逻辑结构 77

5-1-2　数组的内存映像 77

5-2　特殊矩阵的压缩存储 80

5-2-1　对称矩阵 80

5-2-2　三角矩阵 81

5-2-3　带状矩阵 82

5-3　稀疏矩阵 83

5-3-1　稀疏矩阵的三元组表存储 83

5-3-2　稀疏矩阵的十字链表存储 90

5-4　广义表 95

5-4-1 广义表的定义和基本运算 95

5-4-2　广义表的存储 96

5-4-3　广义表基本操作的实现 99

习题 102

第6章　二叉树 104

6-1 二叉树的定义与性质 104

6-1-1　二叉树的基本概念 104

6-1-2　二叉树的主要性质 106

6-2　二叉树的基本操作与存储实现 107

6-2-1　二叉树的存储 107

6-2-2　二叉树的基本操作及实现 110

6-3　二叉树的遍历 112

6-3-1 二叉树的遍历方法及递归实现 112

6-3-2　二叉树遍历的非递归实现 115

6-3-3 由遍历序列恢复二叉树 118

6-3-4　不用栈的二叉树遍历的非递归方法 120

6-4　线索二叉树 121

6-4-1 线索二叉树的定义及结构 121

6-4-2　线索二叉树的基本操作实现 123

6-5　二叉树的应用 128

6-5-1　二叉树遍历的应用 128

6-5-2　最优二叉树——哈夫曼树 131

习题 139

第7章　树与森林 141

7-1　树的概念与表示 141

7-1-1　树的定义及相关术语 141

7-1-2　树的表示 142

7-2　树的基本操作与存储 143

7-2-1　树的基本操作 143

7-2-2　树的存储结构 144

7-3　树、森林与二叉树的转换 147

7-3-1　树转换为二叉树 147

7-3-2　森林转换为二叉树 148

7-3-3　二叉树转换为树和森林 149

7-4　树和森林的遍历 150

7-4-1　树的遍历 150

7-4-2　森林的遍历 150

7-5　树的应用 151

7-5-1　判定树 151

7-5-2　集合的表示 152

7-5-3　等价问题 154

习题 155

第8章　图 157

8-1 图的基本概念 157

8-1-1 图的定义和术语 157

8-1-2　图的基本操作 160

8-2　图的存储结构 160

8-2-1　邻接矩阵 160

8-2-2　邻接表 162

8-2-3　十字链表 164

8-2-4　邻接多重表 166

8-3　图的遍历 168

8-3-1　深度优先搜索 168

8-3-2　广度优先搜索 170

8-3-3　应用图的遍历判定图的连通性 172

8-4　生成树与最小生成树 172

8-4-1　生成树和生成森林 172

8-4-2　最小生成树的概念 174

8-4-3　构造最小生成树的Prim算法 175

8-4-4　构造最小生成树的Kruskal算法 178

8-5　最短路径 180

8-5-1　从一个源点到其他各点的最短路径 180

8-5-2　每一对顶点之间的最短路径 184

8-6　有向无环图及其应用 186

8-6-1　有向无环图的概念 186

8-6-2　AOV网与拓扑排序 187

8-6-3　AOE图与关键路径 192

习题 196

第9章　查找 199

9-1　基本概念 199

9-2　静态查找表 200

9-2-1　静态查找表结构 200

9-2-2　顺序查找 200

9-2-3　有序表的查找 201

9-2-4　分块查找 205

9-3　动态查找表 206

9-3-1 二叉排序树 206

9-3-2　平衡二叉树 211

9-3-3　B树和B＋树 218

9-4　哈希表查找（杂凑法） 225

9-4-1　哈希表与哈希方法 225

9-4-2　常用的哈希函数 226

9-4-3　处理冲突的方法 228

9-4-4　哈希表的查找分析 230

习题 231

第10章　排序 234

10-1　排序的基本概念 234

10-2　插入排序 235

10-2-1　直接插入排序 235

10-2-2　折半插入排序 236

10-2-3　表插入排序 237

10-2-4　希尔排序 239

10-3　交换排序 240

10-3-1 冒泡排序 240

10-3-2　快速排序 241

10-4　选择排序 244

10-4-1　简单选择排序 244

10-4-2　树形选择排序 244

10-4-3　堆排序 245

10-5　归并排序 248

10-6　基数排序 250

10-6-1 多关键码排序 250

10-6-2　链式基数排序 251

10-7　外排序 253

10-7-1　外部排序的方法 253

10-7-2　多路平衡归并的实现 255

习题 258

参考文献 260