第一章 绪论 1
1.1什么是数据结构 1
*1.2数据结构的发展简史及其在计算机科学中的地位 4
1.3算法 5
1.3.1算法及其性质 5
1.3.2基本算法 6
1.3.3算法的描述 7
1.4算法分析 9
1.4.1时间复杂度 10
1.4.2空间复杂度 12
1.4.3其他方面 12
*1.5算法设计的基本步骤 12
习题 13
第二章 线性表 16
2.1线性表的定义及其基本操作 16
2.1.1线性表的定义 16
2.1.2线性表的基本操作 17
2.2线性表的顺序存储结构 18
2.3线性链表及其操作 22
2.3.1线性链表的构造 23
2.3.2线性链表的基本算法 25
2.4循环链表及其操作 38
2.5双向链表及其操作 42
2.5.1双向链表的构造 42
2.5.2双向链表的插入与删除算法 43
*2.6链表的应用举例 45
2.6.1链式存储结构下的一元多项式加法 45
2.6.2打印文本文件的最后n行 48
习题 50
第三章 数组 56
3.1数组的概念 56
3.1.1一维数组 56
3.1.2多维数组 56
3.2数组的存储结构 57
3.3矩阵的压缩存储 59
3.3.1对称矩阵的压缩存储 59
3.3.2对角矩阵的压缩存储 60
3.4稀疏矩阵的三元组表表示 60
3.4.1稀疏矩阵的三元组表存储方法 60
*3.4.2稀疏矩阵的转置算法 61
*3.4.3稀疏矩阵相乘算法 64
*3.5稀疏矩阵的十字链表表示 66
3.6数组的应用举例 71
3.6.1一元多项式的数组表示 71
3.6.2 n阶魔方 72
习题 73
第四章 堆栈和队列 77
4.1堆栈的概念及其操作 77
4.1.1堆栈的定义 77
4.1.2堆栈的基本操作 78
4.2堆栈的顺序存储结构 78
4.2.1顺序堆栈的构造 78
4.2.2顺序堆栈的基本算法 79
*4.2.3多个堆栈共享连续空间问题 80
4.3堆栈的链式存储结构 83
4.3.1链接堆栈的构造 83
4.3.2链接堆栈的基本算法 84
4.4堆栈的应用举例 85
4.4.1数制转换 85
4.4.2堆栈在递归中的应用 86
4.4.3表达式的计算 91
4.4.4又一个趣味游戏——迷宫 95
4.5队列的概念及其操作 97
4.5.1队列的定义 97
4.5.2队列的有关操作 98
4.6队列的顺序存储结构 98
4.6.1顺序队列的构造 98
4.6.2顺序队列的基本算法 100
4.6.3循环队列 101
4.7队列的链式存储结构 103
4.7.1链接队列的构造 103
4.7.2链接队列的基本算法 104
习题 106
第五章 广义表 110
5.1广义表的概念 110
5.2广义表的存储结构 111
*5.3多元多项式的表示 113
习题 114
第六章 串 116
6.1串的基本概念 116
6.1.1串的定义 116
6.1.2串的几个概念 117
6.2串的基本操作 117
6.3串的存储结构 118
6.3.1串的顺序存储结构 119
6.3.2串的链式存储结构 120
6.4串的几个操作 121
习题 126
第七章 树与二叉树 127
7.1树的基本概念 127
7.1.1树的定义 127
7.1.2树的逻辑表示方法 129
7.1.3基本术语 130
7.1.4树的性质 131
7.1.5树的基本操作 132
*7.2树的存储结构 132
7.2.1多重链表表示 132
7.2.2三重链表表示 134
7.3二叉树 135
7.3.1二叉树的定义 135
7.3.2二叉树的基本操作 135
7.3.3两种特殊形态的二叉树 136
7.3.4二叉树的性质 137
*7.3.5二叉树与树、树林之间的转换 138
7.4二叉树的存储结构 140
7.4.1二叉树的顺序存储结构 140
7.4.2二叉树的链式存储结构 142
7.5树的遍历 146
7.5.1二叉树的遍历 146
*7.5.2树和树林的遍历 153
7.5.3由遍历序列恢复二叉树 154
7.6线索二叉树 156
7.6.1线索二叉树的构造 156
7.6.2线索二叉树的利用 158
*7.6.3二叉树的线索化算法 160
*7.6.4线索二叉树的更新 160
7.7二叉排序树 161
7.7.1二叉排序树的定义 162
7.7.2二叉排序树的建立 162
*7.7.3在二叉排序树中删除结点 164
7.7.4二叉排序树的查找 166
*7.8平衡二叉树 169
7.9哈夫曼树及其应用 175
7.9.1哈夫曼树的概念 175
*7.9.2哈夫曼编码 176
习题 180
第八章 图 185
8.1图的基本概念 185
8.1.1图的定义和基本术语 185
8.1.2图的基本操作 188
8.2图的存储方法 189
8.2.1邻接矩阵存储方法 189
8.2.2邻接表存储方法 191
*8.2.3有向图的十字链表存储方法 194
*8.2.4无向图的多重邻接表存储方法 195
8.3图的遍历 196
8.3.1深度优先搜索 196
8.3.2广度优先搜索 198
8.4最小生成树 200
8.4.1普里姆算法 200
8.4.2克鲁斯卡尔算法 203
8.5最短路径问题 204
8.6 AOV网与排扑排序 208
8.6.1 AOV网 208
8.6.2拓扑排序 209
8.6.3拓扑排序算法 210
8.7 AOE网与关键路径 215
8.7.1 AOE网 215
8.7.2关键路径 216
8.7.3关键路径的确定 216
习题 220
第九章 文件及查找 224
9.1文件概述 224
9.1.1基本术语 224
9.1.2文件的存储介质 225
9.1.3文件的基本操作 227
9.2顺序文件 228
9.2.1连续顺序文件及其查找 228
9.2.2链接顺序文件及其查找 232
9.3索引文件 232
9.3.1稠密索引文件 233
9.3.2非稠密索引文件 234
*9.3.3多级索引文件 235
9.4 B-树和B＋树 236
9.4.1 B-树的基本概念 236
*9.4.2 B-树的基本操作 237
9.4.3 B＋树的基本概念 242
*9.4.4 B＋树的基本操作 243
9.5散列（Hash）文件 244
9.5.1概述 244
9.5.2散列函数的几种构造方法 245
9.5.3处理冲突的方法 248
9.5.4散列文件的操作 250
*9.5.5散列法的平均查找长度 253
习题 253
第十章 内排序 259
10.1概述 259
10.1.1排序的基本概念 259
10.1.2排序的分类 260
10.2插入排序 261
10.3选择排序 263
10.4泡排序 265
10.5谢尔排序 266
10.6快速排序 268
10.7堆积排序 271
10.7.1堆积的定义 271
10.7.2堆积排序算法 271
*10.8二路归并排序 275
10.8.1归并子算法 276
10.8.2一趟归并扫描子算法 277
10.8.3二路归并排序算法 277
*10.9基数排序 278
10.10各种内排序方法的比较 282
10.10.1稳定性比较 282
10.10.2复杂性比较 282
习题 283
*第十一章 外排序 287
11.1概述 287
11.2磁带排序 288
11.2.1多路平衡归并排序法 288
11.2.2多步归并排序 290
11.3初始归并段的合理分布与产生 291
11.3.1初始归并段的合理分布 291
11.3.2一种产生初始归并段的方法—置换选择排序 292
11.4磁盘排序 294
习题 297
上机实践题 298
附录 北京市高等教育学历文凭考试“数据结构”课程考试大纲 300
主要参考文献 306