用栈方法、队列方法求解迷宫问题

1、.目录1前言 .12需求分析 .12.1课程设计目的 .12.2课程设计任务 .12.3设计环境 .13概要设计 .13.1数据结构设计 .13.2模块设计 .24详细设计 .341 数据类型的定义 .错误！未定义书签。42 主要模块的算法描述 .错误！未定义书签。5测试分析 .66课程设计总结 .7参考文献 .8致谢.8附录（程序代码实现 ） .9.专业学习资料.1 前言设计一个简单迷宫程序 ，从入口出发 ，按某一方向向前探索 ，若能走通（未走过的 ），即某处可以到达 ，则到达新点 ，否则试探下一方向 ；若所有方向均没有通路 ，则沿原点返回前一点 ，换下一个方向在继续试探 ，直到所有可能的通

2、路都探索到 ，或找到一条通路 ，或无路可走又返回到入口点 。 并利用两种方法实现 ：一种用栈实现 ，另一种用队列实现 。2 需求分析2.1 课程设计目的学生在教师指导下运用所学课程的知识来研究 、解决一些具有一定综合性问题的专业课题 。 通过课程设计 （论文），提高学生综合运用所学知识来解决实际问题 、使用文献资料 、及进行科学实验或技术设计的初步能力 ，为毕业设计（论文）打基础。2.2 课程设计任务给出一个任意大小的迷宫数据 ，求出一条走出迷宫的路径 ，输出迷宫并将所求路径输出 。要求用两种方法实现：一种用栈实现 ，另一种用队列实现。，我主要负责队列方面2.3 设计环境（1）WINDOWS

3、2000/2003/XP/7/Vista 系统（2）Visual C+ 或 TC 集成开发环境3 概要设计3.1 数据结构设计（ 1）迷宫类型设迷宫为 M 行 N 列，利用 mazeMN 来表示一个迷宫 ，maze=0 或 1，其中 0 表示通路 ，1 表示不通 。 当从某点试探是 ，中间点有 8 个不同点可以试探 ，而四个角有 3 个方向，其他边缘点有 5 个方向，为使问题更容易分析我们用 mazeM+2N+2.专业学习资料.来表示迷宫 ，而迷宫四周的值全部为1。定义如下 ：#define M 6/* 迷宫的实际行 */#define N 8/* 迷宫的实际列 */int mazeM+2N+

4、2;（2）队列的类型定义队列的有关数据结构、试探方向等和栈的求解方法处理基本相同。不同的是 ：如何存储搜索路径 。 在搜索过程中必须几下每一个可到达的坐标点 ，以便从这些点出发继续向四周搜索 。到达迷宫的出口点 （ m,n ）后，为能够从出口沿搜索路径回溯直至入口 ，对于每一点 ，记下坐标点的同时 ，还要记下到达该点的前驱点 ，因此用一个结构体数组 eleMAX 作为队列的存储空间 ，因为每一点至少被访问一次 ，所以 MAX 至多等于 m*n 。该结构体有三个域 ：x、y 和 pre 。其中 x、y 分别为所到达点的坐标 ，pre 为前驱点在 elem 中的下标 。除此之外 ，还需设定头 、尾

5、指针，分别指向队头 ，队尾。类型定义如下 ：typedef struct/ 队的相关类型定义 int x,y;int pre;Elemtype;typedef struct/ 队列的类型定义 Elemtype elemMAXSIZE; int front,rear;int len;SqQueue;3.2 模块设计定义函数 DLmazepath( ) ，利用队列实现迷宫求 。定义函数 DLmazepath( ) ，实现队列的迷宫路径输出 。定义函数 InitQueue （） ，实现队列的初始化 。定义函数 QueueEmpty( ) ，判断队列是否为空 ，为空返回 1，否则返回 0.定义函数 G

