2022年迷宫算法集锦 .pdf

《2022年迷宫算法集锦 .pdf》由会员分享，可在线阅读，更多相关《2022年迷宫算法集锦 .pdf（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include#include typedef enum ERROR,OK Status;typedef struct int row;/row 表示行号int line;/line 表示列号PosType;/位置的元素类型typedef struct int ord;/该通道在路径上的 序号 PosType seat;/通道块在迷宫中的 坐标位置 int di;/从此通道走向下以通道块的方向 SelemType;/栈的元素类型typedef struct SelemType*base;SelemType*top;int stacksize;SqStack;/*创建一个空栈 S*/Statu

2、s InitStack(SqStack&S)S.base=(SelemType*)malloc(100*sizeof(SelemType);if(!S.base)return ERROR;S.top=S.base;S.stacksize=100;return OK;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 29 页 -/*插入新元素 a*/Status Push(SqStack&S,SelemType&a)*S.top+=a;return OK;/*删除栈顶元素，a 返回其值*/Status Pop(SqStack&S,SelemType&a)if(S.top=S.base

3、)return ERROR;a=*-S.top;return OK;/*检查是否空栈*/Status StackEmpty(SqStack S)if(S.top=S.base)return OK;else return ERROR;void Initmaze(int maze1212,int size)char select;printf(选择创建方式A:自动生成B:手动创建 n);label:scanf(%c,&select);if(select=a|select=A)/自动生成 for(int i=0;isize+2;i+)maze0i=1;for(i=1;isize+1;i+)mazei

4、0=1;for(int j=1;jsize+1;j+)mazeij=rand()%2;mazeisize+1=1;for(i=0;isize+2;i+)mazesize+1i=1;else if(select=b|select=B)/手动设置名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 29 页 -printf(按行输入%d*%d 数据,0 代表可通,1 代表不可通(每行以 Enter 结束):n,size,size);for(int i=0;isize+2;i+)maze0i=1;for(i=1;isize+1;i+)mazei0=1;for(int j=1;jsize+1;

5、j+)scanf(%d,&mazeij);mazeisize+1=1;for(i=0;isize+2;i+)mazesize+1i=1;else if(select=n)goto label;/排除 Enter键的影响else printf(输入错误!);/*显示迷宫*/void printmaze(int maze1212,int size)printf(nn);printf(显示所建的迷宫(#表示外面的墙):n);for(int i=0;isize+2;i+)printf(%c,#);printf(n);for(i=1;isize+1;i+)printf(%c,#);for(int j=1

6、;jsize+1;j+)printf(%d,mazeij);printf(%c,#);printf(n);for(i=0;iseat.rowp-seat.line=2;/标记为路径中的点p+;for(int i=0;isize+2;i+)printf(%c,#);printf(n);for(i=1;isize+1;i+)printf(%c,#);for(int j=1;jsize+1;j+)if(mazeij=2)printf(%c,0);else printf();printf(%c,#);printf(n);for(i=0;isize+2;i+)printf(%c,#);printf(nn

7、);/*判断当前位置是否可通*/Status Pass(int maze1212,PosType CurPos)if(mazeCurPos.rowCurPos.line=0)return OK;/如果当前位置是可以通过，返回1 else return ERROR;/其它情况返回 0 /*标记当前位置不可通*/void Markfoot(int maze1212,PosType CurPos)mazeCurPos.rowCurPos.line=1;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 29 页 -/*进入下一位置*/PosType NextPos(PosType CurP

8、os,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.ro

9、w=CurPos.row-1;ReturnPos.line=CurPos.line;break;return ReturnPos;/*若迷宫maze 中从入口start 到出口end 的通道，则求得一条存放在栈中*/Status MazePath(int maze1212,SqStack&S,PosType start,PosType end)PosType curpos;int curstep;SelemType e;InitStack(S);curpos=start;/设定当前位置 为入口位置名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 29 页 -curstep=1;/探

10、索第一步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&!Stack

11、Empty(S)Markfoot(maze,e.seat);/留下不能通过的标记，并退回一步Pop(S,e);if(e.di4)e.di+;/换下一个方向探索Push(S,e);curpos=NextPos(e.seat,e.di);/当前位置设为新方向的相邻块 while(!StackEmpty(S);return ERROR;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 29 页 -void main()SqStack S;int size=0;/正方形迷宫尺寸int maze1212;/存储迷宫内路径可通情况for(int n=0;n10;n+)printf(创建一个正方

12、形迷宫，请输入迷宫尺寸(注意不要大于 10):n);/设置迷宫大小scanf(%d,&size);if(size10)printf(输入错误!);return;Initmaze(maze,size);/初始化迷宫printmaze(maze,size);/显示所创建的迷宫PosType start,end;/设置入口和出口printf(输入入口行坐标和列坐标:);scanf(%d,&start.row);scanf(%d,&start.line);printf(输入出口行坐标和列坐标:);scanf(%d,&end.row);scanf(%d,&end.line);if(MazePath(ma

13、ze,S,start,end)/若有通路，显示通路printpath(maze,S,size);else printf(找不到通路!nn);名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 29 页 -一、需求分析1.选题理由本次课设我选择了迷宫问题，迷宫求解是数据结构课程的一个经典问题，迷宫问题要求寻找一条从入口到出口的路径。通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫通路的算法中要应用“栈”的思想。对于栈的内容在整个学期的学习中我也有了一定的了解，所以选择了迷宫这一经典问题作为本次课设

14、的内容。2.基本原理分析迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。3.功能要求（1）以一个二维数组Mazem+2n+2 表示迷宫，其中：Maze0j和Mazem+1j(0

15、=j=n+1)及 Mazei0和 Mazein+1(0=i=m+1)为做外层的一圈障碍。数组中以0 表示通路，1 表示障碍，限定迷宫的大小为：m,n=10。（2）用户需用文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数 m和列数 n；从第 2 行至第 m+1行（每行 n 个数）为迷宫值，用0，1 输入，同行中的两个数字之间用空白字符相隔。（3）迷宫的入口位置和出口位置可由用户随时设定。（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件上，其中字符“#”表示障碍，“*”表示路径，“”表示曾途经该位置但不能到达出口，其余位置用空格符表示。若设定迷宫不存在通路则报告相

16、应信息（5）本程序只求出一条成功的通路。（6）程序执行的命令为：1，创建迷宫；2，求解迷宫；3，输出迷宫的解。二、详细设计源程序:#include#include#include#define MAXLEN 10/迷宫包括外墙最大行列数目#define TRUE 1 名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 29 页 -#define FALSE 0#define OK 1#define ERROR 0 typedef int Status;/坐标位置类型typedef struct int r,c;PosType;/迷宫中 r 行 c 列的位置/迷宫类型typedef s

17、truct int r;int c;char arrMAXLENMAXLEN;/可取,*,#MazeType;typedef struct/int step;/当前位置在路径上的“序号”PosType seat;/当前的坐标位置 int di;/往下一坐标位置的方向SElemType;/结点类型typedef struct NodeType SElemType data;NodeType*next;NodeType,*LinkType;/栈类型typedef struct LinkType top;int stacksize;SqStack;PosType start;PosType end;

18、MazeType maze;bool found;/创建栈Status InitStack(SqStack&S)S.top=(LinkType)malloc(sizeof(NodeType);名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 29 页 -S.top-next=NULL;S.stacksize=0;return OK;/进栈Status Push(SqStack&S,SElemType&e)LinkType p;p=(NodeType*)malloc(sizeof(NodeType);p-data=e;p-next=S.top;S.top=p;S.stacksize+

19、;return OK;/判断是否为栈空Status StackEmpty(SqStack S)if(S.top-next=NULL)return OK;return ERROR;/出栈Status Pop(SqStack&S,SElemType&e)LinkType p;if(StackEmpty(S)return ERROR;p=S.top;e=p-data;S.top=S.top-next;S.stacksize-;free(p);return OK;/销毁栈Status DestroyStack(SqStack&S)LinkType p;while(S.top!=NULL)p=S.top

20、;名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 29 页 -S.top=S.top-next;free(p);/一个一个删除 if(S.top=NULL)return OK;else return ERROR;/曾走过但不是通路标记并返回OK Status MarkPrint(MazeType&maze,PosType curpos)maze.arrcurpos.rcurpos.c=;/表示曾走过但不通 return OK;/曾走过而且是通路标记并返回OK Status FootPrint(MazeType&maze,PosType curpos)maze.arrcurpos

21、.rcurpos.c=*;/*表示可通 return OK;/选择下一步的方向PosType NextPos(PosType&curpos,int i)PosType cpos;cpos=curpos;switch(i)/1.2.3.4分别表示东,南,西,北方向 case 1:cpos.c+=1;break;case 2:cpos.r+=1;break;case 3:cpos.c-=1;break;case 4:cpos.r-=1;break;return cpos;/判断当前位置是否可通Status Pass(MazeType&maze,PosType curpos)if(maze.arrc

22、urpos.rcurpos.c=)return TRUE;else return FALSE;名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 29 页 -/创建迷宫/按照用户输入的二维数组（0 或 1），设置迷宫 maze的初值，包括加上边缘一圈的值void InitMaze(MazeType&maze,char aMAXLENMAXLEN,int row,int col)maze.r=row;maze.c=col;for(int i=0;i=col+1;i+)a0i=1;arow+1i=1;for(i=0;i=row+1;i+)ai0=1;aicol+1=1;for(i=0;

23、i=maze.r+2;i+)for(int j=0;jmaze.c+2;j+)if(aij=1)maze.arrij=#;else maze.arrij=;/求迷宫路径的伪码算法：Status MazePath(MazeType&maze,PosType start,PosType end)/求解迷宫 maze中，从入口 start到出口 end 的一条路径，若存在，返回TRUE,否则返回 FALSE PosType curpos;SqStack S;SElemType e;InitStack(S);curpos=start;/设定“当前位置”为“入口位置”/curstep=1;/探索第一步

24、found=false;do if(Pass(maze,curpos)/当前位置可以通过，即是未曾走到过的通道块留下足迹名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 29 页 -FootPrint(maze,curpos);/做可以通过的标识/e.step=curstep;e.seat=curpos;e.di=1;/为栈顶元素赋值 Push(S,e);/加入路径 if(curpos.r=end.r&curpos.c=end.c)found=true;/如果到达终点返回 true else curpos=NextPos(curpos,1);/下一位置是当前位置的东邻 else

25、/当前位置不能通过 if(!StackEmpty(S)Pop(S,e);while(e.di=4&!StackEmpty(S)MarkPrint(maze,e.seat);/留下不能通过的标记 Pop(S,e);if(e.di4)e.di+;/换下个方向 Push(S,e);/curpos=NextPos(e.seat,e.di);/进行探索 while(!StackEmpty(S)&!found);DestroyStack(S);return found;/将标记路径信息的迷宫（字符型方阵）输出到终端(包括外墙)void PrintMaze(MazeType&maze)for(int i=0

26、;i=maze.r+2;i+)for(int j=0;j=2)if(ncnum)m+;n=1;a2mn=datai;n+;i+;fclose(fp);InitMaze(maze,a2,rnum,cnum);printf(n迷宫建立完成！n);break;case m:printf(n请输入迷宫入口的坐标，以空格为间隔:-);scanf(%d%d,&start.r,&start.c);printf(n请输入迷宫出口的坐标，以空格为间隔:-);scanf(%d%d,&end.r,&end.c);MazePath(maze,start,end);break;名师资料总结-精品资料欢迎下载-名师精心整

27、理-第 15 页，共 29 页 -case p:if(found)printf(n求解迷宫的结果如下-n);PrintMaze(maze);else printf(n找不到路径！n);void main()char cmd;Initialization();do ReadCommand(cmd);/读入一个操作符命令 Interpre(cmd);/解释执行命令操作符while(cmd!=q);名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 29 页 -三、调试分析及测试1、调试分析：（1）本程序有一个核心算法，即求迷宫的路径，在调试的时候，出现了两个问题：没有想到要用 记号，导

28、致迷宫走不出来；没有设置found，不知何时跳出。（2）原本栈的元素 e 中除了 di 往下一坐标位置的方向和seat 当前的坐标位置，还有一个step 当前位置在路径上的序号，后来发现step 没什么用，就删掉了。（3）函数 ReadCommand 中，cmd=getchar();的位置找不准，最后是试出来的。（4）调试的时候多次出现，没有错误，但是dos 环境下就是执行不起来，所以采用了一些输出变量，判断到底是哪里出了问题。（5）本程序中三个主要的算法：InitMaze，MazePath和 MarkPrint的时间复杂度均为 O（m*n）,本程序的空间复杂度也为O（m*n）（栈所占最大空间

29、）2、使用说明和运行结果：（1）首先以文件形式输入迷宫数据，如图三：图三（2）进入演示程序后，会出现以下界面如图四：图四（3）进入“创建迷宫”的命令后，即提示输入迷宫数据的文件名，结束符为“回车符”，该命令执行之后输出“迷宫建立完成”，且输出下面可执行的操作。如图五：名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 29 页 -图五（4）进入“执行迷宫”的命令后，即提示输入迷宫入口，出口的坐标，结束符为“回车符”，该命令执行之后表示迷宫路径已寻找完成或未找到路径。请注意：若迷宫中存在路径，执行此命令后，迷宫状态已经改变，若要重复执行此命令，需重新输入迷宫数据。如图六：图六（5）进

30、入“输出迷宫”的命令后，即输出迷宫求出路径之后的状态。#表示障碍，表示曾走过但不通，*表示路径。如图七：名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 29 页 -图七（6）进入“退出”的命令后，按任意键结束。如图八：图八3.本程序包括三个模块1)主程序模块：void main()初始化；do 接受命令;处理命令;名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 29 页 -while(命令!=”退出”)；2)栈模块-实现栈的抽象数据类型3）迷宫模块-实现迷宫抽象数据类型各个模块之间的调用关系如下：主程序模块-迷宫模块 -栈模块三详细设计1.坐标位置类型typed

31、ef struct PosType/定义坐标 int x;/当前横坐标int y;/当前纵坐标PosType;2.迷宫类型int Maze;/迷宫存放在一个数字型数组中int MazePath(int mazeNN,PosType start,PosType end,LinkStack&stack,int n1,int n2)/求解迷宫maze中，从入口Start 到出口 end 的一条路径 stack=NULL;SElemType e;PosType curpos;InitStack(stack);/初始化 stack curpos.x=start.x;/设定当前位置为入口位置curpos.

32、y=start.y;int curstep=1;/探索第一步do if(Pass(curpos,maze,n1,n2)=1)/当前位置可通 FootPrint(curpos,maze);/留下足迹e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=1;Push(stack,e);/加入路径，入栈if(curpos.x=end.x&curpos.y=end.y)/到达出口位置return 1;else NextPos(curpos,1);/探索下一步curstep+;名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 29 页

33、 -/if else/当前位置不能通过 if(!StackEmpty(stack)Pop(stack,e);while(e.di=4&!StackEmpty(stack)MarkPrint(e.seat,maze);/留下不能通过的标记，并退回一步Pop(stack,e);/while if(e.di4)/换下一个方向探索 e.di+;Push(stack,e);NextPos(e.seat,e.di);/设当前位置是该新方向上的相邻块，1 代表向右，2 代表向下，3 代表向左，4 代表向上。curpos.x=e.seat.x;curpos.y=e.seat.y;while(!StackEmp

34、ty(stack);return 0;void InitMaze(int MazeNN,int r,int c)/初始化迷宫 printf(请输入迷宫(以 0表示可走,1 表示有障碍)：n);/按照用户要求输入一二维数组来表示迷宫for(int i=0;ir;i+)for(int j=0;jnext=NULL;return 1;void DestroyStack(LinkStack&S)LinkStack q;if(S!=NULL)while(S-next!=NULL)/如果栈非空，则释放空间 q=S-next;if(S-next-next!=NULL)S-next=S-next-next;e

35、lse S-next=NULL;free(q);free(S);S=NULL;名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 29 页 -void ClearStack(LinkStack&S)LinkStack q;if(S!=NULL)while(S-next!=NULL)/如果栈非空，则释放空间 q=S-next;if(S-next-next!=NULL)S-next=S-next-next;else S-next=NULL;free(q);int StackEmpty(LinkStack S)if(S!=NULL)/判断栈是否存在 if(S-next=NULL)retu

36、rn 1;return 0;int StackLength(LinkStack S)int m=0;LinkStack q=S;if(S!=NULL)/判断栈是否存在 if(q-next!=NULL)/判断栈是否为空 while(q-next!=NULL)+m;名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 29 页 -q=q-next;return m;return 0;int GetTop(LinkStack S,SElemType&e)LinkStack q=S;if(S!=NULL)/判断栈是否存在 if(q-next!=NULL)/判断栈是否为空 while(q-ne

37、xt!=NULL)q=q-next;e=q-SItem;return 1;return 0;/如果不能得到数据元素，则返回0(false)int Push(LinkStack&S,SElemType e)LinkStack q=S;LinkStack m=(LinkStack)malloc(sizeof(SNode);/通过 malloc 函数分配空间if(S!=NULL)while(q-next!=NULL)q=q-next;m-SItem=e;m-next=NULL;q-next=m;return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 24 页，共 29 页 -int Po

38、p(LinkStack&S,SElemType&e)LinkStack q=S;if(S!=NULL)if(q-next!=NULL)/若栈不是空的 while(q-next-next!=NULL)q=q-next;e=q-next-SItem;q-next=NULL;return 1;return 0;int StackTraverse(LinkStack S)/依次输出从栈底到栈顶的每个元素 if(S!=NULL)LinkStack q=S;if(q-next!=NULL)/若栈不是空的 printf(n 依次输出从栈底到栈顶的每个元素为：n);while(q-next!=NULL)q=q

39、-next;printf(%d,q-SItem);printf(n);return 1;return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 25 页，共 29 页 -3.求解迷宫路径的代码int MazePath(int mazeNN,PosType start,PosType end,LinkStack&stack,int n1,int n2)/求解迷宫maze中，从入口Start 到出口 end 的一条路径 stack=NULL;SElemType e;PosType curpos;InitStack(stack);/初始化 stack curpos.x=start.x;/

40、设定当前位置为入口位置curpos.y=start.y;int curstep=1;/探索第一步if(Pass(curpos,maze,n1,n2)!=1)/判断初始方块是否是障碍物return 0;else do if(Pass(curpos,maze,n1,n2)=1)/当前位置可通 FootPrint(curpos,maze);/留下足迹e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=1;Push(stack,e);/加入路径，入栈if(curpos.x=end.x&curpos.y=end.y)/到达出口位置return 1

41、;else NextPos(curpos,1);/探索下一步curstep+;/if else/当前位置不能通过 if(!StackEmpty(stack)Pop(stack,e);while(e.di=4&!StackEmpty(stack)MarkPrint(e.seat,maze);/留下不能通过的标记，并退回一步Pop(stack,e);/while if(e.di4)/换下一个方向探索名师资料总结-精品资料欢迎下载-名师精心整理-第 26 页，共 29 页 -e.di+;Push(stack,e);NextPos(e.seat,e.di);/设当前位置是该新方向上的相邻块curpos

42、.x=e.seat.x;curpos.y=e.seat.y;while(!StackEmpty(stack);return 0;4.主函数和其他函数的代码void main()int m,n;int mazeNN=0;LinkStack S;PosType start,end;int cmd;for(int i;i+)printf(n-n);printf(1.创建迷宫:n);printf(2.退出n);printf(-n);printf(请输入选择：n);scanf(%d,&cmd);switch(cmd)case 1:printf(请输入迷宫的行数和列数:n);scanf(%d%d,&m,&

43、n);InitMaze(maze,m,n);/迷宫初始化printf(请输入起点坐标:n);scanf(%d%d,&start.x,&start.y);start.x-;start.y-;printf(请输入出口坐标:n);scanf(%d%d,&end.x,&end.y);end.x-;end.y-;名师资料总结-精品资料欢迎下载-名师精心整理-第 27 页，共 29 页 -printf(迷宫为 n);PrintMaze(maze,m,n);/输出初始迷宫if(MazePath(maze,start,end,S,m,n)printf(走出迷宫的路径为:n);StackTraverse(S);

44、else printf(此迷宫无通路！n);printf(此时路径在迷宫中(用 2 标记表示可通路径，用3 表示死胡同)显示为：n);PrintMaze(maze,m,n);/输出改变状态的迷宫break;case 2:exit(0);break;default:exit(0);break;DestroyStack(S);int Pass(PosType seat,int mazeNN,int n1,int n2)/检查当前通道块是否可通 if(mazeseat.xseat.y=0&seat.x=0&seat.y=0)return 1;else return 0;int FootPrint(P

45、osType curpos,int mazeNN)mazecurpos.xcurpos.y=2;return 1;void NextPos(PosType&curpos,int i)/转换至下一个位置 if(i=1)curpos.y+;else if(i=2)curpos.x+;else if(i=3)curpos.y-;else if(i=4)curpos.x-;名师资料总结-精品资料欢迎下载-名师精心整理-第 28 页，共 29 页 -int MarkPrint(PosType curpos,int mazeNN)/标记此处不能走 mazecurpos.xcurpos.y+;return 1;名师资料总结-精品资料欢迎下载-名师精心整理-第 29 页，共 29 页 -