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

第1章 绪论 1

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

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

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

1.1.3数据结构的分类 5

1.1.4数据结构的存储结构 7

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

1.1.6“好”的数据结构 9

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

1.2.1 C语言的数据类型 9

1.2.2算法的控制结构 10

1.2.3算法的函数结构 11

1.2.4动态存储分配 14

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

1.2.6输入与输出 16

1.3算法和算法设计 17

1.3.1算法的定义和特性 17

1.3.2算法的设计步骤 17

1.3.3算法设计的基本方法 18

1.4算法分析与度量 21

1.4.1算法的评价标准 22

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

1.4.3算法的渐进分析 25

小结 29

习题 29

第2章 线性表 32

2.1线性表 32

2.1.1线性表的定义和特点 32

2.1.2线性表的主要操作 33

2.2顺序表 34

2.2.1顺序表的定义和特点 34

2.2.2顺序表的结构定义 35

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

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

2.2.5顺序表的应用举例 40

2.3单链表 41

2.3.1单链表的定义和特点 41

2.3.2单链表的结构定义 42

2.3.3单链表中指针的操作 42

2.3.4单链表中的插入与删除 43

2.3.5带头结点的单链表 46

2.3.6单链表主要操作的性能分析 48

2.3.7单链表的顺序访问与尾递归 49

2.3.8单链表的应用举例 51

2.4顺序表与线性链表的比较 53

2.5线性链表的其他变形 55

2.5.1循环链表 55

2.5.2双向链表 59

2.5.3静态链表 62

2.6线性表的应用：一元多项式及其运算 63

2.6.1一元多项式的表示 64

2.6.2多项式的结构定义 65

2.6.3多项式的加法 66

2.6.4多项式的乘法 68

小结 69

习题 70

第3章 栈和队列 74

3.1栈 74

3.1.1栈的概念 74

3.1.2顺序栈 75

3.1.3链式栈 80

3.1.4栈的混洗 82

3.2队列 83

3.2.1队列的概念 83

3.2.2循环队列 85

3.2.3链式队列 88

3.3栈的应用 90

3.3.1数制转换 91

3.3.2括号匹配 91

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

3.3.4栈与递归的实现 98

3.4队列的应用 100

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

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

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

3.5.1汉诺塔问题与分治法 105

3.5.2迷宫问题与回溯法 107

3.5.3计算组合数与动态规划 111

3.6双端队列 113

3.6.1双端队列的概念 113

3.6.2输入受限的双端队列 113

3.6.3输出受限的双端队列 114

3.6.4双端队列的顺序存储表示 115

3.6.5双端队列的链接存储表示 117

小结 117

习题 118

第4章 数组、串和广义表 122

4.1数组 122

4.1.1一维数组 122

4.1.2多维数组 124

4.1.3数组的应用举例 126

4.2特殊矩阵的压缩存储 127

4.2.1对称矩阵的压缩存储 128

4.2.2三对角矩阵的压缩存储 129

4.3稀疏矩阵 131

4.3.1稀疏矩阵的概念 131

4.3.2稀疏矩阵的三元组表表示 131

4.3.3稀疏矩阵的十字链表表示 132

4.4字符串 134

4.4.1字符串的概念 134

4.4.2字符串的初始化和赋值 134

4.4.3 C语言中有关字符串的库函数 135

4.4.4自定义字符串的存储表示 137

4.4.5串的模式匹配 141

4.5广义表 147

4.5.1广义表的概念 147

4.5.2广义表的性质 148

4.5.3广义表的链接表示 149

4.5.4三元多项式的表示 151

小结 153

习题 154

第5章 树与二叉树 157

5.1树的基本概念 157

5.1.1树的定义和术语 157

5.1.2树的基本操作 160

5.2二叉树 161

5.2.1二叉树的概念 161

5.2.2二叉树的性质 161

5.2.3二叉树的主要操作 163

5.3二叉树的存储表示 165

5.3.1二叉树的顺序存储表示 165

5.3.2二叉树的链表存储表示 166

5.4二叉树的遍历 167

5.4.1二叉树遍历的递归算法 167

5.4.2递归遍历算法的应用举例 168

5.4.3二叉树遍历的非递归算法 171

5.4.4非递归遍历算法的应用举例 176

5.4.5二叉树的计数 178

5.5线索二叉树 181

5.5.1线索二叉树的概念 182

5.5.2线索二叉树的种类 182

5.5.3中序线索二叉树的建立和遍历 183

5.5.4前序与后序线索二叉树 185

5.6树与森林 187

5.6.1树的存储表示 187

5.6.2森林与二叉树的转换 190

5.6.3树与森林的深度优先遍历 192

5.6.4树与森林的广度优先遍历 194

5.6.5树遍历算法的应用举例 195

小结 196

习题 197

第6章 树与二叉树的应用 201

6.1二叉查找树 201

6.1.1二叉查找树的概念 201

6.1.2二叉查找树的查找 202

6.1.3二叉查找树的插入 203

6.1.4二叉查找树的删除 205

6.1.5二叉查找树的性能分析 207

6.2 AVL树 209

6.2.1 AVL树的概念 209

6.2.2平衡化旋转 210

