数据结构PDF电子书下载

目录 1

1绪论……………………………………………………………………（1 ）1.1概述 1

1.1.1什么是数据结构 1

1.1.2学习数据结构的意义 3

1.2基本概念和术语 4

1.2.1数据与数据元素 4

1.2.2数据的逻辑结构 4

1.2.3数据的存储结构 5

1.2.4数据运算 6

1.2.5数据类型 6

1.2.6抽象数据类型 7

1.3算法和算法描述语言 8

1.3.1算法的书写格式 9

1.3.2算法中的语句 9

1.3.3常量、变量说明方式和数据类型标识符 12

1.3.4运算符号约定 13

1.4算法分析 13

思考题与习题 17

2线性表 19

2.1线性表的定义和运算 19

2.1.1线性表的定义 19

2.1.2线性表的运算 20

2.2.1顺序表 21

2.2线性表的顺序存储 21

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

2.2.3顺序表的应用实例 26

2.3线性表的链式存储 27

2.3.1单链表 27

2.3.2循环链表 38

2.3.3双链表 40

2.4线性表存储结构的讨论 42

2.4.1线性表顺序存储与链接存储的比较 42

2.4.2线性表存储空间的静态分配与动态分配 43

2.5线性表的应用举例 45

思考题与习题 48

3栈和队列 50

3.1栈 50

3.1.1栈的定义和运算 50

3.1.2栈的顺序存储 51

3.1.3栈的链表存储 55

3.1.4栈的应用 57

3.2队列 63

3.2.1队列的定义和运算 63

3.2.2队列的链表存储 64

3.2.3顺序队列 67

3.2.4队列应用举例 71

3.3栈的应用——栈和递归 72

3.3.1递归程序的实现 73

3.3.2递归程序设计 80

思考题与习题 84

4 串 86

4.1串的定义和运算 86

4.1.1串的定义 86

4.1.2串的运算 87

4.2串的存储 89

4.2.1串值的存储 89

4.2.2符号表 92

4.3模式匹配 95

4.3.1强行搜索算法 95

4.3.2 KMP算法 97

思考题与习题 102

5数组和广义表 103

5.1数组 103

5.1.1数组的定义和运算 103

5.1.2数组的顺序存储结构 104

5.1.3特殊矩阵的压缩存储 110

5.1.4稀疏矩阵的压缩存储 111

5.2.1广义表的定义和运算 117

5.2广义表 117

5.2.2广义表的存储 119

*5.2.3广义表运算的实现 120

思考题与习题 121

6树 123

6.1概述 123

6.2二叉树 125

6.2.1二叉树的有关概念 126

6.2.2二叉树的性质 126

6.2.3二叉树的存储结构 129

6.3二叉树的遍历 130

6.3.1遍历算法的实现 131

6.3.2遍历算法的进一步讨论与应用 136

6.3.3遍历算法思想的应用 137

6.4线索二叉树 139

6.4.1线索二叉树结构 140

6.4.2线索二叉树中前驱后继的讨论 141

6.4.3线索二叉树的插入 146

6.4.4二叉树的线索化 149

6.5树和森林 150

6.5.1树的存储结构 150

6.5.2树（森林）与二叉树的转换 154

6.5.3树（森林）的遍历 155

6.6哈夫曼树 158

6.6.1问题描述及求解方法 159

6.6.2应用实例 162

思考题与习题 164

7 图 167

7.1图的定义与术语 168

7.1.1图的定义 168

7.1.2图的基本术语 169

7.1.3图的基本操作 170

7.2图的存储表示 172

7.2.1邻接矩阵表示法 172

7.2.2邻接表表示法 173

7.2.3邻接多重表表示法 176

7.2.4十字链表表示法 177

7.3图的遍历 179

7.3.1深度优先遍历 180

7.3.2广度优先遍历 182

7.4最小生成树 184

7.4.1最小生成树的概念 184

7.4.2普里姆算法 185

7.4.3克鲁斯卡尔算法 188

7.5拓扑排序与关键路径 189

7.5.1拓扑排序 190

7.5.2关键路径 193

7.6.1从某个源点到其余各顶点的最短路径 199

7.6最短路径 199

7.6.2所有顶点对之间的最短路径 203

思考题与习题 207

8排序 210

8.1基本概念 210

8.1.1什么是排序 210

8.1.2排序的分类 211

8.1.3基本操作 211

8.1.4存储结构 212

8.1.5内部排序的方法 212

8.2插入排序 213

8.1.6稳定性 213

8.2.1直接插入排序 214

8.2.2折半插入排序 217

8.2.3希尔排序 218

8.3交换排序 220

8.3.1冒泡排序 220

8.3.2快速排序 222

8.4选择排序 229

8.4.1直接选择排序 229

8.4.2堆排序 230

8.5归并排序 235

8.5.1方法描述 235

8.5.2排序算法 236

8.5.3算法分析 238

8.6基数排序 238

8.6.1概述 238

8.6.2从高到低的排序 239

8.6.3从低到高的排序 240

8.7几种排序方法的比较 242

8.7.1时间复杂度 243

8.7.2空间复杂度 243

8.7.3稳定性 244

8.7.4关于“排序方法的时间复杂度的下限” 244

8.7.5实例 245

8.8外部排序简介 247

思考题与习题 249

9查找 250

9.1基本概念 250

9.2顺序表的查找 252

9.2.1简单顺序表的查找 253

9.2.2折半查找 254

9.2.3索引顺序表的查找 257

9.3树表的查找 258

9.3.1二叉排序树 259

9.3.2平衡二叉树 261

9.3.3 B-树和B+树 265

9.4散列表 271

9.4.1散列表 272

9.4.2散列函数的构造方法 273

9.4.3冲突及其解决方法 276

9.4.4散列表的查找及其分析 278

思考题与习题 281

10文件简介 282

10.1文件的基本概念 282

10.1.1文件的分类 282

10.1.3文件的物理结构 283

10.1.4文件的操作 283

10.1.2文件的逻辑结构 283

10.2顺序文件 284

10.3索引文件 285

10.4 ISAM文件和VSAM文件 286

10.4.1 ISAM文件 286

10.4.2VSAM文件 286

10.5散列文件 287

10.6多关键字文件 288

10.6.1多重表文件 288

10.6.2倒排文件 290

思考题与习题 291

参考文献 293