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

1.1 引言 1

1.1.1 几个例子 1

第1章 概论 1

1.1.2数据结构的产生和发展 3

1.1.3基本概念和术语 4

1.2问题、算法和程序 9

1.2.1 问题 9

1.2.2算法 9

1.3算法描述和分析 10

1.3.1算法描述 10

1.2.3程序 10

1.3.2算法分析 12

1.4小结 15

习题 15

第2章 线性表 17

2.1概述 17

2.1.1线性表的概念 17

2.1.2线性表的类型定义 19

2.2顺序表 20

2.2.1线性表的顺序表示 20

2.2.2顺序表的实现 21

2.3.1线性表的链式表示 25

2.3.2线性链表的实现 25

2.3链表 25

2.3.3循环链表的实现 29

2.3.4双向链表的实现 30

2.3.5静态链表的实现 31

2.4栈 31

2.4.1栈的类型定义 31

2.4.2顺序栈的表示和实现 33

2.4.3链栈的表示和实现 34

2.5 队列 36

2.5.1 队列的类型定义 36

2.5.2顺序队列的表示和实现 37

2.5.3链队的表示和实现 39

2.6应用举例 41

2.7小结 44

习题 44

第3章 串 45

3.1概述 45

3.1.1 串的概念 45

3.1.2串的基本操作 46

3.2串的存储表示和操作算法 47

3.2.1定长顺序存储表示 47

3.2.2块链存储表示 49

3.2.3堆分配存储表示 50

3.3.1 模式匹配的基本算法（BF算法） 54

3.3模式匹配 54

3.3.2模式匹配的改进算法（KMP算法） 56

3.4应用举例 59

3.4.1 文本编辑 59

3.4.2建立词索引表 60

3.5 小结 62

习题 62

第4章 数组和广义表 65

4.1数组的定义、表示和实现 65

4.1.1数组的定义 65

4.1.2数组的表示 66

4.1.3数组的实现 67

4.2矩阵的压缩存储 69

4.2.1特殊矩阵 69

4.2.2稀疏矩阵 71

4.3广义表的定义和表示 78

4.3.1广义表的定义 78

4.3.2广义表的存储结构 79

4.3.3广义表的基本算法 81

4.4小结 84

习题 84

5.1树的定义和术语 87

5.1.1树的定义 87

第5章 树和二叉树 87

5.1.2树的基本术语 88

5.1.3树的表示 89

5.1.4树的遍历 90

5.2二叉树 90

5.2.1二叉树的定义 90

5.2.2二叉树的重要性质 91

5.2.3二叉树的存储结构 92

5.3二叉树的遍历和线索二叉树 94

5.3.1二叉树的遍历 94

5.3.2线索二叉树 96

5.4.1树的存储结构 100

5.4树和森林 100

5.4.2森林与二叉树的转换 102

5.4.3森林的遍历 103

5.5哈夫曼树及其应用 104

5.5.1哈夫曼树 104

5.5.2哈夫曼树的应用——哈夫曼编码 105

5.6小结 106

习题 106

第6章 图 109

6.1图的基本概念 109

6.1.1图的定义 109

6.1.2基本术语 110

6.2图的表示和实现 112

6.2.1邻接矩阵 112

6.2.2邻接表 114

6.2.3十字链表 116

6.2.4邻接多重表 117

6.3图的遍历 119

6.3.1深度优先搜索 119

6.3.2广度优先搜索 121

6.3.3非连通图的遍历 122

6.4.1 生成树 123

6.4应用举例 123

6.4.2拓扑排序 128

6.4.3关键路径 132

6.4.4最短路径 137

6.5小结 140

习题 140

第7章 排序 143

7.1内部排序 144

7.1.1简单排序 144

7.1.2希尔排序 148

7.1.3快速排序 149

7.1.4归并排序 152

7.1.5堆排序 154

7.1.6基数排序 156

7.2外部排序 158

7.2.1外部排序方法 158

7.2.2自然归并 159

7.2.3多路平衡归并 160

7.2.4置换－选择排序 161

7.2.5最佳归并树 163

7.3排序效益评估 164

7.4小结 164

习题 164

8.1.1查找的定义 167

第8章 查找 167

8.1基本概念 167

8.1.2基本术语 168

8.2线性表的查找 169

8.2.1顺序查找 169

8.2.2二分查找 170

8.2.3分块查找 173

8.3树表的查找 175

8.3.1二叉排序树和平衡二叉树 175

8.3.2 B树 187

8.3.3键树 196

8.4.1散列表 199

8.4散列查找 199

8.4.2散列函数的构造方法 201

8.4.3处理冲突的方法 203

8.4.4散列表的查找及分析 206

8.5小结 209

习题 209

第9章 算法设计方法 211

9.1递归与分治法 211

9.1.1递归技术 211

9.1.2分治法 214

9.2.2 0-1背包问题 217

9.2.1回溯法的基本思想 217

9.2回溯法 217

9.2.3旅行售货员问题 219

9.2.4 n皇后问题 220

9.3动态规划法 222

9.3.1动态规划法的基本思想 222

9.3.2计算矩阵连乘积 223

9.3.3动态规划法的基本要素 223

9.4贪心法 227

9.4.1贪心法的基本思想 227

9.4.2哈夫曼编码问题 227

9.4.3贪心法与动态规划法的差异 231

9.5.1分支限界法的基本思想 232

9.5分支限界法 232

9.5.2 0-1背包问题 233

9.5.3旅行售货员问题 234

9.6小结 238

习题 238

第10章 高级专题 239

10.1集合 239

10.1.1集合的定义 239

10.1.2字典 243

10.1.3有序字典 248

10.1.4优先队列 250

10.2.1自组织线性表 253

10.2线性结构的扩展 253

10.2.2跳跃表 254

10.2.3动态存储管理 256

10.3树形结构的扩展 259

10.3.1竞赛树 259

10.3.2 Trie树 260

10.3.3伸展树 262

10.4 小结 263

习题 263

附录 数学预备知识 265

参考文献 269