数据结构 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

本章小结 17

习题1 18

算法实验1 19

算法实验题1.1 哥德巴赫猜想问题 19

算法实验题1.2 连续整数和问题 19

第2章 表 20

2.1 表的基本概念 20

2.2 用数组实现表 21

2.3 用指针实现表 25

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

2.5 用游标实现表 32

2.6 循环链表 38

2.7 双链表 41

2.8 表的搜索游标 45

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

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

2.9 应用举例——Josephus排列问题 48

本章小结 49

习题2 49

算法实验2 51

算法实验题2.1 向量分类问题 51

算法实验题2.2 条形图轮廓问题 51

第3章 栈 53

3.1 栈的基本概念 53

3.2 用数组实现栈 54

3.3 用指针实现栈 56

3.4 应用举例——等价类划分问题 59

本章小结 61

习题3 61

算法实验3 63

算法实验题3.1 车皮编序问题 63

算法实验题3.2 单柱Hanoi塔问题 63

算法实验题3.3 多栈模拟问题 64

算法实验题3.4 亲兄弟问题 64

第4章 队列 66

4.1 队列的基本概念 66

4.2 用指针实现队列 67

4.3 用循环数组实现队列 69

4.4 应用举例——电路布线问题 73

本章小结 77

习题4 77

算法实验4 78

算法实验题4.1 组队列问题 78

算法实验题4.2 双栈队列问题 79

算法实验题4.3 猴子分桃问题 79

算法实验题4.4 逆序表问题 79

第5章 排序与选择 81

5.1 简单排序算法 81

5.1.1 冒泡排序 82

5.1.2 插入排序 82

5.1.3 选择排序 83

5.1.4 简单排序算法的计算复杂性 83

5.2 快速排序算法 84

5.2.1 算法基本思想及实现 84

5.2.2 算法的性能 86

5.2.3 随机快速排序算法 86

5.2.4 非递归快速排序算法 87

5.2.5 三数取中划分算法 88

5.2.6 三划分快速排序算法 89

5.3 合并排序算法 90

5.3.1 算法基本思想及实现 90

5.3.2 对基本算法的改进 91

5.3.3 自底向上的合并排序算法 92

5.3.4 自然合并排序 92

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

5.4 线性时间排序算法 94

5.4.1 计数排序 94

5.4.2 桶排序 95

5.5 中位数与第k小元素 96

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

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

5.6 应用举例——带权中位数问题 100

本章小结 101

习题5 102

算法实验5 103

算法实验题5.1 交换排序问题 103

算法实验题5.2 DNA排序问题 103

算法实验题5.3 输油管道问题 104

算法实验题5.4 最优服务次序问题 104

第6章 树 105

6.1 树的定义 105

6.2 树的遍历 107

6.3 树的表示法 109

6.3.1 父结点数组表示法 109

6.3.2 儿子链表表示法 110

6.3.3 左儿子右兄弟表示法 110

6.4 二叉树的基本概念 111

6.5 二叉树的运算 113

6.6 二叉树的实现 114

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

6.6.2 二叉树的结点度表示法 115

6.6.3 用指针实现二叉树 115

6.7 线索二叉树 120

6.8 应用举例——信号增强装置布局问题 122

本章小结 126

习题6 126

算法实验6 128

算法实验题6.1 层序列表问题 128

算法实验题6.2 最近公共祖先问题 128

算法实验题6.3 子树问题 129

算法实验题6.4 同构二叉树问题 129

算法实验题6.5 后序中序遍历问题 130

第7章 图 131

7.1 图的基本概念 131

7.2 抽象数据类型ADT图 134

7.3 图的表示法 134

7.3.1 邻接矩阵表示法 135

7.3.2 邻接表表示法 135

7.3.3 紧缩邻接表 135

7.4 用邻接矩阵实现图 136

7.4.1 用邻接矩阵实现赋权有向图 136

7.4.2 用邻接矩阵实现赋权无向图 139

7.4.3 用邻接矩阵实现有向图 140

