数据结构教程 第2版PDF|Epub|txt|kindle电子书版本网盘下载

数据结构教程 第2版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 绪论1

1.1 什么是数据结构1

1.2 数据结构的发展简史及其在计算机科学中的地位5

1.3 算法5

1.3.1 算法及其性质5

1.3.2 基本算法7

1.3.3 算法的描述8

1.4 算法分析12

1.4.1 时间复杂度12

1.4.2 空间复杂度15

1.4.3 其他方面16

习题16

第2章 线性表21

2.1 线性表的定义及其基本操作21

2.1.1 线性表的定义21

2.1.2 线性表的基本操作22

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

2.2.1 顺序存储结构的构造23

2.2.2 几种常见操作的实现25

2.2.3 顺序存储结构小结30

2.3 线性链表及其操作31

2.3.1 线性链表的构造31

2.3.2 线性链表的基本算法34

2.4 循环链表及其操作50

2.5 双向链表及其操作53

2.5.1 双向链表的构造53

2.5.2 双向链表的插入与删除算法54

2.6 链表的应用举例57

2.6.1 链式存储结构下的一元多项式相加57

2.6.2 打印文本文件的最后n行60

习题63

第3章 数组69

3.1 数组的概念69

3.2 数组的存储结构69

3.3 矩阵的压缩存储71

3.3.1 对称矩阵的压缩存储72

3.3.2 对角矩阵的压缩存储73

3.4 稀疏矩阵的三元组表表示74

3.4.1 稀疏矩阵的三元组表存储方法74

3.4.2 稀疏矩阵的转置算法75

3.4.3 稀疏矩阵的相加算法78

3.4.4 稀疏矩阵的相乘算法79

3.5 稀疏矩阵的链表表示81

3.5.1 线性链表存储方法82

3.5.2 带行指针向量的链表存储方法83

3.5.3 十字链表存储方法83

3.6 数组的应用举例88

3.6.1 一元多项式的数组表示88

3.6.2 n阶魔方89

习题91

第4章 堆栈和队列95

4.1 堆栈的概念及其操作95

4.1.1 堆栈的定义95

4.1.2 堆栈的基本操作96

4.2 堆栈的顺序存储结构96

4.2.1 顺序堆栈的构造97

4.2.2 顺序堆栈的基本算法97

4.2.3 多个堆栈共享连续空间99

4.3 堆栈的链式存储结构102

4.3.1 链接堆栈的构造103

4.3.2 链接堆栈的基本算法103

4.4 堆栈的应用举例106

4.4.1 符号匹配检查106

4.4.2 数制转换107

4.4.3 堆栈在递归中的应用108

4.4.4 表达式的计算113

4.4.5 又一个趣味游戏——迷宫117

4.5 队列的概念及其操作120

4.5.1 队列的定义120

4.5.2 队列的基本操作121

4.6 队列的顺序存储结构121

4.6.1 顺序队列的构造121

4.6.2 顺序队列的基本算法123

4.6.3 循环队列124

4.7 队列的链式存储结构127

4.7.1 链接队列的构造127

4.7.2 链接队列的基本算法128

习题131

第5章 广义表136

5.1 广义表的基本概念136

5.2 广义表的存储结构137

5.3 多元多项式的表示141

习题143

第6章 串145

6.1 串的基本概念145

6.1.1 串的定义145

6.1.2 串的几个概念146

6.2 串的基本操作146

6.3 串的存储结构148

6.3.1 串的顺序存储结构149

6.3.2 串的链式存储结构150

6.4 串的几个操作151

习题157

第7章 树与二叉树158

7.1 树的基本概念158

7.1.1 树的定义158

7.1.2 树的逻辑表示方法160

7.1.3 基本术语161

7.1.4 树的性质163

7.1.5 树的基本操作164

7.2 树的存储结构164

7.2.1 多重链表表示法165

7.2.2 三重链表表示法166

7.3 二叉树167

7.3.1 二叉树的定义167

