实验报告模板.docx
《实验报告模板.docx》由会员分享，可在线阅读，更多相关《实验报告模板.docx（15页珍藏版）》请在冰点文库上搜索。
实验报告模板
实验报告模板填写说明
1、出现的红色部分请填写，并将红色文字删除
2、算法描述是以老师建议的算法简要描述的，如果和你的实现方案或者细节不一致的，请自行修改描述。
3、在实验结果中粘贴真实测试结果截图，不必是100分，这个不作为最终实验评分依据，如：
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称：
数据结构
班级：
计科132
实验日期：
3月23日
姓名：
姓名
学号：
ＸＸＸ
指导教师：
程欣宇
实验序号：
一
实验成绩：
一、实验名称
向量及其应用
二、实验目的及要求
1、熟悉向量（顺序表）的访问方式
2、掌握一种高效的向量排序方法
3、掌握有序向量的二分查找方法
三、实验环境
任何一种C++编写调试工具+清华数据结构OnlineJudge
四、实验内容
完成PA01中的范围查询这道题。
五、算法描述及实验步骤
向量是最基本的一种数据集合的存储方式，他的优点是可以根据元素的秩（也就是C语言中的数组下标）快速定位元素存储位置，完成元素访问。
PA01的范围查询这道题，要求我们统计一个向量内的整数元素值在范围[a,b]中的个数，并且要连续处理这样的查询m次。
对于单次查询来说，我们只要实现如下算法即可完成：
请填写你的代码片段
其算法复杂度为：
O（n），
而这样的查询如果连续查询m次，算法复杂度为O（nm），根据n和m的可能的大小，会导致程序整体的性能较低。
为此，我们可以考虑通过二分查找来优化程序性能，但是题目给出的数据不是有序向量，所以我们需要对向量先进行排序，排序算法的实现如下：
请填写你的代码片段
拿到有序向量，我们再应对m次查询，每次查询可以用二分查找定位查询区间边界a和b的位置，实现如下：
请填写你的代码片段
综上所述，我们可以得到一个高效的，整体算法复杂度为请填写你的分析结论的范围查询算法。
六、调试过程及实验结果
6.1请选取你犯的一、两个典型错误进行简单分析总结
6.2请粘贴你在清华OJ上的测试结果（每个人必须粘贴自己不同的结果）
七、总结
对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
（30-50字即可）
八、附录
其它需要附加说明的内容，没有就不填
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称：
数据结构
班级：
计科132
实验日期：
4月6日
姓名：
姓名
学号：
ＸＸＸ
指导教师：
程欣宇
实验序号：
二
实验成绩：
一、实验名称
栈及其应用
二、实验目的及要求
1、熟悉栈的原理和实现方式；
2、掌握利用栈解决列车调度问题
三、实验环境
任何一种C++编写调试工具+清华数据结构OnlineJudge
四、实验内容
完成PA02的列车调度这道题
五、算法描述及实验步骤
列车调度问题是求解一个已知的顺序序列A，是否能够通过一个容量最大为m的栈S，调度为希望的序列B，如图：
算法框架如下：
初始化栈S
用下标ｊ指向Ｂ中第ｊ个元素，初始化ｊ＝１
一次对所有的列车车厢ｉ，做如下处理：
如果栈的元素数量已经达到ｍ，停止循环
车厢ｉ入栈，记录操作
如果栈顶元素==B[j]，则
元素出栈，记录操作，且j++，且继续循环本判断
如果循环完成，栈非空
输出No
否则
输出记录的入栈出栈操作顺序
实验步骤：
1、阅读PA02的列车调度这道题，完成数据加载；
2、设计栈混洗算法求解完成列车调度问题。
3、在清华OJ上测试程序的正确性和效率。
六、调试过程及实验结果
6.1请选取你犯的一、两个典型错误进行简单分析总结
6.2请粘贴你在清华OJ上的测试结果（每个人必须粘贴自己不同的结果）
七、总结
对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
（30-50字即可）
八、附录
源程序（核心代码，可以不含输入输出）清单或使用说明书
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称：
数据结构
班级：
计科132
实验日期：
4月13日
姓名：
姓名
学号：
ＸＸＸ
指导教师：
程欣宇
实验序号：
三
实验成绩：
一、实验名称
队列及其应用
二、实验目的及要求
1、熟悉队列的原理和队列的一种实现方式（顺序队列或者链式队列）；
2、掌握使用队列解决求队列中的极大值问题；
三、实验环境
任何一种C++编写调试工具+清华数据结构OnlineJudge
四、实验内容
完成PA02的隧道Tuenl这道题
五、算法描述及实验步骤
使用队列进行模拟隧道车辆进出：
初始化队列；
while（有数据要输入）
{
如果有车辆进隧道，则
数据入队，更新最大值
如果有车辆出队，则
数据出队，更新最大值
如果是查询最大值，则
如果有可用的最大值，则
直接输出
否则
重新统计最大值再输出
}
提升算法效率的要点在于何时更新最大值，建议采用懒更新策略，即某些原因导致最大值失效后，不用太积极更新最大值，而是等待真正有查询了再更新。
实验步骤
1、阅读PA02的隧道Tuenl这道题；
2、设计一个队列，能够加载数据，并且输出队列当前最大元素。
3、在清华OJ上测试程序的正确性和效率。
4、优化最大值的求解效率。
六、调试过程及实验结果
详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结
对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
八、附录
源程序（核心代码）清单或使用说明书，可另附纸
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称：
数据结构
班级：
计科132
实验日期：
4月20日
姓名：
姓名
学号：
ＸＸＸ
指导教师：
程欣宇
实验序号：
四
实验成绩：
一、实验名称
重构二叉树
二、实验目的及要求
1、加深对二叉树的各种遍历算法的理解
2、自己设计并掌握一种根据遍历序列重构二叉树的算法
三、实验环境
任何一种C++编写调试工具+清华数据结构OnlineJudge
四、实验内容
完成PA02的真二叉树重构
五、算法描述及实验步骤
真二叉树是每个非叶子结点一定具有左右孩子的二叉树，它的先序遍历顺序和后序遍历顺序如下所示
先序：
PL……R……..
后序：
…..L……….RP
先序遍历的前面两个元素一定是根结点P及其左孩子L
后序遍历的最后两个元素一定是根结点P及其左孩子R
由此，拿到先序序列和后序序列，我们就一定可以拿到其跟结点及其左右孩子的元素值。
算法的关键是：
我们需要递归的建立左子树和右子树。
如上所示，我们如果拿到左子树的先序遍历顺序L……和左子树的后序遍历顺序……L，即可递归的建立左子树，另外右子树同理。
要拿到左子树的先序遍历顺序，只需要求出R在先序遍历中的位置，同理，求出L在后序遍历中的位置，也可以拿到其后序序列。
实验步骤
1、阅读PA02的真二叉树重构这道题；
2、根据以上算法设计思路，给出自己的设计和实现。
3、在清华OJ上测试程序的正确性和效率。
4、优化算法效率，建议改遍历式的查找为按内容的快速查找，请自行思考然后实现这步优化。
六、调试过程及实验结果
详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结
对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
八、附录
源程序（核心代码）清单或使用说明书，可另附纸
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称：
数据结构
班级：
计科132
实验日期：
5月4日
姓名：
姓名
学号：
ＸＸＸ
指导教师：
程欣宇
实验序号：
五
实验成绩：
一、实验名称
图的实现及其应用
二、实验目的及要求
1、加深对图的各种遍历算法的理解
2、自己设计并掌握一种求最长遍历路径的算法
三、实验环境
任何一种C++编写调试工具+清华数据结构OnlineJudge
四、实验内容
完成PA03的旅行商（TSP）
五、算法描述及实验步骤
题目中的旅行商TSP问题需要找图中一条不重复经过任意城市（顶点）的最长路径。
你可以从图的深度/广度优先遍历、图的拓扑排序、或者是类似求图的最最短路径的方法中选一个算法，来改造，以满足此题目的要求。
因为n非常大，如果采用邻接矩阵，将会花费O（n^2）的存储空间，因此建议的图的存储结构，采用邻接表方式。
实验步骤
1、阅读PA03的TSP这道题；
2、给出图的邻接表的实现；
3、将题目的图的数据读入，存入邻接表；（注意，题目的输入示例忘换行了，应该每两个数换一行）
4、利用邻接表和你选用的算法，实现求图中的最长路径。
5、自测并提交测试，排除错误。
六、调试过程及实验结果
详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结
对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
八、附录
源程序（核心代码）清单或使用说明书，可另附纸
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称：
数据结构
班级：
计科132
实验日期：
5月18日
姓名：
姓名
学号：
ＸＸＸ
指导教师：
程欣宇
实验序号：
六
实验成绩：
一、实验名称
散列表的实现及其应用
二、实验目的及要求
1、加深对散列的理解
2、学会解决散列值冲突的问题
3、自己设计并掌握一种高效剔除重复字符串的方法
三、实验环境
任何一种C++编写调试工具+清华数据结构OnlineJudge
四、实验内容
完成PA03的重名剔除问题（Deduplicate）
五、算法描述及实验步骤
散列表是一种循内容访问元素的方法。
要高效的利用散列表，第一要设计合理的散列函数，使得散列冲突尽可能的少，内存空间也尽可能的少占用；第二要设计合理的散列冲突解决方案。
对于本题来说，我们需要对任意长度的字符串S设计一个散列函数hash（S）。
算法流程大致如下：
准备和初始化散列表Ｈ，散列表的每个元素能够存储一个字符串及其出现次数。
一次读入每一个字符串S
查看Ｓ是否已经存储在Ｈ中，如果已经在
则将Ｓ出现的次数加１，如果出现的次数变为２，说明出现重复了
否则
将Ｓ放入Ｈ中，并置出现次数为１
实验步骤
1、阅读PA03的重名剔除这道题；
2、设计出适合题目数据的散列函数及其冲突解决办法。
3、根据上述算法流程，完成算法，自测。
4、提交到ＯＪ测试，如果存在较多超时，建议优化散列函数，具体办法是尽量用足内存，减少冲突，提高一次命中率。
六、调试过程及实验结果
详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结
对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
八、附录
源程序（核心代码）清单或使用说明书，可另附纸
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称：
数据结构
班级：
计科132
实验日期：
6月1日
姓名：
姓名
学号：
ＸＸＸ
指导教师：
程欣宇
实验序号：
七
实验成绩：
一、实验名称
优先级队列及其应用
二、实验目的及要求
1、加深优先级队列的理解
2、掌握优先级队列的实现方法
3、学会利用优先级队列解决PA04的任务调度问题
三、实验环境
任何一种C++编写调试工具+清华数据结构OnlineJudge
四、实验内容
完成PA04的任务调度问题（Schedule）
五、算法描述及实验步骤
优先级队列是一种可以依据队列元素的优先级进行插队的特殊队列，能够很好的模拟不需要完全遵守先进先出规则的问题。
优先队列的最高效的实现方式是采用小顶堆，其性质是：
1、任意一个节点均比其子树所以节点元素值更少；
2、按层次遍历顺序访问到的元素k，其左孩子（如果存在）的访问顺序一定是2k，右孩子（如果存在）的顺序一定是2k+1。
3、从小顶堆中取出最小元素后，可以在log（n）的时间内恢复为小顶堆。
4、任意一个元素，可以在log（n）的时间内插入小顶堆。
最小堆物理结构最小堆逻辑结构
在本题中，队列元素出队后，还会再入队，我们可以得出算法流程大致如下：
初始化有些队列PQ，队列元素为字符串及其优先级
读入参数n,m
循环n次，读取每个元素，插入队列PQ，花费O（nlogn）建堆
循环m次
每次输出堆顶元素e
将e乘以2以后再次入队
实验步骤
1、阅读PA04的任务调度这道题；
2、采用小顶堆实现优先队列，建议实现为模板类；
3、根据上述算法流程，完成算法，自测。
4、提交到ＯＪ测试，如果存在较多超时，建议想办法优化字符串的存储，避免字符串跟随堆的调整而频繁移动。
六、调试过程及实验结果
详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结
对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
八、附录
源程序（核心代码）清单或使用说明书，可另附纸
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称：
数据结构
班级：
计科132
实验日期：
6月15日
姓名：
姓名
学号：
ＸＸＸ
指导教师：
程欣宇
实验序号：
八
实验成绩：
一、实验名称
串匹配算法应用
二、实验目的及要求
1、理解和对比常用串实验算法
2、学会利用高效串匹配算法解决PA04的循环位移检查问题
三、实验环境
任何一种C++编写调试工具+清华数据结构OnlineJudge
四、实验内容
设计数据结构和算法解决完成PA04的循环位移（Cycle）问题
五、算法描述及实验步骤
字符串匹配算法是在待搜索文本T中，搜索模板串P是否在T中间出现。
设计高效匹配算法的关键在于在搜索匹配以前，先花较小的代价分析模式串P，使得在滑动匹配过程中，可以尽量快速地、大范围的跳跃式的匹配，同时要保证这种跳跃不会导致漏配。
针对题目中提到的循环位移问题，可以设计很多算法解决，下面给出两种，假设题目中一个串是A、另外一个是B。
算法一：
将A串复杂一份拼接在A串之后，搜索匹配B串是否在A串中出现过。
算法二：
假设A串的长度是n，在每个可能的切分点i∈[0,n），把A划分为两左右部分AL、AR。
查找AR是否为B的前缀且AL是B的后缀，如果是，则输出YES，否则输出NO。
实验步骤
1、阅读PA04的循环位移这道题；
2、选用某种模式匹配算法，
3、根据上述算法流程，完成算法，自测。
4、提交到ＯＪ测试，如果存在较多超时，建议想办法选取各种高效的字符串匹配算法。
六、调试过程及实验结果
详细记录程序在调试过程中出现的问题及解决方法。
记录程序执行的结果。
七、总结
对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。
八、附录
源程序（核心代码）清单或使用说明书，可另附纸
升级会员 