数据结构 C语言 实践教程 第2版PDF电子书下载

第1章 线性表 1

1.1 内容与要点 1

1.1.1 线性表的定义 1

1.1.2 线性表的顺序存储——顺序表 1

1.1.3 线性表的链式存储 2

1.2 线性表实践 4

实验1 顺序表及基本运算 4

实验2 在表头插入生成单链表 7

实验3 在表尾插入生成单链表 10

实验4 单链表及基本运算 11

实验5 双向链表及基本运算 15

实验6 静态链表 19

第2章 栈和队列 23

2.1 内容与要点 23

2.1.1 栈 23

2.1.2 队列 24

2.2 栈和队列实践 26

实验1 顺序栈及基本运算 26

实验2 链栈及基本运算 29

实验3 循环队列及基本运算 31

实验4 链队列及基本运算 33

第3章 串 36

3.1 内容与要点 36

3.2 串实践 37

实验1 顺序串及基本运算 37

实验2 链串及基本运算 40

实验3 链串中求子串运算 42

实验4 链串中串插入运算 44

实验5 串的简单模式匹配 46

实验6 串的无回溯KMP匹配 48

第4章 数组与广义表 52

4.1 内容与要点 52

4.1.1 数组 52

4.1.2 特殊矩阵 54

4.1.3 稀疏矩阵 54

4.1.4 广义表 57

4.2 数组与广义表实践 58

实验1 矩阵转置 58

实验2 矩阵的快速转置 61

实验3 稀疏矩阵的十字链表存储 65

实验4 广义表及基本运算 68

第5章 树与二叉树 73

5.1 内容与要点 73

5.1.1 树 73

5.1.2 二叉树 73

5.1.3 二叉树的性质 74

5.1.4 二叉树的存储结构 74

5.1.5 二叉树的遍历方法 75

5.1.6 线索二叉树 76

5.1.7 哈夫曼树 77

5.1.8 哈夫曼编码 78

5.2 树与二叉树实践 79

实验1 二叉树的遍历 79

实验2 二叉树的非递归遍历 81

实验3 另一种非递归后序遍历二叉树的方法 85

实验4 二叉树遍历的应用 87

实验5 由二叉树遍历序列恢复二叉树 91

实验6 按层次遍历二叉树 94

实验7 中序线索二叉树 97

实验8 哈夫曼树与哈夫曼编码（1） 101

实验9 哈夫曼树与哈夫曼编码（2） 107

第6章 图 113

6.1 内容与要点 113

6.1.1 图 113

6.1.2 邻接矩阵 113

6.1.3 邻接表 114

6.1.4 图的遍历 115

6.1.5 图的连通性问题 115

6.1.6 生成树与最小生成树 115

6.1.7 最短路径 116

6.1.8 AOV网与拓扑排序 117

6.1.9 AOE网与关键路径 118

6.2 图实践 120

实验1 建立无向图的邻接矩阵 120

实验2 图的深度优先搜索 122

实验3 图的广度优先搜索 125

实验4 图的连通性 129

实验5 深度优先生成树 132

实验6 广度优先生成树 135

实验7 最小生成树的Prim算法 138

实验8 最小生成树的Kruskal算法 142

实验9 单源点最短路径的Dijkstra算法 145

实验10 每一对顶点间最短路径的Floyd算法 148

实验11 拓扑排序 151

实验12 关键路径 155

第7章 查找 162

7.1 内容与要点 162

7.1.1 顺序查找 162

7.1.2 有序表的查找 162

7.1.3 二叉排序树与平衡二叉树 163

7.1.4 哈希表与哈希方法 163

7.1.5 哈希函数的构造方法 164

7.1.6 处理冲突的方法 165

7.2 查找实践 165

实验1 顺序查找 165

实验2 折半（二分）查找 167

实验3 分块查找 169

实验4 二叉排序树 171

实验5 平衡二叉树 176

实验6 哈希（Hash）查找 186

第8章 排序 190

8.1 内容与要点 190

8.1.1 插入排序 190

8.1.2 交换排序 191

8.1.3 选择排序 191

8.1.4 归并排序 193

8.1.5 基数排序 193

8.2 排序实践 194

实验1 插入排序 194

实验2 折半插入排序 196

实验3 希尔（Shell）排序 198

实验4 冒泡排序 200

实验5 快速排序 202

实验6 选择排序 208

实验7 堆排序 210

实验8 归并排序 213

实验9 基数排序 218

第9章 数据结构实践应用 222

9.1 顺序表的应用 222

9.1.1 顺序表的逆置 222

9.1.2 将两个升序的顺序表A和B合并为一个升序的顺序表C 223

9.1.3 单链表的逆置 225

9.1.4 将递增有序的单链表A和B合并成递减有序的单链表C 227

9.1.5 删除单链表中值相同的结点 229

9.1.6 按递增次序输出单链表中各结点的数据值 231

9.2 栈和队列应用 233

9.2.1 用栈判断给定的字符序列是否为回文 233

9.2.2 循环链表中只有队尾指针的入队和出队算法 235

9.2.3 算术表达式中的括号匹配 237

9.2.4 将队列中所有元素逆置 240

9.2.5 用两个栈模拟一个队列 243

9.3 串的应用 246

9.3.1 将串s1中一字符串用串s2替换 246

9.3.2 计算一个子串在字符串中出现的次数 248

9.3.3 输出长度最大的等值子串 249

9.3.4 将链串s中首次与链串t匹配的子串逆置 250

9.4 数组与广义表应用 253

9.4.1 将所有奇数放到数组前半部分，所有偶数放到数组后半部分 253

9.4.2 求出字符数组中连续相同字符构成的子序列长度 254

9.4.3 求广义表的表头和表尾 255

9.4.4 另一种广义表生成方法 259

9.5 树与二叉树应用 263

9.5.1 交换二叉树的左右子树 263

9.5.2 统计二叉树叶子个数的非递归算法实现 265

9.5.3 判定一棵二叉树是否为完全二叉树 267

9.5.4 求二叉树中第一条最长的路径并输出此路径上各结点的值 270

9.6 图的应用 273

9.6.1 邻接矩阵转换为邻接表 273

9.6.2 深度优先搜索的非递归算法实现 275

9.6.3 求无向连通图中距顶点V0路径长度为k的所有结点 278

9.6.4 用深度优先搜索对图中所有顶点进行拓扑排序 281

9.7 查找的应用 284

9.7.1 判定一棵二叉树是否为二叉排序树 284

9.7.2 另一种平衡二叉树的生成方法 287

9.8 排序的应用 293

9.8.1 用双向循环链表表示的插入排序 293

9.8.2 双向冒泡排序 295

9.8.3 单链表存储下的选择排序 297

9.8.4 归并排序的迭代算法实现 299

参考文献 302