数据结构实验报告题目:用栈解决迷宫问题一.需求分析1.以结构体Maze表示迷宫,其中pos表示该位置是否有障碍;freq记录该位置被经过的次数;数组move表示下一步的方向。2.本程序自动随机生成一个12×12大小的迷宫,字符“H”表示有障碍,空符表示通路。3.迷宫的入口为左上角,出口为右下角。4.本程序只求出一条成功的通路。二.概要设计为了实现上述操作,以栈为存储结构。本程序包含三个模块:(1)主程序模块:实现人机交互。(2)迷宫生产模块:随机产生一个12×12的迷宫。(3)路径查找模块:实现通路的查找。(4)求解迷宫中一条通路的伪代码:do{若当前位置可同,则{将当前位置插入栈顶;若该位置是出口位置,则结束;否则切换当前位置的东临方块为新的当前位置;}否则{若栈不空且栈顶位置尚有其他方向未被探索,则设定新的的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通,则{删去栈顶位置;若栈不空,则重新测试新的栈顶位置,直至找到一个可通的相邻块或出栈至栈空。}}}while(栈不空)三.详细设计栈的设计:typedefstruct{Node*base,*top;intlength;}Stack;Stack*initstack();//初始化栈voidprintstack(Stack*s);//打印栈Statusdestroy(Stack*);//销毁整个栈Statusdeltop(Stack*s);//出栈Statuspushelem(Stack*,ElemType,ElemType);//进栈1.主程序模块:intmain(){printf(随机产生一个12×12的迷宫,X字符表示障碍,空符表示通路:\n);Mazea[N][N];makemaze(a);printf(输入回车键显示路径,*字符表示路径。\n);getchar();findpath(a);while(1);return0;}2.迷宫生产模块;voidmakemaze(Maze(*p)[N]){inti,j,conter;for(i=0;iN;++i)for(j=0;jN;++j){(*(p+i)+j)-pos=0;(*(p+i)+j)-freq=0;(*(p+i)+j)-move[0]=0;(*(p+i)+j)-move[1]=0;(*(p+i)+j)-move[2]=0;(*(p+i)+j)-move[3]=0;}for(j=0;jN;++j){(*p+j)-pos='X';(*(p+N-1)+j)-pos='X';}for(i=1;iN-1;++i){(*(p+i))-pos='X';(*(p+i)+N-1)-pos='X';}srand((int)time(NULL));for(conter=0;conter20;++conter){i=rand()%(N-2);j=rand()%(N-2);(*(p+i)+j)-pos='X';if(i==1&&j==1||i==N-1&&j==N-1){(*(p+i)+j)-pos=0;}}printmaze(p);}3.路径查找模块。Maze*testnewpos(Maze(*p)[N],Stack*s,int*i,int*j){Maze*q=NULL;intselect=0;*i=*j=0;for(;q==NULL&&select4;++select)//在可行的方向上只选一个{switch(select){case0:if((*(p+s-top-x)+s-top-y)-move[0]!=1){(*(p+s-top-x)+s-top-y)-move[0]=1;q=*(p+s-top-x)+s-top-y+1;*i=s-top-x+0;*j=s-top-y+1;}//退回前一步检查东方向是否可通break;case1:if((*(p+s-top-x)+s-top-y)-move[1]!=1){(*(p+s-top-x)+s-top-y)-move[1]=1;q=*(p+s-top-x+1)+s-top-y;*i=s-top-x+1;*j=s-top-y+0;}//退回前一步检查南方向是否可通break;case2:if((*(p+s-top-x)+s-top-y)-move[2]!=1){(*(p+s-top-x)+s-top-y)-move[2]=1;q=*(p+s-top-x)+s-top-y-1;*i=s-top-x+0;*j=s-top-y-1;}//退回前一步检查西方向是否可通break;case3:if((*(p+s-top-x)+s-top-y)-move[3]!=1){(*(p+s-top-x)+s-top-y)-move[3]=1;q=*(p+s-top-x-1)+s-top-y;*i=s-top-x-1;*j=s-top-y+0;}//退回前一步检查北方向是否可通}}returnq;}voidprintpath(Stack*s,Maze(*p)[N]){Node*n;inti,j,conter;conter=0;n=s-base;for(;n;n=n-next){(*(p+n-x)+n-y)-pos='*';}for(i=0;iN;++i)for(j=0;jN;++j){++conter;printf(FORMAT,(*(p+i)+j)-pos);if(conter%12==0)TURNLINE;}TURNLINE;}完整的程序:maze.h#ifndefMAZE_H#defineMAZE_H#includemazepath.h#includetime.h#defineN12//10+2#defineFORMAT%2c#defineTURNLINEprintf(\n)typedefstruct{charpos;intfreq;intmove[4];}Maze;voidmakemaze(Maze(*p)[N]);voidprintmaze(Maze(*p)[N]);voidfindpath(Maze(*p)[N]);Maze*testnewpos(Maze(*p)[N],Stack*,int*,int*);voidprintpath(Stack*s,Maze(*p)[N]);voidmakemaze(Maze(*p)[N]){inti,j,conter;for(i=0;iN;++i)for(j=0;jN;++j){(*(p+i)+j)-pos=0;(*(p+i)+j)-freq=0;(*(p+i)+j)-move[0]=0;(*(p+i)+j)-move[1]=0;(*(p+i)+j)-move[2]=0;(*(p+i)+j)-move[3]=0;}for(j=0;jN;++j){(*p+j)-pos='X';(*(p+N-1)+j)-pos='X';}for(i=1;iN-1;++i){(*(p+i))-pos='X';(*(p+i)+N-1)-pos='X';}srand((int)time(NULL));for(conter=0;conter20;++conter){i=rand()%(N-2);j=rand()%(N-2);(*(p+i)+j)-pos='X';if(i==1&&j==1||i==N-1&&j==N-1){(*(p+i)+j)-pos=0;}}printmaze(p);}voidprintmaze(Maze(*p)[N]){inti,j,conter;conter=0;for(i=0;iN;++i)for(j=0;jN;++j){++conter;printf(FORMAT,(*(p+i)+j)-pos);if(conter%12==0)TURNLINE;}TURNLINE;}voidfindpath(Maze(*p)[N]){Maze*q=NULL;inti=1,j=1,*pi=&i,*pj=&j,success=0;Stack*s;s=initstack();//初始化用来存储路径的栈q=*(p+1)+1;//初始化当前位置为入口位置do{if(q-pos!='X'&&!(q-freq))//当前位置通且在当前路径中未被访问过,则入栈{if(i==N-2&&j==N-2){pushelem(s,N-2,N-2);success=1;}elseif(i==1&&j==1){pushelem(s,i,j);q-freq=1;//当前位置已经进栈,作标记,不能再入栈,不然就只能兜死胡同了q-move[0]=1;//切换下一位置为东邻位置,并做标记,东邻位置已经使用i=s-top-x+0;j=s-top-y+1;q=*(p+i)+j;}else{pushelem(s,i,j);q-freq=1;q=*(p+i)+j;}}else//当前位置不通,则在前一步(栈顶)检查是否有其他方向可行{//printf(stephere...);if(s-base!=s-top){do//查找新的通路直到新通路出现或者回到初始位置{q=testnewpos(p,s,&i,&j);//返回其它三个方向的其中一个和新的当前位置的坐标if(q==NULL)deltop(s);//栈顶没有可继续往下走的通路,删除栈顶,在新的栈顶找}while(q==NULL&&s-base!=s-top);}}}while(success!=1);printpath(s,p);}Maze*testnewpos(Maze(*p)[N],Stack*s,int*i,int*j){Maze*q=NULL;intselect=0;*i=*j=0;for(;q==NULL&&select4;++select)//在可行的方向上只选一个{switch(select){case0:if((*(p+s-top-x)+s-top-y)-move[0]!=1){(*(p+s-top-x)+s-top-y)-move[0]=1;q=*(p+s-top-x)+s-top-y+1;*i=s-top-x+0;*j=s-top-y+1;}//退回前一步检查东方向是否可通break;case1:if((*(p+s-top-x)+s-top-y)-move[1]!=1){(*(p+s-top-x)+s-top-y)-move[1]=1;q=*(p+s-top-x+1)+s-top-y;*i=s-top-x+1;*j=s-top-y+0;}//退回前一步检查南方向是否可通break;case2:if((*(p+s-top-x)+s-top-y)-move[2]!=1){(*(p+s-top-x)+s-top-y)-move[2]=1;q=*(p+s-top-x)+s-top-y-1;*i=s-top-x+0;*j=s-top-y-1;}//退回前一步检查西方向是否可通break;case3:if((*(p+s-top-x)+s-top-y)-move[3]!=1){(*(p+s-top-x)+s-top-y)-move[3]=1;q=*(p+s-top-x-1)+s-top-y;*i=s-top-x-1;*j=s-top-y+0;}//退回前一步检查北方向是否可通}}returnq;}voidprintpath(Stack*s,Maze(*p)[N]){Node*n;inti,j,conter;conter=0;n=s-base;for(;n;n=n-next){(*(p+n-x)+n-y)-