数据结构：C++版

目录数据结构(C++版)第1章绪论11.1数据结构的重要性1
1.2面向对象程序设计2
1.2.1面向对象程序设计方法2
1.2.2C++的特征及基本概念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
小结15
习题15
第2章算法分析16
2.1算法分析的概念16
2.2算法运行时间举例18
2.3最大连续子序列之和问题18
2.3.1简单易懂的O(n3)算法19
2.3.2一个改进的O(n2)算法20
2.3.3一个线性算法21
2.4静态搜索问题23
2.4.1顺序搜索23
2.4.2二分搜索24
2.4.3插值搜索26
2.5检验一个算法分析26
2.6Big\|Oh分析法的限制27
小结28
习题28
第3章线性表30
3.1线性表及其抽象数据类型说明30
3.1.1线性表及其逻辑结构30
3.1.2线性表的抽象数据类型描述34
3.2线性表的顺序存储35
3.2.1顺序存储35
3.2.2顺序表类的定义36
3.2.3顺序表类的实现36
3.3线性表的链式存储40
3.3.1线性链表的存储结构40
3.3.2线性链表类的定义41
3.3.3线性链表类的实现43
3.3.4循环链表47
3.3.5循环链表类的实现48
3.3.6双向链表49
3.3.7可利用空间表51
3.3.8表遍历器52
3.4线性表的顺序存储和链式存储的比较54
[2][2]目录[][][2]数据结构(C++版)[]
3.5链式存储结构的应用55
3.5.1约瑟夫问题55
3.5.2一元多项式求和56
小结60
习题60
第4章栈和队列63
4.1栈63
4.1.1栈的定义63
4.1.2栈的顺序存储结构66
4.1.3栈的链式存储结构69
4.1.4顺序栈和链式栈的比较72
4.2栈的应用72
4.2.1迷宫问题72
4.2.2表达式求值75
4.2.3汉诺塔问题78
4.2.4数制转换80
4.2.5行编辑81
4.3队列82
4.3.1队列的定义82
4.3.2队列的顺序存储85
4.3.3队列的链式存储92
4.3.4顺序队列与链式队列的比较96
4.3.5优先队列96
4.4队列的应用97
4.4.1解决设备速度不匹配问题97
4.4.2舞伴问题97
4.4.3火车车厢重排99
小结101
习题101
第5章串105
5.1C++语言的字符和字符串105
5.2串的基本概念106
5.3串的存储结构107
5.3.1串的顺序存储结构107
5.3.2串的链式存储结构109
5.3.3串的索引存储结构110
5.4串的操作111
5.4.1常用的C++字符串函数111
5.4.2串的抽象数据类型的描述112
5.4.3串的类定义113
5.4.4部分成员函数的实现114
5.5串的基本运算与实现117
5.5.1串插入117
5.5.2串删除118
5.6模式匹配120
5.6.1模式匹配的BF算法120
5.6.2模式匹配的KMP算法122
5.7串在文本编辑中的应用126
小结128
习题128
第6章数组和广义表130
6.1C++中数组的定义及抽象数据类型表示130
6.1.1C++中数组的定义130
6.1.2数组的抽象数据类型表示131
6.2数组的顺序存储结构132
6.3矩阵的压缩存储133
6.3.1特殊矩阵的压缩存储134
6.3.2稀疏矩阵的压缩存储136
6.4广义表的概念143
6.5广义表的存储结构表示144
6.6广义表的运算146
小结153
习题153
第7章树157
7.1树的基本概念157
7.1.1树的定义157
7.1.2树的表示形式158
7.1.3树的常用术语159
7.1.4树的基本操作159
7.1.5一个树的接口160
7.1.6树的基本算法161
7.2二叉树162
7.2.1二叉树的定义162
7.2.2二叉树的性质164
7.2.3二叉树的接口166
7.2.4二叉树的存储结构167
7.2.5二叉树的遍历175
7.2.6二叉树遍历的应用178
7.3线索二叉树179
7.3.1线索二叉树的类定义179
7.3.2中序线索二叉树183
7.4树、森林和二叉树的关系186
7.4.1树的存储结构186
7.4.2森林与二叉树的转换189
7.4.3树和森林的遍历192
7.5霍夫曼树及其应用194
7.5.1霍夫曼树的定义194
7.5.2霍夫曼树的构造195
7.5.3霍夫曼树在编码问题中的应用198
小结200
习题200
第8章图204
8.1图的基本概念204
8.1.1图的定义及基本概念204
8.1.2图的抽象数据类型208
8.2图的存储结构209
8.2.1邻接矩阵表示法210
8.2.2邻接表215
8.2.3十字链表221
8.2.4邻接多重表223
8.3图的遍历225
8.3.1深度优先搜索225
8.3.2广度优先搜索227
8.3.3欧拉回路228
8.4图的连通性230
8.4.1连通分量230
8.4.2重连通分量232
8.5生成树233
8.5.1普里姆算法234
8.5.2克鲁斯卡尔算法237
8.6最短路径239
8.6.1单源最短路径240
8.6.2求每一对顶点之间的最短路径242
8.7拓扑排序243
8.8关键路径247
小结253
习题254
第9章查找258
9.1基本概念258
9.2线性表的查找259
9.2.1顺序查找259
9.2.2折半查找261
9.2.3索引查找263
9.2.4分块查找267
9.3树表查找269
9.3.1二叉查找树270
9.3.2平衡二叉树276
9.3.3B-树281
9.4哈希表的查找283
9.4.1哈希表283
9.4.2构造哈希表的基本方法284
9.4.3解决冲突的方法286
9.4.4哈希表的查找方法289
9.5各种查找方法的比较290
小结291
习题291
第10章排序295
10.1基本概念295
10.2内部排序298
10.2.1插入排序298
10.2.2交换排序303
10.2.3选择排序307
10.2.4归并排序315
10.2.5基数排序319
10.3内部排序方法比较323
10.4外部排序简介325
小结325
习题326
第11章递归330
11.1递归的定义330
11.2常见递归问题331
11.2.1汉诺塔问题331
11.2.2八皇后问题332
11.2.3表达式树335
11.3递归的实现337
11.4消除递归340
11.4.1尾递归和单向递归的消除340
11.4.2用栈模拟系统运行时的栈341
11.5递归的评估344
小结345
习题346
第12章文件348
12.1外存储器的介绍348
12.2磁盘349
12.3有关文件的概念350
12.3.1文件及其类别351
12.3.2文件的操作352
12.4文件的组织353
12.4.1顺序文件354
12.4.2索引文件355
12.4.3散列文件361
12.4.4多关键字文件362
12.5外部排序365
12.5.1外部排序的简单方法365
12.5.2两路归并365
12.5.3多路归并368
12.6文件的索引结构369
12.6.1索引向量369
12.6.2树形索引结构370
小结370
习题370
参考文献372
C++C++