数据结构c语言课程设计报告.doc

数据结构课程设计报告设计题目：迷宫求解专 业 机电一体化 班 级 08专接本 学 生 学 号 104910252011 指导教师 高在村 完成时间 2011. 5 目录 一.实验内容3二.需求分析3三总体设计3四详细设计5五代码9六.测试14七. 总结16参考文献17一.实验内容任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：界面友好，函数功能要划分好；总体设计应画一流程图；程序要加必要的注释；要提供程序设计方案；程序一定要经得起测试；宁可功能少一点，也要能运行起来，不能运行的程序是没有价值的。二.需求分析1.可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：使用非递归算法。2.用户可以根据自己的需求进行输入所需的迷宫，其中1表示迷宫的墙壁，0表示迷宫的通路，从而建立自己的迷宫；3.用户还可以自己设计迷宫的入口坐标，当然也可以设计出口了；4.程序执行的命令包括：（1）构造栈Stack, T 描述迷宫中当前位置的结构类型, LinkNode链表结点三个类,其中Stack是Linknode的友元类. （2）构造存取迷宫的二维指针GetMaze(int &m,int &n) （3）恢复迷宫Restore(int *maze,int m,int n) （4）在迷宫中寻找一条通路Mazepath(int *maze,int m,int n) （5）输出所找到的通路PrintPath() (6) 定义当前位置移动的4个方向move数组.三总体设计存储结构：首先用二维指针存储迷宫数据，迷宫数据由用户输入。一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。1从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。经过的位置把0变为-1，带输出迷宫路径后在恢复迷宫院士为止2. 本程序有三个模块： 主程序模块 三个类模块即其对象：实现栈链表抽象数据类型； 迷宫二维指针单元模块：存储迷宫,寻路径,输出迷宫,恢复迷宫。(二)流程图存取迷宫GetMaze(int &m,int &n)求取一条路径MazePath（）if(p.GetPop().x=q.GetPop().x&p.GetPop().y=q.GetPop().y)输入迷宫的长和宽内容显示结果Printpath（）迷宫无路经 END数组move用于更改方向,函数Push, PrintPath, Restore调用函数GetPop, Push,Pop恢复迷宫Restore()调用四详细设计(一).基本算法：首先用二维指针存储迷宫数据，迷宫数据由用户输入。一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、南、西、北4个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宫的外墙；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宫的入口和出口；其余元素值用GetMaze函数获取.假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有4。如果用二维数组move记录4方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用move数组确定： x=x+moveloop0 y=y+moveloop1从迷宫的入口位置开始，沿图示方向顺序依次进行搜索。定义一个栈，按从入口到出口存取路径.在搜索过程中，每前进一步，如果有新位置入栈，则把上一个探索的位置存入栈中,当前位置”-1”（表示这个位置在通路上），并将该位置的坐标压入栈中。如果没有新位置入栈，则返回到上一个位置.到达出口后,最后一个位置入栈,输出路径,并回复路径.把-1变为0.总之,入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。(二). 为实现算法，需要类的象数据类型：类及其对象:类 Stack 对象成员如下:Stack(); 构造函数，置空栈操作结果：构造一个空的栈S。Stack(); 析构函数 void Push(T e); 把元素data压入栈中T Pop(); 使栈顶元素出栈 T GetPop(); 取出栈顶元素 void Clear(); 把栈清空 bool empty(); 判断栈是否为空，如果为空则返回1，否则返回0T类 迷宫中当前位置的结构类型: T对象成员如下:x; x代表当前位置的行坐标y; y代表当前位置的列坐标dir; 0:无效,1:东,2:南,3:西,4:北LinkNode类 链表结点: 对象成员如下:友元类 StackT dataLinkNode *next(三).函数调用关系main GetMaze Mazepath Empy() GetPop() Push() PrintPath() Restore() Pop() GetPop() Push()(四) 算法的时间、空间复杂度1）本算法在空间上主要开辟了一个二维指针，规模都是迷宫(m+2)*(n+2)，一个是栈，一个是迷宫路径记录，输出时候调用栈，在恢复迷宫。2）在时间上为简单的链表栈的存储结构，二维指针GetMaze, Restore两函数算法时间复杂度为O（(m+2)*(n+2)）, Mazepath,PrintPath为O(1),（m为行数，n为列数）。(五) UML图T+X:int+y:int+dir:int LinkNode+T dataStack+push(T e):void+T Getpop ( ):void+T pop ( )+empty ( ):bool+Stack ( )+Stack ( )+Clear ( ):void+nextLinkNodeLinkNode-top五代码/*以一个mn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1），（1,2,2），（2,2,2），（3,2,3），（3,1,2），。*/#includeusing namespace std;class T /定义描述迷宫中当前位置的结构类型public: int x; /x代表当前位置的行坐标 int y; /y代表当前位置的列坐标 int dir; /0:无效,1:东,2:南,3:西,4:北;class LinkNode /链表结点 friend class Stack;public: T data; LinkNode *next;class Stackprivate: LinkNode *top; /指向第一个结点的栈顶指针public: Stack(); /构造函数，置空栈 Stack(); /析构函数 void Push(T e); /把元素data压入栈中 T Pop(); /使栈顶元素出栈 T GetPop(); /取出栈顶元素 void Clear(); /把栈清空 bool empty(); /判断栈是否为空，如果为空则返回1，否则返回0;Stack:Stack() /构造函数，置空栈 top=NULL;Stack:Stack() /析构函数void Stack:Push(T e) /把元素x压入栈中 LinkNode *P; P=new LinkNode; P-data=e; P-next=top; top=P;T Stack:Pop() /使栈顶元素出栈 T Temp; LinkNode *P; P=top; top=top-next; Temp=P-data; delete P; return Temp;T Stack:GetPop() /取出栈顶元素 return top-data;void Stack:Clear() /把栈清空 top=NULL;bool Stack:empty() /判断栈是否为空，如果为空则返回1，否则返回0 if(top=NULL) return 1; else return 0;int move42=0,1,1,0,0,-1,-1,0; /定义当前位置移动的4个方向bool Mazepath(int *maze,int m,int n); /寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回falsevoid PrintPath(Stack p); /输出迷宫的路径void Restore(int *maze,int m,int n); /恢复迷宫int* GetMaze(int &m,int &n); /获取迷宫 /返回存取迷宫的二维指针int main() int m=0,n=0; /定义迷宫的长和宽 int *maze; /定义二维指针存取迷宫 maze=GetMaze(m,n); /调用GetMaze(int &m,int &n)函数，得到迷宫 if(Mazepath(maze,m,n) /调用Mazepath(int *maze,int m,int n)函数获取路径 cout迷宫路径探索成功!n; else cout路径不存在!n; return 0;int* GetMaze(int &m,int &n)/返回存取迷宫的二维指针 int *maze; /定义二维指针存取迷宫 int i=0,j=0; coutab; /输入迷宫的长和宽 cout请输入迷宫内容:n; m=a; n=b; /m,n分别代表迷宫的行数和列数 maze=new int *m+2; /申请长度等于行数加2的二级指针 for(i= 0;im+2;i+) /申请每个二维指针的空间 mazei=new intn+2; for(i=1;i=m;i+) /输入迷宫的内容，0代表可通，1代表不通 for(j=1;jmazeij; for(i=0;im+2;i+) mazei0=mazein+1=1; for(i=0;in+2;i+) maze0i=mazem+1i=1; return maze; /返回存贮迷宫的二维指针maze;bool Mazepath(int *maze,int m,int n)/寻找迷宫maze中从（0，0）到（m,n）的路径 /到则返回true,否则返回false Stack q,p; /定义栈p、q,分别存探索迷宫的过程和存储路径 T Temp1,Temp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push(Temp1); /将入口位置入栈 p.Push(Temp1); maze11=-1; /标志入口位置已到达过 while(!q.empty() /栈q非空，则反复探索 Temp2=q.GetPop(); /获取栈顶元素 if(!(p.GetPop().x=q.GetPop().x&p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入栈，则把上一个探索的位置存入栈p for(loop=0;loop4;loop+) /探索当前位置的4个相邻位置 x=Temp2.x+moveloop0; /计算出新位置x位置值 y=Temp2.y+moveloop1; /计算出新位置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); /输出路径 Restore(maze,m,n); /恢复路径 return 1; /表示成功找到路径 if(p.GetPop().x=q.GetPop().x&p.GetPop().y=q.GetPop().y) /如果没有新位置入栈，则返回到上一个位置 p.Pop(); q.Pop(); return 0; /表示查找失败，即迷宫无路经void PrintPath(Stack p) /输出路径 cout迷宫的路径为n; coutdata=p.Pop(); /取栈p的顶点元素，即第一个位置 t.Push(temp-data); /第一个位置入栈t delete temp; /释放空间 while(!p.empty() /栈p非空，则反复转移 temp=new LinkNode; temp-data=p.Pop(); /获取下一个位置 /得到行走方向 a=t.GetPop().x-temp-data.x; /行坐标方向 b=t.GetPop().y-temp-data.y; /列坐标方向 if(a=1) temp-data.dir=1; /方向向下，用1表示 else if(b=1) temp-data.dir=2; /方向向右，用2表示 else if(a=-1) temp-data.dir=3; /方向向上，用3表示 else if(b=-1) temp-data.dir=4; /方向向左，用4表示 t.Push(temp-data); /把新位置入栈 delete temp; /输出路径，包括行坐标，列坐标，下一个位置方向 while(!t.empty() /栈非空，继续输出 data=t.Pop(); cout(data.x,data.y,data.dir,; /输出行坐标，列坐标 switch(data.dir) /输出相应的方向 case 1:cout)n;break; case 2:cout)n;break; case 3:cout)n;break; case 4:cout)n;break; case 0:cout)n;break; void Restore(int *maze,int m,int n) /恢复迷宫 int i,j; for(i=0;im+2;i+) /遍历指针 for(j=0;jn+2;j+) if(mazeij=-1) /恢复探索过位置，即把-1恢复为0 mazeij=0; 六.测试(一)初始界面:(二) 测试数据迷宫 3行3列0 1 1 0 0 11 0 0迷宫的路径为括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向)(1,1,1,)(2,1,2,)(2,2,1,)(3,2,2,)(3,3,0)迷宫路径探索成功!(三)无解的情况:即路径没找到.缺点与改进:1. 在定义函数Mazepath（）的时候，开始的循环语句的结束条件不对，没出路时,导致一直出现不了正确的结果，最后一一检查和用实例迷宫一一如果没有新位置入栈，则返回到上一个位置, if(p.GetPop().x=q.GetPop().x&p.GetPop().y=q.GetPop().y),否则没路径.2. 只是手动输入,如果迷宫数据大时,很费时间.如时间允许,则可以用随机产生函数.自动产生迷宫.七. 总结要能很好的掌握编程,仅仅通过几个简单的程序的编写时无法达成的,更需要大量积累和深入才可能.就从这个迷宫问题求解来说,在迷宫求路径就需要使用链表的栈,靠出栈和进栈来存取路径数据.在程序的编写中也不能一味的向已有的程序进行模仿,而要自己摸索,去寻找最好的解决方法,只有带着问题去反复进行实践,才能更熟练的掌握和运用,当然,对现有的程序也要多去接触,因为有些程序是我们无法在短时间内想出来的.最重要的一点是持之以恒,要经常性的复习原来接触的程序,这样才能保证我们有足够的经验去面对程序问参考文献【1】 严蔚敏 吴伟民 数据结构(C语言版) 清华大学出版社， 2009年9月【2】 谭浩强 C程序设计(第三版) 清华大学出版社 2009年1月题.