![实验数组的表示及其应用教案_第1页](http://file3.renrendoc.com/fileroot_temp3/2022-3/4/c4694bfb-ffd5-44f1-addd-cfe5681035b9/c4694bfb-ffd5-44f1-addd-cfe5681035b91.gif)
![实验数组的表示及其应用教案_第2页](http://file3.renrendoc.com/fileroot_temp3/2022-3/4/c4694bfb-ffd5-44f1-addd-cfe5681035b9/c4694bfb-ffd5-44f1-addd-cfe5681035b92.gif)
![实验数组的表示及其应用教案_第3页](http://file3.renrendoc.com/fileroot_temp3/2022-3/4/c4694bfb-ffd5-44f1-addd-cfe5681035b9/c4694bfb-ffd5-44f1-addd-cfe5681035b93.gif)
![实验数组的表示及其应用教案_第4页](http://file3.renrendoc.com/fileroot_temp3/2022-3/4/c4694bfb-ffd5-44f1-addd-cfe5681035b9/c4694bfb-ffd5-44f1-addd-cfe5681035b94.gif)
![实验数组的表示及其应用教案_第5页](http://file3.renrendoc.com/fileroot_temp3/2022-3/4/c4694bfb-ffd5-44f1-addd-cfe5681035b9/c4694bfb-ffd5-44f1-addd-cfe5681035b95.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、云南大学软件学院 数据结构实验报告 (本实验项目方案受“教育部人才培养模式创新实验区(X3108005)”项目资助) 实验难度: A B C 序号学号姓名成绩1234指导教师 (签名)学期:2014 秋季学期 任课教师: 张德海 王常吉 实验题目: 数组的表示及其应用 小 组 长: 联系电话: 电子邮件: 完成提交时间:2014年 11月 17日云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号:20131120267 姓名:蔡智霖 本人承担角色:代码设计,算法分析,运行监测,填写报告 评分项目评分指标分值得分实验构思(10%)1. 实验目的明确52. 实验内容理解透彻、对实验
2、所涉及到的知识点分析到位5实验设计(15%)1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整,数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现(25%)1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常,测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写(10%)1. 内容详实无缺漏,文字流畅、图表清楚52. 实验结果分析客观、详细,实验体会真实可信,对原实验方案的改进和对实验内容的发散性思考5个人工作量(30%)1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作(10%)1.
3、有一定用户群52. 应用前景分析5综合得分: (满分100分)指导教师: 年 月 日云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号:20131120272 姓名:邓飞武 本人承担角色:结果检验,实验构思,调试代码 评分项目评分指标分值得分实验构思(10%)1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计(15%)1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整,数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现(25%)1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常
4、,测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写(10%)1. 内容详实无缺漏,文字流畅、图表清楚52. 实验结果分析客观、详细,实验体会真实可信,对原实验方案的改进和对实验内容的发散性思考5个人工作量(30%)1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作(10%)1. 有一定用户群52. 应用前景分析5综合得分: (满分100分)指导教师: 年 月 日云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号:20131120247 姓名:温岩松 本人承担角色:错误总结,结果验证,调试代码 评分项目评分指标分值得分实验构思(10%
5、)1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计(15%)1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整,数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现(25%)1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常,测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写(10%)1. 内容详实无缺漏,文字流畅、图表清楚52. 实验结果分析客观、详细,实验体会真实可信,对原实验方案的改进和对实验内容的发散性思考5个人工作量(30%)1. 个人完成工作量152. 个人技术
6、水平103. 团队合作精神5实验运作(10%)1. 有一定用户群52. 应用前景分析5综合得分: (满分100分)指导教师: 年 月 日云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号:20131120258 姓名:程哲 本人承担角色:调试代码,错误总结,实验分析 评分项目评分指标分值得分实验构思(10%)1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计(15%)1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整,数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现(25%)1. 代码编写
7、规范、风格统一、注释清楚易读 52. 程序运行正常,测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写(10%)1. 内容详实无缺漏,文字流畅、图表清楚52. 实验结果分析客观、详细,实验体会真实可信,对原实验方案的改进和对实验内容的发散性思考5个人工作量(30%)1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作(10%)1. 有一定用户群52. 应用前景分析5综合得分: (满分100分)指导教师: 年 月 日(下面的内容由学生填写,格式统一为,字体: 楷体, 行距: 固定行距18,字号: 小四,个人报告按下面每一项的百分比打分。难度A满分70分,
8、难度B满分90分)一、【实验构思(Conceive)】(10%)(本部分应包括:描述实验实现的基本思路,包括所用到的离散数学、工程数学、程序设计、算法等相关知识)程序设计:利用数组来实现迷宫的设计数学知识:运用到了相关的矩阵知识,以及二维数组的知识二、【实验设计(Design)】(20%)(本部分应包括:抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明,主程序模块与各子程序模块间的调用关系)数据部分包括Point(迷宫中点位置的存储结构),而操作包括CreatMaze(获取迷宫),FindMaze(寻找迷宫maze中从(,)到(m,n)的路径),PrintPath(输出迷宫的路径
9、)具体为:1. Pointclass Point /迷宫中点位置的存储结构public:int x; /x代表当前位置的行坐标int y; /y代表当前位置的列坐标int dir; /0:无效,1:下,2:右,3:上,4:左;2. CreatMaze定义二维指针存取迷宫输入迷宫的长和宽输入迷宫的内容,0代表可通,1代表不通返回存贮迷宫的二维指针maze3. FindMaze将入口位置入栈获取栈顶元素如果有新位置入栈,则把上一个探索的位置存入栈p探索当前位置的相邻位置判断新位置是否可达4. PrintPath定义一个栈,按从入口到出口存取路径取栈p的顶点元素,即第一个位置第一个位置入栈t栈p非空
10、,则反复转移获取下一个位置把新位置入栈输出路径,包括行坐标,列坐标,下一个位置方向三、【实现描述(Implement)】(30%)(本部分应包括:抽象数据类型具体实现的函数原型说明、 关键操作实现的伪码算法、 函数设计、函数间的调用关系,关键的程序流程图等,给出关键算法的时间复杂度分析。)1.抽象数据类型具体实现的函数原型说明:class Point /迷宫中点位置的存储结构public:int x; /x代表当前位置的行坐标int y; /y代表当前位置的列坐标int dir; /0:无效,1:下,2:右,3:上,4:左;2.子程序算法简介int* CreatMaze(int &m,int
11、&n); /获取迷宫bool FindMaze(int *maze,int m,int n); /寻找迷宫maze中从(,)到(m,n)的路径void PrintPath(Stack p); /输出迷宫的路径四、【测试结果(Testing)】(10%)(本部分应包括:对实验的测试结果,应具体列出每次测试所输入的数据以及输出的数据,并对测试结果进行分析总结)1.程序功能选择界面:2.选择后:3.进行数据输入后的结果:4.再次输入数据:四、【实验总结】(10%)(本部分应包括:自己在实验中完成的任务,注意组内的任意一位同学都必须独立完成至少一项接口的实现;对所完成实验的经验总结、心得)蔡智霖:迷宫
12、求解的算法并没有一开始想的那么难,但也需要一步一步小心的把它完成,才能避免在小细节上出错,同时这次的实验堆我们在矩阵上的了解有一定考察。在本次试验中,也运用到了栈来进行迷宫的存储。总之,在本次试验中,我们学到了很多,多今后在矩阵的运用有了一个全新的了解。邓飞武:在做实验前,一定要将课本上的知识吃透,因为这是做实验的基础,否则,在老师讲解时就会听不懂,这将使你在做实验时的难度加大,浪费做实验的宝贵时间.温岩松:通过这次实验,使我学到了不少实用的知识,更重要的是,做实验的过程,思考问题的方法,这与做其他的实验是通用的,真正使我们受益匪浅.程哲:在这次实验中,我学到很多东西,加强了我的动手能力,并且
13、培养了我的独立思考能力。特别是在做实验报告时,因为在做数据处理时出现很多问题,如果不解决的话,将会很难的继续下去。五、【项目运作描述(Operate)】(10%)(本部分应包括:项目的成本效益分析,应用效果等的分析。)本程序可以实现基本的迷宫求解功能,可以根据使用者所输入的迷宫来判断是否有同路,以及同路路径。因为本程序并不具备可视化的运行界面,因此本程序并不具备较高的成本价值,但同时也因为本程序制作成本并不高,因此其效益相对来说尚可。六、【代码】(10%)(本部分应包括:完整的代码及充分的注释。 注意纸质的实验报告无需包括此部分。格式统一为,字体: Georgia , 行距: 固定行距12,字
14、号: 小五)#include StdAfx.h#includeusing namespace std;class Point /迷宫中点位置的存储结构public:int x; /x代表当前位置的行坐标int y; /y代表当前位置的列坐标int dir; /0:无效,1:下,2:右,3:上,4:左;class LinkNode /链表结点的存储结构class Stack;public:Point data;LinkNode *next;class Stackprivate:LinkNode *top; /指向第一个结点的栈顶指针public:Stack(); /构造函数,置空栈Stack()
15、; /析构函数void Push(Point e); /把元素data压入栈中Point Pop(); /使栈顶元素出栈Point GetPop(); /取出栈顶元素void Clear(); /把栈清空bool empty(); /判断栈是否为空,如果为空则返回,否则返回;Stack:Stack() /构造函数,置空栈top=NULL;Stack:Stack() /析构函数void Stack:Push(Point e) /把元素x压入栈中LinkNode *P = new LinkNode;/ P=new LinkNode;P-data=e;P-next=top;top=P;Point S
16、tack:Pop() /使栈顶元素出栈Point Temp;LinkNode *P;P=top;top=top-next;Temp=P-data;delete P;return Temp;Point Stack:GetPop() /取出栈顶元素的值return top-data;void Stack:Clear() /把栈清空top=NULL;bool Stack:empty() /判断栈是否为空,如果为空则返回,否则返回if(top=NULL) return 1;else return 0;/函数说明int* CreatMaze(int &m,int &n); /获取迷宫bool FindM
17、aze(int *maze,int m,int n); /寻找迷宫maze中从(,)到(m,n)的路径void PrintPath(Stack p); /输出迷宫的路径 void main()int back = 1;while(back)int m=0,n=0; /定义迷宫的长和宽int *maze; /定义二维指针存取迷宫int flag;cout*欢迎使用迷宫求解系统*;coutn 菜单:nt1.输入迷宫并探索路径nt;cout2.退出n*nendl;cout请选择:flag;for(;flag=0)if(flag=1)maze=CreatMaze(m,n); /调用CreatMaze(
18、int &m,int &n)函数,得到迷宫if(FindMaze(maze,m,n) /调用FindMaze(int *maze,int m,int n)函数获取路径;cout结论:迷宫路径探索成功!n;else cout结论:迷宫路径不存在!nn;continue;if(flag=2) back = 0;break;if(flag3) coutError!n;continue;int* CreatMaze(int &m,int &n)/创建迷宫,返回存取迷宫的二维指针int *maze; /定义二维指针存取迷宫/int i=0,j=0;coutab; /输入迷宫的长和宽cout请输入迷宫内容
19、(0为通路,1为堵塞):n;m=a;n=b; /m,n分别代表迷宫的行数和列数maze=new int *m+2; /申请长度等于行数加的二级指针for(int i=0;im+2;i+) /申请每个二维指针的空间mazei=new intn+2;for( int i=1;i=m;i+) /输入迷宫的内容,0代表可通,1代表不通for(int j=1;jmazeij;for( int i=0;im+2;i+)/将迷宫的外围全部置,这样输入的时候是从(1,1)开始mazei0=mazein+1=1;for( int i=0;in+2;i+)maze0i=mazem+1i=1;cout您输入的迷宫如
20、下:nt;for( int i = 1 ; i = m;i+)for(int j =1;j = n;j+)if(mazeij= 0)cout;if(mazeij= 1) cout;if(j = n)coutendl;coutt;return maze; /返回存贮迷宫的二维指针maze;bool FindMaze(int *maze,int m,int n)/寻找迷宫maze中从(,)到(m,n)的路径/到则返回true,否则返回falseStack p,q; /定义栈p存储路径,q存探索迷宫的过程Point Temp1,Temp2; int x,y,z;Temp1.x=1;Temp1.y=1
21、;q.Push(Temp1); /将入口位置入栈p.Push(Temp1);maze11=-1; /标志入口位置已到达过while(!q.empty() /栈q非空,则反复探索int orient42=0,1,1,0,0,-1,-1,0; /定义当前位置移动的个方向Temp2=q.GetPop(); /获取栈顶元素if(!(p.GetPop().x=q.GetPop().x & p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入栈,则把上一个探索的位置存入栈pfor(z=0;z4;z+) /探索当前位置的个相邻位置x=Temp2.x+ orie
22、ntz0; /计算出新位置x位置值y=Temp2.y+ orientz1; /计算出新位置y位置值if(mazexy=0) /判断新位置是否可达Temp1.x=x;Temp1.y=y;mazexy=-1; /标志新位置已到达过q.Push(Temp1); /新位置入栈if(x=(m)&(y=(n) /成功到达出口Temp1.x=m;Temp1.y=n;Temp1.dir=0;p.Push(Temp1); /把最后一个位置入栈PrintPath(p); /输出路径return 1; /表示成功找到路径if(p.GetPop().x=q.GetPop().x&p.GetPop().y=q.GetPop().y)/如果没有新位置入栈,则返回到上一个位置p.Pop();q.Pop
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论