数据结构

第一章绪论.1
1.1数据结构概念1
1.2面向对象程序设计OOP与抽象数据类型ADT3
1.3算法概念和算法描述语言5
第二章算法分析基础9
2.1引论9
2.2算法时间复杂性的分析方法11
2.3时间与空间分析15
习题16
第三章面向对象程序设计与C++语言18
3.1类和对象18
3.1.1类声明18
3.1.2类实现19
3.1.3对象声明20
3.2C++语言的基本操作21
3.2.1输入输出的C++实现21
3.2.2友元函数（friendfuntction）23
3.2.3参数传递24
3.2.4多态性25
3.2.5动态存储分配28
3.3模板29
3.3.1模板函数29
3.3.2模板类31
3.4继承32
习题34
第四章线性表.堆栈.队列35
4.1线性表的定义和基本操作35
4.2线性表的存储结构36
4.2.1顺序存储结构36
4.2.2链接存储结构----单链表36
4.2.3循环链表47
4.2.4双向循环链表49
4.3堆栈和队列53
4.3.1定义和主要操作53
4.3.2顺序存储56
4.3.3链接存储63
4.3.4应用--算术表达式求值65
习题68
第五章数组字符串和集合类71
5.1数组71
5.1.1顺序存储的数组71
5.1.2静态数组与动态数组73
5.1.3稀疏矩阵77
5.2字符串84
5.2.1定义和主要操作84
5.2.2存储方式85
5.2.3模式匹配算法*86
5.3整型集合90
习题94
第六章树98
6.1基本概念98
6.2二叉树99
6.2.1主要性质和定义99
6.2.2二叉树的实现102
6.2.3二叉树的遍历108
6.2.4复制二叉树110
6.3线索二叉树111
6.4树与森林119
6.4.1树的顺序存储结构119
6.4.2树的链接存储结构121
6.4.3森林与二叉树的转换125
6.4.4树和森林的遍历126
6.5压缩与哈夫曼树131
习题135
第七章图137
7.1概念和定义137
7.2图的存储结构与类Graph139
7.2.1存储结构139
7.2.2Graph类141
7.3遍历函数的实现153
7.3.1深度优先遍历153
7.3.2广度优先遍历155
7.4拓扑排序156
7.5关键路径159
7.6最短路径问题163
7.6.1无权最短路径问题163
7.6.2正权最短路径问题165
7.6.3负权最短路径问题*168
7.6.4每对顶点之间的最短路径171
7.7最小支撑树173
7.8应用178
7.8.1可及性与Warshall算法178
7.8.2连通分量180
习题182
第八章递归..186
8.1什么是递归186
8.2基本递归过程188
8.3递归过程的实现：堆栈与递归191
8.4递归到非递归的转换196
8.5递归的应用203
8.5.1应用实例1：算术表达式求值203
8.5.2应用实例2：回溯205
习题210
第九章排序211
9.1插入排序212
9.2交换排序217
9.2.1冒泡排序217
9.2.2分划交换排序222
9.3选择排序231
9.3.1直接选择排序231
9.3.2堆排序232
9.4合并排序238
9.5排序下界242
9.6分布排序*243
9.6.1基数分布244
9.6.2值分布247
9.7外排序*249
9.7.1外存储器249
9.7.2磁带排序250
9.7.3磁盘排序260
习题266
第十章查找与二叉查找树269
10.1线性表查找269
10.1.1顺序查找270
10.1.2有序表的查找271
10.2二叉查找树278
10.2.1定义和基本操作278
10.2.2静态树281
10.2.3动态树289
10.3数字查找树320
10.4杂凑322
10.4.1杂凑表的定义和主要操作322
10.4.2杂凑函数323
10.4.3冲突调节326
10.5(a,b)-树.B树和B+树*334
习题341
第十一章内存管理344
11.1均匀大小记录的管理和废料收集方法344
11.1.1访问计数器法345
11.1.2废料收集346
11.2不同大小记录的查找分配和压缩分配350
11.2.1查找分配351
11.2.2压缩分配357
11.3伙伴系统362
11.4C++中的动态内存分配*368
习题369
第十二章复杂数据结构371
12.1优先级队列371
12.1.1类声明371
12.1.2优先级队列的应用：长归并段372
12.2不相交集合类378
12.2.1等价关系378
12.2.2动态等价379
12.2.3快速查找算法383
12.2.4快速合并算法384
12.2.5C++实现390
12.2.6最坏情况下的归并和路径压缩391
第十三章文件393
13.1文件结构概论393
13.2顺序文件396
13.2.1串行处理文件396
13.2.2顺序处理文件399
13.2.3增补文件400
13.3杂凑（散列）文件402
13.3.1杂凑文件的设计402
13.3.2可扩充的杂凑文件405
13.4索引文件410
13.4.1动态索引结构和静态索引结构414
13.4.2索引顺序文件B+414
13.4.3B+索引文件418
13.5倒排文件和多重链表文件422
习题430
第十四章应用*432
14.1事件驱动模拟432
14.1.1模拟设计432
14.1.2模拟建立436
14.1.3运行模拟437
14.2在线等价类443
14.2.1树形描述443
14.2.2操作444
14.2.3性能评价445
14.2.4性能改进445
14.3残缺棋盘451
14.4图像压缩454
参考文献...461