C++ 迷宫问题实验报告.doc

《C++ 迷宫问题实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构集中上机试验报告学院：计算机科学与技术专业：计算机科学与技术学号：00000000班级：（6）姓名：20010.10.27题目：编制一个求解迷宫通路的程序以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。实验要求：实现一个以链表作存储结构的栈类型。然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。实验过程：1.基本算法以及分析：本程序主要是以链表构造栈的

2、形式，寻找迷宫路径，根据创立的结点，输入结点里的一些数据，如下structStack//构造栈{intMaze_x,Maze_y;//定义迷宫X，Y坐标Stack*next;//定义栈指针};程序由主函数开始，首先，定义一个二维数组迷宫。选择开始坐标点，然后，开始入栈，利用各个位置的判断循环建立结点，记录各个位置的数据，若走进死胡同则退栈，并且判断是否栈空，找到路径并到达出口后将栈倒置，使其按从入口到出口的顺序输出，之后调用迷宫图案输出函数，使其按要求输出。2.程序源代码：迷宫问题#include#include

3、ip>usingnamespacestd;structStack//构造栈{intMaze_x,Maze_y,Maze_z;//定义迷宫X，Y坐标,z方向Stack*next;//定义栈指针};Stack*ps;//链头指针voidPop()//出栈函数{Stack*p;p=ps;ps=ps->next;deletep;}voidpush(intx,inty,intz)//进栈函数{Stack*t;t=newStack;t->Maze_x=x;t->Maze_y=y;t->Maze_z=z;t->next=ps;ps=t;}voidMazepa

4、th(inta[][10],inti,intj)//迷宫路线寻找函数{a[i][j]=2;intc,d,m=1;//定义变量c,d为出口坐标,变量m作为走过的步数cout<<"请输入出口坐标：";cin>>c>>d;while(i!=c

5、

6、j!=d)//判断是否到达出口{if(a[i][j+1]==0)//判断右边是否可行{push(i,j,1);j++;a[i][j]=2;//标记走过的位置}elseif(a[i+1][j]==0)//判断下边是否可行{push(i,j,2);i++;a[i][j]=2;//标记走过的位置}elseif(a[

7、i][j-1]==0)//判断左边是否可行{push(i,j,3);j--;a[i][j]=2;//标记走过的位置}elseif(a[i-1][j]==0)//判断上边是否可行{push(i,j,4);i--;a[i][j]=2;//标记走过的位置}else//四个方向都不可行，退栈{inte1,e2;Stack*p;p=ps;ps=ps->next;e1=p->Maze_x;e2=p->Maze_y;a[e1][e2]=3;//标记走过的死胡同坐标deletep;//删除栈顶元素i=ps->Maze_x;j=ps->Maze_y;if(ps=

8、=NULL)//判断栈空否{cout<<"nopath!"<next=NULL;while(ps!=NULL)//倒置栈中的数据,使其从开始坐标输出{Stack*t;t=ps;ps=ps->next;t->next=pk->next;pk->next=t;}Stack*k=pk;pk=pk->next;delete(k);//释放PK空间while(pk!=NULL)//输出走过的坐标{cout<<"("<Maze_x<<","<Maze_y<<"

9、,"<Maze_z<<")"<next;deletek;}cout<

10、ut<