迷宫求解课程设计报告.doc

资源描述

数据结构实验报告题目：迷宫问题姓名学号任务分配孙盛 20084045048 问题分析罗剑 20084045042 代码实现杨滢钢 20084045045 论文编写一．需求分析 1．以结构体Maze表示迷宫，其中BuideMaze调用建立迷宫；Seat用来记录迷宫坐标；SqTack用来记录当前路径；数组；SElemType表示当前位置； Display用于显示栈中所有元素；BuideMaze用于根据用户要求建立一个迷宫地图。 2．本程序根据需要产生一个迷宫，0表示有障碍，1表示通路；MazePath为求解迷宫。 3．迷宫的入口为左上角，出口为右下角。 4．本程序只求出一条成功的通路。二．概要设计为了实现上述操作，以栈为存储结构。本程序包含三个模块：（1）主程序模块:实现人机交互。（2）迷宫生产模块：根据需要产生一个迷宫模型。（3）路径查找模块：实现通路的查找。（4）求解迷宫中一条通路的伪代码： do{ 若当前位置可同，则{ 将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东临方块为新的当前位置； } 否则{ 若栈不空且栈顶位置尚有其他方向未被探索，则设定新的的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通，则{ 删去栈顶位置；若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空。 } } } while(栈不空) 三．详细分析与源程序 #include<iostream.h> #include <stdlib.h> #include<iomanip.h> #define STACK_INIT_SIZE 100 //初始栈大小 #define STACKINCREAMENT 10 //添加栈的长度 #define SIZE_OF_MAPH 20 //迷宫高度 #define SIZE_OF_MAPW 20 //迷宫长度 // MazeCell功能：用来描述迷宫组成单元的信息 typedef struct { int Pass; // Pass: 当Pass为1时，表示导通块；为0则表示障碍块； bool Footprint; // Footprint: 当 Footprint为1时，表示留下足迹，反之，表示未经此地。 }MazeCell; // SElemType功能：此为栈的元素，用来表示当前位置，（栈用来描述当前路径） typedef struct { int ord; // ord: 通道块的序号 int x; // x : 当前位置的横坐标 int y; // y : 当前位置的纵坐标 int di; // di : 搜索方向 1向东，2向南，3向西，4向北 }SElemType; // SqTack功能：此为栈，用来记录当前路径 typedef struct { SElemType *base; // *base 栈底指针，指向起点 SElemType *top; // *top 栈顶指针，指向路径的末点 int stacksize; // stacksize 栈的容量 }SqStack; // Seat功能：用来记录迷宫坐标，此结构体为中间变量，纯粹为方便编程而建立 typedef struct { int x; // x: 用来记录横坐标 int y; // y: 用来记录纵坐标 }Seat; // InitStack功能：此函数用于初始化一个栈 bool InitStack(SqStack &S) // 函数参数： SqStack &S { // 函数返回值类型： bool S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) { return 0; } S.top=S.base; S.stacksize=STACK_INIT_SIZE; return 0; } // BuideMaze功能：此函数的功能是用于根据用户要求建立一个迷宫地图，将用户输入的// 整形数组形状给迷宫数组 // 函数参数： MazeCell Map[SIZE_OF_MA[SIZE_OF_MAP] // Seat &start 起点坐标 // Seat &end 终点坐标 // 函数返回值类型： bool 建立成功则返回1，反之返回0。 Void BuideMaze(MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW],int ma[SIZE_OF_MAPH][SIZE_OF_MAPW]) { for(int i=0;i<SIZE_OF_MAPH;i++) { for(int j=0;j<SIZE_OF_MAPW;j++) { Map[i][j].Pass=ma[i][j]; Map[i][j].Footprint=0; } } } // Pass功能：此函数用于判断当前点是否可通，如果可通则返回1，反之返回0。 bool Pass(Seat curpos,MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW]) { // 参数Seat curpos 当前块的坐标， // MazeCell Map[SIZE_OF_MAP][SIZE_OF_MAP] 迷宫地图 // 函数返回值类型： bool 若当前块可通则返回1，反之则返回0。 if(Map[curpos.x][curpos.y].Pass==0) { return 0; } else if(Map[curpos.x][curpos.y].Footprint==1) { return 0; } else { return 1; } } // FootPrint功能：此函数用于在当前路径下留下脚印。 // Seat curpos 当前坐标 // MazeCell Map[SIZE_OF_MAP][SIZE_OF_MAP] 迷宫地图 // 函数返回值类型：无 void FootPrint(Seat curpos,MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW]) { Map[curpos.x][curpos.y].Footprint=1; } bool Push(SqStack &S,SElemType e)//栈插入函数 { if(S.top-S.base>=S.stacksize) { S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(SElemType)); if(!S.base) { return 0; } S.top=S.base+S.stacksize; S.stacksize=S.stacksize+STACKINCREAMENT; } *S.top++=e; return 1; } bool Pop(SqStack &S,SElemType &e)//栈取出最上面的元素，将值给e { if(S.base==S.top)return false; S.top--; e=*S.top; return true; } // NextPos功能：此函数用于将坐标为x,y位置的di方向位置切换为当前位置。 // Seat curpos 当前坐标， int di 方向，int x,y 坐标，函数返回值类型：无 void NextPos(int x,int y,Seat &curpos,int di) { if(di==1) { curpos.y=y+1; curpos.x=x; } else if(di==2) { curpos.x=x+1; curpos.y=y; } else if(di==3) { curpos.y=y-1; curpos.x=x; } else if(di==4) { curpos.x=x-1; curpos.y=y; } } // PutIn功能：向数组里输入元素 // int map[] 将得到的数组给map, int Wei 迷宫的长度, int Hig 迷宫的高度,返回值类型：无 void PutIn(int map[],int &Wei,int &Hig) { int w,h; cout<<"如果您想输入的迷宫大于所规定的大小，您只需修改SIZE_OF_MAPH和SIZE_OF_MAP"<<endl; cout<<"请输入迷宫的长度(长度小于等于"<<SIZE_OF_MAPW-2<<")："; cin>>w; cout<<"请输入迷宫的高度(高度小于等于"<<SIZE_OF_MAPW-2<<")："; cin>>h; cout<<"1表示导通块；0表示障碍块"<<endl; Wei=w; Hig=h; for(int i=0;i<SIZE_OF_MAPH;i++) for(int j=0;j<SIZE_OF_MAPW;j++) *(map+i*SIZE_OF_MAPW+j)=0; for(int is=1;is<h+1;is++) { cout<<"请输入第"<<is<<"行:"; for(int js=1;js<w+1;js++) { int point; cin>>point; *(map+is*SIZE_OF_MAPW+js)=point; } cout<<endl; } } // Display功能：用于显示栈中所有元素 void Display(SqStack S) { int i=1; SElemType *p; p=S.base; cout<<"从base到top:"<<endl; cout<<"di搜索方向:di=1向东，di=2向南，di=3向西，di=4向北"<<endl; while(p!=S.top) //从base到top打印元素 { cout<<"第"<<i<<"步: "; cout<<"("<<(*p).y; cout<<","<<(*p).x; cout<<","<<(*p).di<<")"<<endl; p++; i++; } } void DisplayMaze(int ma[SIZE_OF_MAPH][SIZE_OF_MAPW],int w,int h) { cout<<"迷宫为(1代表可以通过；0代表不可以通过): "<<endl; for(int i=0;i<h+2;i++) { for(int j=0;j<w+2;j++) { cout<<ma[i][j]<<" "; } cout<<endl; } cout<<endl; } // MazePath功能：组织所有子函数，求解迷宫 // 函数返回值类型： int 迷宫有解则返回1，反之则返回0； int MazePath(MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW],Seat start,Seat end) { SElemType e; SqStack S; //定义一个栈 InitStack(S); //初始化栈 Seat curpos; //定义当前位置 int curstep; //计步器 curstep=1; //计步器计1 curpos.x=start.x; // curpos.y=start.y; //当前位置设为起点 cout<<"起点是:"<<start.y<<" "<<start.x<<endl; cout<<"终点是:"<<end.y<<" "<<end.x<<endl; /////////////////////////////////////////////////////////////////////////// // // 下面的循环是求解迷宫的核心程序 //////////////////////////////////////////////////////////////////////////// do { if(Pass(curpos,Map)) //如果当前块可通，则进行如下操作 { FootPrint(curpos,Map); //留下脚印 e.ord=curstep; //记下计步器 e.x=curpos.x; //记下行数 e.y=curpos.y; //记下列数 e.di=1; //设一个方向为东方 Push(S,e); //压栈操作，将当前位置纳入当前路径 if(curpos.x==end.x&&curpos.y==end.y) //如果当前块为终点，进行如下操作 { // cout<<"ok!"; // Display(S); //调用显示栈的子程序显示结果 return 1; //函数返回1 } // else //如果当前位置不是终点，进行如下操作 { // NextPos(curpos.x,curpos.y,curpos,1); //切换东方向的位置为当前位置 curstep++; //计步器自增1 } }//if else { if(S.base!=S.top) //如果当前块不通，且栈不为空（说明还有解） { Pop(S,e); //将栈顶元素弹出进行观察 while(e.di==4&&(S.top-S.base)) //如果栈顶元素四方均不通 { Pop(S,e); //弹出下一个栈顶元素进行观察 }//while if(e.di<4) //如果栈顶元素还有其他方向没有走过 { // e.di++; //切换下一个方向为当前方向 Push(S,e); //压入栈 NextPos(e.x,e.y,curpos,e.di); //切换下一个方向位置为当前位置 }//if }//if }//else }while(S.base!=S.top); //只要栈不空则说明有解，重复循环 cout<<"没找到路径"<<endl; return 0; } // main功能：组织所有子函数，求解迷宫 // 函数返回值类型： bool 迷宫有解则返回1，反之则返回0； void main() { MazeCell Map[SIZE_OF_MAPH][SIZE_OF_MAPW]; //定义一个迷宫数组 /*int migong[SIZE_OF_MAPH][SIZE_OF_MAPW]= { { 0,0,0,0,0,0,0,0,0,0}, { 0,1,1,0,0,0,0,0,0,0}, //1 { 0,0,1,1,1,0,1,1,1,0}, //2 { 0,0,1,0,1,1,1,0,1,0}, //3 { 0,0,1,0,0,0,0,0,1,0}, //4 { 0,0,1,0,1,1,1,0,0,0}, //5 { 0,0,1,1,1,0,1,1,1,0}, //6 { 0,0,0,0,0,0,0,0,0,0}, }; //以数组表示的迷宫*/ int w,h; int migong[SIZE_OF_MAPH][SIZE_OF_MAPW]; PutIn(migong[0],w,h); BuideMaze(Map,migong); //调用建立迷宫的子函数 DisplayMaze(migong,w,h); //显示迷宫的形状 Seat start,end; //定义当前位置，起点位置，终点位置的结构体 /*start.x=1; //起点 start.y=1; // end.x=2; //终点 end.y=2; //*/ cout<<"起点横坐标:"; cin>>start.y; cout<<"起点纵坐标:"; cin>>start.x; cout<<"终点横坐标:"; cin>>end.y; cout<<"终点纵坐标:"; cin>>end.x; MazePath(Map,start,end); } 四．运行结果分析五. 课设设计总结通过数据结构课程设计，使我们更好的了解了数据结构这门课程，以及对问题过程的思考，程序调试，都有很好的帮助。此次课程设计中，我们遇到了很多困难，但最终通过我们三个人共同的努力，最后还是完成了任务，使我们更好的了解了团队的重要性。

展开阅读全文