目录

第1章绪论1

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

1.2数据结构的基本概念2

1.2.1数据2

1.2.2数据元素和数据项2

1.2.3数据结构3

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

1.3.1数据类型4

1.3.2抽象数据类型4

1.4算法和算法分析4

1.4.1算法4

1.4.2算法分析5

1.5实例研究: 生命游戏7

1.6深入学习导读13

1.7习题13

第2章线性表14

2.1线性表的逻辑结构14

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

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

2.3.1单链表23

2.3.2循环链表32

2.3.3双向链表35

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

2.4实例研究: 计算任意大整数的阶乘42

2.5深入学习导读45

2.6习题45

第3章栈和队列46

3.1栈46

3.1.1栈的基本概念46

3.1.2顺序栈47

3.1.3链式栈52

3.2队列59

3.2.1队列的基本概念59

3.2.2链队列60

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

3.2.4队列应用——显示二项式(a+b)i的系数70

3.3优先队列71

3.4实例研究: 表达式求值75

3.5深入学习导读79

3.6习题79

第4章串80

4.1串类型的定义80

4.2字符串的实现81

4.3字符串模式匹配算法86

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

4.3.2首尾字符串模式匹配算法88

4.3.3KMP字符串模式匹配算法88

4.4实例研究: 文本编辑94

4.5深入学习导读103

4.6习题103

第5章数组和广义表105

5.1数组105

5.1.1数组的基本概念105

5.1.2数组的顺序表105

5.1.3数组的类模板定义107

5.2矩阵111

5.2.1矩阵的定义和操作111

5.2.2特殊矩阵113

5.2.3稀疏矩阵118

5.3广义表130

5.3.1基本概念130

5.3.2广义表的存储结构132

5.4实例研究: 稳定伴侣问题142

5.5深入学习导读145

5.6习题146

第6章树和二叉树147

6.1树的基本概念147

6.1.1树的定义147

6.1.2基本术语147

6.2二叉树149

6.2.1二叉树的定义149

6.2.2二叉树的性质151

6.2.3二叉树的存储结构153

6.3二叉树遍历162

6.3.1遍历的定义162

6.3.2遍历算法163

6.3.3二叉树遍历应用举例169

6.4线索二叉树174

6.4.1线索的概念174

6.4.2线索二叉树的实现176

6.5树和森林的实现184

6.5.1树的存储表示184

6.5.2树的显示191

6.5.3森林的存储表示192

6.5.4树和森林的遍历197

6.5.5将树和森林与二叉树相互转换199

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

6.6.1哈夫曼树的基本概念202

6.6.2哈夫曼树构造算法203

6.6.3哈夫曼编码204

6.6.4哈夫曼树的实现205

6.7树的计数209

6.8树在等价关系上的应用212

6.9实例研究: 哈夫曼压缩算法216

6.10深入学习导读221

6.11习题222

第7章图223

7.1图的定义和术语223

7.2图的存储表示227

7.2.1邻接矩阵227

7.2.2邻接表232

7.3图的遍历240

7.3.1深度优先搜索240

7.3.2广度优先搜索242

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

7.4.1Prim算法244

7.4.2Kruskal算法247

7.5有向无环图及应用250

7.5.1拓扑排序251

7.5.2关键路径253

7.6最短路径257

7.6.1单源点最短路径问题258

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

7.7实例研究: 周游世界问题——哈密顿圈263

7.8深入学习导读265

7.9习题265

第8章查找267

8.1查找的基本概念267

8.2静态表的查找267

8.2.1顺序查找267

8.2.2有序表的查找268

8.3动态查找表272

8.3.1二叉排序树272

8.3.2平衡二叉树282

8.3.3B树和B+树306

8.4哈希表309

8.4.1哈希表的概念309

8.4.2构造哈希函数的方法309

8.4.3处理冲突的方法309

8.4.4哈希表的实现311

8.5实例研究: 查找3个数组的最小共同元素316

8.6深入学习导读317

8.7习题317

第9章排序319

9.1概述319

9.2插入排序320

9.2.1直接插入排序320

9.2.2Shell排序321

9.3交换排序323

9.3.1冒泡排序323

9.3.2快速排序324

9.4选择排序327

9.4.1简单选择排序327

9.4.2堆排序328

9.5归并排序332

9.6基数排序336

9.6.1多关键字排序336

9.6.2基数排序337

9.7各种内部排序方法讨论339

9.8外部排序341

9.8.1外部排序基础341

9.8.2外部排序的方法342

9.9实例研究: 用堆实现优先队列343

9.10深入学习导读346

9.11习题346

第10章文件348

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

10.2各种常用文件结构348

10.2.1顺序文件348

10.2.2索引文件349

10.2.3哈希文件350

10.3实例研究350

10.3.1VSAM文件350

10.3.2多关键字文件351

10.4深入学习导读353

10.5习题353

第11章算法设计与分析354

11.1算法设计354

11.1.1递归算法354

11.1.2分治算法356

11.1.3动态规划算法357

11.1.4贪婪算法358

11.1.5回溯法359

11.1.6分支限界法361

11.2算法分析363

11.2.1递归分析363

11.2.2利用生成函数进行分析364

11.3实例研究: 图着色问题366

11.4深入学习导读368

11.5习题368

参考文献370

附录A调和级数371

附录B泊松分布372

附录C配套软件包文件索引373

附录D主流C++开发环境的使用方法379