迷宫寻路数据结构栈实现 #include <iostream> using std::c

文件名称: 迷宫寻路数据结构栈实现

所属分类: C

开发工具:

文件大小: 8kb

下载次数: 0

上传时间: 2009-05-22

提供者: k3st*****

下载 (8kb)

不能下载？报告错误

详细说明： #include using std::cout; using std::cin; #include #include #include #define OVERFLOW -2 #define INIT_SIZE 100 //存储空间初始分配量 #define INCREMENT 10 //存储空间分配增量 typedef struct{ int r; int c; }PostType;//迷宫中r行c列的位置 typedef struct{ int ord; //当前位置在路径上的序号 PostType seat;//当前坐标 int di; //往下一坐标的方向 }SElemType; //栈元素类型 typedef struct{ SElemType* base;//栈基址,构造前销毁后为空 SElemType* top;//栈顶 int stackSize; //栈容量 }Stack; //栈类型 int InitStack(Stack &S){ //构造空栈s S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType)); if(!S.base) exit(OVERFLOW);//存储分配失败 S.top=S.base; S.stackSize=INIT_SIZE; return 0; } int StackEmpty(Stack S)//若s为空返回TRUE,否则返回FALSE { if(S.top==S.base) return 1; return 0; } int Push(Stack &S,SElemType e){ //插入元素e为新的栈顶元素 if(S.top-S.base >=S.stackSize){//栈满，加空间 S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); //存储分配失败 S.top=S.base+S.stackSize; S.stackSize+=INCREMENT; } *S.top++=e; return 1; } int Pop(Stack &S,SElemType &e){//若栈不空删除栈，顶元素用e返回 if(S.top==S.base) return 0; e=*--S.top; return 1; } int DestroyStack(Stack &S){//销毁栈S, free(S.base); S.top=S.base; return 1; } #define MAXLEN 16//迷宫包括外墙最大行列数目 typedef struct{ int r; int c; char adr[MAXLEN][MAXLEN]; }MazeType; //迷宫类型 int InitMaze(MazeType &maze){ //初始化迷宫若成功返回TRUE,否则返回FALSE int i,j; cout<<"输入迷宫尺寸（长和宽）: "; cin>>maze.r>>maze.c; //迷宫行和列数 for(i=0;i<=maze.c+1;i++){//迷宫行外墙 maze.adr[0][i]='#'; maze.adr[maze.r+1][i]='#'; } for(i=0;i<=maze.r+1;i++){//迷宫列外墙 maze.adr[i][0]='#'; maze.adr[i][maze.c+1]='#'; } for(i=1;i<=maze.r;i++) for(j=1;j<=maze.c;j++) maze.adr[i][j]=' ';//初始化迷宫 int m=1,n=maze.c; for(m;m<8;m++) maze.adr[2][m]='#'; for(n;n>1;n--) maze.adr[6][n]='#'; maze.adr[4][5]='#'; maze.adr[4][6]='#'; maze.adr[3][3]='#'; maze.adr[3][2]='#'; maze.adr[5][7]='#'; maze.adr[5][6]='#'; maze.adr[8][3]='#'; maze.adr[7][2]='#'; maze.adr[7][5]='#'; return 1; }//InitMaze int Pass(MazeType maze,PostType curpos){ if(maze.adr[curpos.r][curpos.c]==' ') return 1; else return 0; }//Pass int FootPrint(MazeType &maze,PostType curpos){ //若走过并且可通返回TRUE,否则返回FALSE //在返回之前销毁栈S maze.adr[curpos.r][curpos.c]='!';//"*"表示可通 return 1; }//FootPrint PostType NextPos(PostType &curpos,int i){ //指示并返回下一位置的坐标 PostType cpos; cpos=curpos; switch(i){ case 1 : cpos.c+=1; break; case 2 : cpos.r+=1; break; case 3 : cpos.c-=1; break; case 4 : cpos.r-=1; break; default: exit(0); } return cpos; }//Nextpos int MarkPrint(MazeType &maze,PostType curpos){ maze.adr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通 return 1; } int MazePath(MazeType &maze,PostType start,PostType end){ //若迷宫maze存在从入口start到end的通道则求得一条存放在栈中 Stack S; PostType curpos; int curstep;//当前序号,1.2.3.4分别表示东,南,西,北方向 SElemType e; InitStack(S); curpos=start; //设置"当前位置"为"入口位置" curstep=1; //探索第一步 do{ if(Pass(maze,curpos)){//当前位置可以通过,即是未曾走到过的通道 FootPrint(maze,curpos);//留下足迹 e.ord=curstep; e.seat=curpos; e.di=1; Push(S,e); //加入路径 if(curpos.r==end.r&& curpos.c==end.c) if(!DestroyStack(S))//销毁失败 exit(OVERFLOW); else return 1; //到达出口 else{ curpos=NextPos(curpos,1); //下一位置是当前位置的东邻 curstep++; //探索下一步 } } else{ //当前位置不通 if(!StackEmpty(S)){ Pop(S,e); while(e.di==4 && !StackEmpty(S)){ MarkPrint(maze,e.seat); Pop(S,e); //留下不能通过的标记,并退一步 } if(e.di < 4){ e.di++;//换下一个方向探索 Push(S,e); curpos=NextPos(e.seat,e.di);//设定当前位置是该新方向上的相邻位置 } } } }while(!StackEmpty(S)); if(!DestroyStack(S))//销毁失败 exit(OVERFLOW); else return 0; }//MazePath void PrintMaze(MazeType &maze){ //将标记路径信息的迷宫输出 int i,j; cout<<"\n——!为所求迷宫路线路线——:\n\n"; cout<<" "; for(i=0;i<=maze.r+1;i++)//打印列数名 cout<<" "<>start.r>>start.c; if(start.r>maze.r || start.c>maze.c){ cout<<"\n越界!!!\n"; continue; } }while(start.r>maze.r || start.c>maze.c); do{ cout<<"\n输入结束点坐标: "; cin>>end.r>>end.c; if(end.r>maze.r || end.c>maze.c){ cout<<"\n越界!!!\n"; continue; } }while(end.r>maze.r || end.c>maze.c); if(!MazePath(maze,start,end)) cout<<"\n不能求得路径!\n"; else PrintMaze(maze); cout<<"\n是否继续?(y/n): "; cin>>cmd; }while(cmd=='y' || cmd=='Y'); } ...展开收缩

(系统自动生成,下载前可以参看下载内容)