目录
第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
鄂公网安备 42010302001612号 