数据结构、算法及应用PDF电子书下载

第1章 绪论 1

1.1什么是数据结构 1

1.1.1数据的逻辑结构 3

1.1.2数据的存储结构 4

1.2算法与算法设计 6

1.2.1算法的概念 6

1.2.2算法设计 7

1.3算法分析 9

1.3.1算法的渐进分析 9

1.3.2最坏、最好和平均情况 12

1.3.3时间和空间资源开销 14

1.4数据结构的选择和评价 14

习题 15

第2章 线性表 16

2.1线性表的概念 16

2.1.1线性表的定义及特征 16

2.1.2线性表的抽象数据类型 17

2.1.3线性表的存储结构 18

2.1.4线性表运算分类 18

2.2顺序表 18

2.2.1顺序表的实现 19

2.2.2多维数组 23

2.3链表 25

2.3.1链表的实现 26

2.3.2线性表实现方法的比较 35

2.4栈 36

2.4.1顺序栈 36

2.4.2链式栈 39

2.4.3栈与递归 41

2.5队列 44

2.5.1顺序队列 45

2.5.2链式队列 48

2.6字符串 50

2.6.1基本概念 50

2.6.2存储结构和实现 52

2.6.3字符串运算的算法实现 55

2.6.4字符串的模式匹配 58

2.7线性表的应用 63

2.7.1栈：简易计算器 63

2.7.2队列：银行叫号系统的实现 69

2.7.3字符串及链表：简易文本编辑器 75

习题 79

第3章树 81

3.1树的基本概念 81

3.1.1树的定义和基本术语 81

3.1.2树的基本性质 82

3.1.3树的逻辑表示方式 83

3.2二叉树 85

3.2.1二叉树的定义和相关概念 85

3.2.2几种特殊的二叉树 85

3.2.3二叉树的性质 87

3.2.4二叉树的存储结构 88

3.2.5二叉树的抽象数据类型 90

3.2.6二叉树的遍历 92

3.2.7线索二叉树 97

3.2.8二叉搜索树 102

3.2.9平衡二叉树 108

3.2.10堆与优先队列 117

3.2.11 Huffman编码树 124

3.3树与森林 127

3.3.1二叉树、树、森林之间的转换 127

3.3.2树和森林的遍历 129

3.3.3树的存储 131

3.4树的应用 134

3.4.1二叉树：图像压缩算法 134

3.4.2树：医院设施管理 137

习题 141

第4章图 144

4.1图的基本概念 144

4.1.1图的定义和概念 144

4.1.2图的抽象数据类型 148

4.2图的存储及基本操作 150

4.2.1图的邻接矩阵表示法 150

4.2.2图的邻接表表示法 152

4.2.3十字链表和邻接多重表 157

4.3图的遍历 159

4.3.1深度优先搜索（DFS） 159

4.3.2广度优先搜索（BFS） 161

4.4最小生成树 163

4.4.1普里姆（Prim）算法 163

4.4.2克鲁斯卡尔（Kruskal）算法 166

4.5最短路径 169

4.5.1单源最短路径 169

4.5.2顶点对之间的最短路径 173

4.6拓扑排序 175

4.7关键路径 178

4.8图的应用 182

4.8.1图的存储和遍历：地图染色应用的实现 182

4.8.2最小生成树：通信线路铺设问题 186

4.8.3最短路径：指定时间内路口拦截犯罪分子问题 190

4.8.4关键路径：软件项目管理的流程控制问题 193

习题 197

第5章 查找 199

5.1静态查找 200

5.1.1顺序查找法 200

5.1.2折半查找法 201

5.1.3分块查找 205

5.2动态查找 206

5.2.1 B-树 208

5.2.2 B+树 217

5.3散列 222

5.3.1散列的概念 222

5.3.2散列函数 223

5.3.3冲突解决方法 226

5.3.4散列算法设计与分析 231

5.4查找的应用：通讯录 234

习题 238

第6章 排序 240

6.1排序的基本概念 240

6.2插入排序 241

6.2.1直接插入排序 241

6.2.2折半插入排序 242

6.2.3希尔排序 244

6.3交换排序 247

6.3.1冒泡排序 247

6.3.2快速排序 249

6.4选择排序 257

6.4.1简单选择排序 257

6.4.2堆排序 259

6.5归并排序 262

6.6比较排序算法的时间复杂度下界 265

6.7基数排序 266

6.8各种内部排序算法的比较和选择 270

6.9外部排序 271

6.9.1置换选择排序 272

6.9.2多路归并 274

6.10排序的应用：书库信息排序 278

习题 281

参考文献 282