数据结构PDF电子书下载

第1章 绪论 1

1.1基本术语 1

1.2算法的概念 3

1.3算法描述 5

1.4算法分析 6

1.4.1时间复杂度 7

1.4.2空间复杂度 10

1.5算法设计的基本步骤 10

第2章 线性表 13

2.1线性表的概念和基本操作 13

2.1.1线性表的定义 13

2.1.2线性表的基本操作 15

2.2线性表的顺序存储结构 16

2.2.1线性表的顺序存储结构 16

2.2.2顺序存储基本操作的实现 18

2.2.3顺序存储操作的时间分析 21

2.3线性表的链式存储结构 22

2.3.1单链表和指针 23

2.3.2单链表基本操作的实现 25

2.3.3创建单链表的实现 30

2.4线性表其他操作示例 31

2.5循环链表及其操作 37

2.6双向链表及其操作 39

2.6.1双向链表的构造 40

2.6.2双向链表的插入与删除算法 41

第3章 堆栈和队列 45

3.1堆栈的概念及操作 45

3.1.1堆栈的定义 45

3.1.2堆栈的有关操作 46

3.2堆栈的顺序存储结构 47

3.3堆栈的链式存储结构 50

3.4堆栈的应用举例 51

3.4.1算术表达式的求值 52

3.4.2数制转换 56

3.4.3括号匹配问题 57

3.4.4栈与递归调用的实现 59

3.5队列的概念及操作 63

3.5.1队列的定义 63

3.5.2队列的有关操作 63

3.6队列的顺序存储结构 64

3.7循环队列 67

3.8队列的链式存储结构 70

第4章 数组 73

4.1数组的定义和操作 73

4.2数组的顺序存储结构 74

4.3特殊矩阵的压缩存储 76

4.3.1对称矩阵的压缩存储 76

4.3.2对角矩阵的压缩存储 77

4.4稀疏矩阵的表示法 78

4.4.1三元组表示法 78

4.4.2三元组顺序存储结构 79

4.4.3三元组链式存储结构 80

4.5稀疏矩阵的运算 82

第5章 字符串 88

5.1字符串的概念和基本操作 88

5.1.1字符串的定义 88

5.1.2字符串的基本操作 89

5.2字符串的存储结构 90

5.2.1字符串的顺序存储结构 91

5.2.2字符串的链式存储结构 92

5.3字符串操作的算法 93

5.4串的模式匹配算法 96

5.4.1Brute-Force模式匹配算法 96

5.4.2模式匹配的一种改进算法KMP 98

第6章 广义表 101

6.1广义表的定义 101

6.2广义表的存储结构 103

6.3广义表的操作 106

第7章 树与二叉树 110

7.1树的概念 110

7.1.1树的定义 110

7.1.2树的逻辑表示法 112

7.1.3树的基本术语 113

7.1.4树的基本操作 114

7.2二叉树 115

7.2.1二叉树的定义 115

7.2.2二叉树的基本操作 116

7.2.3二叉树的性质 117

7.3二叉树的存储结构 119

7.3.1二叉树的顺序存储结构 119

7.3.2二叉树的链式存储结构 120

7.4二叉树的遍历 122

7.4.1遍历的概念 122

7.4.2二叉树遍历算法的实现及应用 124

7.5线索二叉树 129

7.5.1二叉树的线索化 129

7.5.2利用线索进行遍历 132

7.5.3线索二叉树的创建算法及示例 133

7.6二叉排序树 134

7.6.1二叉排序树的定义 134

7.6.2二叉排序树的查找 135

7.6.3二叉排序树的插入和生成算法 136

7.6.4二叉排序树中节点的删除 138

7.7哈夫曼树 141

7.7.1哈夫曼树的基本术语 141

7.7.2哈夫曼树的构造 142

7.7.3哈夫曼编码 143

7.7.4哈夫曼算法的实现 145

7.8树和森林 147

7.8.1树的存储结构 147

7.8.2二叉树与树、森林之间的转换 149

第8章 图 154

8.1图的基本概念 154

8.1.1图的定义 154

8.1.2图的基本术语 155

8.1.3图的基本操作 158

8.2图的存储结构 158

8.2.1邻接矩阵（数组） 159

8.2.2邻接表 160

8.2.3邻接多重表 162

8.2.4采用邻接表存储的图生成算法 163

8.3图的遍历 165

8.3.1DFS和BFS的基本思想 165

8.3.2DFS和BFS算法 166

8.3.3非连通图的遍历 171

8.3.4DFS和BFS算法的应用 172

8.4网的最小生成树 174

8.5最短路径 177

8.6拓扑排序 181

第9章 查找 188

9.1顺序查找 189

9.2二分查找 191

9.3静态查找表的示例 193

9.4分块查找 194

9.5树表的查找 195

9.5.1二叉排序树 196

9.5.2平衡二叉树 197

9.5.3平衡二叉树的算法 201

9.5.4B树和B＋树 204

9.6哈希表查找 206

9.6.1哈希表 206

9.6.2哈希函数的构造方法 208

9.6.3解决冲突的方法 209

9.6.4哈希表操作的相关算法实现 213

第10章 排序 217

10.1排序的概念 217

10.2插入排序 218

10.2.1直接插入排序 218

10.2.2希尔排序 220

10.3快速排序 221

10.3.1冒泡排序 221

10.3.2快速排序 222

10.4选择排序 227

10.4.1简单选择排序 227

10.4.2树形选择排序 229

10.4.3堆排序 230

10.4.4选择排序示例 235

10.5归并排序 236

10.6小结 238

参考文献 240