目录 1
前言 1
第1章绪论 1
1.1数据结构发展概况 1
1.2数据结构的基本概念和数据类型 2
1.2.1基本概念 2
1.2.2数据类型和抽象数据类型 3
1.3.1算法描述 4
1.3算法描述和分析 4
1.3.2算法分析 6
习题一 8
第2章线性表、栈和队列 10
2.1线性表的逻辑结构 10
2.2线性表的顺序存储结构 11
2.3线性链表、循环链表和双向链表 14
2.3.1线性链表 14
2.3.2循环链表 19
2.3.3双向链表 20
2.3.4静态链表 24
2.4栈的定义和实现 27
2.4.1栈的定义 27
2.4.2栈的表示和实现 27
2.5队列的定义和实现 30
2.5.1队列的定义 30
2.5.2队列的顺序存储结构 31
2.5.3链队列 34
习题二 35
第3章串 37
3.1串的逻辑结构和存储结构 37
3.1.1串的逻辑结构 37
3.1.2串的基本操作 38
3.1.3串的存储结构 38
3.2串的算法 43
3.2.1串的基本操作的实现 43
3.2.2串的模式匹配法 48
3.3串的应用 52
习题三 53
第4章递归 54
4.1递归的概念 54
4.2用C语言实现递归 57
4.3递归算法的设计 59
4.4递归模拟 62
4.4.1递归的实现机制 62
4.4.2用非递归算法模拟递归算法 63
习题四 69
第5章数组 70
5.1数组的定义及其操作 70
5.1.1数组的定义 70
5.1.2数组的基本操作 71
5.2数组的存储结构 71
5.3特殊矩阵的压缩存储 74
5.3.1对称矩阵的压缩存储 74
5.3.2对角矩阵的压缩存储 75
5.4.1稀疏矩阵的三元组顺序表 76
5.4稀疏矩阵的压缩存储 76
5.4.2十字链表 78
习题五 82
第6章树型结构 84
6.1树的逻辑结构和存储结构 84
6.1.1树的定义 84
6.1.2树的存储结构 85
6.2树的基本操作 87
6.3二叉树的定义与性质 87
6.4二叉树的存储结构 90
6.5二叉树的遍历 91
6.6线索二叉树 93
6.7森林与二叉树的转换 97
6.8树的应用 99
6.8.1二叉排序树 99
6.8.2哈夫曼树 100
6.8.3判定树 102
6.8.4集合的表示 103
习题六 105
第7章图 107
7.1 图的概念 107
7.1.1图的定义和术语 107
7.1.2图的基本操作 108
7.1.3图的存储表示 109
7.2图的遍历及生成树 111
7.3图的连通性和生成树 113
7.4最小生成树 114
7.4.1克鲁斯卡尔（Kruskal）算法 114
7.4.2普里姆（Prim）算法 114
7.5有向无环图及其应用 117
7.5.1拓扑排序 117
7.5.2关键路径 119
7.6最短路径 123
7.6.1从某个源点到其余各个顶点之间的最短路径 123
7.6.2每一对顶点之间的最短路径 125
7.7二部图与图匹配 127
习题七 131
第8章存储管理 133
8.1存储管理问题 133
8.2空闲存储块链表 135
8.3存储的动态分配和回收 138
8.3.1可利用空间表的结构 138
8.3.2分配算法 139
8.3.3回收算法 141
8.4伙伴系统 143
8.4.1可利用空间表的结构 144
8.4.2分配算法 145
8.4.3回收算法 146
8.5无用单元收集 147
8.6存储紧缩 151
习题八 153
第9章查找 154
9.1基本概念 154
9.2.1顺序查找 155
9.2顺序表的静态查找 155
9.2.2二分查找 156
9.3树表的动态查找 159
9.3.1二叉排序树查找 159
9.3.2 B—树查找 165
9.4哈希表的查找 170
9.4.1基本概念 170
9.4.2构造哈希函数的方法 171
9.4.3哈希冲突的解决方法 174
9.4.4哈希表的查找 176
9.4.5哈希算法的举例 176
习题九 178
第10章排序 180
10.1排序的概念 180
10.2插入排序 182
10.2.1直接插入排序 182
10.2.2希尔排序 184
10.3.1直接选择排序 187
10.3选择排序 187
10.3.2堆排序 189
10.4交换排序 194
10.4.1冒泡排序 194
10.4.2快速排序 196
10.5归并排序 200
10.6基数排序 203
习题十 209
11.2文件的存储介质 211
11.1文件的演变过程及基本概念 211
第11章文件 211
11.3文件的基本操作 213
11.4顺序文件 214
11.5索引文件 216
11.6 ISAM文件 217
11.7 VSAM文件 220
11.8直接存取文件 222
习题十一 224
参考文献 225