数据结构PDF电子书下载

第1章绪论 1

1.1数据结构的重要意义 1

1.1.1计算机处理问题分类 1

1.1.2非数值性问题求解 2

1.2数据结构的相关概念 3

1.2.1数据概念 3

1.2.2结构概念 4

1.2.3类型概念 8

1.3算法描述及算法分析 9

1.3.1算法概念 9

1.3.2算法描述 11

1.3.3算法分析 13

习题 18

第2章线性表 20

2.1线性表的逻辑结构 20

2.1.1线性表的定义 20

2.1.2线性表的抽象数据类型 21

2.2线性表的顺序存储结构及操作实现 22

2.2.1顺序表的定义 22

2.2.2顺序表的操作实现 23

2.3线性表的链式存储结构及操作实现 28

2.3.1单链表的定义 28

2.3.2单链表的操作实现 29

2.3.3循环链表 34

2.3.4双向链表 35

2.3.5静态链表 38

2.4线性表两种存储结构的比较 39

2.4.1基于空间的比较 39

2.4.2基于时间的比较 40

习题 40

第3章栈和队列 42

3.1栈 42

3.1.1栈的逻辑结构 42

3.1.2栈的顺序存储结构及操作实现 44

3.1.3栈的链式存储结构及操作实现 47

3.1.4栈与递归问题 51

3.2队列 54

3.2.1队列的逻辑结构 54

3.2.2队列的顺序存储结构及操作实现 55

3.2.3队列的链式存储结构及操作实现 59

习题 64

第4章串 66

4.1串的逻辑结构 66

4.1.1串的定义 66

4.1.2串的抽象数据类型 67

4.2串的顺序存储结构与操作实现 68

4.2.1静态顺序串的定义 69

4.2.2动态顺序串的定义 69

4.2.3顺序串的操作实现 70

4.2.4串的块链存储方式 73

4.3串的模式匹配 75

4.3.1简单的模式匹配方法 76

4.3.2改进的模式匹配方法 77

习题 81

第5章数组和广义表 83

5.1数组 83

5.1.1数组的逻辑结构 83

5.1.2数组的顺序存储结构与操作实现 85

5.2矩阵的压缩存储 88

5.2.1特殊矩阵的压缩存储 88

5.2.2稀疏矩阵的压缩存储 92

5.3广义表 99

5.3.1广义表的逻辑结构 99

5.3.2广义表的链式存储结构及操作实现 101

习题 104

第6章树和二叉树 106

6.1树的逻辑结构 106

6.1.1树的定义 107

6.1.2树的抽象数据类型 110

6.2树的存储结构与操作实现 111

6.2.1树的存储结构 111

6.2.2树的操作实现 115

6.3二叉树的逻辑结构 117

6.3.1二叉树的定义 117

6.3.2二叉树的抽象数据类型 122

6.4二叉树的存储结构与操作实现 123

6.4.1二叉树的存储结构 124

6.4.2二叉树的操作实现 125

6.4.3线索链表 128

6.5树和森林与二叉树的转换 131

6.5.1树与二叉树的转换 132

6.5.2森林与二叉树的转换 133

6.6哈夫曼树及其应用 135

6.6.1哈夫曼树 135

6.6.2哈夫曼编码 140

习题 143

第7章图 146

7.1图的逻辑结构 146

7.1.1图的定义 146

7.1.2图的抽象数据类型 150

7.2图的存储结构与操作实现 153

7.2.1图的存储结构 153

7.2.2图的操作实现 158

7.3图的连通性及其应用 161

7.3.1无向图的连通分量 161

7.3.2生成树和生成森林 162

7.3.3最小生成树 163

7.4有向无环图及其应用 168

7.4.1拓扑排序 169

7.4.2关键路径 171

7.5最短路径 176

7.5.1单源最短路径 176

7.5.2其他最短路径 179

习题 180

第8章查找 183

8.1查找的基本概念 183

8.2静态查找表 185

8.2.1顺序表的查找 185

8.2.2有序表的查找 186

8.2.3索引顺序表的查找 188

8.3动态查找表 190

8.3.1二叉排序树 190

8.3.2平衡二叉树 196

8.3.3B_树和B+树 203

8.4哈希表 211

8.4.1哈希表的定义 211

8.4.2哈希函数的构造 212

8.4.3处理冲突的方法 215

8.4.4哈希表上的查找 216

习题 219

第9章排序 222

9.1排序的基本概念 222

9.2插入排序 224

9.2.1直接插入排序 224

9.2.2希尔排序 226

9.3交换排序 227

9.3.1冒泡排序 228

9.3.2快速排序 229

9.4选择排序 232

9.4.1简单选择排序 232

9.4.2堆排序 234

9.5归并排序 237

9.5.12-路归并排序 237

9.5.2归并排序 239

9.6基数排序 240

9.6.1多关键字排序 240

9.6.2链式基数排序 241

9.7排序方法比较 244

习题 247

第10章课程实验 250

10.1实验概述 250

10.1.1教学目的 250

10.1.2实验步骤 251

10.1.3报告示例 252

10.2实验内容 253

10.2.1线性表综合实验 253

10.2.2栈综合实验 254

10.2.3队列综合实验 255

10.2.4广义表综合实验 255

10.2.5树和二叉树综合实验 256

10.2.6图综合实验 256

10.2.7查找综合实验 257

10.2.8排序综合实验 257

附录习题参考答案 259

参考文献 277