第1章 绪论 1
1.1什么是数据结构 2
1.1.1数据结构的定义 2
1.1.2逻辑结构 3
1.1.3存储结构 6
1.1.4数据运算 8
1.1.5数据类型和抽象数据类型 9
1.2算法及其描述 14
1.2.1什么是算法 14
1.2.2算法设计的目标 15
1.2.3算法描述 16
1.3算法分析 18
1.3.1算法分析概述 18
1.3.2算法时间性能分析 18
1.3.3算法空间性能分析 22
1.4数据结构＋算法＝程序 24
1.4.1程序和数据结构 24
1.4.2算法和程序 24
1.4.3算法和数据结构 24
1.4.4数据结构的发展 25
本章小结 26
练习题1 26
上机实验题1 28
验证性实验 28
设计性实验 29
第2章线性表 30
2.1线性表及其逻辑结构 31
2.1.1线性表的定义 31
2.1.2线性表的抽象数据类型描述 31
2.2线性表的顺序存储结构 33
2.2.1线性表的顺序存储结构——顺序表 33
2.2.2顺序表基本运算的实现 35
2.3线性表的链式存储结构 43
2.3.1线性表的链式存储结构——链表 43
2.3.2单链表 45
2.3.3双链表 54
2.3.4循环链表 59
2.4线性表的应用 61
2.5有序表 65
2.5.1有序表的抽象数据类型描述 65
2.5.2有序表的存储结构及其基本运算算法 66
2.5.3有序表的归并算法 66
2.5.4有序表的应用 69
本章小结 70
练习题2 71
上机实验题2 74
验证性实验 74
设计性实验 76
综合性实验 76
第3章 栈和队列 78
3.1栈 79
3.1.1栈的定义 79
3.1.2栈的顺序存储结构及其基本运算的实现 80
3.1.3栈的链式存储结构及其基本运算的实现 83
3.1.4栈的应用 87
3.2队列 97
3.2.1队列的定义 97
3.2.2队列的顺序存储结构及其基本运算的实现 98
3.2.3队列的链式存储结构及其基本运算的实现 103
3.2.4队列的应用举例 108
3.2.5双端队列 113
本章小结 115
练习题3 115
上机实验题3 117
验证性实验 117
设计性实验 119
综合性实验 119
第4章串 121
4.1串的基本概念 122
4.2串的存储结构 122
4.2.1串的顺序存储结构——顺序串 123
4.2.2串的链式存储结构——链串 128
4.3串的模式匹配 134
4.3.1 Brute-Force算法 134
4.3.2 KMP算法 136
本章小结 143
练习题4 143
上机实验题4 144
验证性实验 144
设计性实验 145
综合性实验 145
第5章 递归 146
5.1什么是递归 147
5.1.1递归的定义 147
5.1.2何时使用递归 148
5.1.3递归模型 149
5.1.4递归与数学归纳法 152
5.2栈和递归 152
5.2.1函数调用栈 152
5.2.2递归调用的实现 153
5.2.3递归到非递归的转换 155
5.3递归算法的设计 156
5.3.1递归算法设计的步骤 156
5.3.2基于递归数据结构的递归算法设计 158
5.3.3基于递归求解方法的递归算法设计 159
本章小结 161
练习题5 162
上机实验题5 162
验证性实验 162
设计性实验 163
综合性实验 163
第6章 数组和广义表 164
6.1数组 165
6.1.1数组的基本概念 165
6.1.2数组的存储结构 166
6.1.3特殊矩阵的压缩存储 168
6.2稀疏矩阵 171
6.2.1稀疏矩阵的三元组表示 172
6.2.2稀疏矩阵的十字链表表示 175
6.3广义表 177
6.3.1广义表的定义 177
6.3.2广义表的存储结构 179
6.3.3广义表的运算 180
本章小结 185
练习题6 186
上机实验题6 186
验证性实验 186
设计性实验 187
综合性实验 187
第7章 树和二叉树 189
7.1树的基本概念 190
7.1.1树的定义 190
7.1.2树的逻辑表示方法 190
7.1.3树的基本术语 191
7.1.4树的性质 192
7.1.5树的基本运算 194
7.1.6树的存储结构 195
7.2二叉树的概念和性质 198
7.2.1二叉树的定义 198
7.2.2二叉树的性质 199
7.2.3二叉树与树、森林之间的转换 200
7.3二叉树的存储结构 203
7.3.1二叉树的顺序存储结构 204
7.3.2二叉树的链式存储结构 205
7.4二叉树的基本运算及其实现 206
7.4.1二叉树的基本运算概述 206
7.4.2二叉树的基本运算算法实现 207
7.5二叉树的遍历 211
7.5.1二叉树遍历的概念 211
7.5.2先序、中序和后序遍历递归算法 212
7.5.3先序、中序和后序遍历非递归算法 218
7.5.4层次遍历算法 226
7.6二叉树的构造 228
7.7线索二叉树 233
7.7.1线索二叉树的概念 233
7.7.2线索化二叉树 233
7.7.3遍历线索化二叉树 236
7.8哈夫曼树 237
7.8.1哈夫曼树概述 237
7.8.2哈夫曼树的构造算法 238
7.8.3哈夫曼编码 239
7.9用并查集求解等价问题 241
7.9.1什么叫并查集 241
7.9.2并查集的算法实现 243
本章小结 245
练习题7 245
上机实验题7 247
验证性实验 247
设计性实验 248
综合性实验 249
第8章 图 252
8.1图的基本概念 253
8.1.1图的定义 253
8.1.2图的基本术语 254
8.2图的存储结构和基本运算算法 256
8.2.1邻接矩阵存储方法 256
8.2.2邻接表存储方法 258
8.2.3图基本运算算法设计 260
8.2.4其他存储方法 262
8.3图的遍历 264
8.3.1图的遍历的概念 264
8.3.2深度优先遍历 265
8.3.3广度优先遍历 266
8.3.4非连通图的遍历 267
8.3.5图遍历算法的应用 269
8.4生成树和最小生成树 279
8.4.1生成树的概念 279
8.4.2无向图的连通分量和生成树 280
8.4.3普里姆算法 281
8.4.4克鲁斯卡尔算法 285
8.5最短路径 290
8.5.1路径的概念 290
8.5.2从一个顶点到其余各顶点的最短路径 290
8.5.3每对顶点之间的最短路径 296
8.6拓扑排序 301
8.7 AOE网与关键路径 303
8.7.1相关概念 303
8.7.2求AOE网的关键活动 306
本章小结 307
练习题8 308
上机实验题8 310
验证性实验 310
设计性实验 311
综合性实验 313
第9章 查找 314
9.1查找的基本概念 315
9.2线性表的查找 316
9.2.1顺序查找 316
9.2.2折半查找 317
9.2.3索引存储结构和分块查找 321
9.3树表的查找 324
9.3.1二叉排序树 324
9.3.2平衡二叉树 333
9.3.3 B_树 339
9.3.4 B＋树 345
9.4哈希表的查找 346
9.4.1哈希表的基本概念 346
9.4.2哈希函数的构造方法 348
9.4.3哈希冲突的解决方法 350
9.4.4哈希表的运算算法 352
本章小结 360
练习题9 360
上机实验题9 362
验证性实验 362
设计性实验 363
综合性实验 364
第10章内排序 365
10.1排序的基本概念 366
10.2插入排序 368
10.2.1直接插入排序 368
10.2.2折半插入排序 370
10.2.3希尔排序 371
10.3交换排序 374
10.3.1冒泡排序 374
10.3.2快速排序 376
10.4选择排序 380
10.4.1简单选择排序 380
10.4.2堆排序 382
10.5归并排序 386
10.6基数排序 389
10.7各种内排序方法的比较和选择 392
本章小结 394
练习题10 394
上机实验题10 396
验证性实验 396
设计性实验 397
综合性实验 397
第11章 外排序 399
11.1外排序概述 400
11.2磁盘排序 400
11.2.1磁盘排序概述 400
11.2.2生成初始归并段 402
11.2.3多路平衡归并 404
11.2.4最佳归并树 407
11.3磁带排序 409
11.3.1多路平衡归并排序 409
11.3.2多阶段归并排序 411
本章小结 412
练习题11 412
上机实验题11 413
验证性实验 413
设计性实验 413
第12章 文件 414
12.1文件的基本概念 415
12.1.1什么是文件 415
12.1.2文件的逻辑结构及操作 415
12.1.3文件的存储结构 416
12.2顺序文件 416
12.3索引文件 417
12.3.1 ISAM文件 418
12.3.2 VSAM文件 421
12.4哈希文件 422
12.5多关键字文件 423
12.5.1多重表文件 423
12.5.2倒排文件 424
本章小结 425
练习题12 425
上机实验题12 425
验证性实验 425
设计性实验 426
第13章 采用面向对象的方法描述算法 427
13.1面向对象的概念 428
13.2用C＋＋描述面向对象的程序 429
13.2.1类 429
13.2.2类对象 432
13.2.3构造函数和析构函数 433
13.2.4模板类 436
13.3用C＋＋描述数据结构算法 438
13.3.1顺序表类模板 439
13.3.2链栈类模板 441
13.4使用STL设计数据结构算法 443
附录A实验报告格式 450
一、设计人员相关信息 450
二、程序设计相关信息 450
三、实验提交内容 450
附录B引用型参数和指针引用型参数的说明 451
附录C算法索引 453
附录D名词索引 457
附录E全国计算机专业数据结构2016年联考大纲 461
参考文献 463