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

第1章 绪论 1

1.1问题求解与程序设计 2

1.1.1程序设计的一般过程 2

1.1.2数据结构在程序设计中的作用 4

1.1.3算法在程序设计中的作用 5

1.1.4本书讨论的主要内容 6

1.2数据结构的基本概念 8

1.2.1数据结构 8

1.2.2抽象数据类型 10

1.3算法的基本概念 12

1.3.1算法及其重要特性 12

1.3.2算法的描述方法 13

1.4算法分析 15

1.4.1算法的时间复杂度 15

1.4.2算法的空间复杂度 17

1.4.3算法分析举例 17

习题1 20

第2章 基本算法设计技术 22

2.1蛮力法 23

2.1.1蛮力法的设计思想 23

2.1.2算法设计实例——数字谜 23

2.2分治法 24

2.2.1分治法的设计思想 24

2.2.2算法设计实例——数字旋转方阵 25

2.3减治法 27

2.3.1减治法的设计思想 27

2.3.2算法设计实例——假币问题 28

2.4贪心法 30

2.4.1贪心法的设计思想 30

2.4.2算法设计实例——埃及分数 31

2.5动态规划法 33

2.5.1动态规划法的设计思想 33

2.5.2算法设计实例——数塔问题 33

习题2 36

第3章 线性表 38

3.1引言 39

3.2线性表的逻辑结构 40

3.2.1线性表的定义 40

3.2.2线性表的抽象数据类型定义 40

3.3线性表的存储结构及实现 42

3.3.1顺序表 42

3.3.2单链表 47

3.3.3双链表 56

3.3.4循环链表 58

3.3.5静态链表 60

3.3.6顺序表和链表的比较 61

3.4应用实例 62

3.4.1约瑟夫环问题 62

3.4.2一元多项式求和 65

习题3 69

第4章 栈和队列 72

4.1引言 73

4.2栈 74

4.2.1栈的逻辑结构 74

4.2.2栈的顺序存储结构及实现 75

4.2.3栈的链接存储结构及实现 79

4.2.4顺序栈和链栈的比较 80

4.3队列 81

4.3.1队列的逻辑结构 81

4.3.2队列的顺序存储结构及实现 82

4.3.3队列的链接存储结构及实现 85

4.2.4循环队列和链队列的比较 87

4.4应用举例 87

4.4.1括号匹配问题 87

4.4.2表达式求值 89

习题4 92

第5章 字符串和多维数组 94

5.1引言 95

5.2字符串 95

5.2.1字符串的逻辑结构 95

5.2.2字符串的存储结构 97

5.2.3模式匹配 98

5.3多维数组 101

5.3.1数组的逻辑结构 101

5.3.2数组的存储结构与寻址 102

5.4矩阵的压缩存储 103

5.4.1对称矩阵的压缩存储 104

5.4.2三角矩阵的压缩存储 104

5.4.3对角矩阵的压缩存储 105

5.4.4稀疏矩阵的压缩存储 105

5.5应用实例 107

5.5.1发纸牌 107

5.5.2八皇后问题 109

习题5 111

第6章 树和二叉树 114

6.1引言 115

6.2树的逻辑结构 116

6.2.1树的定义和基本术语 116

6.2.2树的抽象数据类型定义 117

6.2.3树的遍历操作 118

6.3树的存储结构 119

6.3.1双亲表示法 119

6.3.2孩子表示法 120

6.3.3孩子兄弟表示法 121

6.4二叉树的逻辑结构 122

6.4.1二叉树的定义 122

6.4.2二叉树的基本性质 123

6.4.3二叉树的抽象数据类型定义 125

6.4.4二叉树的遍历操作 126

6.5二叉树的存储结构 127

6.5.1顺序存储结构 127

6.5.2二叉链表 128

6.5.3三叉链表 131

6.5.4线索链表 132

6.6二叉树遍历的非递归算法 134

6.6.1前序遍历非递归算法 135

6.6.2中序遍历非递归算法 136

6.6.3后序遍历非递归算法 136

6.7树、森林与二叉树的转换 138

6.8应用实例 140

6.8.1文件系统 140

6.8.2哈夫曼树及哈夫曼编码 144

习题6 148

第7章 图 150

7.1引言 151

7.2图的逻辑结构 152

7.2.1图的定义和基本术语 152

7.2.2图的抽象数据类型定义 154

7.2.3图的遍历操作 155

7.3图的存储结构及实现 157

7.3.1邻接矩阵 157

7.3.2邻接表 160

7.3.3邻接矩阵和邻接表的比较 164

7.4最小生成树 164

7.4.1 Prim算法 165

7.4.3 Kruskal算法 167

7.5最短路径 170

7.5.1 Dijkstra算法 171

7.5.2 Floyd算法 172

7.6有向无环图及其应用 174

7.6.1 AOV网与拓扑排序 174

7.6.2 AOE网与关键路径 177

7.7应用实例 179

7.7.1七巧板涂色问题 179

7.7.2医院选址问题 180

习题7 182

第8章 查找技术 185

8.1概述 186

8.1.1查找的基本概念 186

8.1.2查找算法的性能 187

8.2线性表的查找技术 187

8.2.1顺序查找 187

8.2.2折半查找 188

8.2.3分块查找 191

8.3树表的查找技术 192

8.3.1二叉排序树 192

8.3.2平衡二叉树 197

8.3.3 B树 200

8.3.4 B+树 204

8.4散列表的查找技术 205

8.4.1概述 205

8.4.2散列函数的设计 206

8.4.3处理冲突的方法 207

8.4.4散列查找的性能分析 211

8.4.5开散列表与闭散列表的比较 211

8.5各种查找方法的比较 212

习题8 212

第9章 排序技术 215

9.1概述 216

9.1.1排序的基本概念 216

9.1.2排序算法的性能 217

9.2插入排序 217

9.2.1直接插入排序 217

9.2.2折半插入排序 219

9.2.3希尔排序 220

9.3交换排序 222

9.3.1起泡排序 222

9.3.2快速排序 224

9.4选择排序 228

9.4.1简单选择排序 228

9.4.2堆排序 229

9.5归并排序 233

9.5.1二路归并排序的递归实现 233

9.5.2二路归并排序的非递归实现 235

9.6分配排序 237

9.6.1桶式排序 237

9.6.2基数排序 240

9.7各种排序方法的比较 242

习题9 244

附录A 词汇索引 247

附录B 计算机学科硕士研究生入学考试专业基础综合考试大纲（数据结构部分） 251

参考文献 253