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

查看更多关于的内容

第1章 引论 1

1.1 算法及其复杂性的概念 1

1.1.1 算法与程序 1

1.1.2 算法复杂性的概念 1

1.1.3 算法复杂性的渐近性态 3

1.2 算法的表达与数据表示 5

1.2.1 问题求解 5

1.2.2 表达算法的抽象机制 5

1.3 抽象数据类型 8

1.3.1 抽象数据类型的基本概念 8

1.3.2 使用抽象数据类型的好处 9

1.4 数据结构、数据类型和抽象数据类型 10

1.5 用C语言描述数据结构与算法 11

1.5.1 变量和指针 11

1.5.2 函数与参数传递 12

1.5.3 结构 13

1.5.4 动态存储分配 14

1.6 递归 15

1.6.1 递归的基本概念 15

1.6.2 间接递归 17

本章小结 18

习题1 18

算法实验题1 19

第2章 表 21

2.1 表的基本概念 21

2.2 用数组实现表 22

2.3 用指针实现表 26

2.4 用间接寻址方法实现表 30

2.5 用游标实现表 32

2.6 循环链表 37

2.7 双链表 39

2.8 表的搜索游标 43

2.8.1 用数组实现表的搜索游标 43

2.8.2 单循环链表的搜索游标 44

2.9 应用举例 45

本章小结 47

习题2 47

算法实验题2 49

第3章 栈 52

3.1 栈的基本概念 52

3.2 用数组实现栈 53

3.3 用指针实现栈 55

3.4 应用举例 57

本章小结 60

习题3 60

算法实验题3 62

第4章 队列 64

4.1 队列的基本概念 64

4.2 用指针实现队列 64

4.3 用循环数组实现队列 67

4.4 应用举例 70

本章小结 74

习题4 74

算法实验题4 75

第5章 排序与选择算法 78

5.1 简单排序算法 78

5.1.1 冒泡排序算法 79

5.1.2 插入排序算法 79

5.1.3 选择排序算法 80

5.1.4 简单排序算法的复杂性 80

5.2 快速排序算法 81

5.2.1 算法基本思想及实现 81

5.2.2 算法的性能 82

5.2.3 随机快速排序算法 83

5.2.4 非递归快速排序算法 83

5.2.5 三数取中划分算法 84

5.2.6 三划分快速排序算法 85

5.3 合并排序算法 86

5.3.1 算法基本思想及实现 86

5.3.2 对基本算法的改进 87

5.3.3 自底向上合并排序算法 88

5.3.4 自然合并排序算法 88

5.3.5 链表结构的合并排序算法 89

5.4 线性时间排序算法 90

5.4.1 计数排序算法 90

5.4.2 桶排序算法 91

5.4.3 基数排序算法 92

5.5 中位数与第k小元素 94

5.5.1 平均情况下的线性时间选择算法 94

5.5.2 最坏情况下的线性时间选择算法 96

5.6 应用举例 98

本章小结 100

习题5 100

算法实验题5 101

第6章 树 104

6.1 树的定义 104

6.2 树的遍历 106

6.3 树的表示法 108

6.3.1 父结点数组表示法 108

6.3.2 儿子链表表示法 108

6.3.3 左儿子右兄弟表示法 108

6.4 二叉树的基本概念 109

6.5 二叉树的运算 111

6.6 二叉树的实现 112

6.6.1 二叉树的顺序存储结构 112

6.6.2 二叉树的结点度表示 113

6.6.3 用指针实现二叉树 113

6.7 线索二叉树 118

6.8 二叉搜索树 119

6.9 线段树 128

6.10 序列树 134

6.11 应用举例 142

本章小结 146

习题6 147

算法实验题6 149

第7章 散列表 154

7.1 集合的基本概念 154

7.1.1 集合的定义和记号 154

7.1.2 定义在集合上的基本运算 155

7.2 简单集合的实现方法 156

7.2.1 用位向量实现集合 156

7.2.2 用链表实现集合 158

7.3 散列技术 161

7.3.1 符号表 161

7.3.2 开散列 163

7.3.3 闭散列 164

7.3.4 散列函数及其效率 168

7.3.5 闭散列的重新散列技术 169

7.4 应用举例 170

本章小结 171

习题7 172

算法实验题7 173

第8章 优先队列 176

8.1 优先队列的定义 176

8.2 优先队列的简单实现 177

8.3 优先级树和堆 177

8.4 用数组实现堆 179

8.5 可并优先队列 181

8.5.1 左偏树的定义 182

8.5.2 用左偏树实现可并优先队列 182

8.6 应用举例 185

本章小结 190

习题8 190

算法实验题8 191

第9章 并查集 194

9.1 并查集的定义及其简单实现 194

9.2 用父结点数组实现并查集 195

9.3 应用举例 198

本章小结 201

习题9 201

算法实验题9 202

第10章 图 205

10.1 图的基本概念 205

10.2 抽象数据类型图 208

10.3 图的表示法 209

10.3.1 邻接矩阵表示法 209

10.3.2 邻接表表示法 209

10.3.3 紧缩邻接表表示法 210

10.4 用邻接矩阵实现图 211

10.4.1 用邻接矩阵实现赋权有向图 211

10.4.2 用邻接矩阵实现赋权无向图 213

10.4.3 用邻接矩阵实现有向图 213

10.4.4 用邻接矩阵实现无向图 213

10.5 用邻接表实现图 214

10.5.1 用邻接表实现有向图 214

10.5.2 用邻接表实现无向图 217

10.5.3 用邻接表实现赋权有向图 218

10.5.4 用邻接表实现赋权无向图 221

10.6 图的遍历 222

10.6.1 广度优先搜索 222

10.6.2 深度优先搜索 224

10.7 最短路径 225

10.7.1 单源最短路径 225

10.7.2 Bellman-Ford最短路径算法 228

10.7.3 所有顶点对之间的最短路径 230

10.8 无圈有向图 231

10.8.1 拓扑排序 231

10.8.2 DAG的最短路径 233

10.8.3 DAG的最长路径 234

10.8.4 DAG所有顶点对之间的最短路径 234

10.9 最小支撑树 235

10.9.1 最小支撑树性质 235

10.9.2 Prim算法 235

10.9.3 Kruskal算法 237

10.10 图匹配 239

10.11 应用举例 241

本章小结 243

习题10 244

算法实验题10 245

参考文献 250

查看更多关于的内容