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

第一章 绪论 1

1.1 问题求解 1

1.1.1 问题分析 2

1.1.2 程序设计 3

1.2 数据结构 5

1.3 算法 7

1.4 算法分析 9

1.5 抽象数据类型 12

小结 14

习题 15

上机题 16

第二章 线性表 17

2.1 线性表的概念 17

2.2 顺序表示 19

2.3 链接表示 27

2.3.1 单链表 27

2.3.2 循环链表 36

2.3.3 双链表 36

2.4 应用举例——Josephus问题 39

2.4.1 顺序表表示 40

2.4.2 循环链表表示 42

小结 45

习题 48

上机题 49

第三章 字符串 50

3.1 字符串及其运算 50

3.2 字符串的存储表示 51

3.2.1 顺序表示 52

3.2.2 链接表示 53

3.3 模式匹配 56

3.3.1 朴素的模式匹配 56

3.3.2 无回溯的模式匹配 58

小结 63

习题 64

上机题 64

第四章 栈与队列 65

4.1 栈及其基本运算 65

4.2 栈的实现 66

4.2.1 顺序表示 66

4.2.2 链接表示 69

4.3 栈的应用 72

4.3.1 栈与递归 72

4.3.2 迷宫问题 80

4.3.3 表达式计算 84

4.4 队列 85

4.5 队列的实现 87

4.5.1 顺序表示 87

4.5.2 链接表示 91

4.6 队列的应用——农夫过河问题 95

4.7 限制存取点的表 99

小结 100

习题 101

上机题 101

5.1.1 树的定义 103

5.1 树与树林 103

第五章 树与二叉树 103

5.1.2 基本术语 105

5.1.3 树林 106

5.1.4 树的基本运算 107

5.1.5 树的周游 107

5.1.6 树林的周游 112

5.2 树和树林的存储表示 113

5.2.1 树的存储表示 113

5.2.2 树林的存储表示 119

5.2.3 树和树林的其他表示法 119

5.3.1 二叉树的基本概念 123

5.3 二叉树 123

5.3.2 二叉树的性质 125

5.3.3 二叉树的基本运算 128

5.3.4 二叉树的周游 128

5.3.5 树、树林与二叉树的转换 134

5.4 二叉树的存储表示 137

5.4.1 顺序表示 137

5.4.2 链接表示 139

5.4.3 二叉树的生成 141

5.4.4 线索二叉树 142

5.5.1 哈夫曼树 147

5.5 哈夫曼算法及其应用 147

5.5.2 哈夫曼算法 148

5.5.3 哈夫曼编码 152

小结 155

习题 155

上机题 156

第六章 字典与检索 157

6.1 基本概念 157

6.2 线性表表示 158

6.2.1 顺序表表示 158

6.2.2 链表表示和索引结构 162

6.3.1 散列表 163

6.3 散列表示 163

6.3.2 散列函数 164

6.3.3 存储表示与碰撞的处理 166

6.4 二叉树表示 171

6.4.1 二叉排序树 171

6.4.2 最佳二叉排序树 177

6.5 AVL树表示 185

6.5.1 调整平衡的模式 186

6.5.2 插入元素的算法 192

6.6.1 B树 198

6.6 B树表示 198

6.6.2 B+树 203

小结 206

习题 207

上机题 208

第七章 排序 209

7.1 排序的基本概念 209

7.2 插入排序 210

7.2.1 直接插入排序 210

7.2.2 二分法插入排序 212

7.2.3 表插入排序 214

7.2.4 Shell排序 216

7.3 选择排序 218

7.3.1 直接选择排序 218

7.3.2 堆排序 219

7.4 交换排序 224

7.4.1 起泡排序 224

7.4.2 快速排序 225

7.5 分配排序 228

7.5.1 概述 228

7.5.2 基数排序 229

7.6 归并排序 232

小结 235

习题 236

上机题 237

第八章 图 238

8.1 基本概念 238

8.2 图的基本运算与周游 241

8.2.1 基本运算 242

8.2.2 图的周游 243

8.3 存储表示 246

8.3.1 邻接矩阵表示法 246

8.3.2 邻接表表示法 248

8.4 最小生成树 250

8.4.1 Prim算法 252

8.4.2 Kruskal算法 256

8.5 最短路径 258

8.5.1 从一个顶点到其他各个顶点的最短路径 258

8.5.2 每一对顶点间的最短路径 263

8.6 拓扑排序 268

8.6.1 AOV网 268

8.6.2 拓扑排序 269

8.7.1 AOE网 273

8.7 关键路径 273

8.7.2 关键路径 274

小结 280

习题 280

上机题 282

第九章 算法分析与设计 283

9.1 算法分析技术 283

9.1.1 空间代价分析 283

9.1.2 时间代价分析 285

9.2 算法设计技术 288

9.2.1 分治法 288

9.2.2 贪心法 290

9.2.3 动态规划法 293

9.2.4 回溯法 299

9.2.5 分枝界限法与0/1背包问题 303

小结 307

上机题 308

附录A C语言介绍 309

A.1 C程序全貌 309

A.2 词法成分 309

A.3 类型与声明 310

A.4 运算符 313

A.5 控制语句 314

A.6 指针 319

A.7 函数 321

A.8 指针与函数 324

附录B 数学基础知识 327

B.1 级数 327

B.2 对数 328

B.3 排列、组合与阶乘 331

B.4 Fibonacci级数 333

附录C “上机实习报告”实例 334

简化文本编辑器上机报告 334

参考文献 341