数据结构实验二 迷宫实验报告电子版

福州大学数计学院《数据结构》上机实验报告专业：应用数学学号姓名班级实验名称栈、队列结构及其应用--综合运用实验内容利用栈实现迷宫求解实验目的和要求【实验目的】应用栈结构来解决应用问题，加深对栈结构特点的认识和应用。【基本要求】首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如:对于下列数据的迷宫，输出的一条通路为;(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),....问题描述和主要步骤【问题描述】以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论【测试数据】迷宫的测试数据如下：左上角（1，1）为入口，右下角（8，9）为出口12345678001000100010001000001101011100100001000001000101011110011100010111000000代码如下:#include"stdafx.h"#include"conio.h"#include"stdlib.h"#defineOK1#defineERROR0intMaze[11][10]={1,1,1,1,1,1,1,1,1,1,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,};typedefstructLStack{ intx; inty; intd; LStack*next;}LStack,*LinkStack;intInitStack_L(LinkStack&S){S=(LinkStack)malloc(sizeof(LStack));if(!S)printf("overflow");S->next=NULL;returnOK;}intPush_L(LinkStack&S,inta,intb,intc){LinkStackP;P=(LinkStack)malloc(sizeof(LStack));if(!P)returnERROR;P->x=a;P->y=b;P->d=c;P->next=S->next;S->next=P;returnOK;}intStackEmpty(LinkStack&S){if(S->next==NULL)return1;elsereturn0;}intPop_L(LinkStack&S){ LinkStackp; p=S->next; S->next=p->next; free(p); returnOK;}voidprint(LinkStack&B) { if(B->next!=NULL)print(B->next); printf("(%d,%d,%d)->",B->x,B->y,B->d); }intStackTraverse(LinkStack&S){ LinkStackw; w=S->next; print(w); printf("out\n"); returnOK;}voidWay(LinkStack&a){ Maze[1][1]=2; Push_L(a,1,1,1); do { if(a->next->d==1&&Maze[a->next->x][a->next->y+1]==0){Push_L(a,a->next->x,a->next->y+1,0);Maze[a->next->x][a->next->y]=2;} Elseif(a->next->d==2&&Maze[a->next->x+1][a->next->y]==0){Push_L(a,a->next->x+1,a->next->y,0);Maze[a->next->x][a->next->y]=2;} elseif(a->next->d==3&&Maze[a->next->x][a->next->y-1]==0){Push_L(a,a->next->x,a->next->y-1,0);Maze[a->next->x][a->next->y]=2;} elseif(a->next->d==4&&Maze[a->next->x-1][a->next->y]==0){Push_L(a,a->next->x-1,a->next->y,0);Maze[a->next->x][a->next->y]=2;} if(a->next->d<4) a->next->d++; else{Maze[a->next->x][a->next->y]=3;Pop_L(a);a->next->d++;} }while(!StackEmpty(a)&&Maze[9][8]!=2);}voidmain(){ LinkStackm; InitStack_L(m);inti,j; Way(m); printf("==problemofmaze==\n"); printf("themazedestinationis(9,8),\n"); printf("thegraphofmaze.\n"); printf("012345678\n"); printf("**************************************************************************\n"); for(i=0;i<11;i++) { printf("%d*",i); for(j=0;j<9;j++) printf("%d*",Maze[i][j]); printf("\n***************************************