数据结构：基于C++模板类的实现PDF电子书下载

第1章 绪论 1

1.1数据结构的概念 1

1.1.1为什么要学习数据结构 2

1.1.2相关概念和术语 4

1.2抽象数据类型 6

1.2.1数据类型 6

1.2.2抽象数据类型 7

1.3算法和算法分析 10

1.3.1问题求解概述 10

1.3.2算法特性 10

1.3.3常见的算法类型 11

1.3.4算法描述 12

1.3.5算法性能分析与度量 12

习题 15

实习题 16

第2章 线性表 17

2.1线性表的逻辑结构 17

2.1.1线性表的定义 17

2.1.2线性表的基本操作 17

2.2线性表的顺序存储及操作实现 20

2.2.1顺序表 20

2.2.2顺序表上基本操作的实现 22

2.2.3顺序表应用举例 25

2.2.4小结 25

2.3线性表的链式存储及操作实现 26

2.3.1单向链表 26

2.3.2单向链表上基本操作的实现 28

2.3.3循环链表 34

2.3.4双向链表 37

2.3.5静态链表 41

2.3.6单向链表应用举例 44

2.4顺序表和链表的选取 47

习题 47

实习题 49

第3章 栈和队列 50

3.1栈 50

3.1.1栈的定义及基本操作 50

3.1.2栈的存储及操作实现 51

3.1.3栈应用举例 56

3.2队列 66

3.2.1队列的定义及基本操作 66

3.2.2队列的存储及操作实现 66

3.2.3优先队列 72

3.2.4双端队列 74

3.2.5队列应用举例 74

习题 79

实习题 80

第4章 递归和广义表 82

4.1何谓递归 82

4.2递归的执行过程 84

4.3尾部递归函数 88

4.4递归的应用 89

4.4.1汉诺塔问题 89

4.4.2迷宫问题 90

4.4.3n皇后问题 92

4.5递归程序到非递归程序的转换 94

4.5.1简单转换 95

4.5.2复杂转换 95

4.5.3转化的形式化步骤 97

4.6广义表 101

4.6.1广义表的定义及基本操作 101

4.6.2广义表的存储 103

4.6.3广义表有关操作的实现 105

习题 107

实习题 108

第5章 字符串 110

5.1字符串及其基本操作 110

5.1.1字符串的基本概念 110

5.1.2字符串的基本操作 111

5.2字符串的定长顺序存储及基本操作 112

5.2.1字符串的定长顺序存储 112

5.2.2定长顺序串的基本操作 114

5.2.3模式匹配 114

5.3字符串的堆存储 123

5.3.1字符串名的存储映像 123

5.3.2堆存储结构 124

5.3.3基于堆存储结构的基本操作 125

5.4字符串的链式存储 128

5.5字符串的应用 128

5.5.1中文分词 128

5.5.2遗传算法 130

习题 131

实习题 133

第6章 数组与矩阵 134

6.1数组 134

6.1.1数组的逻辑结构 134

6.1.2数组的内存映像 137

6.2特殊矩阵的压缩存储 139

6.2.1对角矩阵 139

6.2.2三对角矩阵 140

6.2.3三角矩阵 141

6.2.4对称矩阵 142

6.3稀疏矩阵 143

6.3.1稀疏矩阵的三元组表存储 143

6.3.2稀疏矩阵的链式存储 149

6.3.3稀疏矩阵的十字链表存储 149

习题 155

实习题 156

第7章 树与二叉树 157

7.1树的定义及表示 157

7.1.1树的定义 157

7.1.2树的表示 158

7.1.3树的特点 159

7.1.4与树相关的基本术语 159

7.1.5树形结构的逻辑特征 160

7.1.6树的存储 161

7.2二叉树 165

7.2.1二叉树的定义及相关概念 165

7.2.2二叉树的主要性质 167

7.2.3二叉树的存储 168

7.2.4二叉树的基本操作及实现 171

7.3二叉树的遍历 171

7.3.1二叉树的遍历方法及递归实现 171

