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

第1章 绪论 1

1.1数据结构的基本概念 1

1.2算法的描述 2

1.3VC++6.0开发工具简介 4

1.4算法的评价 7

1.4.1评价算法的一般原则 7

1.4.2算法复杂性的分析 7

1.5应用示例及分析 8

小结 9

习题与练习一 10

第2章 线性表 12

2.1线性表基本特征和基本运算 12

2.2线性表的顺序存储及运算实现 13

2.2.1顺序表 13

2.2.2顺序表上基本运算的实现 14

2.3线性表的链式存储及运算实现 16

2.3.1单链表 16

2.3.2单链表的基本运算 17

2.3.3循环链表 21

2.3.4双链表 21

2.3.5静态链表 23

2.4顺序表和链表的比较 24

2.5线性表的应用 25

2.5.1顺序表的应用 25

2.5.2一元多项式的算术运算 26

2.6应用示例及分析 27

小结 31

习题与练习二 31

第3章 栈与队列 34

3.1栈 34

3.1.1栈的定义 34

3.1.2栈的存储实现和运算实现 34

3.1.3堆栈的应用 38

3.2队列 40

3.2.1队列的定义 40

3.2.2队列的存储实现及运算实现 40

3.2.3队列的应用 46

3.3递归 47

3.4应用示例及分析 50

小结 55

习题与练习三 55

第4章 串 58

4.1串的定义及其基本运算 58

4.2串的存储结构 59

4.2.1串的顺序存储结构 59

4.2.2串的链接存储结构 60

4.3串的匹配运算 61

4.4应用示例及分析 63

小结 65

习题与练习四 66

第5章 数组、特殊矩阵和广义表 68

5.1多维数组 68

5.1.1数组的定义和操作 68

5.1.2多维数组的存储表示和寻址 69

5.2特殊矩阵的压缩存储 70

5.2.1对称矩阵 71

5.2.2三角矩阵 72

5.2.3带状矩阵 73

5.3稀疏矩阵 73

5.3.1稀疏矩阵的三元组表存储 74

5.3.2稀疏矩阵的十字链表存储 75

5.4广义表 77

5.5应用示例与分析 78

小结 79

习题与练习五 80

第6章 树 82

6.1树的定义和基本术语 82

6.2二叉树 84

6.2.1二叉树的基本概念 84

6.2.2二叉树的主要性质 85

6.2.3二叉树的存储结构 86

6.3二叉树的遍历 88

6.3.1二叉树的递归遍历 88

6.3.2二叉树的非递归遍历 90

6.4树和森林 93

6.4.1树、森林与二叉树的转换 93

6.4.2树和森林的存储表示 94

6.4.3树和森林的遍历 95

6.5线索二叉树 96

6.6二叉排序树 100

6.7平衡树 103

6.8树的应用 105

6.8.1等价类问题 106

6.8.2最优二叉树——哈夫曼树 109

6.9应用示例及分析 113

小结 115

习题与练习六 116

第7章 图 119

7.1图的定义和基本术语 119

7.2图的存储方式 121

7.2.1邻接矩阵 121

7.2.2邻接表 123

7.3图的遍历 125

7.3.1深度优先搜索（DFS） 125

7.3.2广度优先搜索（BFS） 128

7.4最小生成树 130

7.4.1普里姆（Prim）算法 131

7.4.2克鲁斯卡尔（Kruskal）算法 132

7.5最短路径 135

7.5.1从一个源点到其他各点的最短路径 135

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

7.6拓扑排序 140

7.7关键路径法 144

7.8应用示例与分析 147

小结 150

习题与练习七 151

第8章 排序 155

8.1排序的基本概念 155

8.23种简单排序方法 156

8.2.1简单选择排序 156

8.2.2冒泡排序 157

8.2.3直接插入排序 158

8.3堆排序 159

8.3.1堆的概念 159

8.3.2构建堆 160

8.3.3利用堆排序 162

8.4快速排序 164

8.5希尔排序 166

8.6归并排序 168

8.7基数排序 171

8.8应用示例及分析 175

小结 176

习题与练习八 177

第9章 查找 180

9.1查找的基本概念 180

9.2基本查找方法 181

9.2.1顺序查找 181

9.2.2二分查找 181

9.2.3分块查找 182

9.3树状查找 184

9.3.1二叉排序树查找 184

9.3.2B-树 186

9.4哈希法 187

9.4.1哈希法概述 187

9.4.2哈希函数构造方法 188

9.4.3处理冲突的方法 190

9.4.4哈希法的查找运算 191

9.5应用示例及分析 193

小结 195

习题与练习九 196

第10章 算法的分析与设计 199

10.1算法的分析 199

10.1.1分析算法的一般原则 199

10.1.2算法复杂性分析 200

10.2算法的设计 203

10.2.1分治法 203

10.2.2贪心法 206

10.2.3动态规划法 209

10.2.4回溯法 212

10.2.5分支界限法 216

小结 219

习题与练习十 220

第11章 实验与上机指导 222

实验1线性表及其运算 222

实验2栈与队列的实现及应用 230

实验3二叉树的存储与遍历 237

实验4图的存储与遍历 243

实验5排序 246

实验6查找 252

附录 习题与练习解答 258

参考文献 312