资源描述：
《C++迷宫问题实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构集中上机试验报告班级：学号：姓名：燕文静题目：编制一个求解迷宫通路的程序以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。实验要求：实现一个以链表作存储结构的栈类型。然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。实验过程：1.基本算法以及分析：本程序主要是以链表构造栈的形式，寻找迷宫路径，根据创立的结点，输入结点里的一些数据
2、，如下structStack//构造栈{intMaze_x,Maze_y;//定义迷宫X，Y坐标Stack*next;//定义栈指针};程序由主函数开始，首先，定义一个二维数组迷宫。选择开始坐标点，然后，开始入栈，利用各个位置的判断循环建立结点，记录各个位置的数据，若走进死胡同则退栈，并且判断是否栈空，找到路径并到达出口后将栈倒置，使其按从入口到出口的顺序输出，之后调用迷宫图案输出函数，使其按要求输出。二．概要设计1.抽象数据类型定义为：ADTstack{数据对象：D={ai
3、ai∈LinkList,i=1,2,...
4、n,n≥0}数据关系：R1={
5、ai-1,ai∈D
6、=2,……n}，即当前结点与下一个结点的关系基本操作：stack();构造函数，建立一个空栈；操作结果：通过字符串a构造两个位数不限的长整数。voidPush(DataTypedata);初始条件：已存在栈操作结果：把元素data压入栈顶DataTypePop();初始条件：已存在栈，且非空操作结果：栈顶元素出栈，且删除栈顶元素DataTypeGetPop();初始条件：已存在栈，且非空操作结果：获取栈顶元素voidClear();初始条件：已存在栈操作结果：把当前的
7、栈清空boolIsEmpty();初始条件：已存在栈操作结果：如果栈为空，则结果为“真”，否则为“假”}ADTOrderedList2.程序源代码：#include#includeusingnamespacestd;structStack//构造栈{intMaze_x,Maze_y,Maze_z;//定义迷宫X，Y坐标,z方向Stack*next;//定义栈指针};Stack*ps;//链头指针voidPop()//出栈函数{Stack*p;p=ps;ps=ps->next;del
8、etep;}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;}voidMazepath(inta[][10],inti,intj)//迷宫路线寻找函数{a[i][j]=2;intc,d,m=1;//定义变量c,d为出口坐标,变量m作为走过的步数cout<<"请输入出口坐标：";cin>>c>>d;while(i!=c
9、
10、j!=d)//判断是否到达出口{if(a[i]
11、[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[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/
12、/四个方向都不可行，退栈{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==NULL)//判断栈空否{cout<<"nopath!"<next=NULL;while(ps!=NULL)//倒置栈中的数据,使其从开始坐标输出{Sta
13、ck*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<<","<