6、etHead (SqQueue q,Elemtype *e)，实现队头元素的读取 。定义函数定义函数EnQueue(SqQueue *q,Elemtype e)DeQueue(SqQueue *q,Elemtype *e)，实现入队操作 。，实现出队操作 。定义函数 Sprint(int aM+2N+2)，实现，迷宫的输出 。.专业学习资料.4 详细设计（ 1）主函数void main()int a,i,j,maze2M+2N+2; /* 构造一个迷宫 */ int mazeM+2N+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1

7、,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1;item move8=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;/* 坐标增量数组 move 的初始化 */为使得程序更加人性化 ，更加友好 ，因此可将系统输出界面设置如下：printf(" |* *迷宫求解系统 *|n");printf(" | 1、栈方法 求解迷宫的路径|n");printf("

8、| 2、队列求解的迷宫路径|n");printf(" | 3、 退出系统|n");printf(" |*|n");printf("tnn 请选择 (0-3 ):"); scanf("%d",&a) ; while(a!=3) switch(a) Case 1:Sprint(maze);printf( “路径为 ：n");Zmazepath(maze,move);break;Case2:Sprint(maze2);printf(" 路径 ：n");DLmazepath(

9、maze2,move);break;default : printf("tt选择错误 ！ n");.专业学习资料.printf("tn请选择 (0-3).n"); scanf("%d",&a);printf("ntt非常感谢您的使用 !n") ;（2）利用队列实现迷宫求解伪代码如下：intDLmazepath_(int mazeM+2N+2,item move8)/* 采用队列的迷宫算法。MazeM+2N+2 表示迷宫数组 ，move8 表示坐标增量数组 */队的初始化 ；将入口点坐标及到达该点的方向（设为

10、 -1 ）入队；While( 队不为空 ) For( 从 1 到 8 个方向 )求新坐标点坐标 ，并将可到达点分别入队 ；If （点（x,y）为出口点 ）结束输出路径 ，迷宫有路 ；当前点搜索完 8 个方向后出队 ；Return o /* 迷宫五路 */void DLprintpath(SqQueue q)/输出迷宫路径 ，队列中保存的就是一条迷宫的通路int i;i=q.rear-1;doprintf("(%d,%d)<-",(q.elemi).x,(q.elemi).y); i=(q.elemi).pre;while(i!=-1)利用栈方法和队列方法用到的是同一个

11、迷宫数组，在使用栈方法实现迷宫求解时，为避免死循环改变了原来的迷宫数组的个别路径值，因此使用队列求解时不能得到相应的路径解，为避免此 ，我们可在用栈方法求解迷宫路径之前将数组赋值给另一个数组，这样队列求解迷宫时可以再原来不改.专业学习资料.变的迷宫数组下进行 。具体实现代码如下 ：for(i=0;i<M+2;i+)for( j=0;j<N+2;j+) maze2i j=mazeij;（3）队列的操作void InitQueue(SqQueue *q)/* 队列的初始化 */ 将队中元素赋值为 0；int QueueEmpty(SqQueue q)/* 判队空 */ if（队长度为

12、0） 返回 1；else 返回 0；void GetHead (SqQueue q,ElemType *e)/*读队头元素 */if （队的长度为 0） 输出提示队列为空 ； else 将队中值赋给 e；void EnQueue(SqQueue *q,ElemType e)/*入队 */ if（ 队列长度已满 ）输出提示 ；else 将 e 中元素赋给队列 ；队尾指针指向下一个元素 ；队长加 1；void DeQueue(SqQueue *q,ElemType *e)/*出队 */ if（判队空） 输出提示 ；else 将队中元素赋给 e；队头指向下一个元素 ；队长减 1；.专业学习资料.5

