数据结构 C语言描述 第2版PDF电子书下载

第1章 绪论 1

1.1数据结构的概念及分类 1

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

1.1.2与数据结构相关的基本术语 2

1.1.3数据结构的分类 4

1.1.4数据结构的存储结构 6

1.1.5定义在数据结构上的操作 7

1.2使用C语言描述数据结构 7

1.2.1数据类型 7

1.2.2算法的控制结构 8

1.2.3算法的函数结构 9

1.2.4动态存储分配 12

1.2.5逻辑和关系运算的约定 12

1.2.6输入与输出 13

1.3算法和算法设计 13

1.3.1算法的定义和特性 13

1.3.2算法的设计步骤 14

1.3.3算法设计的基本方法 15

1.4算法分析与度量 19

1.4.1算法的评价标准 19

1.4.2算法的时间和空间复杂度度量 20

1.4.3算法的渐近分析 23

小结 25

习题 25

第2章 线性表 27

2.1概述 27

2.1.1线性表的定义和特点 27

2.1.2线性表的主要操作 28

2.2顺序表 29

2.2.1顺序表的定义和特点 29

2.2.2顺序表的结构定义 30

2.2.3顺序表主要操作的实现 31

2.2.4顺序表主要操作的性能分析 32

2.2.5顺序表的应用举例 33

2.3单链表 34

2.3.1单链表的定义和特点 34

2.3.2单链表的结构定义 35

2.3.3单链表中的插入与删除 36

2.3.4带头结点的单链表 38

2.3.5单链表的顺序访问与尾递归 40

2.3.6单链表的应用举例 42

2.3.7循环单链表 44

2.3.8双向链表 47

2.3.9静态链表 51

2.4顺序表与单链表的比较 52

2.5单链表的应用：一元多项式及其运算 53

2.5.1一元多项式的表示 53

2.5.2多项式的结构定义 54

2.5.3多项式的加法 56

2.5.4多项式的乘法 57

小结 59

习题 59

第3章 栈和队列 62

3.1栈 62

3.1.1栈的概念 62

3.1.2顺序栈 63

3.1.3链式栈 67

3.1.4栈的混洗 69

3.2队列 70

3.2.1队列的概念 71

3.2.2循环队列 72

3.2.3链式队列 75

3.3栈的应用 77

3.3.1数制转换 77

3.3.2括号匹配 78

3.3.3表达式的计算与优先级处理 79

3.3.4栈与递归的实现 84

3.4队列的应用 87

3.4.1打印杨辉三角形与逐行处理 87

3.4.2电路布线与两点间的最短路径 89

3.5在算法设计中使用递归 91

3.5.1汉诺塔问题与分治法 91

3.5.2迷宫问题与回溯法 94

3.6双端队列 96

3.6.1双端队列的概念 97

3.6.2输入受限的双端队列 97

3.6.3输出受限的双端队列 98

3.6.4双端队列的存储表示 98

3.7优先队列 100

3.7.1优先队列的概念 100

3.7.2优先队列的实现 100

小结 101

习题 102

第4章 字符串 105

4.1字符串的概念 105

4.1.1字符串的基本概念 105

4.1.2字符串的初始化和赋值 106

4.1.3 C语言中有关字符串的库函数 107

4.1.4字符串的自定义操作 108

4.2字符串的实现 109

4.2.1定长顺序存储表示 109

4.2.2堆分配存储表示 110

4.2.3块链存储表示 112

4.3字符串的模式匹配 113

4.3.1 BF模式匹配算法 113

4.3.2无回溯的KMP模式匹配算法 114

4.3.3 BM模式匹配算法 119

小结 121

习题 121

第5章 多维数组和广义表 123

5.1数组 123

5.1.1一维数组 123

5.1.2多维数组 125

5.2特殊矩阵 126

5.2.1对称矩阵的压缩存储 127

5.2.2三对角矩阵的压缩存储 128

5.2.3w对角矩阵的压缩存储 129

5.3稀疏矩阵 130

5.3.1稀疏矩阵的概念 130

5.3.2稀疏矩阵的顺序存储表示 130

5.3.3稀疏矩阵的链接存储表示 137

5.4广义表 140

5.4.1广义表的概念 140

5.4.2广义表的性质 141

5.4.3广义表的头尾表示法 142

5.4.4广义表的扩展线性链表表示 145

5.4.5广义表的层次表示法 146

5.4.6广义表的应用举例：三元多项式的表示 148

小结 150

习题 151

第6章 树与二叉树 153

6.1树的基本概念 153

6.1.1树的定义和术语 153

6.1.2树的基本操作 155

6.2二叉树及其存储表示 156

6.2.1二叉树的概念 156

6.2.2二叉树的性质 157

6.2.3二叉树的主要操作 159

6.2.4二叉树的顺序存储表示 160

6.2.5二叉树的链接存储表示 161

6.3二叉树的遍历 163

6.3.1二叉树遍历的递归算法 163

6.3.2递归遍历算法的应用举例 164

6.3.3二叉树遍历的非递归算法 167

6.3.4利用队列实现二叉树的层次序遍历 170

6.3.5二叉树的计数 171

6.4线索二叉树 173

6.4.1线索二叉树的概念 173

6.4.2线索二叉树的种类 174

6.4.3中序线索二叉树的建立和遍历 174

6.4.4先序与后序线索二叉树 176

6.5树与森林 178

6.5.1树的存储表示 178

6.5.2森林与二叉树的转换 183

