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

《用栈方法、队列方法求解迷宫问题》由会员分享，可在线阅读，更多相关《用栈方法、队列方法求解迷宫问题（16页珍藏版）》请在装配图网上搜索。

1、目录 1 前言 .1.2 需求分析 .1.2.1 课程设计目的 .1.2.2课程设计任务 .1.2.3 设计环境 .1.3 概要设计 .1.3.1数据结构设计 .1.3.2 模块设计 .2.4 详细设计 .3.5 测试分析 6 课程设计总结 参考文献 .8.41 数据类型的定义 .错 误.！未定义书签 42 主要模块的算法描述 .错 误！未定义书签.6.7.附 录（程序代码实现）.9.致 谢 .8.1 前言 设计一个简单迷宫程序，从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有方 向均没有通路，则沿原点返回前一点，换下一个方向在继续试探

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

3、S 2000/2003/XP/7/Vist a 系统（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+2;(2)队列的类型定义 队列的有关

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

5、ct/队的相关类型定义 int x,y;int pre;Elemtype;typedef struct/队列的类型定义 Elemtype elemMAXSIZE;int front,rear;int len;SqQueue;3.2 模块设计 定义函数 DLmazepath()，利用队列实现迷宫求。定义函数 DLmazepath()，实现队列的迷宫路径输出。定义函数 InitQueue()，实现队列的初始化。定义函数 QueueEmpty()，判断队列是否为空，为空返回 1，否则返回 0.定义函数 GetHead(SqQueue q,Elemtype*e)，实现队头元素的读取。定义函数 EnQu

6、eue(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,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,

7、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(|2、队列 求解的迷宫路径|n);printf(|3、退出系统|n);printf(|*|n);printf(tnn 请选择(0-3):);scanf(%d,&a);while(a!=3)switch(a)Case

8、1:Sprint(maze);printf(“路径为：n);Zmazepath(maze,move);break;Case2:Sprint(maze2);printf(路径：n);DLmazepath(maze2,move);break;default:printf(tt 选择错误！n);printf(tn 请选择(0-3).n);scanf(%d,&a);printf(ntt 非常感谢您的使用!n);(2)利用队列实现迷宫求解伪代码如下：int DLmazepath_(int mazeM+2N+2,item move8)/*采用队列的迷宫算法。MazeM+2N+2 表示迷宫数组,move8表

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

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

11、ead(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测试分析 测试数据及结果如下：(1)系统友好界面输出 C:Us&rsleno voDeskopDe bugj IF题.e

12、xeH 图5.1进入系统界面运行结果(2)选择1,运行结果输出如下：啓:1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 S 1 0 1 1 1 1 1 6 1 0 0&e 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 1 0 1 1 U&1 0 1 1 1 1 1 1 1 1 1 1 木解路径 图5.2迷宫以及使用栈求解迷宫路径的输出(3)选择2、3运行结果如下：情选择0-3 图5.3迷宫以及使用队列求解迷宫路径的输出(4)选择3运行结果如下：请选择0-3：3 非常感谢您的使 Press 豆 to cont inue 图5.

13、3退出程序 根据结果分析：利用栈求得的路径不一定是最短路径，而用队列求得的路径是 最短路径。6课程设计总结 课程设计终于在本组组员共同的努力下完成了。通过本次课程设计让我对栈和 队列这一章的知识有了进一步了解，也让我知道了用栈和队列实现迷宫问题的基本 原理，知道了栈和队列的不同存储结构的定义和算法描述，同时也学会了编写简单 的迷宫问题的程序。选了题目之后，我感觉题目之前已经做过一点相关的实验，本以为很快就能搞 好,但是，真正做起来才感觉没有那么简单，让我更加意识到自己的不足，我所知道 的，所懂的太少了。在刚开始编程的时候，我感到有点迷茫，虽然懂得了其相应的 算法和思想，但是却不知道要怎样安排程

14、序的结构、以及什么方法将其功能实现，更不知道要从哪里开始着手进行。老师说的没错，我们平时的学习中选解-3为 倜径 8 5-c-zx-7程序练习太 少，写的太少，什么事不可能一蹴而就，都是通过一点一滴的锻炼慢慢积累起来 的。所以我觉得在以后的学习中，我会更加注重实践，注重多练，多积累，为自己 的以后工作打下结实的基础 参考文献 1 黄同成，黄俊民，董建寅 数据结构 M 北京：中国电力出版社，2008 2 董建寅，黄俊民，黄同成 数据结构实验指导与题解 M 北京：中国电力出版社，2008 3 严蔚敏，吴伟民.数据结构（C语言版）M.北京：清华大学出版社，2002 4 刘振鹏，张晓莉，郝杰数据结构

15、M 北京：中国铁道出版社，2003 致谢 在这次课程设计的撰写过程中，我得到了许多人的鼓励和帮助，在此，我表示 衷心的感谢。首先，我要感谢我的指导老师黄同城老师，他在课程设计上给予我的很大的帮 助，指导课程设计的具体实现方向。并且为我分析部分比较难懂的地方，让我把此 次课程设计做得更加完善。在此期间，我对迷宫问题有了更深刻的认识，而且也明 白了很多做课程设计需要注意的地方，让我变得更严谨。然后，我要感谢我们第一大组组员们，在组内讨论时，他们各抒己见，思路发 散，讨论时锱铢必较，正是因为这份热情，我们对这次的课程设计充满了激情，方 向也很明确。在汇报进程的时候，组内积极讨论，相互竞争，优缺互补，

16、让我们的 课程设计更加完美，让我们自己在讨论中知道自己的优点，认识自己的缺点，不断 完善自己 最后感谢我的母校 邵阳学院，谢谢母校为我们提供了这样一个环境 同学们能相聚在一起，让我们有这样一起奋斗共同完成目标的经历。附录 具体程序代码实现#include#include#define M 6#define N 8#define MAXSIZE 100#define MAX M*N typedef struct/栈的相关类型定义 int x,y,d;/d 下一步方向 elemtype;typedef struct elemtype dataMAXSIZE;int top;Sqstack;type

17、def struct int x,y;item;typedef struct/队的相关类型定义 int x,y;int pre;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;else return 0;void push(Sqstack*s,elemtype e)/入

18、栈 if(s-top=MAXSIZE-1)printf(Stack is fulln);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-top-;/*队函数*/void InitQueue(SqQueue*q)/队的初始化 q-front=q

19、-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)/入队 if(q-len=MAXSIZE)printf(Queue is fulln);else q-elemq-rear.x=e.x;q-elemq-rear.y=e.y;q

