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

第1章 绪论 1

1.1数据结构的概念和学习数据结构的必要性 1

1.2数据结构的基本概念 2

1.2.1数据 2

1.2.2数据元素和数据项 2

1.2.3数据结构 2

1.3抽象数据类型及其实现 4

1.3.1数据类型 4

1.3.2抽象数据类型（Abstract Data Type——ADT） 4

1.3.3 C++的类和对象 4

1.3.4运算符重载 6

1.3.5有关C++的动态存储分配 9

1.3.6 C++的模板（template） 10

1.4算法和算法分析 11

1.4.1算法 11

1.4.2算法分析 12

1.5实用程序软件包 15

1.6深入学习导读 19

1.7习题1 19

第2章 线性表 21

2.1线性表的逻辑结构 21

2.2线性表的顺序存储结构 23

2.3线性表的链式存储结构 31

2.3.1单链表 31

2.3.2循环链表 39

2.3.3双向链表 43

2.3.4在链表结构中保存当前位置和元素个数 46

2.4实例研究：一元多项式的表示 55

2.5深入学习导读 60

2.6习题2 60

第3章 栈和队列 61

3.1栈 61

3.1.1栈的基本概念 61

3.1.2顺序栈 62

3.1.3链式栈 67

3.2队列 74

3.2.1队列的基本概念 74

3.2.2链队列 75

3.2.3循环队列——队列的顺序存储结构 79

3.2.4队列应用——显示二项式（a+b）i的系数 84

3.3实例研究：表达式求值 85

3.4深入学习导读 88

3.5习题3 89

第4章串 90

4.1串类型的定义 90

4.2字符串的实现 91

4.3字符串模式匹配算法 98

4.3.1简单字符串模式匹配算法 98

4.3.2 KMP字符串模式匹配算法 99

4.4实例研究：文本编辑 104

4.5深入学习导读 114

4.6习题4 114

第5章 数组和广义表 115

5.1数组 115

5.1.1数组的基本概念 115

5.1.2数组的顺序表 116

5.1.3数组的类定义 118

5.2矩阵 122

5.2.1矩阵的定义和操作 122

5.2.2特殊矩阵 123

5.2.3稀疏矩阵 128

5.3广义表 139

5.3.1基本概念 139

5.3.2广义表的存储结构 141

5.4深入学习导读 151

5.5习题5 152

第6章 树和二叉树 153

6.1树的基本概念 153

6.1.1树的定义 153

6.1.2基本术语 154

6.2二叉树 155

6.2.1二叉树的定义 155

6.2.2二叉树的性质 157

6.2.3二叉树的存储结构 160

6.3二叉树遍历 168

6.3.1遍历的定义 168

6.3.2遍历算法 169

6.3.3二叉树遍历应用举例 175

6.4线索二叉树 180

6.4.1线索的概念 180

6.4.2线索二叉树的实现 182

6.5树和森林 190

6.5.1树的存储表示 190

6.5.2树的显示 198

6.5.3森林的存储表示 198

6.5.4树和森林的遍历 203

6.5.5树和森林与二叉树的转换 206

6.6哈夫曼树与哈夫曼编码 208

6.6.1哈夫曼树的基本概念 209

6.6.2哈夫曼树构造算法 210

6.6.3哈夫曼编码 210

6.6.4哈夫曼树的实现 212

6.7树的计数 216

6.8实例研究：树与等价关系 218

6.9深入学习导读 222

6.10习题6 222

第7章 图 224

7.1图的定义和术语 224

7.2图的存储表示 228

7.2.1邻接矩阵 228

7.2.2邻接表 234

7.3图的遍历 242

7.3.1深度优先搜索 242

7.3.2广度优先搜索 244

7.4连通无向网的最小代价生成树 246

7.4.1 Prim算法 246

7.4.2 Kruskal算法 249

7.5有向无环图及应用 252

7.5.1拓扑排序 253

7.5.2关键路径 256

7.6最短路径 260

7.6.1单源点最短路径问题 260

7.6.2所有顶点之间的最短路径 263

7.7深入学习导读 265

7.8习题7 265

第8章 查找 267

8.1查找的基本概念 267

8.2静态表的查找 270

8.2.1顺序查找 270

8.2.2有序表的查找 271

8.3动态查找表 274

8.3.1二叉排序树 274

8.3.2二叉平衡树 285

8.3.3 B-树和B+-树 310

8.4散列表 312

8.4.1散列表的概念 312

8.4.2构造散列函数的方法 313

8.4.3处理冲突的方法 313

8.4.4散列表的实现 315

8.5深入学习导读 320

8.6习题8 320

第9章 排序 321

9.1概述 321

9.2插入排序 322

9.2.1直接插入排序 322

9.2.2 Shell排序 324

9.3交换排序 325

9.3.1起泡排序 325

9.3.2快速排序 326

9.4选择排序 329

9.4.1简单选择排序 330

9.4.2堆排序 331

9.5归并排序 334

9.6基数排序 338

9.6.1多关键排序 338

9.6.2基数排序 339

9.7各种内部排序方法讨论 341

9.8外部排序 342

9.8.1外部排序基础 342

9.8.2外部排序的方法 343

9.9实例研究：各种排序算法运行时间测试 344

9.10深入学习导读 347

9.11习题9 347

第10章 文件 349

10.1主存储器和辅助存储器 349

10.2各种常用文件结构 349

10.2.1顺序文件 349

10.2.2索引文件 350

10.2.3散列文件 351

10.2.4 VSAM文件 351

10.2.5多关键字文件 352

10.3深入学习导读 354

10.4习题10 354

第11章 算法设计与分析 355

11.1算法设计 355

11.1.1递归算法 355

11.1.2分治算法 357

11.1.3回溯算法 358

11.2算法分析 361

11.2.1递归分析 361

11.2.2利用生成函数进行分析 362

11.3深入学习导读 363

11.4习题11 364

附录A调和级数 365

附录B课本的软件包 366

附录C实验题目 371

附录D课程设计项目 372

D1算术表达式求值 372

D2简单本文编辑器 372

D3压缩软件 373

D4公园导游系统 373

D5专家系统应用——动物游戏 373

D6词典变位词检索系统 374

附录E实验报告格式 375

附录F课程设计报告格式 376

参考文献 377