数据结构PDF电子书下载

第1章 数据结构概述 1

1.1数据的逻辑结构 1

1.1.1数据及数据间的邻接关系 2

1.1.2数据的逻辑结构 3

1.1.3数据逻辑结构的形式化描述 4

1.2数据的存储结构 5

1.2.1顺序式存储结构 5

1.2.2链式存储结构 6

1.3算法及算法分析 7

1.3.1算法及算法的描述 7

1.3.2算法分析 11

小结 15

习题 15

第2章 线性表 18

2.1线性表的基本知识 18

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

2.2.1顺序表 19

2.2.2顺序表的基本算法描述 20

2.3线性表的链式存储实现 28

2.3.1单链表 28

2.3.2单链表的基本算法描述 29

2.4链式存储的推广 36

2.4.1双链表 36

2.4.2循环链表 39

2.5线性表的应用 44

2.5.1多项式的求值和相加 44

2.5.2约瑟夫问题 48

小结 50

习题 51

第3章 堆栈与队列 55

3.1堆栈 55

3.1.1堆栈的基本知识 55

3.1.2堆栈的顺序存储实现 57

3.1.3堆栈的链式存储实现 62

3.2队列 65

3.2.1队列的基本知识 65

3.2.2队列的顺序存储实现 66

3.2.3循环队列的顺序存储实现 70

3.2.4队列的链式存储实现 75

3.3堆栈与队列的应用 81

3.3.1堆栈应用——算术表达式求值 81

3.3.2堆栈应用——函数递归调用 87

3.3.3队列应用——操作系统中的任务队列 90

小结 91

习题 92

第4章 串、数组、矩阵和广义表 96

4.1串与串的存储实现 96

4.1.1串的基本知识 96

4.1.2串的顺序存储实现 97

4.1.3串的链式存储实现 104

4.2串的模式匹配 111

4.2.1串的简单模式匹配 111

4.2.2串的快速模式匹配 116

4.3数组 126

4.3.1数组简介 126

4.3.2数组的顺序存储 127

4.4特殊矩阵及稀疏矩阵 130

4.4.1特殊矩阵 130

4.4.2稀疏矩阵 135

4.5广义表 141

4.5.1广义表的定义和性质 141

4.5.2广义表的存储结构 143

4.5.3广义表基本操作的实现 145

小结 147

习题 147

第5章 二叉树 152

5.1二叉树概述 152

5.1.1二叉树的基本概念 152

5.1.2二叉树的性质 156

5.2二叉树的存储结构 159

5.2.1二叉树的顺序存储结构 159

5.2.2二叉树的链式存储结构 160

5.3遍历二叉树 163

5.3.1遍历二叉树的含义 163

5.3.2遍历二叉树的实现 166

5.3.3对二叉树遍历序列的讨论 173

5.4线索二叉树 177

5.4.1线索二叉树的概念 177

5.4.2二叉树的线索化 179

5.4.3在线索二叉树上求指定结点的前驱和后继 183

5.5哈夫曼树及哈夫曼编码 186

5.5.1编码概述 186

5.5.2哈夫曼树的构造方法 188

5.5.3哈夫曼树在编码中的应用 192

小结 198

习题 198

第6章 树与森林 203

6.1树的概述 203

6.1.1树的定义及特性 203

6.1.2有关树的常用术语 205

6.1.3树的若干性质 207

6.2树、森林和二叉树间的转换 209

6.2.1树、森林转换到二叉树 209

6.2.2二叉树转换到树、森林 211

6.3树的存储结构 212

6.4树的遍历 219

6.5树的应用 224

6.5.1判定树 224

6.5.2树与等价关系 226

小结 233

习题 233

第7章 图 238

7.1图的概述 238

7.1.1图的定义 238

7.1.2有关图的常用术语 239

7.2图的存储结构 243

7.2.1邻接矩阵 243

7.2.2邻接表 245

7.3图的遍历 248

7.3.1图的深度优先搜索 248

7.3.2广度优先搜索 250

7.4生成树与最小生成树 252

7.4.1生成树与最小生成树的概念 252

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

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

7.5最短路径 261

7.5.1单源最短路径 262

7.5.2每对顶点间的最短路径 268

7.6拓扑排序与关键路径 274

7.6.1拓扑排序 274

7.6.2 AOE网与关键路径 278

小结 285

习题 286

第8章 查找 290

8.1查找的基本概念 290

8.2静态查找算法 292

8.2.1顺序查找 292

8.2.2折半查找 293

8.2.3分块查找 298

8.3二叉查找树 300

8.3.1二叉查找树及查找算法 301

8.3.2二叉查找树的插入 303

8.3.3二叉查找树的删除 305

8.4平衡二叉树 310

8.4.1平衡二叉树的定义 310

8.4.2 AVL树中插入的不平衡类型及调整方法 311

8.5 B树与B＋树 315

8.5.1 B树及B树的查找 315

8.5.2 B树的插入和删除 319

8.5.3 B＋树简介 323

8.6散列及散列表的动态查找 324

8.6.1散列的概念 324

8.6.2常用散列函数的构造方法 326

8.6.3冲突的处理 327

8.6.4散列表上的操作算法 331

小结 335

习题 336

第9章 排序 340

9.1排序的基本概念 340

9.2插入排序 341

9.2.1直接插入排序 341

9.2.2折半插入排序 345

9.2.3表插入排序 347

9.2.4希尔排序 349

9.3交换排序 351

9.3.1冒泡排序 351

9.3.2快速排序 354

9.4选择排序 358

9.4.1直接选择排序 358

9.4.2堆排序 360

9.5归并排序与基数排序 366

9.5.1归并排序 366

9.5.2基数排序 370

9.6外排序简介 375

9.6.1外排序概述 375

9.6.2磁盘排序 377

9.6.3磁带排序 382

小结 386

习题 386

参考文献 391