第1章 概论 1
1．1 为什么要学习数据结构 1
1．2 什么是数据结构 2
1．3 算法的描述 4
1．4 算法分析 6
习题 9
第2章 线性表 11
2．1 线性表的定义及其基本运算 11
2．1．1 线性表的逻辑结构定义 11
2．1．2 线性表的运算 13
2．2 线性表的顺序存储结构 13
2．2．1 顺序表——线性表的顺序存储结构 13
2．2．2 顺序表的基本运算 14
2．3 线性表的链式存储结构 19
2．3．1 线性链表 19
2．3．2线性链表的基本运算 20
2．3．3静态链表 25
2．3．4 循环链表 31
2．3．5 双向链表 31
2．4 一元多项式的表示及相加 33
2．5 顺序表和链表的比较 36
习题 37
第3章 栈与队列 40
3．1 栈 40
3．1．1 栈的定义及其运算 40
3．1．2 顺序栈——栈的顺序存储结构 41
3．1．3 链栈——栈的链式存储结构 42
3．2 栈的应用举例 43
3．3 栈与递归 46
3．3．1 递归概念 46
3．3．2 递归子程序的内部实现 47
3．3．3 递归子程序到非递归子程序的变换 50
3．4 队列 55
3．4．1 队列的定义及其运算 55
3．4．2 顺序队列——队列的顺序存储结构 55
3．4．3 链队列——队列的链式存储结构 58
3．5 离散事件模拟 59
习题 64
第4章 串 66
4．1 串及其运算 66
4．1．1 什么是串？ 66
4．1．2 串的基本运算 67
4．2 串的存储结构 68
4．2．1 静态存储结构 68
4．2．2 动态存储结构 68
4．3 串的基本运算的实现 69
4．3．1 静态结构存储字符串时的操作 69
4．3．2 模式匹配的一种改进算法 71
习题 71
第5章 内部排序 75
5．1 概述 75
5．2 插入排序 76
5．3 交换排序 80
5．4 选择排序 83
5．5 归并排序 84
5．6 基数排序 86
5．7 各种内部排序方法的比较讨论 89
习题 89
第6章 线性表的检索 92
6．1 基本概念 92
6．2 顺序检索 93
6．3 二分法检索 94
6．4 分块检索 96
6．5 散列表的检索 97
6．6 基于属性的检索 104
习题 107
第7章 树和二叉树 110
7．1 树的概念和运算 110
7．2 二叉树 113
7．3 二叉树的遍历 117
7．4 穿线树 122
7．5 树和森林 126
习题 130
第8章 目录表 136
8．1 二叉排序树 136
8．2 平衡的二叉排序树 141
8．3 B-树 147
8．4 键树 154
习题 157
第9章 树形结构的其它应用 159
9．1 Huffman算法及其应用 159
9．2 堆排序 164
9．3 决策树 167
9．4 判定树 169
习题 170
第10章 图 172
10．1 图的定义、术语及基本运算 172
10．2 图的存储结构 175
10．3 图的遍历 181
10．4 图的连通性问题 182
10．5 有向无环图及其应用 188
10．6 最短路径 198
习题 204
第11章 多维数组、稀疏矩阵和广义表 206
11．1 多维数组 206
11．2 矩阵的压缩存储 208
11．3 广义表 219
习题 227
第12章 文件 229
12．1 有关文件的基本概念 229
12．2 外存储器简介 231
12．3 顺序文件 233
12．4 索引文件 234
12．5 ISAM文件和VSAM文件 236
12．6 直接存取文件 239
12．7 多关键字文件 240
习题 242
第13章 外部排序 243
13．1 外部排序的方法 243
13．2 多路平衡归并的实现 244
13．3 置换-选择排序 247
13．4 最佳归并树 251
13．5 缓冲区的并行操作处理 252
13．6 磁带归并排序 253
习题 258
参考书目 260