《数据结构》上机实验报告(迷宫求解)

（说明：实验报告必须包含下面的每项内容，根据实验情况认真填写，封面必须打印或复印（A4纸），书写上机实验报告内容的纸张也用A4纸，最后从侧面装订）一【上机实验目的】了解栈的应用编写迷宫程序二【实验环境】PC机每人1台三【上机实验内容】（此次上机实验老师布置的具体任务）迷宫求解主要利用栈实现，要求能动态生成迷宫，显示有几条路径，用图形界面显示最合适的路径。四【上机调试程序流程图】（注：可打印）（用传统流程图的形式表示）五【上机调试中出现的错误信息、错误原因及解决办法】（记录下你调试程序中出现的错误信息的英文提示，分析出错原因及可能的解决办法）马虎造成的错误程序的逻辑有问题语法用错调试过程中，将整个程序分为一个个子块，逐个解决六【上机调试后的源程序及还存在的问题】（注：源程序可打印）（同时记录下你对你编写此程序的其它具体想法，）#include<stdlib.h>#include<time.h>#include<stack>#include<queue>usingnamespacestd;#defineOVERFLOW0#defineOK1#defineERROE0#defineTRUE1#defineFALSE0#defineSIZE102//迷宫的最大范围typedefintStatus;typedefstruct{ intx; inty;}PosType;//坐标位置typedefstruct{ PosTypeseat;//通道块在迷宫中的"坐标位置" intdi;//从上一通道块走向此通道块的"方向"}SElemType;StatusCheck(char&choice);//确认输入正确voidRandom(intmg[SIZE][SIZE],intsize,PosTypestart,PosTypeend){ inti,j,k; srand(time(NULL)); for(j=0;j<size;j++) mg[0][j]=mg[size-1][j]=1;//设置迷宫外围"不可走"，保证只有一个出口和入口 for(i=1;i<size-1;i++) mg[i][0]=mg[i][size-1]=1; for(i=1;i<size-1;i++) for(j=1;j<size-1;j++){ k=rand()%4;//随机生成0、1、2、3四个数 if(k) mg[i][j]=0; else{ mg[i][j]=1; }//else } mg[start.y][start.x]=0; mg[end.y][end.x]=0;//将入口、出口设置为"0"即可通过}StatusPass(PosTypee,intmg[SIZE][SIZE]){ if(mg[e.y][e.x]==0)//0时可以通过 returnOK;//如果当前位置是可以通过，返回1 returnOVERFLOW;//其它情况返回0}StatusFootPrint(PosTypee,intmg[SIZE][SIZE]){ mg[e.y][e.x]=7; returnOK;}PosTypeNextPos(PosTypee,intdir){ PosTypeE; switch(dir){ case1:E.x=e.x+1;//向右 E.y=e.y; break; case2:E.x=e.x;//向下 E.y=e.y+1; break; case3:E.x=e.x-1;//向左 E.y=e.y; break; case4:E.x=e.x;//向上 E.y=e.y-1; break; } returnE;}StatusEqual(PosTypee1,PosTypee2){ if((e1.x==e2.x)&&(e1.y==e2.y)) returnTRUE; returnFALSE;}StatusMarkPath(PosTypee,intmg[SIZE][SIZE],intdi){ switch(di) {case1://向右 mg[e.y][e.x]=11; break; case2://向下 mg[e.y][e.x]=12; break; case3://向左 mg[e.y][e.x]=13; break; case4://向上 mg[e.y][e.x]=14; break; } returnOK;}PosTypeFrontPos(PosTypee,intdir){ PosTypeE; switch(dir){ case1:E.x=e.x-1;//向左 E.y=e.y; break; case2:E.x=e.x;//向上 E.y=e.y-1; break; case3:E.x=e.x+1;//向右 E.y=e.y; break; case4:E.x=e.x;//向下 E.y=e.y+1; break; } returnE;}StatusPathPrint(stack<SElemType>s,intmg[SIZE][SIZE]){ SElemTypee,front,tail; intdi; e=s.top(); tail=e; s.pop(); MarkPath(e.seat,mg,1); while(!s.empty()) { front=s.top(); s.pop(); if(Equal(front.seat,FrontPos(e.seat,e.di))) { di=e.di; e=front; MarkPath(e.seat,mg,di); } } returnOK;}StatusPathClean(intmg[SIZE][SIZE],stack<SElemType>s){ SElemTypee; while(!s.empty()) { e=s.top(); s.pop(); mg[e.seat.y][e.seat.x]=0; } returnOK;}StatusMazePath(PosTypestart,PosTypeend,intmg[SIZE][SIZE],stack<SElemType>&s){ queue<SElemType>q; SElemTypee; intdi=0; e.di=di; e.seat=start;//设定"当前位置"为"入口位置" q.push(e); s.push(e); do { e=q.front();//得到队首的值 q.pop();///重复使用时，用这个初始化 for(di=1;di<=4;di++) { e.seat=NextPos(e.seat,di); e.di=di; if(Pass(e.seat,mg)) { q.push(e); s.push(e); FootPrint(e.seat,mg); if(Equal(e.seat,end)) { PathPrint(s,mg); returnTRUE; } } e.seat=FrontPos(e.seat,di); } }while(!q.empty()); printf("\n\n囧!不能到达终点!"); returnFALSE;}voidPrintMaze(intmg[SIZE][SIZE],intsize){ inti,j; printf("\n"); for(i=0;i<size;i++) { for(j=0;j<size;j++) { switch(mg[i][j]) { case0: case7: printf(""); break; case1: if((1==i&&0==j)||((size-2)==i&&(size-1)==j)) printf(""); else printf("■"); break; case11: printf("→"); break; case12: printf("↓"); break; case13: printf("←"); break; case14: printf("↑"); break; } } printf("\n"); } printf("\n");}StatusCheck(char&choice){ while(!(((choice=getchar())=='y')||(choice=='n')||(choice=='Y')||(choice=='N')))//非正确输入 { if(choice!='\n') { printf("请输入确定选择(y/n)\n"); getchar(); } } getchar();//跳过'\n' returnOK;}intmain(){ stack<SElemType>s; intmg[SIZE][SIZE]={1},size; PosTypestart,end; charchoice; system("modeconcols=200lines=200"); printf("\n==================迷宫最短路径游戏=================="); printf("\n说明:■不能走的区域"); printf("\n'空格'代表可通过的区域"); printf("\n默认起点为左上角位置，默认终点为右下角位置\n"); printf("\n============================================\n"); printf("请输入迷宫边长(3~%d),系统将为你产生一个随机迷宫：",SIZE-2); scanf("%d",&size); while((size>SIZE-2)||(size<1)) { printf("输入有误！\n"); printf("请输入迷宫边长(3~%d),系统将为你产生一个随机迷宫：",SIZE-2);scanf("%d",&size); } size+=2;//补上外围 getchar();//跳过'\n' start.x=1;start.y=1;//起点坐标 end.x=size-2;end.y=size-2;//终点坐标 Random(mg,size,start,end);PrintMaze(mg,size); while(!((choice=='Q')||(choice=='q'))) { printf("是否使用该迷宫?(y/n)\n"); Check(choice); if((choice=='Y')||(choice=='y')) { PathClean(mg,s); } while((choice=='n')||(choice=='N')) { while(!s.empty()) s.pop(); choice=''; printf("请输入迷宫边长(3~%d),系统将为你产生一个随机迷宫：",SIZE-2); scanf("%d",&size); while((size>SIZE-2)||(size<1)) { printf("输入有误！\n"); printf("请输入迷宫边长(3~%d),系统将为你产生一个随机迷宫：",SIZE-2); scanf("%d",&size); } size+=2;//补上外围 start.x=1;start.y=1;//起点坐标 end.x=size-2;end.y=size-2;//终点坐标 getchar();//跳过'\n' Random(mg,size,start,end); PrintMaze(mg,size); printf("是否使用该迷宫?(y/n)\n"); Check(choice); } printf("是否人工选择起点和终点(y/n)?【默认：起点(1,1),终点(%d,%d)】\n",size-2,size-2); Check(choice); if((choice=='y')||(choice=='Y')) { printf("请输入“起点”坐标(1~%d)用空格分隔：",size-2); scanf("%d%d",&start.x,&start.y); while(((start.x>size-2)||start.x<1)||((start.y>size-2)||(start.y<1))||!Pass(start,mg)) { if(!Pass(start,mg)) printf("些位置不能为“起点”！\n"); elseprintf("输入有误！\n"); printf("请输入“起点”坐标(1~%d)用空格分隔：",size-2); scanf("%d%d",&start.x,&start.y); } printf("请输入“终点”坐标(1~%d)用空格分隔：",size-2); scanf("%d%d",&end.x,&end.y); while(((end.x>size-2)||end.x<1)||((end.y>size-2)||(end.y<1))||!Pass(end,mg)||Equal(start,end)) { if(!Pass(end,mg)) printf("些位置不能为“终点”！\n"); elseif(Equal(start,end))printf("该位置已为起点！\n"); elseprintf("输入有误！\n"); printf("请输入“终点”坐标(1~%d)用空格分隔：",size-2); scanf("%d%d",&end.x,&