7.3.2二叉树遍历的非递归实现 173

7.3.3遍历算法应用举例 176

7.3.4由遍历序列恢复二叉树 178

7.3.5不用栈的二叉树遍历非递归方法 179

7.4线索二叉树 179

7.4.1线索二叉树的定义及结构 179

7.4.2线索二叉树的基本操作及实现 181

7.5最优二叉树——赫夫曼树 187

7.5.1赫夫曼树的基本概念 187

7.5.2赫夫曼树的构造算法 189

7.5.3赫夫曼树的应用 190

7.6树、森林与二叉树的转换 193

7.6.1树、森林到二叉树的转换 193

7.6.2二叉树到树和森林的转换 194

7.7树和森林的遍历 195

7.7.1树的遍历 195

7.7.2森林的遍历 196

7.7.3树和森林的层次次序遍历 197

7.8树的应用 197

7.8.1判定树 197

7.8.2集合的表示 198

习题 200

实习题 202

第8章 图 203

8.1基本概念 203

8.1.1图的定义和术语 203

8.1.2图的抽象数据类型 207

8.2图的存储结构 208

8.2.1邻接矩阵 208

8.2.2邻接表 212

8.2.3邻接矩阵和邻接表的比较 215

8.2.4十字链表 216

8.2.5邻接多重表 217

8.2.6索引表 218

8.3图的遍历 218

8.3.1深度优先搜索 219

8.3.2广度优先搜索 220

8.4图的连通性 221

8.4.1无向图的连通性 221

8.4.2有向图的连通性 222

8.4.3生成树和生成森林 223

8.4.4关节点和双连通分量 224

8.5最小生成树 226

8.5.1最小生成树的基本概念 226

8.5.2Prim算法 227

8.5.3Kruskal算法 230

8.6最短路径 231

8.6.1无权最短路径问题 232

8.6.2从一个源点到其他各顶点的最短路径 233

8.6.3边上权值为任意值的单源最短路径问题 236

8.6.4负权最短路径问题 237

8.6.5每对顶点之间的最短路径 239

8.7DAG及其应用 240

8.7.1DAG的概念 240

8.7.2AOV网与拓扑排序 241

8.7.3AOE图与关键路径 246

习题 250

实习题 253

第9章 查找 254

9.1基本概念 254

9.2静态查找表 255

9.2.1静态查找表结构 255

9.2.2顺序查找 256

9.2.3有序表的二分查找 257

9.2.4有序表的斐波那契查找和插值查找 260

9.2.5分块查找 261

9.3动态查找表 262

9.3.1二叉排序树 263

9.3.2平衡二叉树 267

9.3.3红黑树 280

9.3.4B树 289

9.3.5B＋树 298

9.4散列表查找 299

9.4.1散列表与散列方法 299

9.4.2常用的散列函数 300

9.4.3处理冲突的方法 302

9.4.4散列表的查找分析 306

9.4.5散列表的操作 308

习题 310

实习题 311

第10章 排序 312

10.1基本概念 312

10.2插入排序 314

10.2.1直接插入排序 314

10.2.2二分插入排序 316

10.2.3表插入排序 317

10.2.4谢尔排序 319

10.3交换排序 321

10.3.1冒泡排序 321

10.3.2快速排序 323

10.4选择排序 326

10.4.1线性选择排序 326

10.4.2交换线性选择排序 328

10.4.3树形选择排序 329

10.4.4堆排序 331

10.4.5用堆实现的优先队列 336

10.5两路归并排序 337

10.6分配排序 339

10.6.1多键排序 339

10.6.2桶排序 340

10.6.3链式基数排序 340

10.7其他排序方法 342

10.7.1二叉树排序法 342

10.7.2计数排序法 342

10.8各种内排序方法的比较 344

10.9外排序 346

10.9.1外排序的方法 346

10.9.2自然归并排序法 347

10.9.3k路归并法 347

10.9.4多段归并法 349

习题 352

实习题 354

参考文献 355