实验数组的表示及其应用教案

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