数据结构 C++语言描述PDF电子书下载

第一章 面向对象的程序设计与C++ 1

1.1 什么是面向对象的程序设计 1

1.2 面向对象的程序设计与C++ 1

1.3 C++类与对象设计 2

1.4 继承性 3

1.5 多态性、虚函数和纯虚函数 6

1.6 generic类、函数模板和模板类 8

1.7 友元函数 9

1.8 引用 10

习题 14

第二章 数据结构概述 15

2.1 基本概念 15

2.1.1 数据、数据元素、数据对象 15

2.1.2 数据结构 16

2.2 数据结构的分类 17

2.3 抽象数据类型 19

2.3.1 两种软件设计方法 19

2.3.2 数据类型 19

2.3.3 抽象数据类型 20

2.4.1 算法概念 22

2.4 算法和算法分析 22

2.4.2 算法分析 24

习题 26

第三章 向量、栈和队列 29

3.1 线性表 29

3.1.1 线性表的抽象数据类型 29

3.1.2 线性表的类表示 31

3.2 向量 35

3.2.1 向量的抽象数据类型 35

3.2.2 向量的插入和删除 38

3.2.3 向量的应用 40

3.3 栈 44

3.3.1 栈的抽象数据类型及其实现 44

3.3.2 栈的应用 46

3.4 队列 56

3.4.1 队列的抽象数据类型及其实现 57

3.4.2 队列的应用 61

习题 69

4.1 动态数据结构 70

第四章 链表 70

4.2 单链表 71

4.2.1 基本概念 72

4.2.2 结点类 73

4.2.3 链表类 75

4.2.4 栈的链表实现 86

4.2.5 队列的链表实现 89

4.2.6 链表的应用举例 91

4.3 循环链表 97

4.4 双链表 100

习题 104

第五章 排序 107

5.1 基本概念 107

5.2 插入排序 108

5.2.1 直接插入排序 108

5.2.2 折半插入排序 110

5.2.3 Shell排序 112

5.3 交换排序 114

5.3.1 起泡排序 114

5.3.2 快速排序 116

5.4.1 基本思想 120

5.4 分配排序 120

5.4.2 基数排序 121

5.5 归并排序 124

5.6 外部排序 128

5.6.1 2路合并排序 128

5.6.2 多路替代选择合并排序 129

5.6.3 最佳合并排序 131

习题 132

6.2 顺序查找 133

第六章 查找 133

6.1 基本概念 133

6.3 折半查找 134

6.4 分块查找 136

6.5 散列查找 138

6.5.1 概述 138

6.5.2 散列函数 139

6.5.3 冲突的处理 142

习题 146

6.5.4 散列查找的效率 146

第七章 树和二叉树 148

7.1 树的概念 148

7.2 二叉树 149

7.2.1 二叉树的概念 149

7.2.2 二叉树的性质 150

7.2.3 二叉树的存储方式 152

7.2.4 树(树林)与二叉树的相互转换 154

7.3.1 树(树林)的遍历 155

7.3 树(树林)、二叉树的遍历 155

7.3.2 二叉树的遍历 156

7.4 抽象数据类型BinaryTree以及类BinaryTree 157

7.4.1 抽象数据类型BinaryTree 157

7.4.2 一个完整的包含类BinaryTreeNode、类BinaryTree实现的例子 157

7.5 二叉树的遍历算法 162

7.5.1 非递归(使用栈)的遍历算法 162

7.5.2 线索化二叉树的遍历 164

习题 169

8.1 二叉排序树 171

8.1.1 二叉排序树与类BinarySTree 171

第八章 树形结构的应用 171

8.1.2 二叉排序树的检索、插入、删除运算 172

8.1.3 等概率查找对应的最佳二叉排序树 176

8.2 平衡的二叉排序树 179

8.2.1 平衡的二叉排序树与类AVLTree 179

8.2.2 平衡的二叉排序树的插入、删除 181

8.2.3 类AVLTree与AVL树高度 190

8.3 B-树、B+-树 191

8.4.1 键树 196

8.4 键树和2-3树 196

8.4.2 2-3树 198

8.5 Huffman最优树 200

8.5.1 Huffman最优树 200

8.5.2 树编码 204

8.6 堆排序 205

8.7 判定树 214

习题 215

第九章 图 217

9.1 基本概念 217

9.2.1 相邻矩阵表示图 220

9.2 图的存储表示 220

9.2.2 图的邻接表表示 221

9.2.3 邻接多重表、十字链表 221

9.3 构造Graph类 224

9.3.1 基于邻接表表示的Graph类 224

9.3.2 Graph类的实现 226

9.4 图的遍历 231

9.4.1 深度优先遍历 232

9.5 最小代价生成树 234

9.4.2 广度优先遍历 234

9.6 单源最短路径问题 239

9.7 每一对顶点间的最短路径问题 242

9.8 有向无回路图 244

9.8.1 DAG图和AOV、AOE网 244

9.8.2 AOV网的拓扑排序 246

9.8.3 AOE网的关键路径 248

习题 250

10.1 多维数组 253

10.1.1 多维数组的顺序存储 253

第十章 多维数组和广义表 253

10.1.2 特殊矩阵的顺序存储 254

10.1.3 稀疏矩阵的存储 256

10.1.4 抽象数据类型稀疏矩阵与class SparseMatrix 258

10.2 广义表 265

10.2.1 广义表的概念 265

10.2.2 广义表的存储方式 266

10.2.3 广义表结点类和抽象类class List 269

习题 272

11.1 外部存储设备简介 273

第十一章 文件 273

11.2 有关文件的基本概念 275

11.3 顺序文件 277

11.4 索引文件 277

11.5 ISAM文件和VSAM文件 279

11.6 倒排文件和多重表文件 283

11.7 散列文件 284

习题 285

参考文献 286