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

第1章 绪论 1

1.1数据结构的重要性 1

1.2面向对象程序设计 2

1.2.1面向对象方法 2

1.2.2 C＋＋的特征及基本概念 3

1.3基本术语 4

1.4抽象数据类型 6

1.5数据结构的概念 8

1.6数据的逻辑结构 10

1.7数据的存储结构 11

1.8数据的运算 13

1.9数据的逻辑结构、存储结构及数据的运算的关系 14

1.10算法的描述和分析 14

1.10.1算法描述 14

1.10.2算法分析 15

小结 17

习题一 17

第2章 算法基础 19

2.1算法的相关概念 19

2.1.1算法的概念 19

2.1.2算法与程序 19

2.1.3数据结构与算法 20

2.2算法分析的相关概念 20

2.2.1算法分析的概念 21

2.2.2算法的时间复杂度 22

2.2.3算法的空间复杂度 25

2.3算法分析举例 26

2.3.1多项式问题 26

2.3.2静态搜索问题 27

2.4检验一个算法分析 30

小结 31

习题二 31

第3章 面向对象程序设计与C＋＋ 35

3.1面向对象程序设计的概念 35

3.2面向对象的程序设计与C＋＋ 35

3.3变量、常量与数据类型 36

3.3.1变量 36

3.3.2常量 36

3.3.3数据类型 37

3.4控制语句 41

3.4.1表达式语句和空语句 41

3.4.2块语句 41

3.4.3选择语句 42

3.4.4循环语句 42

3.4.5转移语句 42

3.5函数 43

3.5.1函数定义 43

3.5.2函数声明 43

3.5.3函数调用 44

3.5.4参数传递 44

3.5.5函数重载 46

3.5.6构造函数和析构函数 47

3.5.7友元函数 48

3.6继承与派生 48

3.7多态性、虚函数和纯虚函数 49

3.8模板 51

3.8.1模板的概念 51

3.8.2函数模板与模板函数 52

3.8.3类模板与模板类 54

3.9输入与输出 55

小结 56

习题三 56

第4章 线性表 57

4.1线性表及其抽象数据类型说明 57

4.1.1线性表及其逻辑结构 57

4.1.2线性表的抽象数据类型描述 61

4.2线性表的顺序存储 62

4.2.1顺序存储 62

4.2.2顺序表（LinearList）类的定义 63

4.2.3顺序表（LinearList）类的实现 64

4.3线性表的链式存储 67

4.3.1线性链表的存储结构 67

4.3.2线性链表（Chain）类的定义 69

4.3.3线性链表（Chain）类的实现 70

4.3.4循环链表 74

4.3.5循环链表CircularList类的实现 75

4.3.6双向链表 76

4.3.7可利用空间表 78

4.3.8表遍历器 79

4.4线性表的顺序存储和链式存储的比较 81

4.5链式存储结构的应用 82

4.5.1约瑟夫问题 82

4.5.2一元多项式求和 83

小结 87

习题四 87

第5章 栈和队列 91

5.1栈 91

5.1.1栈的定义 91

5.1.2栈的顺序存储结构 94

5.1.3栈的链式存储结构 97

5.1.4顺序栈和链式栈的比较 99

5.2栈的应用 100

5.2.1迷宫问题 100

5.2.2表达式求值 103

5.2.3汉诺塔问题 106

5.2.4数制转换 108

5.2.5行编辑 108

5.3队列 110

5.3.1队列的定义 110

5.3.2队列的顺序存储 112

5.3.3队列的链式存储 120

5.3.4顺序队列与链式队列的比较 123

5.3.5优先队列 124

5.4队列的应用 124

5.4.1解决设备速度不匹配问题 124

5.4.2舞伴问题 125

5.4.3火车车厢重排 126

小结 128

习题五 129

第6章 串 133

6.1 C＋＋语言的字符和字符串 133

6.2串的基本概念 134

6.3串的存储结构 135

6.3.1串的顺序存储结构 136

6.3.2串的链式存储结构 137

6.3.3串的索引存储结构 138

6.4串的操作 139

6.4.1常用的C＋＋字符串函数 139

6.4.2串的抽象数据类型的描述 141

6.4.3串的类定义 142

6.4.4部分成员函数的实现 143

6.5串的基本运算与实现 146

6.5.1串插入 146

6.5.2串删除 147

6.6模式匹配 149

6.6.1模式匹配的BF算法 149

6.6.2模式匹配的KMP算法 151

