数据结构PDF电子书下载

第1章 绪论 1

1.1 数据结构的概念和基本术语 1

1.1.1 数据结构简介 1

1.1.2 基本术语 3

1.1.3 顺序存储结构 7

1.1.4 链式存储结构 8

1.2 算法及评价 9

1.2.1 算法的概念及特性 9

1.2.2 算法描述 9

1.2.3 算法评价 12

1.3 学习“数据结构”课程的意义 14

1.4 小结 14

1.5 习题 15

第2章 线性表 17

2.1 线性表的定义与基本运算 17

2.2 线性表的顺序存储结构与实现 19

2.2.1 顺序表的初始化 20

2.2.2 按值查找 20

2.2.3 插入 21

2.2.4 删除 22

2.3 线性表的链式存储结构与实现 23

2.3.1 单链表 24

2.3.2 静态单链表 30

2.3.3 循环链表 32

2.3.4 双向链表 33

2.4 一元多项式的表示和运算 35

2.5 小结 37

2.5.1 主要知识点 37

2.5.2 习题类型 38

2.6 习题 38

第3章 特殊线性表 41

3.1 栈 41

3.1.1 栈的定义及其抽象数据类型 41

3.1.2 栈的顺序存储和运算实现 42

3.1.3 栈的链式存储和运算实现 47

3.2 栈的应用 48

3.3 队列 52

3.3.1 队列的定义及其抽象数据类型 52

3.3.2 队列的顺序存储和运算实现 53

3.3.3 队列的链式存储和运算实现 57

3.4 队列的应用 59

3.5 小结 63

3.5.1 主要知识点 63

3.5.2 习题类型 64

3.6 练习题 65

3.7 上机实验题 66

第4章 数组、广义表及字符串 68

4.1 数组的定义 68

4.2 数组的顺序存储结构 69

4.3 特殊矩阵及其压缩存储 70

4.3.1 特殊矩阵 70

4.3.2 压缩存储 71

4.4 稀疏矩阵的压缩存储 72

4.4.1 稀疏矩阵的三元组顺序表 72

4.4.2 稀疏矩阵的转置运算 73

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

4.5 广义表 78

4.5.1 基本概念 78

4.5.2 广义表的基本运算 80

4.5.3 广义表的头尾存储法 80

4.5.4 广义表基本操作的实现 82

4.6 串的基本概念 83

4.7 串的存储结构 85

4.7.1 串的顺序存储结构 85

4.7.2 串的链式存储结构 87

4.8 小结 88

4.9 习题 89

4.10 上机实验题 91

第5章 树与二叉树 92

5.1 树 92

5.1.1 树的定义 92

5.1.2 树的基本术语 93

5.1.3 树的表示 93

5.1.4 树的抽象数据类型 94

5.2 二叉树 95

5.2.1 二叉树的定义 95

5.2.2 二叉树的抽象数据类型 96

5.2.3 二叉树的性质 97

5.2.4 二叉树的存储结构 97

5.2.5 二叉树的实现 99

5.3 二叉树的遍历 101

5.3.1 二叉树遍历的递归实现 102

5.3.2 二叉树遍历的非递归实现 103

5.4 线索二叉树 107

5.4.1 线索二叉树的基本概念 107

5.4.2 线索二叉树的基本操作 108

5.5 树和森林 113

5.5.1 树的存储结构 113

5.5.2 树和二叉树的转换 116

5.5.3 树和森林的遍历 118

5.6 哈夫曼树及其应用 119

5.6.1 哈夫曼树的基本概念及构造方法 119

5.6.2 哈夫曼树的实现 120

5.6.3 哈夫曼编码 122

5.7 小结 124

5.7.1 主要知识点 124

5.7.2 习题类型 124

5.8 习题 125

5.9 上机实验题 126

第6章 图 127

6.1 图的概述 127

6.1.1 图的基本概念 127

6.1.2 图的抽象数据类型 130

6.2 图的存储结构 131

6.2.1 图的邻接矩阵存储结构 131

6.2.2 图的邻接表存储结构 132

6.3 图的操作 133

6.3.1 邻接矩阵存储结构下图的操作 133

6.3.2 邻接表存储结构下图的操作 136

6.4 图的遍历 141

6.4.1 图的深度遍历及其实现 141

6.4.2 图的广度遍历及其实现 142

6.5 最小生成树 143

6.5.1 最小生成树的基本概念 143

6.5.2 普里姆算法 144

6.5.3 克鲁斯卡尔算法 147

6.6 最短路径 148

6.6.1 最短路径的基本概念 148

6.6.2 从一个结点到其余各结点的最短路径 148

6.6.3 每对结点之间的最短路径 150

6.7 有向无环图及其应用 153

6.7.1 拓扑排序 153

6.7.2 关键路径 156

6.8 小结 160

6.8.1 主要知识点 160

6.8.2 习题类型 160

6.9 习题 160

第7章 查找 163

7.1 基本概念 163

7.2 静态查找表 164

7.2.1 顺序表上的查找 164

7.2.2 有序表上的查找 165

7.2.3 索引顺序表上的查找 168

7.3 动态查找表 169

7.3.1 二叉排序树 169

7.3.2 平衡二叉排序树 175

7.3.3 B-树 181

7.4 散列表 186

7.4.1 散列表的概念 186

7.4.2 散列函数的构造方法 187

7.4.3 处理冲突的方法 189

7.4.4 散列表的查找 192

7.4.5 散列表的性能分析 193

7.5 小结 194

7.5.1 主要知识点 194

7.5.2 习题类型 195

7.6 习题 195

7.7 上机实验题 197

第8章 排序 198

8.1 排序的基本概念 198

8.2 简单的排序方法 200

8.2.1 直接选择排序 200

8.2.2 直接插入排序 203

8.2.3 冒泡排序 205

8.3 快速排序 208

8.4 堆排序 212

8.5 归并排序 217

8.6 基数排序 222

8.7 各种内部排序方法的比较与讨论 229

8.8 小结 230

8.8.1 主要知识点 230

8.8.2 习题类型 231

8.9 习题 231

8.10 上机实验题 234

参考文献 235