6.2.3 AVL树的插入 212

6.2.4 AVL树的删除 214

6.2.5 AVL树的性能分析 216

6.3 Huffman树 218

6.3.1带权路径长度的概念 218

6.3.2 Huffman树的概念 219

6.3.3最优判定树 222

6.3.4 Huffman编码 224

6.4堆 225

6.4.1小根堆和大根堆 225

6.4.2堆的建立 227

6.4.3堆的插入 228

6.4.4堆的删除 230

6.5并查集 230

6.5.1并查集的定义及其实现 230

6.5.2并查集操作的分析和改进 232

6.6八皇后问题与树的剪枝 234

6.6.1八皇后问题的提出 234

6.6.2八皇后问题的状态树 235

6.6.3八皇后问题算法 237

小结 238

习题 238

第7章图 242

7.1图的基本概念 242

7.1.1与图有关的若干概念 242

7.1.2图的基本操作 245

7.2图的存储结构 247

7.2.1图的邻接矩阵表示 247

7.2.2图的邻接表表示 251

7.2.3邻接矩阵表示与邻接表表示的比较 256

7.2.4图的邻接多重表表示 256

7.3图的遍历 258

7.3.1深度优先搜索 258

7.3.2广度优先搜索 260

7.3.3连通分量 261

7.3.4重连通图 263

7.3.5有向图的强连通分量 265

7.4最小生成树 267

7.4.1最小生成树求解和贪婪法 267

7.4.2 Kruskal算法 269

7.4.3 Prim算法 272

7.5最短路径 274

7.5.1非负权重的单源最短路径 274

7.5.2所有顶点之间的最短路径 278

7.5.3无权重的最短路径 281

7.6活动网络 282

7.6.1 AOV网络与拓扑排序 282

7.6.2 AOE网络与关键路径法 286

小结 291

习题 291

第8章 查找 297

8.1查找的基本概念 297

8.1.1查找的概念 297

8.1.2查找算法的性能分析 298

8.2顺序查找法 298

8.2.1在顺序表上的顺序查找算法 298

8.2.2在线性链表上的顺序查找算法 302

8.3折半查找法 302

8.3.1折半查找法 302

8.3.2次优查找树：折半查找的改进方法 305

8.3.3斐波那契查找：折半查找的变形 310

8.3.4插值查找：折半查找的变形 312

8.4 B树 313

8.4.1索引顺序表与分块查找 313

8.4.2多级索引结构与m叉查找树 315

8.4.3 B树的概念 316

8.4.4 B树上的查找 317

8.4.5 B树上的插入 318

8.4.6 B树上的删除 320

8.4.7 B+树 321

8.5散列表及其查找 324

8.5.1散列的概念 324

8.5.2常见的散列函数 325

8.5.3解决冲突的开地址法 328

8.5.4解决冲突的链地址法 335

8.5.5散列法分析 337

小结 338

习题 339

第9章 内排序 344

9.1排序的概念 344

9.1.1排序的概念 344

9.1.2排序算法的性能 345

9.1.3数据表的结构定义 346

9.2插入排序 347

9.2.1直接插入排序 347

9.2.2基于链表的直接插入排序 349

9.2.3折半插入排序 350

9.2.4希尔排序 352

9.3交换排序 353

9.3.1起泡排序 354

9.3.2快速排序 356

9.3.3快速排序的改进算法 359

9.4选择排序 360

9.4.1简单选择排序 361

9.4.2堆排序 362

9.4.3锦标赛排序 366

9.5归并排序 367

9.5.1二路归并排序的设计思路 367

9.5.2二路归并排序的递归算法 367

9.5.3基于链表的归并排序算法 369

9.5.4迭代的归并排序算法 371

9.6基数排序 373

9.6.1基数排序 373

9.6.2 MSD基数排序 374

9.6.3 LSD基数排序 376

9.7内排序算法的分析和比较 379

9.7.1排序方法的下界 379

9.7.2分布计数排序 380

9.7.3各种内排序方法的比较 381

小结 384

习题 385

第10章 外排序 389

10.1主存储器和外存储器 389

10.1.1磁带 389

10.1.2磁盘存储器 390

10.1.3缓冲区 391

10.2基于磁盘的外排序过程 392

10.2.1基于磁盘排序的过程 392

10.2.2基于磁盘排序的性能分析 393

10.3 m路平衡归并 394

10.3.1 m路平衡归并的过程 394

10.3.2用败者树选最小记录 395

10.3.3败者树的构造 396

10.4初始归并段的生成 398

10.4.1置换-选择排序 398

10.4.2用败者树实现置换-选择排序 398

10.4.3用小根堆实现置换-选择排序 399

10.4.4置换-选择排序的性能分析 402

10.5最佳归并树 403

10.6并行操作的缓冲区处理 405

10.6.1使用固定缓冲区实现并行操作 405

10.6.2使用缓冲区队列实现并行操作 405

10.7磁带归并排序 407

10.7.1平衡归并排序 408

10.7.2多步归并排序 408

10.7.3多步归并排序初始归并段的分配 409

小结 410

习题 411

附录A程序索引 413

附录B实训作业要求与样例 420

参考文献 426