6.5.3树与森林的深度优先遍历 184

6.5.4树与森林的广度优先遍历 187

6.5.5树遍历算法的应用举例 188

小结 189

习题 190

第7章 树与二叉树的应用 193

7.1 Huffman树 193

7.1.1带权路径长度的概念 193

7.1.2 Huffman树的概念 194

7.1.3最优判定树 197

7.1.4 Huffman编码 199

7.2堆 200

7.2.1小根堆和大根堆 200

7.2.2堆的建立 201

7.2.3堆的插入 202

7.2.4堆的删除 203

7.3二叉查找树 204

7.3.1二叉查找树的概念 204

7.3.2二叉查找树的查找 205

7.3.3二叉查找树的插入 206

7.3.4二叉查找树的删除 207

7.3.5二叉查找树的性能分析 208

7.4 AVL树 211

7.4.1 AVL树的概念 211

7.4.2平衡化旋转 211

7.4.3 AVL树的插入 213

7.4.4 AVL树的删除 215

7.4.5 AVL树的性能分析 217

7.5表达式树 218

7.5.1从中缀表达式建立表达式树 218

7.5.2从后缀表达式建立表达式树 221

7.5.3利用表达式树求值 222

7.6等价类与并查集 223

7.6.1等价关系与等价类 223

7.6.2确定等价类的方法 223

7.6.3并查集的定义及其实现 224

7.6.4并查集操作的分析和改进 226

7.7八皇后问题与树的剪枝 228

7.7.1八皇后问题的提出 228

7.7.2八皇后问题的状态树 228

7.7.3八皇后问题的算法 230

小结 231

习题 231

第8章 图 234

8.1图的基本概念 234

8.1.1与图有关的若干概念 234

8.1.2图的基本操作 237

8.2图的存储结构 238

8.2.1图的邻接矩阵表示 238

8.2.2图的邻接表表示 241

8.2.3邻接矩阵表示与邻接表表示的比较 245

8.2.4无向图的邻接多重表表示 246

8.2.5有向图的十字链表表示 247

8.3图的遍历 247

8.3.1深度优先搜索 248

8.3.2广度优先搜索 249

8.3.3连通分量 250

8.3.4双连通图 251

8.3.5有向图的强连通分量 253

8.4最小生成树 254

8.4.1最小生成树求解和贪心法 255

8.4.2 Kruskal算法 256

8.4.3 Prim算法 258

8.4.4 Rosenstiehl和管梅谷算法 260

8.5最短路径 261

8.5.1非负权值的单源最短路径 261

8.5.2边上权值为任意值的单源最短路径问题 264

8.5.3所有顶点之间的最短路径 266

8.5.4无权有向图的最短路径 269

8.5.5无权有向图的传递闭包 270

8.6活动网络 271

8.6.1 AOV网络和拓扑排序 271

8.6.2 AOE网络与关键路径 274

小结 278

习题 279

第9章 查找 282

9.1查找的基本概念 282

9.1.1查找的概念 282

9.1.2查找算法的性能分析 283

9.2顺序查找 283

9.2.1在普通顺序表上的顺序查找算法 283

9.2.2在有序顺序表上的顺序查找算法 284

9.3折半查找 285

9.3.1折半查找方法 285

9.3.2最优二叉查找树 288

9.3.3次优二叉查找树 289

9.3.4斐波那契查找和插值查找 292

9.3.5跳表 293

9.4 B树 294

9.4.1索引顺序表与分块查找 294

9.4.2多级索引结构与m叉查找树 296

9.4.3 B树的概念 297

9.4.4 B树上的查找 298

9.4.5 B树上的插入 299

9.4.6 B树上的删除 301

9.4.7 B+树 303

9.5其他查找树 306

9.5.1红黑树 306

9.5.2伸展树 308

9.5.3键树 310

9.6散列法 312

9.6.1散列的概念 312

9.6.2常见的散列函数 313

9.6.3解决冲突的开地址法 316

9.6.4解决冲突的链地址法 323

9.6.5散列法分析 325

小结 326

习题 327

第10章 排序 330

10.1排序的概念与算法性能 330

10.1.1排序的概念 330

10.1.2排序算法的性能 331

10.1.3数据表的结构定义 332

10.2插入排序 333

10.2.1直接插入排序 333

10.2.2基于静态链表的直接插入排序 335

10.2.3折半插入排序 336

10.2.4希尔排序 337

10.3交换排序 338

10.3.1起泡排序 338

10.3.2快速排序 340

10.3.3快速排序的改进算法 343

10.4选择排序 344

10.4.1简单选择排序 344

10.4.2锦标赛排序 346

10.4.3堆排序 348

10.5归并排序 350

10.5.1二路归并排序的设计思路 350

10.5.2二路归并排序的递归算法 351

10.5.3二路归并排序的迭代算法 352

10.6基数排序 354

10.6.1基数排序的概念 354

10.6.2 MSD基数排序 355

10.6.3 LSD基数排序 357

10.7内部排序算法的分析和比较 359

10.7.1排序算法的下界 359

10.7.2各种内部排序算法的比较 360

10.8外部排序 362

10.8.1常用的外存储器与缓冲区 362

10.8.2基于磁盘的外部排序过程 363

10.8.3 m路平衡归并的过程 365

10.8.4初始归并段的生成 369

10.8.5最佳归并树 371

10.8.6磁带归并排序 374

小结 376

习题 377

附录 实训作业要求与样例 380

参考文献 385