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

数据结构集中上机试验报告学院： 计算机科学与技术 专业：计算机科学与技术学号：00000000 班级：（6） 姓名： 20010.10.27题目：编制一个求解迷宫通路的程序 以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。实验要求： 实现一个以链表作存储结构的栈类型。然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i , j , d）的形式输出，其中（i , j ）指示迷宫中的一个坐标，d表示走到下一坐标的方向。实验过程：1.基本算法以及分析：本程序主要是以链表构造栈的形式，寻找迷宫路径，根据创立的结点，输入结点里的一些数据，如下struct Stack /构造栈int Maze_x,Maze_y; /定义迷宫X，Y坐标Stack * next; /定义栈指针;程序由主函数开始，首先，定义一个二维数组迷宫。选择开始坐标点，然后，开始入栈，利用各个位置的判断循环建立结点，记录各个位置的数据，若走进死胡同则退栈，并且判断是否栈空，找到路径并到达出口后将栈倒置，使其按从入口到出口的顺序输出，之后调用迷宫图案输出函数，使其按要求输出。2.程序源代码： 迷宫问题#include#includeusing namespace std;struct Stack /构造栈int Maze_x,Maze_y,Maze_z; /定义迷宫X，Y坐标,z方向Stack * next; /定义栈指针;Stack *ps; /链头指针void Pop() /出栈函数Stack *p; p = ps;ps=ps-next;delete p; void push(int x,int y,int z) /进栈 函数Stack *t;t = new Stack;t-Maze_x = x;t-Maze_y = y;t-Maze_z = z; t-next = ps;ps = t;void Mazepath(int a10,int i,int j) /迷宫路线寻找 函数aij=2;int c,d,m=1; /定义变量c,d为出口坐标,变量m作为走过的步数coutcd;while(i!=c | j!=d) /判断是否到达出口if(aij+1=0) /判断右边是否可行 push(i,j,1);j+; aij = 2; /标记走过的位置else if(ai+1j=0) /判断下边是否可行push(i,j,2);i+;aij = 2; /标记走过的位置else if(aij-1=0) /判断左边是否可行 push(i,j,3);j-;aij = 2; /标记走过的位置else if(ai-1j=0) /判断上边是否可行push(i,j,4);i-;aij = 2; /标记走过的位置else /四个方向都不可行，退栈int e1,e2; Stack *p; p = ps; ps=ps-next;e1=p-Maze_x;e2=p-Maze_y;ae1e2=3; /标记走过的死胡同坐标 delete p; /删除栈顶元素i = ps-Maze_x;j = ps-Maze_y;if(ps=NULL) /判断栈空否coutno path!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,Maze_z)next;delete k;coutendl;coutendl;void PrintMaze(int a10) /迷宫图案输出 函数for(int i=0;i11;i+)for(int j=0;j10;j+)if(aij=1)coutsetw(2)#; /符号#标记为迷宫的围墙else if(aij=2)coutsetw(2)*; /符号*标记为走过的路线else if(aij=3)coutsetw(2); /符号标记为死胡同的路线else if(aij=0)coutsetw(2) ; /空格标记为可走但没走过的路线coutsetw(8) endl;int main() /主 函数int Maze1110=1,1,1,1,1,1,1,1,1,1, /二维数组直接定义迷宫,1为围墙，0为可走的路线 1,0,0,1,0,0,0,1,0,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,0,0,1,1,0,1,1, 1,0,1,1,1,0,0,1,0,1, 1,0,0,0,1,0,0,0,0,1, 1,0,1,0,0,0,1,0,1,1, 1,0,1,1,1,1,0,0,1,1, 1,1,1,0,0,0,1,0,1,1, 1,1,1,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1; cout开始坐标：;cout11 21 31 41 51 61 71endl; coutab; Mazepath(Maze,a,b);cout迷宫路线图案：endl;coutendl; PrintMaze(Maze);coutendl