7.3.2 二叉树的基本操作168

7.3.3 两种特殊形态的二叉树169

7.3.4 二叉树的性质169

7.3.5 二叉树与树、树林之间的转换171

7.4 二叉树的存储结构174

7.4.1 二叉树的顺序存储结构174

7.4.2 二叉树的链式存储结构176

7.5 二叉树与树的遍历180

7.5.1 二叉树的遍历181

7.5.2 由遍历序列恢复二叉树189

7.5.3 二叉树的等价性190

7.5.4 树和树林的遍历191

7.5.5 基于二叉树遍历操作的算法举例192

7.6 线索二叉树199

7.6.1 线索二叉树的构造200

7.6.2 线索二叉树的利用201

7.6.3 二叉树的线索化204

7.6.4 线索二叉树的更新205

7.7 二叉排序树206

7.7.1 二叉排序树的定义206

7.7.2 二叉排序树的建立206

7.7.3 在二叉排序树中删除结点209

7.7.4 二叉排序树的查找212

7.8 平衡二叉树215

7.9 哈夫曼树及其应用222

7.9.1 哈夫曼树的概念222

7.9.2 哈夫曼编码223

习题227

第8章 图233

8.1 图的基本概念233

8.1.1 图的定义和基本术语233

8.1.2 图的基本操作237

8.2 图的存储方法238

8.2.1 邻接矩阵存储方法238

8.2.2 邻接表存储方法240

8.2.3 有向图的十字链表存储方法244

8.2.4 无向图的多重邻接表存储方法245

8.3 图的遍历246

8.3.1 深度优先搜索247

8.3.2 广度优先搜索250

8.3.3 连通分量251

8.4 最小生成树252

8.4.1 普里姆算法253

8.4.2 克鲁斯卡尔算法255

8.5 最短路径258

8.6 AOV网与拓扑排序262

8.6.1 AOV网262

8.6.2 拓扑排序263

8.6.3 拓扑排序算法264

8.7 AOE网与关键路径269

8.7.1 AOE网270

8.7.2 关键路径271

8.7.3 关键路径的确定271

习题276

第9章 文件及查找281

9.1 文件概述281

9.1.1 文件的基本概念281

9.1.2 文件的存储介质283

9.1.3 文件的基本操作285

9.2 顺序文件287

9.2.1 连续顺序文件及其查找287

9.2.2 链接顺序文件及其查找291

9.3 索引文件292

9.3.1 稠密索引文件292

9.3.2 非稠密索引分块文件293

9.3.3 多级索引文件294

9.4 B－树和B＋树296

9.4.1 B－树的基本概念296

9.4.2 B－树的基本操作297

9.4.3 B＋树的基本概念303

9.4.4 B＋树的基本操作304

9.5 散列（hash）文件305

9.5.1 概述305

9.5.2 散列函数的几种常见构造方法306

9.5.3 处理冲突的方法309

9.5.4 散列文件的操作313

9.5.5 散列法的平均查找长度315

习题316

第10章 内排序323

10.1 概述323

10.1.1 排序的基本概念323

10.1.2 排序的分类324

10.2 插入排序325

10.3 选择排序328

10.4 泡排序330

10.5 谢尔排序332

10.6 快速排序334

10.7 堆积排序338

10.7.1 堆积的定义338

10.7.2 堆积排序算法338

10.8 二路归并排序343

10.8.1 归并子算法343

10.8.2 一趟归并扫描子算法344

10.8.3 二路归并排序算法345

10.9 基数排序346

10.10 各种内排序方法的比较350

10.10.1 稳定性比较350

10.10.2 复杂性比较350

习题352

第11章 外排序358

11.1 概述358

11.2 磁带排序359

11.2.1 多路平衡归并排序法359

11.2.2 多步归并排序361

11.3 初始归并段的合理分布与产生362

11.3.1 初始归并段的合理分布362

11.3.2 一种产生初始归并段的方法——置换选择排序364

11.4 磁盘排序366

习题369