目录
第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