第1章 绪论 1
1.1引言 1
1.1.1为什么要学习数据结构 1
1.1.2数据结构课程的内容 3
1.2数据结构的概念 5
1.2.1基本概念和术语 5
1.2.2抽象数据类型 7
1.3算法 8
1.3.1算法及其特征 8
1.3.2算法的描述 9
1.3.3算法的性能分析 9
1.4小结 12
习题 12
第2章 线性表 15
2.1线性表的逻辑结构 15
2.1.1线性表的定义 15
2.1.2线性表的基本运算 15
2.2线性表的顺序存储 16
2.2.1顺序表 16
2.2.2顺序表上基本运算的实现 17
2.2.3顺序表应用举例 21
2.3线性表的链式存储 23
2.3.1单链表 23
2.3.2单链表上基本运算的实现 24
2.3.3循环链表 31
2.3.4双向链表 31
2.3.5静态链表 33
2.3.6链表应用举例 34
2.4顺序表和链表的比较 37
2.5小结 38
习题 38
第3章 栈和队列 42
3.1栈 42
3.1.1栈的定义及基本运算 42
3.1.2栈的存储及运算实现 42
3.2栈的应用举例 45
3.3队列 54
3.3.1队列的定义及基本运算 54
3.3.2队列的存储及运算实现 55
3.4队列的应用举例 60
3.5小结 63
习题 63
第4章 字符串及线性结构的扩展 65
4.1字符串 65
4.1.1字符串的基本概念 65
4.1.2顺序串 66
4.1.3模式匹配 68
4.2数组 74
4.2.1数组的逻辑结构及内存映象 74
4.2.2特殊矩阵 76
4.2.3稀疏矩阵 79
4.3广义表 89
4.3.1广义表的逻辑结构 89
4.3.2广义表的存储 91
4.4小结 93
习题 93
第5章 树结构 97
5.1二叉树 97
5.1.1二叉树的概念 97
5.1.2二叉树的主要性质 99
5.1.3二叉树的存储 101
5.1.4二叉树基本运算的实现 104
5.2二叉树的遍历 106
5.2.1以递归方法实现二叉树的3种遍历 106
5.2.2以非递归方法实现二叉树的3种遍历 108
5.2.3按层次遍历二叉树 111
5.3二叉树遍历的应用 112
5.3.1构造二叉树的二叉链表存储 112
5.3.2由遍历序列恢复二叉树 113
5.3.3在二叉树中查找值为x的数据元素 115
5.3.4统计给定二叉树中叶子结点的数目 115
5.3.5表达式运算 116
5.4线索二叉树 116
5.4.1线索二叉树的定义及结构 116
5.4.2线索二叉树的构建及遍历 118
5.5哈夫曼树及哈夫曼编码 122
5.5.1问题的引入 122
5.5.2哈夫曼树 123
5.5.3哈夫曼树的构造 124
5.5.4哈夫曼编码 126
5.6树 129
5.6.1树的概念 129
5.6.2树的表示 130
5.6.3树的存储 131
5.7树和森林与二叉树之间的转换 134
5.7.1树转换为二叉树 135
5.7.2森林转换为二叉树 135
5.7.3二叉树转换为树和森林 136
5.8树或森林的遍历 137
5.8.1树的遍历 137
5.8.2森林的遍历 137
5.9树的应用 138
5.9.1判定树 138
5.9.2集合的表示 139
5.9.3等价问题 141
5.10小结 142
习题 142
第6章 图结构 147
6.1图的基本概念 147
6.1.1图的定义和术语 147
6.1.2图的基本操作 150
6.2图的存储方法 150
6.2.1邻接矩阵 150
6.2.2邻接表 153
6.2.3十字链表 155
6.2.4邻接多重表 157
6.3图的遍历 158
6.3.1深度优先搜索 159
6.3.2广度优先搜索 160
6.3.3应用图的遍历判定图的连通性 162
6.4生成树和最小生成树 163
6.4.1生成树和生成森林 163
6.4.2最小生成树 165
6.4.3构造最小生成树的Prim算法 166
6.4.4构造最小生成树的Kruskal算法 168
6.5有向无环图及其应用 171
6.5.1有向无环图的概念 171
6.5.2AOV网与拓扑排序 172
6.5.3AOE网与关键路径 176
6.6最短路径 181
6.6.1从一个源点到其他各点的最短路径 181
6.6.2每一对顶点之间的最短路径——弗洛伊德算法 185
6.7小结 186
习题 186
第7章 查找 190
7.1基本概念 190
7.2线性表查找 191
7.2.1顺序查找 191
7.2.2在顺序存储的有序表上查找 193
7.3树表查找 198
7.3.1二叉排序树 198
7.3.2平衡二叉树 204
7.3.3B树和B＋树 210
7.4散列表查找 216
7.4.1散列表 216
7.4.2常用的散列函数 217
7.4.3处理冲突的方法及散列表的构造 219
7.4.4散列表上的查找 223
7.4.5散列表上的删除 224
7.5小结 225
习题 225
第8章 排序 229
8.1基本概念 229
8.2插入排序 230
8.2.1直接插入排序 230
8.2.2折半插入排序 232
8.2.3表插入排序及重排 233
8.2.4希尔排序 235
8.3交换排序 237
8.3.1冒泡排序 237
8.3.2快速排序 238
8.4选择排序 240
8.4.1简单选择排序 240
8.4.2树结构选择排序 241
8.4.3堆排序 242
8.5归并排序 245
8.6基数排序 247
8.6.1多关键码排序 247
8.6.2链式基数排序 248
8.7外部排序 251
8.7.1外部排序的方法 251
8.7.2多路平衡归并的实现 252
8.8小结 255
习题 255
参考文献 259