7.4.4 用邻接矩阵实现无向图 140

7.5 用邻接表实现图 141

7.5.1 用邻接表实现有向图 141

7.5.2 用邻接表实现无向图 144

7.5.3 用邻接表实现赋权有向图 145

7.5.4 用邻接表实现赋权无向图 148

7.6 图的遍历 149

7.6.1 广度优先搜索 149

7.6.2 深度优先搜索 151

7.7 最短路径 152

7.7.1 单源最短路径 153

7.7.2 Bellman-Ford最短路径算法 156

7.7.3 所有顶点对之间的最短路径 158

7.8 无圈有向图DAG 160

7.8.1 拓扑排序 160

7.8.2 DAG的最短路径 162

7.8.3 DAG的最长路径 163

7.8.4 DAG所有顶点对之间的最短路径 163

7.9 最小支撑树 164

7.9.1 最小支撑树性质 164

7.9.2 Prim算法 164

7.9.3 Kruskal算法 166

7.10 图匹配 169

7.11 应用举例——差分约束系统 170

本章小结 172

习题7 172

算法实验7 174

算法实验题7.1 图的二着色问题 174

算法实验题7.2 赋权有向图中心问题 174

算法实验题7.3 最长简单路径问题 175

算法实验题7.4 计算机网络问题 175

算法实验题7.5 差分约束问题 176

算法实验题7.6 有截止时间的工作排序问题 176

第8章 集合 178

8.1 以集合为基础的抽象数据类型 178

8.1.1 集合的定义和记号 178

8.1.2 定义在集合上的基本运算 179

8.2 用位向量实现集合 179

8.3 用链表实现集合 183

8.4 应用举例——Eratosthenes筛法 186

本章小结 187

习题8 187

算法实验8 188

算法实验题8.1 半数集问题 188

第9章 符号表 190

9.1 实现符号表的简单方法 190

9.2 用散列表实现符号表 191

9.2.1 开散列 192

9.2.2 闭散列 194

9.2.3 散列函数及其效率 198

9.2.4 闭散列的重新散列技术 199

9.3 应用举例——字符串频率统计问题 199

本章小结 201

习题9 201

算法实验9 202

算法实验题9.1 伪随机排列问题 202

算法实验题9.2 字符串散列问题 202

算法实验题9.3 英文文本分析问题 202

算法实验题9.4 最长模式串问题 203

第10章 字典 204

10.1 字典的定义 204

10.2 用数组实现字典 204

10.3 用二叉搜索树实现字典 205

10.4 AVL树 213

10.4.1 AVL树的定义和性质 213

10.4.2 旋转变换 214

10.4.3 AVL树的插入运算 217

10.4.4 AVL树的删除运算 220

10.5 应用举例——条形图统计问题 223

本章小结 225

习题10 225

算法实验10 226

算法实验题10.1 装箱问题 226

算法实验题10.2 电路板连线问题 227

算法实验题10.3 辞典问题 227

第11章 优先队列 229

11.1 优先队列的定义 229

11.2 用字典实现优先队列 230

11.3 优先级树和堆 230

11.4 用数组实现堆 232

11.5 可并优先队列 235

11.5.1 左偏树的定义 235

11.5.2 用左偏树实现可并优先队列 236

11.6 应用举例——哈夫曼编码 239

本章小结 243

习题11 243

算法实验11 244

算法实验题11.1 多机调度问题 244

算法实验题11.2 整数字典问题 244

算法实验题11.3 最小权语言问题 245

算法实验题11.4 二叉搜索堆问题 245

第12章 并查集 247

12.1 并查集的定义及其简单实现 247

12.2 用父结点数组实现并查集 248

12.3 应用举例——离线最小值问题 251

本章小结 253

习题12 253

算法实验12 254

算法实验题12.1 二进制方程问题 254

算法实验题12.2 网络连通问题 255

算法实验题12.3 朋友问题 255

算法实验题12.4 无向图的连通分支问题 255

参考文献 257