第1章 抽象数据类型 1
1.1 实验目的 1
1.2 实验内容及要求 1
1.2.1 实验内容 1
1.2.2 实验要求 1
1.3 知识点提示 2
1.3.1 抽象类型定义 2
1.3.2 复数 2
1.3.3 抽象数据类型的复数例 2
1.3.4 结构体类型定义 3
1.3.5 程序的组织 4
1.4 实验步骤 4
1.5 实验程序参考 5
1.5.1 Complex.h 5
1.5.2 Complex.cpp 6
1.5.3 main.cpp 8
1.5.4 运行截图 9
1.6 常见问题及思考 10
1.6.1 常见问题及解答 10
1.6.2 思考 10
1.7 选做：三元组 11
第2章 线性表 12
2.1 实验目的 12
2.2 实验内容及要求 12
2.2.1 实验内容 12
2.2.2 实验要求 12
2.3 知识点提示 13
2.3.1 线性表的基本定义 13
2.3.2 线性表的顺序存储结构 13
2.3.3 线性表顺序表示的插入操作 14
2.3.4 线性表顺序表示的删除操作 15
2.3.5 线性表的链式存储结构 15
2.3.6 线性链表的插入操作 16
2.4 实验步骤 17
2.5 实验程序参考 18
2.5.1 Common.h 18
2.5.2 LinkList.h 18
2.5.3 main.cpp 22
2.5.4 运行截图 24
2.6 常见问题及思考 25
2.7 选做：线性表的逆置 26
第3章 栈及其应用 27
3.1 实验目的 27
3.2 实验内容及要求 27
3.2.1 实验内容 27
3.2.2 实验要求 27
3.3 知识点提示 28
3.3.1 顺序栈的结构定义 28
3.3.2 链栈的结构定义 28
3.3.3 栈的基本操作 29
3.4 实验步骤 29
3.5 实验程序参考 30
3.5.1 SeqStack.h 30
3.5.2 main.cpp 32
3.5.3 结果截图 33
3.6 常见问题及思考 33
3.7 选做：迷宫问题 34
3.7.1 问题描述 34
3.7.2 参考程序Stack.h 34
3.7.3 参考程序Main.cpp 36
第4章 队列及其应用 40
4.1 实验目的 40
4.2 实验内容及要求 40
4.2.1 实验内容 40
4.2.2 实验要求 40
4.3 知识点提示 41
4.3.1 队列的基本概念与操作 41
4.3.2 顺序队列 41
4.3.3 循环队列 42
4.3.4 改进的凯撒加密法 44
4.4 实验步骤 44
4.5 实验程序参考 44
4.5.1 CircularQueue.h 44
4.5.2 main.cpp 46
4.5.3 结果截图 49
4.6 常见问题及思考 49
第5章 串的模式匹配 50
5.1 实验目的 50
5.2 实验内容及要求 50
5.2.1 实验内容 50
5.2.2 实验要求 50
5.3 知识点提示 51
5.3.1 ADT SString 51
5.3.2 字符串的存储结构 51
5.3.3 朴素匹配算法 52
5.3.4 KMP算法 53
5.4 实验步骤 54
5.5 实验程序参考 55
5.5.1 SString.cpp 55
5.5.2 main.cpp 57
5.5.3 结果截图 57
5.6 选做：两种子串匹配算法的性能对比 58
第6章 二叉树的建立、遍历及常用运算 59
6.1 实验目的 59
6.2 实验内容及要求 59
6.2.1 实验内容 59
6.2.2 实验要求 60
6.3 知识点提示 60
6.3.1 ADT Tree 60
6.3.2 二叉树的存储结构 61
6.3.3 二叉树的遍历 62
6.3.4 二叉树遍历的非递归算法（中序） 63
6.3.5 二叉树构造的递归算法（扩展先序） 64
6.4 实验步骤 64
6.5 实验程序参考 65
6.5.1 BiTree.cpp 65
6.5.2 main.cpp 70
6.5.3 运行截图 71
6.6 常见问题及思考 72
6.7 选做：哈夫曼树与哈夫曼编码 72
第7章 图及其应用 73
7.1 实验目的 73
7.2 实验内容及要求 73
7.2.1 实验内容 73
7.2.2 实验要求 73
7.3 知识点提示 74
7.3.1 图的抽象数据类型 74
7.3.2 邻接矩阵表示法 74
7.3.3 邻接表表示法 75
7.3.4 图的深度优先遍历 76
7.3.5 图的广度优先遍历 77
7.3.6 最短路径算法 78
7.4 实验步骤 79
7.5 实验程序参考 80
7.5.1 ArcInfoType.h 81
7.5.2 VertexInfoType.h 81
7.5.3 Queue.h 82
7.5.4 ALGraph.h 84
7.5.5 Main.cpp 93
7.5.6 输入文件 94
7.5.7 运行截图 95
7.6 常见问题及思考 95
7.7 实验扩展 96
第8章 查找与排序 97
8.1 实验目的 97
8.2 实验内容及要求 97
8.2.1 实验内容 97
8.2.2 实验要求 98
8.3 知识点提示 99
8.3.1 直接插入排序 99
8.3.2 快速排序 100
8.3.3 堆排序 101
8.3.4 顺序查找 102
8.3.5 二分查找 103
8.4 实验步骤 104
8.5 实验程序参考 105
8.5.1 SortApp.cpp 105
8.5.2 排序运行截图 109
8.5.3 SearchApp.cpp 110
8.5.4 查找运行截图 113
8.6 常见问题及思考 114
8.7 实验扩展 114
第9章 综合实例——内存分配模拟系统 115
9.1 课程设计目的 115
9.2 课程设计内容 115
9.2.1 背景介绍 115
9.2.2 内存分配算法 116
9.2.3 策略模式 116
9.3 课程设计过程 117
9.3.1 系统的总体设计 117
9.3.2 系统的类定义 117
9.3.3 首次适应算法 119
9.3.4 最佳适应算法 120
9.3.5 最差适应算法 121
9.4 实验程序参考 122
9.4.1 Job与JobList类 122
9.4.2 EmptyBlock类 124
9.4.3 EmptyBlockManager类 125
9.4.4 AllocateStrategy类 128
9.4.5 策略实现类 129
9.4.6 主程序文件——MemoryAllocationSimulator.cpp 133
9.5 系统运行结果截图 136
9.6 实验扩展 138
附录一：实验报告规范 140
附录二：VS2015简单调试 142
附录三：数据生成软件 151
附录四：排序结果检查软件 155
参考文献 159