数据结构上机实验报告-迷宫求解
- 格式：docx
- 大小：164.20 KB
- 文档页数：12
数据结构上机实验报告迷宫求解陈冠豪20102105010101015二O一O年5月26号实验目的任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；实现代码://////////By Lea//////////////////////2010210501////////////#include<stdio.h>#include<stdlib.h>/*数据定义*/typedefenum { ERROR, OK } Status;typedefstruct{int row; //row表示"行"号int line; //line表示"列"号}PosType; //位置的元素类型typedefstruct{intord; //该通道在路径上的"序号"PosType seat; //通道块在迷宫中的"坐标位置"int di; //从此通道走向下以通道块的"方向"}SElemType; //栈的元素类型typedefstruct{SElemType * base;SElemType * top;intstacksize;}SqStack;/*函数原型说明*/Status InitStack(SqStack&S); //创建一个空栈SStatus Push(SqStack&S,SElemType&a); //插入新元素aStatus Pop(SqStack&S,SElemType&a); //删除栈顶元素，a返回其值Status StackEmpty(SqStack S); //检查是否空栈Status MazePath(int maze[12][12],SqStack&S, PosType start, PosType end); //找通路voidInitmaze(int maze[12][12],intx,int y); //初始化迷宫voidprintmaze(int maze[12][12],intx,int y); //显示迷宫Status Pass(int maze[12][12],PosTypeCurPos); //判断当前位置是否可通voidMarkfoot(int maze[12][12], PosTypeCurPos); //标记当前位置不可通PosTypeNextPos(PosTypeCurPos, intDir); //进入下一位置voidprintpath(int maze[12][12],SqStackS,intx,inty,PosTypestart,PosType end); //显示通路/*主函数*/void main (void){PosTypestart,end;int t=0;SqStack S;int maze[12][12];do{if(t!=0)printf("\n");for(int i=0;i<20;i++){printf("* ");}if(t==0){printf("\n*\t欢迎来到迷宫世界\t * \n");printf("*\t 1.设置迷宫\t\t * \n");}else{printf("\n* 请继续选择：\t\t\t * \n");printf("*\t 1.设置迷宫\t\t * \n");}printf("*\t 2.设置迷宫路径\t\t * \n");printf("*\t 3.输出迷宫通路路径\t * \n");printf("*\t 4.结束\t\t\t *\n");t++;for(int j=0;j<20;j++){printf("* ");}printf("\n");int s;printf("请选择：");scanf("%d",&s);intaa; intx,y;switch(s){case 1://1.初始化迷宫aa=1;printf("迷宫设置：请输入\n"); //设置迷宫大小do{printf("行X(x<10)=");scanf("%d",&x);printf("列Y(y<10)=");scanf("%d",&y);if(x<1 || x>10||y<1 || y>10){printf("输入错误!\n");}}while(x<1 || x>10||y<1 || y>10);Initmaze(maze,x,y); //初始化迷宫printmaze(maze,x,y); //显示所创建的迷宫break;case 2://寻找迷宫路径if(aa==1){aa=2; //设置入口和出口do{printf("输入入口行坐标:");scanf("%d",&start.row);if(start.row>x)printf("输入错误!\n");}while(start.row>x);do{printf("输入入口列坐标:");scanf("%d",&start.line);if(start.line>y)printf("输入错误!\n");}while(start.line>y);do{printf("输入出口行坐标:");scanf("%d",&end.row);if(end.row>x)printf("输入错误!\n");}while(end.row>x);do{printf("输入出口列坐标:");scanf("%d",&end.line);if(end.line>y)printf("输入错误!\n");}while(end.line>y);}elseprintf("请先初始化迷宫！\n");printf("\n所设置入口坐标为(%d,%d),出口坐标为(%d,%d).\n",start.row,start.line,end.row,end.line);break;case 3://输出此迷宫通路路径if(aa==2){aa=3;if(MazePath(maze,S,start,end)) //若有通路，显示通路printpath(maze,S,x,y,start,end);elseprintf("\n抱歉，找不到通路!\n\n");}elseprintf("请先初始化迷宫并寻找路径！\n");break;case 4:exit(0);break;default:exit(0);}}while(1);}/*若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中 */Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end){PosType curpos;int curstep;SElemType e;InitStack(S);curpos = start; // 设定"当前位置"为"入口位置curstep = 1; // 探索第一步do {if (Pass(maze,curpos)) // 当前位置可通过，即是未曾走到过的通道块{Markfoot(maze,curpos); // 留下足迹e.di =1;e.ord = curstep;e.seat= curpos;Push(S,e); // 加入路径if (curpos.row==end.row && curpos.line==end.line)return OK; // 到达终点（出口）curpos = NextPos(curpos, 1); // 下一位置是当前位置的东邻curstep++; // 探索下一步}else // 当前位置不能通过{if (!StackEmpty(S)){Pop(S,e);while (e.di==4 && !StackEmpty(S)){Markfoot(maze,e.seat); // 留下不能通过的标记，并退回一步Pop(S,e);}if (e.di<4){e.di++; // 换下一个方向探索Push(S, e);curpos = NextPos(e.seat, e.di); // 当前位置设为新方向的相邻块}}}} while (!StackEmpty(S));return ERROR;}/*初始化迷宫时间复杂度：n^2*/void Initmaze(int maze[12][12],int x,int y){char select;do{printf("创建方式 A:自动生成 B:手动创建\n");label: scanf("%c",&select);if(select=='a'||select=='A') //自动生成{for(int i=1;i<x+1;i++){for(int j=1;j<y+1;j++)maze[i][j]=rand()%2;}break;}else if(select=='b'||select=='B') //手动设置{printf("按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):\n",x,y);for(int i=1;i<x+1;i++){for(int j=1;j<y+1;j++)scanf("%d",&maze[i][j]);maze[i][y+1]=1;}for(i=0;i<x+2;i++)maze[x+1][i]=1;break;}else if(select=='\n')goto label; //排除Enter键的影响elseif(select!='b'||select!='B'||select!='a'||select!='A')printf("输入错误!\n");}while(select!='b'||select!='B'||select!='a'||select!='A');}/*显示迷宫时间复杂度：n^2*/void printmaze(int maze[12][12],int x,int y){printf("\n\n");printf("显示所建的迷宫(#表示墙):\n");printf("%c ",'#');printf("%c ",'y');for(int j=1;j<y+1;j++)printf("%d ",j);printf("%c ",'#');printf("\nx ");for(int i=1;i<y+3;i++)printf("%c ",'#');printf("\n");for(i=1;i<x+1;i++){if(i<x+1)printf("%d ",i);elseprintf("%c ",'#');printf("%c ",'#');for(int j=1;j<y+1;j++){printf("%d ",maze[i][j]);}printf("%c",'#');printf("\n");}for(i=0;i<y+3;i++)printf("%c ",'#');printf("\n");}/*输出路径时间复杂度：n^2*/void printpath(int maze[12][12],SqStack S,int x,int y,PosType start,PosType end) {printf("\n\n\001通路路径:\n");SElemType * p=S.base;while(p!=S.top){maze[p->seat.row][p->seat.line]=2; //标记为路径中的点p++;}printf("\001路径图为：\n");printf("%c ",'#');printf("%c ",'y');for(int j=1;j<y+1;j++)printf("%d ",j);printf("%c ",'#');printf("\nx ");for(int m=1;m<y+3;m++)printf("%c ",'#');printf("\n");for(int i=1;i<x+1;i++){if(i<x+1)printf("%d ",i);elseprintf("%c ",'#');printf("%c ",'#');for(int j=1;j<y+1;j++){if(maze[i][j]==2){if(i==start.row&&j==start.line||i==end.row&&j==end.line){if(i==start.row&&j==start.line)printf("i ");if(i==end.row&&j==end.line)printf("o ");}elseprintf("%c ",' ');}elseprintf("%c ",'#');}printf("%c ",'#');printf("\n");}for(i=0;i<y+3;i++)printf("%c ",'#');printf("\n\n");printf("\001路径线路为：\n");SqStack M;InitStack(M);SElemType a;while (!StackEmpty(S)){Pop(S,a);Push(M,a);}while (!StackEmpty(M)){Pop(M,a);printf("(%d,%d)",a.seat.row,a.seat.line);}printf("\n");printf("路径输出成功！\n");}/* 判断当前位置是否可通*/Status Pass(int maze[12][12],PosType CurPos){if(maze[CurPos.row][CurPos.line]==0)return OK; // 如果当前位置是可以通过，返回1 elsereturn ERROR; // 其它情况返回0}/* 标记当前位置不可通*/void Markfoot(int maze[12][12],PosType CurPos){maze[CurPos.row][CurPos.line]=1;}/*进入下一位置*/PosType NextPos(PosType CurPos, int Dir){PosType ReturnPos;switch (Dir){case 1:ReturnPos.row=CurPos.row;ReturnPos.line=CurPos.line+1;break;case 2:ReturnPos.row=CurPos.row+1;ReturnPos.line=CurPos.line;break;case 3:ReturnPos.row=CurPos.row;ReturnPos.line=CurPos.line-1;break;case 4:ReturnPos.row=CurPos.row-1;ReturnPos.line=CurPos.line;break;}return ReturnPos;}/*创建一个空栈S*/Status InitStack(SqStack &S){S.base=(SElemType *)malloc(100*sizeof(SElemType));if(!S.base)return ERROR;S.top=S.base;S.stacksize=100;return OK;}/*插入新元素a*/Status Push(SqStack &S,SElemType &a){*S.top++=a;return OK;}/* 删除栈顶元素，a返回其值*/Status Pop(SqStack &S,SElemType &a){if(S.top==S.base)return ERROR;a=*--S.top;return OK;}/*检查是否空栈*/Status StackEmpty(SqStack S){if(S.top==S.base)return OK;return ERROR;}。
