数据结构

第1章概述1
1.1数据结构的发展1
1.2基本概念2
1.3算法描述与分析4
习题110

第2章线性表13
2.1线性表的定义及基本操作13
2.1.1线性表的基本概念13
2.1.2线性表的基本操作14
2.2顺序表14
2.2.1顺序表的定义14
2.2.2基本操作在顺序表上的实现15
2.3链表19
2.3.1单链表的表示和实现19
2.3.2双链表的表示和实现27
2.3.3循环链表的表示和实现31
*2.3.4静态链表的表示和实现38
2.4栈43
2.4.1栈的定义及其基本操作43
2.4.2顺序栈的表示和实现44
*2.4.3链栈的表示和实现48
2.5队列51
2.5.1队列的定义及其基本操作51
2.5.2顺序队列的表示和实现52
2.5.3链队列的表示和实现56
2.6串58数据结构(C语言版)目录2.6.1串的定义及其基本操作58
2.6.2顺序串的表示和实现59
*2.6.3链串的表示和实现64
**2.6.4串的模式匹配70
习题275

第3章数组和广义表81
3.1数组81
3.1.1数组的定义及基本操作81
3.1.2数组存储结构82
3.1.3矩阵的压缩存储83
*3.2广义表97
3.2.1广义表的定义和基本操作97
3.2.2广义表的存储98
习题3103

第4章树和二叉树107
4.1树的定义和基本操作107
4.1.1树的定义和基本术语107
4.1.2树的基本操作108
4.2二叉树的定义和性质109
4.2.1二叉树的定义109
4.2.2二叉树的性质与结论110
4.3二叉树的存储112
4.3.1二叉树的顺序存储结构112
4.3.2二叉树的链式存储结构114
4.4二叉树的遍历及应用116
4.4.1二叉树的遍历116
4.4.2二叉树递归遍历应用举例119
*4.4.3二叉树的非递归遍历122
*4.5线索二叉树124
4.5.1线索二叉树的定义124
4.5.2线索化处理算法125
4.6树和森林128
4.6.1树的存储结构128
4.6.2树、森林与二叉树之间的转换132
4.6.3树和森林的遍历133
4.7霍夫曼树及其应用133
4.7.1霍夫曼树134
4.7.2霍夫曼编码136
习题4139

第5章图143
5.1图的基本概念143
5.2图的存储146
5.2.1邻接矩阵147
5.2.2邻接表与逆邻接表148
*5.2.3十字链表150
*5.2.4邻接多重表151
5.3图的遍历152
5.3.1深度优先搜索及其生成树152
5.3.2广度优先搜索及其生成树153
5.4最小生成树154
5.4.1Kruskal算法154
5.4.2Prim算法156
5.5图的应用157
5.5.1拓扑排序157
5.5.2关键路径159
5.5.3最短路径161
习题5163

第6章查找167
6.1静态查找表168
6.1.1顺序查找168
6.1.2二分查找169
6.1.3分块查找171
6.2动态查找表173
6.2.1二叉排序树173
6.2.2平衡二叉树178
*6.2.3B_树与B+树184
*6.2.4键树186
6.3散列表187
6.3.1散列表的定义187
6.3.2散列函数的构造方法188
6.3.3处理冲突的方法190
*6.3.4散列表的查找与分析192
习题6193

第7章内部排序197
7.1概述197
7.2插入排序199
7.3交换排序207
7.4选择排序210
7.5归并排序217
7.6计数排序与基数排序219
7.7各种排序方法的综合比较222
习题7223

**第8章外部排序227
8.1外存储器简介227
8.2外部排序的方法229
8.3多路归并排序230
8.4置换选择排序232
8.5最佳归并树234
习题8235

**第9章动态存储管理237
9.1概述237
9.2可利用空间表及分配方法239
9.3边界标识法242
9.3.1可利用空间表的结构242
9.3.2分配算法243
9.3.3回收算法244
9.4伙伴系统246
9.4.1可利用空间表的结构246
9.4.2分配算法248
9.4.3回收算法249
9.5无用单元收集249
9.6存储紧缩254

**第10章文件257
10.1表与文件257
10.1.1有关文件的基本概念257
10.1.2记录的逻辑结构和物理结构258
10.1.3文件的操作258
10.2外存储器简介259
10.2.1文件的物理结构259
10.2.2文件的逻辑结构和文件的存储结构260
10.2.3顺序文件261
10.2.4索引文件262
10.3ISAM文件265
10.4VSAM文件266
10.5直接存取文件267
10.6多关键字文件268
10.6.1多重表文件268
10.6.2倒排文件269
习题10270

参考文献271