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

第1章 绪论 1

1.1引言 1

1.2数据结构的主要概念与术语 2

1.3抽象数据类型的概念与描述 4

1.3.1基本数据类型的概念 4

1.3.2抽象数据类型 5

1.4算法的度量 8

1.4.1算法的定义 8

1.4.2算法效率的度量 9

1.5面向对象C＋＋描述工具简介 11

1.5.1函数的定义格式 11

1.5.2函数模板 11

1.5.3类的定义 12

小结 16

习题 17

第2章 线性表 18

2.1案例引入及分析 18

2.1.1学生基本信息管理 18

2.1.2线性表的定义 18

2.1.3线性表的存储结构 20

2.2学生基本信息管理之顺序表的实现 22

2.2.1学生基本信息管理之顺序表类定义 22

2.2.2学生基本信息管理之顺序表操作实现 23

2.2.3学生基本信息管理之顺序表的主程序的实现 28

2.2.4顺序表的其他操作 30

2.3学生基本信息管理之单链表实现 31

2.3.1学生基本信息管理之单链表类定义 32

2.3.2学生基本信息管理之单链表操作实现 32

2.3.3学生基本信息管理之单链表的主程序的实现 40

2.3.4单链表的其他操作 42

2.4算法分析 44

2.5循环链表和双向链表 46

2.5.1循环链表 46

2.5.2双向链表 47

2.5.3双向链表的类定义 47

2.6静态链表 51

2.7顺序结构与链表结构的比较 54

小结 54

习题 55

第3章 堆栈 58

3.1案例引入及分析 58

3.1.1提交批改作业 58

3.1.2堆栈的定义 58

3.1.3堆栈的存储结构 59

3.2提交批改作业的顺序实现 64

3.3提交批改作业的链式实现 65

3.4算法分析 67

3.5堆栈的其他应用 67

3.5.1堆栈与递归的实现 67

3.5.2表达式求值 69

3.5.3背包问题 72

小结 75

习题 75

第4章 队列 77

4.1案例的引入及分析 77

4.1.1看病排队候诊 77

4.1.2队列的定义 77

4.1.3队列的存储结构 78

4.2看病排队候诊的顺序实现 83

4.3看病排队候诊的链式实现 85

4.4算法分析 87

4.5队列的其他应用 87

4.5.1二进制数转换为十进制数 87

4.5.2十进制数转换为二进制数 88

小结 89

习题 90

第5章 串 91

5.1案例引入及分析 91

5.1.1大整数计算器 91

5.1.2串的定义 91

5.1.3串的存储结构 93

5.2大整数计算器的顺序实现 97

5.3大整数计算器的链式实现 99

5.4算法分析 101

5.5串的其他应用 101

5.5.1简单模式匹配 101

5.5.2 KMP模式匹配 102

小结 106

习题 106

第6章 广义表和数组 108

6.1案例引入及分析 108

6.1.1本科生导师制问题 108

6.1.2广义表的定义 108

6.1.3广义表的存储结构 110

6.2本科生导师制问题的实现 111

6.2.1实现内容 111

6.2.2实现过程 112

6.3数组 120

6.3.1数组的定义 120

6.3.2数组的存储结构 122

6.4矩阵的压缩存储 123

6.4.1特殊矩阵的压缩存储 123

6.4.2稀疏矩阵的压缩存储 124

小结 136

习题 136

第7章 树和二叉树 139

7.1案例引入及分析 139

7.1.1家谱管理 139

7.1.2树和二叉树的定义 140

7.1.3树和二叉树的存储结构 144

7.1.4树与二叉树的转换 149

7.1.5森林与二叉树的转换 151

7.1.6树与森林的遍历 151

7.2家谱管理的实现 152

7.3遍历二叉树 154

7.3.1前序遍历 154

7.3.2中序遍历 155

7.3.3后序遍历 156

7.3.4按层次遍历 156

7.4线索二叉树 157

7.5树的其他应用——哈夫曼树及编码 161

7.5.1哈夫曼树 161

7.5.2哈夫曼编码 162

小结 163

习题 164

第8章 图 165

8.1图的基本概念与术语 165

8.1.1图的基本概念 165

8.1.2图的基本术语 166

8.1.3抽象数据类型 169

8.2图的存储结构 171

8.2.1邻接矩阵 171

8.2.2邻接表 173

8.2.3双链式存储结构 174

8.3图的ADT设计与实现 179

8.4图的遍历 180

8.4.1深度优先搜索 181

8.4.2广度优先搜索 183

8.5图的连通性 184

8.5.1无向图的连通分量和生成树 184

8.5.2有向图的强连通分量 185

8.5.3最小生成树 186

8.6最短路径 192

8.6.1单源最短路径 192

8.6.2任意顶点间的最短路径 196

8.7有向无环图及其应用 196

8.7.1拓扑排序 196

8.7.2关键路径 199

小结 202

习题 202

第9章 查找 207

9.1查找的基本概念 207

9.2静态查找表 208

9.2.1顺序查找表 209

9.2.2有序表的查找 209

9.2.3静态索引顺序表的查找 212

9.3动态查找表 213

9.3.1二叉排序树和平衡二叉树 214

9.3.2 B-树和B＋树 226

9.4哈希表 233

9.4.1哈希表与哈希函数 233

9.4.2哈希函数的构造方法 234

9.4.3解决冲突的方法 236

9.4.4哈希表的查找及其效率分析 239

小结 241

习题 242

第10章 排序 245

10.1排序的基本概念 245

10.2插入排序 246

10.2.1直接插入排序 246

10.2.2折半插入排序 247

10.2.3 2—路插入排序 249

10.2.4表插入排序 250

10.2.5希尔排序 251

10.3交换排序 252

10.3.1冒泡排序 252

10.3.2快速排序 253

10.4选择排序 256

10.4.1简单选择排序 256

10.4.2堆排序 257

10.5二路归并排序 259

10.6基数排序 260

10.6.1多关键字排序 260

10.6.2链式基数排序 260

10.6.3各种排序方法的比较 265

小结 266

习题 266