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

第1章 绪论 1

1.1 数据及其逻辑结构 1

1.1.1 基本概念 1

1.1.2 逻辑结构 2

1.2 数据结构 2

1.2.1 什么是数据结构 2

1.2.2 数据结构的二元组描述 3

1.2.3 数据结构和数据类型 4

1.3 存储实现与运算实现 4

1.3.1 顺序存储结构 4

1.3.2 链式存储结构 5

1.3.3 索引存储结构 6

1.3.4 散列存储结构 6

1.3.5 运算实现 7

1.3.6 进一步讨论 8

1.4 算法描述和算法分析 8

1.4.1 什么是算法 8

1.4.2 算法描述 9

1.4.3 算法分析 11

1.5 网络教辅资源 14

1.6 小结 14

练习一 15

第2章 线性表 19

2.1 线性表的基本概念 19

2.2 线性表的顺序表示和实现 21

2.3 线性表的链接表示和实现 26

2.3.1 线性表的链式存储原理 27

2.3.2 线性表的链式存储算法实现 27

2.3.3 算法效率分析 32

2.4 循环链表和双链表 32

2.4.1 循环链表 32

2.4.2 双向链表 33

2.5 线性表的应用举例 35

2.5.1 问题的提出 35

2.5.2 分析问题 36

2.5.3 算法实现 36

2.5.4 程序 39

2.6 小结 44

练习二 45

第3章 栈和队列 54

3.1 栈 54

3.1.1 栈的定义 54

3.1.2 栈的基本运算 54

3.1.3 栈的顺序存储结构 55

3.1.4 栈的链式存储结构 58

3.1.5 栈的应用 60

3.2 队列 63

3.2.1 队列的定义 63

3.2.2 队列的基本运算 63

3.2.3 队列的顺序存储结构 64

3.2.4 队列的链式存储结构 68

3.2.5 队列的应用 72

3.3 小结 74

练习三 75

第4章 串和数组 79

4.1 串的基本概念 79

4.2 串的基本操作和串的存储结构 80

4.2.1 串的基本操作 80

4.2.2 串的静态顺序存储结构 81

4.2.3 串的动态顺序存储结构 87

4.2.4 串的链式存储结构 91

4.3 数组的定义和运算 92

4.4 数组的顺序存储结构 92

4.5 特殊矩阵的压缩存储 94

4.5.1 特殊矩阵 95

4.5.2 稀疏矩阵 96

4.6 小结 103

练习四 104

第5章 树和二叉树 110

5.1 树的概念与定义 110

5.1.1 树的定义 110

5.1.2 树的基本操作 111

5.2 二叉树的性质和存储结构 111

5.2.1 二叉树的定义与基本操作 111

5.2.2 二叉树的性质 112

5.2.3 二叉树的存储结构 114

5.3 二叉树的遍历与线索化 116

5.3.1 二叉树的遍历 116

5.3.2 二叉树的非递归遍历 119

5.3.3 树的唯一性问题 120

5.3.4 二叉树遍历的应用 121

5.3.5 线索二叉树 124

5.4 树、森林和二叉树的关系 126

5.4.1 树的存储结构 127

5.4.2 树、森林与二叉树的相互转换 129

5.4.3 树与森林的遍历 132

5.5 哈夫曼树及其应用 133

5.5.1 哈夫曼树的定义 133

5.5.2 哈夫曼树的构造 134

5.5.3 哈夫曼编码 135

5.6 小结 137

练习五 139

第6章 图 146

6.1 图的定义及理论 146

6.2 图的存储结构及算法实现 149

6.2.1 图的基本运算的抽象 149

6.2.2 数组表示法 150

6.2.3 邻接表表示 154

6.2.4 十字链表表示 160

6.3 图的算法实现 162

6.3.1 图的遍历算法 162

6.3.2 图的连通性 166

6.4 图的应用 167

6.4.1 图的最小生成树 167

6.4.2 最短路径 171

6.4.3 任意顶点最短路径 175

6.5 小结 176

练习六 177

第7章 查找表 183

7.1 查找表的基本概念 183

7.2 静态查找表 184

7.2.1 顺序查找 184

7.2.2 折半查找 187

7.2.3 分块查找 190

7.3 动态查找表 192

7.3.1 二叉排序树 192

7.3.2 平衡二叉树 199

7.4 哈希表 200

7.4.1 哈希表的基本概念 201

7.4.2 哈希函数的构造方法 202

7.4.3 处理哈希冲突的方法 206

7.5 小结 209

练习七 210

第8章 内部排序 217

8.1 排序的基本概念 217

8.1.1 排序 217

8.1.2 内部排序和外部排序 218

8.1.3 排序算法评价 218

8.1.4 排序算法的稳定性 218

8.1.5 待排序记录序列的存储结构 218

8.2 直接插入排序和希尔排序 218

8.2.1 直接插入排序 219

8.2.2 折半查找插入排序 222

8.2.3 希尔排序 223

8.3 选择排序和堆排序 225

8.3.1 选择排序 226

8.3.2 堆排序 227

8.4 冒泡排序和快速排序 229

8.4.1 冒泡排序 229

8.4.2 快速排序 231

8.5 归并排序 235

8.6 基数排序 236

8.6.1 基本思想 236

8.6.2 基数排序过程与算法 237

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

8.8 外部排序 243

8.8.1 外部存储系统 243

8.8.2 外部排序面临的问题 246

8.8.3 外部排序的基本过程 246

8.9 小结 247

练习八 248