第1章 数据结构概述 1
1.1数据结构研究的内容 1
1.2基本概念和术语 3
1.3抽象数据类型 5
1.4算法分析 7
1.4.1算法及性质 7
1.4.2算法度量及分析 8
1.5习题 12
1.6实验 14
第2章 线性表 16
2.1线性表的定义及其操作 16
2.1.1线性表的定义 16
2.1.2线性表的抽象数据类型 17
2.2顺序表 18
2.2.1顺序表的定义 18
2.2.2顺序表的基本操作 19
2.3链表 27
2.3.1单链表 27
2.3.2循环链表 37
2.3.3双向链表 38
2.3.4静态链表 42
2.4顺序表与链表的比较 44
2.5综合实例——文具店的货品管理 45
2.6习题 51
2.7实验 54
第3章 栈和队列 56
3.1栈的定义及其操作 56
3.1.1栈的定义 56
3.1.2栈的抽象数据类型 58
3.2顺序栈 58
3.2.1顺序栈的定义 58
3.2.2顺序栈的基本操作 59
3.3链栈 63
3.3.1链栈的定义 63
3.3.2链栈的基本操作 64
3.4队列的定义及其操作 68
3.4.1队列的定义 68
3.4.2队列的抽象数据类型 69
3.5顺序队列 70
3.5.1顺序队列的定义 70
3.5.2顺序队列的基本操作 73
3.6链队列 78
3.6.1链队列的定义 78
3.6.2链队列的基本操作 79
3.7栈与队列的应用 84
3.7.1数制转换 84
3.7.2表达式计算 86
3.7.3输入输出缓冲区 89
3.8综合实例——停车场管理 89
3.9习题 94
3.10实验 97
第4章 串 100
4.1串的基本概念及其操作 100
4.1.1串的基本概念 100
4.1.2串的抽象数据类型 101
4.2串的顺序存储结构 101
4.2.1串的定长顺序存储表示 102
4.2.2串的堆存储表示 107
4.3串的链式存储结构 110
4.4串的模式匹配 116
4.4.1Brute-Force算法 116
4.4.2KMP算法 118
4.5综合实例——简易文本编辑软件 123
4.6习题 128
4.7实验 129
第5章 数组和广义表 131
5.1数组的基本概念及其操作 131
5.1.1数组的基本概念 131
5.1.2数组的抽象数据类型 132
5.2数组的顺序存储 132
5.3特殊矩阵及其压缩存储 133
5.3.1对称矩阵与三角矩阵 133
5.3.2对角矩阵 135
5.4稀疏矩阵 136
5.4.1三元组顺序表表示 136
5.4.2十字链表表示 142
5.5广义表 147
5.5.1广义表的基本概念 147
5.5.2广义表的抽象数据类型 149
5.5.3广义表的存储结构 149
5.6综合实例——n阶魔方 156
5.7习题 159
5.8实验 162
第6章 树和二叉树 163
6.1树 163
6.1.1树的定义 163
6.1.2树的表示方法 165
6.1.3树的抽象数据类型 165
6.1.4树的存储结构 166
6.2二叉树 168
6.2.1二叉树的定义 169
6.2.2二叉树的性质 172
6.2.3二叉树的存储结构 174
6.2.4二叉树的遍历 179
6.3线索二叉树 186
6.3.1线索二叉树的定义 186
6.3.2线索二叉树的操作 187
6.4森林 192
6.4.1树、森林与二叉树的转换 192
6.4.2树和森林的遍历 195
6.5哈夫曼树及其应用 196
6.5.1哈夫曼树 196
6.5.2哈夫曼编码 198
6.6综合实例——高校社团管理 202
6.7习题 207
6.8实验 211
第7章 图 212
7.1图的基本概念 212
7.1.1图的定义 212
7.1.2图的抽象数据类型 215
7.2图的存储结构 216
7.2.1邻接矩阵 216
7.2.2邻接表 221
7.2.3十字链表 225
7.2.4邻接多重表 225
7.3图的遍历 226
7.3.1深度优先搜索 226
7.3.2广度优先搜索 228
7.4最小生成树 231
7.4.1普里姆算法 232
7.4.2克鲁斯卡尔算法 234
7.5最短路径 235
7.5.1从某个顶点到其余顶点的最短路径 235
7.5.2每对顶点之间的最短路径 237
7.6拓扑排序和关键路径 239
7.6.1拓扑排序 239
7.6.2关键路径 240
7.7综合实例——故宫导游咨询 243
7.8习题 248
7.9实验 251
第8章 查找 252
8.1查找的基本概念 252
8.2顺序查找 253
8.3折半查找 254
8.4分块查找 255
8.5二叉排序树 256
8.5.1二叉排序树的定义 256
8.5.2二叉排序树的基本操作 257
8.6B-树 263
8.6.1B-树的定义 263
8.6.2B-树的基本操作 264
8.7哈希表 269
8.7.1哈希表的定义 269
8.7.2哈希函数的构造方法 270
8.7.3处理冲突的方法 272
8.7.4哈希表的基本操作 274
8.8综合实例——十大流行歌手排行榜 278
8.9习题 284
8.10实验 287
第9章 排序 288
9.1排序的基本概念 288
9.2插入排序 289
9.2.1直接插入排序 289
9.2.2折半插入排序 291
9.2.3希尔排序 292
9.3交换排序 294
9.3.1冒泡排序 294
9.3.2快速排序 295
9.4选择排序 298
9.4.1直接选择排序 299
9.4.2堆排序 300
9.5归并排序 306
9.6基数排序 308
9.7各种排序方法的比较 310
9.8习题 311
9.9实验 314
附录A综合测试 315
附录B部分习题答案 319
参考文献 334