13、测试分析测试数据及结果如下 ：（1）系统友好界面输出图 5.1 进入系统界面运行结果（2）选择 1,运行结果输出如下 ：图 5.2 迷宫以及使用栈求解迷宫路径的输出（3）选择 2、3 运行结果如下 ：.专业学习资料.图 5.3 迷宫以及使用队列求解迷宫路径的输出（4）选择 3 运行结果如下 ：图 5.3 退出程序根据结果分析 ：利用栈求得的路径不一定是最短路径，而用队列求得的路径是最短路径 。6 课程设计总结课程设计终于在本组组员共同的努力下完成了 。通过本次课程设计让我对栈和队列这一章的知识有了进一步了解 ，也让我知道了用栈和队列实现迷宫问题的基本原理，知道了栈和队列的不同存储结构的定义和算

14、法描述 ，同时也学会了编写简单的迷宫问题的程序 。选了题目之后 ，我感觉题目之前已经做过一点相关的实验，本以为很快就能搞好，但是 ，真正做起来才感觉没有那么简单 ，让我更加意识到自己的不足 ，我所知道的，所懂的太少了 。 在刚开始编程的时候 ，我感到有点迷茫 ，虽然懂得了其相应的算法和思想 ，但是却不知道要怎样安排程序的结构 、以及什么方法将其功能实现 ，更不知道要从哪里开始着手进行 。 老师说的没错 ，我们平时的学习中程序练习太少，写的太少 ，什么事不可能一蹴而就 ，都是通过一点一滴的锻炼慢慢积累起来的。所以我觉得在以后的学习中，我会更加注重实践 ，注重多练 ，多积累 ，为自己.专业学习资料

15、.的以后工作打下结实的基础。参考文献1 黄同成 ，黄俊民 ，董建寅 数据结构 M 北京 ：中国电力出版社 ， 20082 董建寅 ，黄俊民 ，黄同成 数据结构实验指导与题解M 北京：中国电力出版社， 20083 严蔚敏 ，吴伟民 . 数据结构 （ C 语言版 ） M. 北京 ：清华大学出版社 ， 20024 刘振鹏 ，张晓莉 ，郝杰 数据结构 M 北京 ：中国铁道出版社 ， 2003致谢在这次课程设计的撰写过程中 ，我得到了许多人的鼓励和帮助 ，在此，我表示衷心的感谢 。首先，我要感谢我的指导老师黄同城老师 ，他在课程设计上给予我的很大的帮助，指导课程设计的具体实现方向 。并且为我分析部分比较

16、难懂的地方 ，让我把此次课程设计做得更加完善 。 在此期间 ，我对迷宫问题有了更深刻的认识 ，而且也明白了很多做课程设计需要注意的地方 ，让我变得更严谨 。然后，我要感谢我们第一大组组员们 ，在组内讨论时 ，他们各抒己见 ，思路发散，讨论时锱铢必较 ，正是因为这份热情 ，我们对这次的课程设计充满了激情 ，方向也很明确 。 在汇报进程的时候 ，组内积极讨论 ，相互竞争 ，优缺互补 ，让我们的课程设计更加完美 ，让我们自己在讨论中知道自己的优点 ，认识自己的缺点 ，不断.专业学习资料.完善自己 。最后感谢我的母校 邵阳学院 ，谢谢母校为我们提供了这样一个环境，让同学们能相聚在一起 ，让我们有这样一

17、起奋斗共同完成目标的经历。附录具体程序代码实现#include<stdio.h>#include<stdlib.h>#define M 6#define N 8#define MAXSIZE 100#define MAX M*Ntypedef struct/ 栈的相关类型定义int x,y,d ;/d下一步方向elemtype;typedef structelemtype dataMAXSIZE;int top;Sqstack;typedef structint x,y;item;typedef struct/ 队的相关类型定义int x,y;.专业学习资料.int p

