电子计算机软件数据结构PDF电子书下载

第一章 绪论 1

1.1 什么是数据结构 1

1.2 数据结构发展概况 3

1.3 数据结构课程与其它课程的关系 4

1.4 算法所用语言的几点说明 4

第二章 静态结构 8

2.1 向量 8

2.2 数组 11

2.2.1 数组与向量的比较 11

2.2.2 访问公式 13

2.2.3 数组相交部分和子数组 15

2.2.4 三角数组 19

2.2.5 稀疏数组 23

2.2.6 分配 25

2.3 记录 26

2.3.1 记录的逻辑结构 26

2.3.2 记录的物理表示和运算 27

2.3.3 明显命名的作用 29

2.4 记录数组 31

习题 35

第三章 半静态结构 37

3.1 自描述记录 37

3.2 数组的修改 40

3.3 栈、队列和双向队列 47

3.3.1 栈 47

3.3.2 多个栈共享邻接空间 50

3.3.3 栈的应用 52

3.3.4 队列 53

3.3.5 双向队列 56

习题 57

第四章 动态结构 59

4.1 向前链表 60

4.2 循环链表和双向循环链表 66

4.3 链式栈和链式队列 69

4.4 多项式的算术运算 70

4.5 共享元素及稀疏矩阵运算 75

4.6 等价关系的处理 81

4.7 广义链表、多重链表和丛结构 85

习题 89

第五章 串 91

5.1 串的逻辑特征 92

5.2 串的物理表示法 94

5.3 处理串的算法 100

习题 104

第六章 树 105

6.1 术语、树的逻辑结构及物理表示 105

6.2 二叉树 107

6.2.1 二叉树的定义及逻辑结构 107

6.2.2 二叉树的性质 107

6.2.3 二叉树的物理表示法 110

6.3 遍历二叉树 111

6.3.1 二叉树结点的排序 112

6.3.2 前序遍历 112

6.3.3 中序遍历 113

6.3.4 后序遍历 115

6.4 线索树 116

6.5 一般树的二叉树表示、遍历和运算 121

6.5.1 一般树的二叉树表示法 121

6.5.2 一般树的遍历 124

6.5.3 一般树的插入和删除 125

6.6 森林与二叉树间的转换及遍历 129

6.7 树的应用 131

6.7.1 集合表示法 131

6.7.2 表达式求值 135

6.7.3 判定树 138

6.7.4 比赛树 139

6.8 计算二叉树的数目 144

习题 149

第七章 图 151

7.1 术语 151

7.2 图的物理表示法 152

7.2.1 邻接矩阵表示法 152

7.2.2 邻接表 153

7.2.3 邻接多重表 155

7.3 图的遍历与求图的连通分量 156

7.3.1 纵向优先搜索法 156

7.3.2 横向优先搜索法 157

7.3.3 求图的连通分量 158

7.4 生成树和最小（代价）生成树 158

7.5 最短路径和传递闭包 162

7.5.1 从某个源点到其它各顶点的最短路径 162

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

7.5.3 传递闭包 168

7.6 拓扑排序 170

7.7 关键路径 175

7.8 列举所有路径 180

习题 183

第八章 存贮管理 186

8.1 存贮管理的若干问题 186

8.2 空闲存贮块链表 187

8.3 存贮的动态分配与回收 189

8.3.1 首次-配给、最佳-配给、最大-配给方法 189

8.3.2 引用计数器法 192

8.3.3 不用单元收集法 196

8.4 紧凑存贮的方法 203

8.4.1 折叠法 204

8.4.2 紧凑法 206

8.5 伙伴系统 209

习题 212

第九章 内部分类 214

9.1 查找 214

9.2 什么是分类 219

9.3 计数分类 220

9.4 选择分类 221

9.5 冒泡分类 222

9.6 线性插入 224

9.7 折半插入 225

9.8 归并分类 226

9.8.1 分类文件的归并 226

9.8.2 k个分类文件的归并 227

9.8.3 归并分类 229

9.9 堆垒分类 231

9.10 快速分类 237

9.11 基数分类 239

习题 242

第十章 数据查找 244

10.1 链表结构的线性查找 244

10.2 静态树型查找 245

10.3 动态树型查找 254

10.4 Hash（杂凑）技术 259

10.4.1 为什么要引入Hash技术 259

10.4.2 Hash函数 260

10.4.3 冲突处理 262

10.4.4 动态结构下的探测技术 269

习题 273

第十一章 文件 275

11.1 存贮设备 275

11.1.1 磁带 275

11.1.2 磁盘 276

11.2 文件的基本概念和逻辑特性 278

11.3 文件的物理结构 279

11.3.1 顺序式文件 279

11.3.2 索引技术 282

11.3.3 随机式文件 289

11.3.4 链接式文件和多重表文件 291

11.3.5 倒排文件 292

11.4 外存贮器管理 294

习题 294

第十二章 外部分类 296

12.1 关于磁盘文件的归并分类 296

12.1.1 k-路归并 298

12.1.2 并行操作的缓冲区处理 302

12.1.3 初始归并段的生成 308

12.2 关于磁带文件的归并分类 314

12.2.1 平衡归并分类法 315

12.2.2 多阶段归并分类法 320

习题 324

第十三章 数据结构示例 325

13.1 数据及其相适应的运算 325

13.2 访问路径和子结构 326

13.2.1 学生数据子结构 327

13.2.2 课程数据子结构 329

13.3 存贮需要量估算 331

13.4 运算的实现 331

参考文献 332