高等学校教材 数据结构 修订版PDF电子书下载

第一章 绪论 1

1.1数据结构的研究对象 1

1.2数据结构发展概况 3

1.3抽象数据型 3

1.3.1抽象数据型的定义 3

1.3.2数据型、数据结构和抽象数据型 6

1.3.3抽象数据型的规格描述 7

1.3.4抽象数据型的实现 9

1.3.5多层次抽象技术 12

1.3.6抽象数据型的优点 13

1.4逐步求精的程序设计方法 13

1.4.1如何求解一个问题 13

1.4.2算法的逐步求精 14

1.4.3小结 18

1.5程序的运行时间 18

1.6关于本书采用的描述语言 24

1.6.1结构类型说明 24

1.6.2输入输出 25

1.6.3用new和delete的动态存储分配 25

1.6.4引入引用类型 25

习题 27

第二章 线性表 29

2.1抽象数据型线性表 29

2.2线性表的实现 30

2.2.1指针和游标 31

2.2.2线性表的数组实现 31

2.2.3线性表的指针实现 34

2.2.4线性表的游标实现 38

2.2.5 双向链接表 39

2.2.6环形链表 40

2.3栈 41

2.3.1栈的数组实现 42

2.3.2栈和递归过程 44

2.4排队 45

2.4.1排队的指针实现 45

2.4.2排队的循环数组实现 47

2.5多项式的代数运算 49

2.6串 52

2.6.1抽象数据型串 52

2.6.2串的表示 54

2.7数组 57

2.7.1抽象数据型数组 57

2.7.2数组的表示 58

2.8广义表 60

习题 63

第三章树 66

3.1基本术语 66

3.2二元树 67

3.2.1二元树的定义及遍历 67

3.2.2二元树的性质 69

3.2.3抽象数据型二元树 69

3.2.4二元树的表示 71

3.2.5二元树的复制 77

3.3树 79

3.3.1抽象数据型树 79

3.3.2树的表示 80

3.4森林和二元树间的转换 85

3.5树的应用 88

3.5.1用树结构表示集合 88

3.5.2判定树 92

3.5.3哈夫曼（Huffman）树 93

3.5.4表达式求值 102

习题 105

第四章 图以及与图有关的算法 108

4.1基本定义 108

4.2图的表示 110

4.2.1邻接矩阵（adjacency matrix） 110

4.2.2邻接表（adjacency list） 110

4.3图的搜索算法 111

4.3.1先深搜索与先深编号 111

4.3.2先广搜索与先广编号 112

4.4图与树的联系 113

4.4.1先深生成森林和先广生成森林 113

4.4.2无向图与开放树的联系 114

4.4.3最小生成树 115

4.5无向图的双连通性（Biconnectivity） 118

4.5.1无向图的双连通分量 119

4.5.2求关节点、 120

4.6有向图的搜索 123

4.7强连通性 124

4.8拓扑分类 126

4.8.1无环路有向图 126

4.8.2拓扑分类算法 126

4.9关键路径 128

4.10单源最短路径 133

4.11每一对结点之间的最短路径 135

4.11.1 Floyd算法 135

4.11.2 Warshall算法 138

4.11.3求有向图的中心点 139

4.12求有向图的基本环路 140

习题 142

第五章 查找 146

5.1 线性查找 146

5.2 折半查找 148

5.3分块查找 149

5.4二元查找树 151

5.5散列法 155

5.5.1内散列表 156

5.5.2散列函数 158

5.5.3冲突的处理 160

5.5.4外散列表 162

习题 164

第六章 分类 166

8.1简单的分类算法 167

6.1.1气泡分类 167

6.1.2插入分类 168

6.1.3选择分类 168

6.2快速分类 169

6.3归并分类 173

6.3.1合并两个分类序列 173

6.3.2归并分类 174

6.4堆分类 176

6.5基数分类 179

习题 183

第七章 外部分类 186

7.1磁盘文件的归并分类 186

7.1.1 K路归并 187

7.1.2并行操作的缓冲区处理 189

7.1.3初始归并段的生成 190

7.2磁带文件的归并分类 191

7.2.1平衡归并分类 191

7.2.2多阶段归并分类 192

习题 194

第八章 文件 195

8.1文件及文件操作 195

8.1.1文件的有关概念 195

8.1.2文件操作 196

8.2文件组织 196

8.2.1顺序式文件 197

8.2.2索引文件 198

8.2.3散列文件 200

8.2.4链接式文件和多重链表文件 201

8.2.5倒排文件 202

习题 203

参考文献 204