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

第1章 概论 1

1.1什么是数据结构 1

1.1.1数据和数据元素 1

1.1.2数据类型与数据对象 1

1.1.3数据结构 2

1.2为什么要学习数据结构 4

1.2.1学习数据结构的重要性 4

1.2.2数据结构的应用举例 5

1.3算法和算法分析 6

1.3.1算法的概念 6

1.3.2算法的描述和设计 7

1.3.3算法分析 7

本章小结 9

习题1 10

第2章 线性表 12

2.1线性表的基本概念 12

2.1.1线性表的定义 12

2.1.2线性表的基本操作 13

2.2线性表的顺序存储 13

2.2.1顺序表 13

2.2.2顺序表的基本操作 14

2.2.3一个完整的例子（1） 17

2.3线性表的链式存储 19

2.3.1单链表的基本概念 20

2.3.2单链表的基本操作 21

2.3.3一个完整的例子（2） 25

2.3.4循环链表 27

2.3.5双向链表 30

2.3.6双向循环链表 32

2.3.7静态链表 33

2.4线性表顺序存储与链式存储的比较 34

2.5线性表的应用 35

2.5.1约瑟夫问题 36

2.5.2多项式加法 38

2.5.3电文加密 40

本章小结 42

习题2 42

第3章 栈和队列 44

3.1栈 44

3.1.1栈的定义与基本操作 44

3.1.2顺序栈的存储结构和操作的实现 45

3.1.3链栈的存储结构和操作的实现 49

3.2栈的应用 50

3.2.1数制转换 50

3.2.2括号匹配问题 52

3.2.3子程序的调用 53

3.2.4利用一个顺序栈逆置一个带头结点的单链表 54

3.3队列 57

3.3.1队列的定义与基本操作 57

3.3.2链队列的存储结构和操作的实现 58

3.3.3顺序队列的存储结构和操作的实现 60

3.4队列的应用 64

3.4.1打印杨辉三角形 64

3.4.2迷宫问题：寻找一条从迷宫入口到出口的最短路径 67

3.5递归 69

3.5.1递归的定义与实现 70

3.5.2递归消除 73

本章小结 75

习题3 76

第4章 串 79

4.1串的定义和基本操作 79

4.1.1串的定义 79

4.1.2串的基本操作 81

4.2串的表示和实现 82

4.2.1串的定长顺序存储 82

4.2.2串的堆存储结构 85

4.2.3串的块链存储结构 86

4.3串的模式匹配算法 91

4.3.1基本的模式匹配算法 91

4.3.2模式匹配的改进算法——KMP算法 93

本章小结 95

习题4 95

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

5.1多维数组 97

5.1.1多维数组的定义 97

5.1.2数组的存储结构 98

5.2矩阵的压缩存储 99

5.2.1特殊矩阵 99

5.2.2稀疏矩阵 101

5.3广义表 107

本章小结 109

习题5 109

第6章 树和二叉树 111

6.1树的概念与基本操作 111

6.1.1树的定义 111

6.1.2树的一些基本概念 112

6.1.3树的基本操作 112

6.2二叉树 113

6.2.1二叉树的定义和基本操作 113

6.2.2二叉树的性质 114

6.2.3二叉树的存储结构 115

6.3二叉树的遍历与线索化 116

6.3.1二叉树的遍历 116

6.3.2线索二叉树 119

6.3.3基于遍历的应用与线索二叉树的应用 121

6.4树和森林 126

6.4.1树的存储结构 126

6.4.2树、森林和二叉树之间的转换 128

6.4.3树和森林的遍历 132

6.5哈夫曼树及其应用 133

6.5.1与哈夫曼树相关的基本概念 133

6.5.2哈夫曼树的应用 135

6.5.3哈夫曼编码算法的实现 137

6.6树的计数 138

本章小结 141

习题6 141

第7章 图 144

7.1基本概念 144

7.1.1图的定义 144

7.1.2图的相关术语 145

7.2图的存储结构 147

7.2.1邻接矩阵表示法 147

7.2.2邻接表表示法 149

7.3图的遍历 153

7.3.1深度优先搜索法 153

7.3.2广度优先搜索法 155

7.3.3非连通图的遍历 156

7.4生成树与最小生成树 157

7.4.1生成树的概念 157

7.4.2构造最小生成树的普里姆（Prim）算法 158

7.4.3构造最小生成树的克鲁斯卡尔（Kruskal）算法 160

7.5最短路径 163

7.5.1从某个源点到其余各顶点的最短路径 163

7.5.2每一对顶点之间的最短路径 167

7.6拓扑排序 170

7.7关键路径 173

本章小结 178

习题7 178

第8章 查找 182

8.1查找的基本概念 182

8.2线性表的查找 183

8.2.1顺序查找 183

8.2.2二分查找 185

8.2.3分块查找 188

8.3树表的查找 190

8.3.1二叉排序树 190

8.3.2 B-树 195

8.3.3 B-树上的基本运算 197

8.4散列表的查找 202

8.4.1散列表的概念 202

8.4.2散列函数的构造方法 203

8.4.3处理冲突的方法 204

8.4.4散列表上的运算 207

本章小结 211

习题8 211

第9章 排序 213

9.1排序的基本概念 213

9.1.1关键字与排序 213

9.1.2排序的稳定性 214

9.1.3排序方法的分类 214

9.1.4排序算法性能评价 214

9.1.5不同存储方式的排序过程 214

9.2插入排序 215

9.2.1直接插入排序 215

9.2.2希尔排序 218

9.3交换排序 220

9.3.1冒泡排序 220

9.3.2快速排序 221

9.4选择排序 225

9.4.1直接选择排序 225

9.4.2堆排序 226

9.5归并排序 230

9.6基数排序 233

9.6.1多关键字的排序 233

9.6.2链式基数排序 234

9.7内部排序算法比较 236

9.8外部排序简介 238

本章小结 239

习题9 239

参考文献 242