数据结构实用教程 C++版PDF电子书下载

第1章 绪论 1

1.1 数据与数据类型 1

1.1.1 数据 1

1.1.2 数据的计算机表示与数据类型 2

1.1.3 抽象数据类型 5

1.2 数据结构 7

1.3 算法与算法分析 10

1.3.1 算法 10

1.3.2 算法的性能分析与度量 11

1.3.3 算法的时间复杂度 11

1.3.4 算法的空间复杂度 13

习题1 14

第2章 线性表 15

2.1 线性表的类型定义及结构特征 15

2.2 线性表类型的实现——顺序映像 17

2.3 线性表类型的实现——链式存储映像 26

2.3.1 单链表 26

2.3.2 其他形式的链表 35

2.4 线性表的应用 37

2.4.1 两个有序表的合并 38

2.4.2 集合运算 40

2.4.3 一元多项式的表示和相加 42

习题2 47

第3章 其他线性结构 48

3.1 栈 48

3.1.1 栈的定义和基本操作 48

3.1.2 栈的存储结构及操作实现 49

3.1.3 栈的应用举例 55

3.2 队列 68

3.2.1 队列的定义和基本操作 68

3.2.2 队列的存储结构及操作实现 70

3.2.3 队列应用举例 77

3.3 串 83

3.3.1 串的基本概念和基本操作 83

3.3.2 串的存储结构 85

3.4 数组 87

3.4.1 数组的定义和基本操作 87

3.4.2 数组的存储表示 89

3.4.3 特殊矩阵的压缩存储 90

3.4.4 稀疏矩阵的压缩存储 92

3.5 广义表 96

3.5.1 广义表的基本概念和基本操作 97

3.5.2 广义表的存储结构 99

习题3 101

第4章 树 104

4.1 树、森林的定义及基本术语 104

4.2 二叉树 105

4.2.1 二叉树的结构定义 105

4.2.2 几种特殊形态的二叉树 106

4.2.3 二叉树的性质 107

4.2.4 二叉树的存储结构 108

4.2.5 二叉链表类的定义 110

4.2.6 二叉树的递归遍历 114

4.2.7 几个二叉树基本操作的例子 116

4.2.8 二叉树的非递归遍历 118

4.2.9 其他部分成员函数的实现 121

4.2.10 主函数（演示二叉链表类部分基本操作的执行结果） 123

4.2.11 线索二叉树 126

4.3 树与森林的再讨论 129

4.3.1 树的存储结构 129

4.3.2 树和森林的遍历 132

4.4 树型结构的应用 134

4.4.1 算术表达式求值 134

4.4.2 树与等价问题 139

4.4.3 赫夫曼树及赫夫曼编码 145

习题4 154

第5章 图 156

5.1 图的定义和术语 156

5.2 图的存储结构 160

5.2.1 邻接矩阵表示法 160

5.2.2 邻接表表示法 162

5.2.3 十字链表表示法 164

5.2.4 邻接多重表表示法 165

5.3 图的基本操作 167

5.3.1 类的定义与实现 167

5.3.2 图的遍历 175

5.3.3 图的连通性 181

5.4 最小生成树 182

5.4.1 Prim算法 183

5.4.2 Kruskal算法 186

5.5 拓扑排序和关键路径 187

5.5.1 有向无环图 187

5.5.2 拓扑排序 188

5.5.3 关键路径 190

5.6 最短路径 194

5.6.1 单源最短路径 194

5.6.2 每对顶点间的最短路径 197

习题5 199

第6章 查找 201

6.1 查找表的定义 201

6.2 静态查找表 202

6.2.1 顺序查找 202

6.2.2 折半查找 203

6.2.3 分块查找 206

6.3 动态查找表 207

6.3.1 二叉排序树 207

6.3.2 平衡二叉排序树 213

6.3.3 B－树和B＋树 221

6.4 哈希查找 226

6.4.1 哈希表的定义 227

6.4.2 哈希函数的构造方法 227

6.4.3 处理冲突的办法 229

6.4.4 哈希表的查找及分析 231

6.4.5 哈希表的构建与查找算法 233

习题6 236

第7章 排序 238

7.1 插入类排序 238

7.1.1 直接插入排序 239

7.1.2 折半插入排序 240

7.1.3 2-路插入排序 241

7.1.4 希尔排序 241

7.2 分划类排序 243

7.2.1 冒泡排序 243

7.2.2 快速排序 244

7.3 选择类排序 248

7.3.1 简单选择排序 248

7.3.2 树形选择排序 249

7.3.3 堆排序 250

7.4 归并类排序 253

7.5 基数排序 254

7.5.1 多关键字的排序 254

7.5.2 基数排序 255

7.6 内部排序的比较 260

7.7 外部排序 262

7.7.1 外部存储设备 262

7.7.2 外部排序的方法 263

7.7.3 败者树 264

习题7 265

附录A 267

参考文献 270