20、-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);else e-x=q-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;iM+2;i+)for(j=0;jN+2;j+)printf(%2d,ai

21、j);printf(n);void Zprintpath(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(&s);/栈的初始化 temp.x=1;temp.y=1;temp.d=

22、-1;push(&s,temp);while(!Stackempty(s)pop(&s,&temp);x=temp.x;y=temp.y;d=temp.d+1;while(d8)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；else d=0;/if else d+;/while /while return;printf(迷宫无路 n);return;void DLprin

23、tpath(SqQueue q)/输出迷宫路径，队列中保存的就是 通路 int i;i=q.rear-1;do printf(%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)宫求解 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(!Que

24、ueEmpty(q)GetHead(q,&head);x=head.x;y=head.y;for(v=0;v8;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;/if if(i=M&j=N)DLprintpath(q);return;/for DeQueue(&q,&head);/while printf(迷宫无路!n);return;void main()int a,i,j,maze2M+2N+2;int mazeM+2N+2=1,1,1

25、,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,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 的初始化*/for(i=0;iM+2;i+)for(j=0;jN+2;j+)maze2i j=mazeij;printf(|*迷宫求解系统*|n

26、);printf(|n);printf(|1、栈 求解迷宫的路径|n);printf(|n);printf(|2、队列 求解的迷宫路径|n);printf(|n);printf(|3、退出系统|n);printf(|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;case 2:printf(求解路径为：n);DLmazepath(maze2,move);break;default:printf(tt 选择错误！n);printf(tn 请选择(0-3)：);scanf(%d,&a);printf(ntt 结束退出程序!n);