数据结构与算法PDF电子书下载

第1章 绪论 1

1.1数据结构的概念 2

1.1.1引言 2

1.1.2数据结构有关概念与术语 4

1.2抽象数据类型 6

1.3算法描述与分析 7

1.3.1什么是算法 7

1.3.2算法分析技术初步 9

1.4基本的算法策略 12

1.4.1穷举法 12

1.4.2递推法与迭代法 13

1.4.3分治法 15

1.4.4贪婪算法 16

1.4.5动态规划 17

1.5案例分析 19

1.6小结 20

讨论小课堂1 21

习题1 22

第2章 线性表 24

2.1线性表的定义及其运算 24

2.1.1线性表的定义 24

2.1.2线性表的基本操作 25

2.2线性表的顺序存储结构及实现 26

2.2.1顺序存储结构 26

2.2.2线性表在向量中基本运算的实现 27

2.3线性表的链表存储结构 32

2.3.1单链表 32

2.3.2线性链表基本运算的实现 35

2.4循环链表和双向链表 41

2.4.1循环链表 41

2.4.2双向链表 42

2.4.3顺序存储结构与链表存储结构的综合分析与比较 43

2.5单链表的应用 44

2.5.1多项式相加的链表存储结构 44

2.5.2多项式相加的算法实现 45

2.6小结 46

讨论小课堂2 47

习题2 47

第3章 栈和队列 49

3.1栈 49

3.1.1栈的定义 49

3.1.2栈的基本操作 50

3.2栈的顺序存储结构及实现 51

3.2.1栈的顺序存储结构 51

3.2.2顺序栈的定义 52

3.3栈的链表存储结构及实现 54

3.4栈的应用 56

3.4.1表达式的计算 56

3.4.2子程序的嵌套调用 58

3.4.3递归调用 59

3.5队列 60

3.5.1队列的定义及运算 60

3.5.2队列的抽象数据类型描述 61

3.6队列的顺序存储结构及实现 61

3.7队列的链表存储结构及实现 64

3.8队列的应用 67

3.9算法实例——Hanoi塔问题 68

3.10小结 70

讨论小课堂3 70

习题3 71

第4章串 72

4.1串的基本概念 72

4.1.1串的定义 72

4.1.2串的基本操作 73

4.2串的存储与基本操作的实现 74

4.2.1定长顺序串 74

4.2.2堆串 75

4.2.3块链串 75

4.2.4串操作的实现 76

4.3串的模式匹配 80

4.3.1朴素模式匹配算法 80

4.3.2模式匹配的KMP算法 81

4.4串的应用举例：文本编辑 85

4.5小结 86

讨论小课堂4 87

习题4 87

第5章 数组和广义表 88

5.1数组 88

5.1.1数组的基本概念 88

5.1.2二维数组 89

5.1.3数组的顺序存储方式 89

5.2矩阵的压缩存储 90

5.2.1特殊矩阵 91

5.2.2稀疏矩阵 93

5.3广义表 98

5.3.1广义表的定义 98

5.3.2广义表的存储结构 99

5.4案例分析 101

5.4.1概述和方法 101

5.4.2算法和程序 103

5.5小结 105

讨论小课堂5 106

习题5 106

第6章 树与二叉树 108

6.1树、二叉树的概念及术语 108

6.1.1树的定义 108

6.1.2树的基本操作 110

6.1.3树的表示方式 110

6.1.4树的存储结构 111

6.2二叉树 112

6.2.1二叉树的定义 112

6.2.2二叉树的重要性质 112

6.2.3二叉树的存储结构 114

6.3二叉树的遍历 115

6.3.1先序遍历 116

6.3.2中序遍历 117

6.3.3后序遍历 117

6.3.4按层遍历 118

6.3.5非递归遍历算法 118

6.3.6二叉树的建立 121

6.3.7二叉树遍历的应用举例 122

6.4二叉树与树、森林的转换 123

6.4.1树与二叉树的转换 124

6.4.2森林与二叉树的转换 124

6.5树的遍历 126

6.5.1一般树的遍历 126

6.5.2森林的遍历 127

6.6二叉树的应用 128

6.6.1哈夫曼树 128

6.6.2哈夫曼树的构造 128

6.6.3哈夫曼树的实现算法 129

6.6.4哈夫曼编码 131

6.7小结 131

讨论小课堂6 132

习题6 132

第7章图 134

7.1图的基本概念 134

7.1.1图的定义 134

7.1.2图的术语 136

7.1.3图的基本操作 137

7.2图的存储结构 138

7.2.1图的邻接矩阵 138

7.2.2邻接矩阵表示法的C语言类型描述 139

7.2.3邻接矩阵表示下的基本操作的实现 140

7.2.4图的邻接链表 141

7.2.5图的邻接表表示法的C语言类型描述 143

7.2.6邻接表表示下基本操作的实现 144

7.3图的遍历与图的连通性 146

7.3.1图的深度优先遍历 146

7.3.2图的广度优先遍历 148

7.3.3非连通图和连通分量 150

7.4图的最小生成树 150

7.4.1最小生成树的基本概念 150

7.4.2普里姆（Prim）算法 151

7.4.3克鲁斯卡尔（Kruskal）算法 153

7.5最短路径 154

7.5.1从某顶点到其余各顶点的最短路径 155

7.5.2每对顶点之间的最短路径 157

7.6拓扑排序与关键路径 159

7.6.1拓扑排序 160

7.6.2关键路径 163

7.7图的应用 168

7.7.1图在路由器寻径中的应用 168

7.7.2图在物流信息系统中的应用 169

7.8小结 169

讨论小课堂7 170

习题7 170

第8章 查找 172

8.1查找的基本概念 172

8.2静态查找表 173

8.2.1顺序表的查找 173

8.2.2有序表的折半查找 174

8.2.3索引顺序表查找 177

8.3动态查找表 178

8.3.1二叉排序树 178

8.3.2平衡二叉树 184

8.4案例分析 191

8.4.1直方图问题 191

8.4.2箱子装载问题 192

8.5小结 194

讨论小课堂8 194

习题8 195

第9章 排序 196

9.1排序的基本概念 196

9.2插入排序 197

9.2.1直接插入排序 197

9.2.2折半插入排序 198

9.2.3希尔排序 198

9.3交换排序 200

9.3.1冒泡排序 200

9.3.2快速排序 201

9.4选择排序 204

9.4.1简单选择排序 204

9.4.2堆排序 205

9.5归并排序 208

9.6基数排序 210

9.7小结 213

讨论小课堂9 214

习题9 215

第10章 索引结构与散列 217

10.1静态索引结构 217

10.1.1索引表 217

10.1.2索引表查找 217

10.2动态索引结构（B一树和B+树） 219

10.2.1 B一树的定义 220

10.2.2 B一树的运算 221

10.2.3 B+树 223

10.3键树及Trie树 224

10.3.1键树的定义 224

10.3.2双链树 225

10.3.3 Trie树 226

10.4散列表及其查找 227

10.4.1哈希表与哈希函数 227

10.4.2构造哈希函数的常用方法 228

10.4.3解决冲突的主要方法 230

10.4.4哈希查找的性能分析 234

10.5小结 234

讨论小课堂10 235

习题10 235

附录 上机实验指导 238

第1部分 上机实验要求及规范 238

第2部分 实验部分 239

实验1复数ADT及其实现 239

实验2线性表 241

实验3栈和队列 248

实验4串 253

实验5数组 255

实验6树与二叉树 257

实验7图 261

实验8查找 265

实验9排序 267

实验10哈希查找 272

参考文献 275