数据结构

第一章绪论.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