第1章 数据结构的基本概念 1
1.1数据结构的产生和发展 1
1.2何谓数据结构 2
1.3基本术语 4
1.4数据的存储结构 7
1.4.1顺序存储结构 7
1.4.2链式存储结构 8
1.4.3其他存储结构 9
1.5算法及算法分析 9
1.5.1算法 9
1.5.2算法的评价 10
1.5.3常用的数学术语 11
1.5.4算法分析 11
1.5.5算法的描述 14
1.6 C语言预备知识 15
1.7数据结构课程定位 21
习题 21
第2章 线性表 23
2.1何谓线性表 23
2.2线性表的抽象数据类型和基本操作 24
2.3线性表的顺序存储结构 28
2.3.1顺序表 28
2.3.2顺序表应用举例 35
2.4线性表的链式存储结构 38
2.4.1单链表 38
2.4.2双向链表 47
2.4.3循环链表 52
2.4.4链表应用举例 53
2.5顺序表和链表的比较 57
习题 58
第3章栈 60
3.1何谓栈 60
3.2栈的抽象数据类型和基本操作 61
3.3栈的存储结构 62
3.3.1栈的顺序存储结构 62
3.3.2栈的链式存储结构 65
3.4递归——汉诺塔问题 66
3.4.1何谓递归 66
3.4.2汉诺塔问题 68
3.5栈的应用 70
3.6习题 75
第4章 队列 77
4.1何谓队列 77
4.2队列的抽象数据类型和基本操作 78
4.3队列的存储结构 78
4.3.1队列的顺序存储结构 78
4.3.2顺序队列的改进——循环队列 83
4.3.3队列的链式存储结构 84
4.3.4顺序队列和链式队列的比较 89
4.3.5其他队列结构 89
4.4队列的应用 90
习题 94
第5章 字符串 96
5.1字符串概述 96
5.2字符串的抽象数据类型和基本操作 97
5.3字符串的操作的实现 98
5.3.1字符串的顺序存储结构 98
5.3.2字符串的堆存储结构 103
5.3.3字符串的块链存储结构 106
5.4模式匹配 107
5.4.1子串定位操作 107
5.4.2模式匹配的——种改进算法——KMP算法 108
5.5字符串操作应用 111
习题 117
第6章 二叉树 118
6.1树形结构概述 118
6.1.1树 118
6.1.2树形结构的种类 119
6.1.3树的相关术语 119
6.2二叉树的概念 120
6.2.1何谓二叉树 120
6.2.2满二叉树和完全二叉树 121
6.2.3二叉树的性质 121
6.2.4二叉树的抽象数据类型和基本操作 122
6.3二叉树的存储结构 123
6.3.1顺序存储结构 124
6.3.2链式存储结构 125
6.4二叉树的遍历 129
6.4.1前序遍历 129
6.4.2中序遍历 130
6.4.3后序遍历 130
6.4.4层序遍历 131
6.5线索二叉树 133
6.5.1何谓线索二叉树 133
6.5.2中序线索二叉树的构造和遍历 134
6.6二叉树的应用 137
6.7霍夫曼树及其应用 147
6.7.1何谓霍夫曼树 147
6.7.2霍夫曼树的应用 151
习题 153
第7章 树和森林 154
7.1树和森林的概念 154
7.1.1何谓树 154
7.1.2树和二叉树的三个主要差别 155
7.1.3何谓森林 155
7.2树的抽象数据类型和基本操作 155
7.3树和森林的遍历 156
7.3.1树的遍历 156
7.3.2森林的遍历 157
7.4树的存储结构 158
7.5树、森林与二叉树的转换 165
7.5.1树与二叉树的相互转换 166
7.5.2森林与二叉树的相互转换 166
7.6 K叉树 167
习题 168
第8章 图状结构 169
8.1图的定义与基本术语 169
8.1.1何谓图 170
8.1.2图的相关术语 170
8.2图的抽象数据类型和基本操作 173
8.3图的存储 174
8.3.1邻接矩阵 174
8.3.2邻接链表 179
8.3.3十字链表 186
8.3.4邻接多重表 188
8.4图的遍历 191
8.4.1深度优先搜索 191
8.4.2广度优先搜索 194
8.5最短路径问题 197
8.5.1最短路径问题的概念 197
8.5.2单源最短路径问题 198
8.5.3狄克斯特拉算法 198
8.6最小生成树 202
8.6.1最小生成树的概念 202
8.6.2最小生成树的性质 203
8.6.3构造最小生成树的算法 203
8.7 AOV网和拓扑排序 213
8.7.1 AOV网 213
8.7.2拓扑排序 214
习题 216
第9章 排序 218
9.1排序问题的基本概念 218
9.2简单排序算法 219
9.2.1直接插入排序 219
9.2.2冒泡排序 222
9.2.3直接选择排序 223
9.2.4简单排序算法的时间代价对比 224
9.3希尔排序 225
9.4基于分治的排序 227
9.4.1快速排序 229
9.4.2归并排序 233
9.5堆排序 237
9.6基数排序 241
9.6.1多关键字排序 241
9.6.2链式基数排序 242
9.7各种内排序算法的比较 244
9.8外排序 246
9.8.1文件的相关概念 247
9.8.2二路外排序 248
9.8.3多路归并——选择树 249
习题 252
第10章 查找 254
10.1查找的基本概念 254
10.2静态查找表 256
10.2.1顺序查找 256
10.2.2二分查找 259
10.2.3分块查找 262
10.3动态查找表 265
10.3.1二叉排序树 265
10.3.2平衡二叉排序树 271
10.3.3 B树和B+树 274
10.4哈希表查找 279
10.4.1何谓哈希表 279
10.4.2哈希函数的构造方法 280
10.4.3处理冲突的方法 283
10.4.4哈希表的查找 285
10.4.5哈希表的实现 285
10.4.6哈希表的查找分析 288
习题 289
参考文献 291