6.7串在文本编辑中的应用 155

小结 156

习题六 156

第7章 数组和广义表 159

7.1 C＋＋中数组的定义及抽象数据类型表示 159

7.1.1 C＋＋中数组的定义 159

7.1.2数组的抽象数据类型表示 160

7.2数组的顺序存储结构 161

7.3矩阵的压缩存储 162

7.3.1特殊矩阵的压缩存储 163

7.3.2稀疏矩阵的压缩存储 166

7.4广义表的概念 173

7.5广义表的存储结构表示 174

7.6广义表的运算 176

小结 183

习题七 183

第8章 树 187

8.1树 187

8.1.1树的定义 187

8.1.2树的表示形式 188

8.1.3树的常用术语 189

8.1.4树的基本操作 189

8.1.5一个树的接口 190

8.1.6树的基本算法 191

8.2二叉树 193

8.2.1二叉树的定义 193

8.2.2二叉树的性质 194

8.2.3二叉树的接口 197

8.2.4二叉树的存储结构 197

8.2.5二叉树的遍历 204

8.2.6二叉树遍历的应用 207

8.3线索二叉树 208

8.3.1线索二叉树的类定义 208

8.3.2中序线索二叉树 212

8.4树、森林和二叉树的关系 215

8.4.1树的存储结构 215

8.4.2森林与二叉树的转换 218

8.4.3树和森林的遍历 220

8.5哈夫曼树及其应用 222

8.5.1哈夫曼树的定义 222

8.5.2哈夫曼树的构造 223

8.5.3哈夫曼树在编码问题中的应用 226

小结 227

习题八 228

第9章 图 231

9.1图的基本概念 231

9.1.1图的定义及基本概念 231

9.1.2图的抽象数据类型 234

9.2图的存储结构 236

9.2.1邻接矩阵表示法 236

9.2.2邻接表 242

9.2.3十字链表 249

9.2.4邻接多重表 250

9.3图的遍历 252

9.3.1深度优先搜索 252

9.3.2广度优先搜索 254

9.3.3欧拉回路 255

9.4图的连通性 257

9.4.1连通分量 257

9.4.2重连通分量 259

9.5生成树 259

9.5.1普里姆（Prim）算法 261

9.5.2克鲁斯卡尔（Kruskal）算法 264

9.6最短路径 266

9.6.1单源最短路径 266

9.6.2求每一对顶点之间的最短路径 269

9.7拓扑排序 270

9.8关键路径 274

小结 280

习题九 280

第10章 查找 285

10.1基本概念 285

10.2线性表的查找 286

10.2.1顺序查找 286

10.2.2折半查找 288

10.2.3索引查找 290

10.2.4分块查找 294

10.3树表查找 296

10.3.1二叉查找树 296

10.3.2平衡二叉树 303

10.3.3 B—树 307

10.4哈希表的查找 309

10.4.1哈希表 309

10.4.2构造哈希表的基本方法 311

10.4.3解决冲突的方法 313

10.4.4哈希表的查找方法 315

10.5各种查找方法的比较 316

小结 317

习题十 318

第11章 排序 321

11.1基本概念 321

11.2内部排序 324

11.2.1插入排序 324

11.2.2交换排序 329

11.2.3选择排序 333

11.2.4归并排序 341

11.2.5基数排序 345

11.3内部排序方法比较 349

11.4外部排序简介 350

小结 351

习题十一 351

第12章 递归 355

12.1递归的定义 355

12.2常见递归问题 356

12.2.1汉诺塔问题 356

12.2.2八皇后问题 358

12.2.3表达式树 360

12.3递归的实现 362

12.4消除递归 365

12.4.1尾递归和单向递归的消除 365

12.4.2用栈模拟系统运行时的栈 367

12.5递归的评估 370

小结 371

习题十二 371

第13章 文件 375

13.1外存储器的介绍 375

13.2磁盘 376

13.3有关文件的概念 377

13.3.1文件及其类别 378

13.3.2文件的操作 379

13.4文件的组织 380

13.4.1顺序文件 381

13.4.2索引文件 382

13.4.3散列文件 388

13.4.4多关键字文件 389

13.5外部排序 391

13.5.1外部排序的简单方法 392

13.5.2两路归并 392

13.5.3多路归并 395

13.6文件的索引结构 396

13.6.1索引向量 396

13.6.2树形索引结构 397

小结 397

习题十三 397

参考文献 399