18、re;Elemtype;typedef struct/ 队列的类型定义Elemtype elemMAXSIZE;int front,rear;int len;SqQueue;/*栈函数*/void InitStack(Sqstack *s)/ 构造空栈s->top=-1;int Stackempty(Sqstack s)/ 判断栈是否为空if(s.top=-1)return 1;elsereturn 0;void push(Sqstack *s,elemtype e)/ 入栈if(s->top=MAXSIZE-1) printf("Stack is fulln"

19、); return;s->top+;s->datas->top.x=e.x;s->datas->top.y=e.y;s->datas->top.d=e.d;.专业学习资料.void pop (Sqstack *s,elemtype *e)/出栈算法if(s->top=-1) printf("Stack is emptyn"); return; e->x=s->datas->top.x; e->y=s->datas->top.y; e->d=s->datas->top.d;s

20、->top-;/*队函数*/void InitQueue(SqQueue *q)/ 队的初始化q->front=q->rear=0;q->len=0;int QueueEmpty(SqQueue q)/ 判断队空if (q.len=0)return 1;else return 0;void GetHead (SqQueue q,Elemtype *e)/ 读队头元素if (q.len=0)printf("Queue is emptyn");else*e=q.elemq.front;void EnQueue(SqQueue *q,Elemtype e)

21、/ 入队if(q->len=MAXSIZE).专业学习资料.printf("Queue is fulln");elseq->elemq->rear.x=e.x;q->elemq->rear.y=e.y; q->elemq->rear.pre=e.pre;q->rear=q->rear+1; q->len+;void DeQueue(SqQueue *q,Elemtype *e)/ 出队if(q->len=0)printf("Queue is emptyn");elsee->x=q-&

22、gt;elemq->rear.x;e->y=q->elemq->rear.y; e->pre=q->elemq->rear.pre;q->front=q->front+1; q->len-;void Sprint(int aM+2N+2)int i,j;printf(" 迷宫为 ：n");for(i=0;i<M+2;i+)for( j=0;j<N+2;j+)printf("%2d",aij);printf("n");.专业学习资料.void Zprintpath(

23、Sqstack s)/ 输出迷宫路径 ，栈中保存的就是一条迷宫的通路elemtype temp;printf("(%d,%d)<-",M,N);while(!Stackempty(s)pop(&s,&temp);printf("(%d,%d)<-",temp.x,temp.y);printf("n");void Zmazepath(int mazeM+2N+2,item move8)/ 栈的迷宫求解输出Sqstack s;elemtype temp;int x,y,d,i,j;InitStack(&

24、s); / 栈的初始化temp.x=1;temp.y=1;temp.d=-1;push(&s,temp);while(!Stackempty (s)pop(&s,&temp);x=temp.x;y=temp.y;d=temp.d+1;while(d<8)i=x+moved.x;j=y+moved.y;if(mazei j=0) temp.x=x;temp.y=y;temp.d=d; push(&s,temp);x=i;y=j;.专业学习资料.mazexy=-1;if(x=M&&y=N) Zprintpath(s); return ； els

25、e d=0;/ifelse d+;/while /while return;printf(" 迷宫无路 n");return;void DLprintpath(SqQueue q)/ 输出迷宫路径 ，队列中保存的就是一条迷宫的通路int i;i=q.rear-1;doprintf("(%d,%d)<-",(q.elemi).x,(q.elemi).y);i=(q.elemi).pre; while(i!=-1);printf("n");void DLmazepath(int maze1M+2N+2,item move8)/ 队列

26、的迷宫求解SqQueue q;Elemtype head,e;int x,y,v,i,j;InitQueue(&q);/ 队列的初始化e.x=1;e.y=1;e.pre=-1;EnQueue (&q,e);.专业学习资料.maze111=-1;while(!QueueEmpty (q) GetHead(q,&head); x=head.x;y=head.y; for(v=0;v<8;v+) i=x+movev.x; j=y+movev.y;if(maze1i j=0) e.x=i;e.y=j;e.pre=q.front;EnQueue(&q,e);maze1xy=-1;/ifif(i=M&&j=N) DLprintpath(q); return ; /for DeQueue(&q,&head);/whileprintf(" 迷宫无路 !n");return;void main() int a,i,j,maze2M+2N+2; int mazeM+2N+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,