数据结构教程PDF电子书下载

第1章 绪论 1

1.1数据结构的概念 2

1.1.1数据与数据元素 2

1.1.2数据结构 3

1.2逻辑结构与存储结构 4

1.2.1逻辑结构 4

1.2.2存储结构 5

1.3算法与算法分析 6

1.3.1算法的定义和描述 6

1.3.2算法分析和复杂度计算 7

习题1 8

第2章 线性表 11

2.1线性表及其逻辑结构 11

2.1.1线性表的定义 11

2.1.2线性表的基本操作 12

2.2线性表的顺序存储结构及运算实现 12

2.2.1线性表的顺序存储——顺序表 12

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

2.3线性表的链式存储结构及运算实现 19

2.3.1单链表 19

2.3.2单链表上基本运算的实现 21

2.3.3循环链表 27

2.3.4双向链表 28

2.3.5静态链表 31

2.3.6单链表应用示例 33

习题2 36

第3章 栈和队列 40

3.1栈 40

3.1.1栈的定义及基本运算 40

3.1.2栈的存储结构和运算实现 41

3.2栈与递归 46

3.2.1递归及其实现 46

3.2.2递归调用过程分析 47

3.3队列 50

3.3.1队列的定义及基本运算 50

3.3.2队列的存储结构和运算实现 51

3.4递归转化为非递归的研究 56

3.4.1汉诺塔问题递归解法 56

3.4.2汉诺塔问题非递归解法 59

3.4.3八皇后问题递归解法 62

3.4.4八皇后问题非递归解法 64

习题3 66

第4章串 70

4.1串的概念及基本运算 70

4.1.1串的基本概念 70

4.1.2串的基本运算 71

4.2串的顺序存储结构及基本运算 72

4.2.1串的顺序存储结构 72

4.2.2顺序串的基本运算 73

4.3串的链式存储结构及基本运算 75

4.3.1串的链式存储结构 75

4.3.2链串的基本运算 76

4.4串的模式匹配 78

4.4.1简单模式匹配 79

4.4.2无回溯的KMP匹配 80

4.4.3 next函数的改进 85

习题4 86

第5章 数组与广义表 89

5.1数组的概念与存储结构 89

5.1.1数组的基本概念 89

5.1.2数组的存储结构 90

5.2特殊矩阵的压缩存储 92

5.2.1对称矩阵 92

5.2.2三角矩阵 93

5.2.3对角矩阵 95

5.3稀疏矩阵 96

5.3.1稀疏矩阵的三元组表示 96

5.3.2稀疏矩阵的十字链表表示 100

5.4广义表 104

5.4.1广义表的基本概念 104

5.4.2广义表的存储结构 105

5.4.3广义表基本操作实现算法 109

习题5. 114

第6章 树与二叉树 118

6.1树的基本概念 118

6.1.1树的概念与定义 118

6.1.2树的基本术语 119

6.2二叉树 120

6.2.1二叉树的定义 120

6.2.2二叉树的性质 121

6.2.3二叉树的存储结构 123

6.3二叉树的遍历 125

6.3.1二叉树的遍历方法 125

6.3.2遍历二叉树的递归算法及遍历示例 126

6.3.3遍历二叉树的非递归算法 129

6.3.4二叉树的层次遍历算法 133

6.3.5由遍历序列恢复二叉树 134

6.3.6二叉树遍历的应用 136

6.4线索二叉树 139

6.4.1线索二叉树的定义及结构 139

6.4.2线索化二叉树 141

6.4.3访问线索二叉树 143

6.5哈夫曼树 145

6.5.1哈夫曼树的基本概念及构造方法 145

6.5.2哈夫曼算法的实现 148

6.5.3哈夫曼编码 150

6.6树和森林 153

6.6.1树的定义与存储结构 153

6.6.2树、森林与二叉树之间的转换 155

6.6.3树和森林的遍历 156

习题6. 157

第7章图 162

7.1图的基本概念 162

7.1.1图的定义 162

7.1.2图的基本术语 163

7.2图的存储结构 165

7.2.1邻接矩阵 166

7.2.2邻接表 167

7.2.3有向图的十字链表存储方法 170

7.2.4无向图的邻接多重表存储方法 171

7.3图的遍历 172

7.3.1深度优先搜索 172

7.3.2广度优先搜索 175

7.3.3图的连通性问题 177

7.4生成树与最小生成树 178

7.4.1生成树和生成森林 178

7.4.2最小生成树与构造最小生成树的Prim算法 181

7.4.3构造最小生成树的Kruskal算法 185

7.5最短路径 188

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

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

7.6拓扑排序和关键路径 195

7.6.1 AOV网与拓扑排序 195

7.6.2 AOE网与关键路径 199

习题7. 204

第8章 查找 211

8.1查找的基本概念 211

8.2静态查找表 212

8.2.1顺序查找 212

8.2.2有序表的查找 213

8.3树表形式的动态查找表 218

8.3.1二叉排序树 218

8.3.2平衡二叉树 225

8.3.3 B树和B+树 231

8.4地址映射方式下的动态查找表——哈希表 238

8.4.1哈希表与哈希方法 238

8.4.2哈希函数的构造方法 239

8.4.3处理冲突的方法 241

8.4.4哈希表的查找 243

习题8 246

第9章 排序 253

9.1排序的基本概念 253

9.2插入排序 254

9.2.1直接插入排序 254

9.2.2折半插入排序 256

9.2.3希尔（Shell）排序 257

9.3交换排序 259

9.3.1冒泡排序 259

9.3.2快速排序 261

9.4选择排序 264

9.4.1直接选择排序 264

9.4.2堆排序 266

9.5归并排序 269

9.6基数排序 274

9.6.1多关键字排序 274

9.6.2链式基数排序 275

9.7外排序简介 278

9.8各种内排序方法的比较 281

习题9. 283

参考文献 288