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

目 录1 前言12 需求分析12.1课程设计目的12.2课程设计任务12.3设计环境13 概要设计13.1数据结构设计13.2模块设计24 详细设计341数据类型的定义342主要模块的算法描述35 测试分析66 课程设计总结7参考文献8致 谢8附 录（程序代码实现）91 前言设计一个简单迷宫程序，从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有方向均没有通路，则沿原点返回前一点，换下一个方向在继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。并利用两种方法实现：一种用栈实现，另一种用队列实现。2 需求分析2.1课程设计目的学生在教师指导下运用所学课程的知识来研究、解决一些具有一定综合性问题的专业课题。通过课程设计（论文），提高学生综合运用所学知识来解决实际问题、使用文献资料、及进行科学实验或技术设计的初步能力，为毕业设计（论文）打基础。2.2课程设计任务给出一个任意大小的迷宫数据，求出一条走出迷宫的路径，输出迷宫并将所求路径输出。要求用两种方法实现：一种用栈实现，另一种用队列实现。，我主要负责队列方面2.3设计环境（1）WINDOWS 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+2;（2）队列的类型定义队列的有关数据结构、试探方向等和栈的求解方法处理基本相同。不同的是：如何存储搜索路径。在搜索过程中必须几下每一个可到达的坐标点，以便从这些点出发继续向四周搜索。到达迷宫的出口点（m,n）后，为能够从出口沿搜索路径回溯直至入口，对于每一点，记下坐标点的同时，还要记下到达该点的前驱点，因此用一个结构体数组eleMAX作为队列的存储空间，因为每一点至少被访问一次，所以MAX至多等于m*n。该结构体有三个域：x、y和pre。其中x、y分别为所到达点的坐标，pre为前驱点在elem中的下标。除此之外，还需设定头、尾指针，分别指向队头，队尾。类型定义如下：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.定义函数GetHead (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,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(" | 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(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表示坐标增量数组*/ 队的初始化； 将入口点坐标及到达该点的方向（设为-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)利用栈方法和队列方法用到的是同一个迷宫数组，在使用栈方法实现迷宫求解时，为避免死循环改变了原来的迷宫数组的个别路径值，因此使用队列求解时不能得到相应的路径解，为避免此，我们可在用栈方法求解迷宫路径之前将数组赋值给另一个数组，这样队列求解迷宫时可以再原来不改变的迷宫数组下进行。具体实现代码如下： for(i=0;i<M+2;i+) for(j=0;j<N+2;j+) maze2ij=mazeij;（3）队列的操作void InitQueue(SqQueue *q) /*队列的初始化*/ 将队中元素赋值为0；int QueueEmpty(SqQueue q) /*判队空*/ if（队长度为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 测试分析测试数据及结果如下：（1）系统友好界面输出 图5.1 进入系统界面运行结果（2）选择1,运行结果输出如下： 图5.2 迷宫以及使用栈求解迷宫路径的输出（3）选择2、3 运行结果如下： 图5.3 迷宫以及使用队列求解迷宫路径的输出（4）选择3运行结果如下： 图5.3 退出程序 根据结果分析：利用栈求得的路径不一定是最短路径，而用队列求得的路径是最短路径。6 课程设计总结课程设计终于在本组组员共同的努力下完成了。通过本次课程设计让我对栈和队列这一章的知识有了进一步了解，也让我知道了用栈和队列实现迷宫问题的基本原理，知道了栈和队列的不同存储结构的定义和算法描述，同时也学会了编写简单的迷宫问题的程序。选了题目之后，我感觉题目之前已经做过一点相关的实验，本以为很快就能搞好，但是，真正做起来才感觉没有那么简单，让我更加意识到自己的不足，我所知道的，所懂的太少了。在刚开始编程的时候，我感到有点迷茫，虽然懂得了其相应的算法和思想，但是却不知道要怎样安排程序的结构、以及什么方法将其功能实现，更不知道要从哪里开始着手进行。老师说的没错，我们平时的学习中程序练习太少，写的太少，什么事不可能一蹴而就，都是通过一点一滴的锻炼慢慢积累起来的。所以我觉得在以后的学习中，我会更加注重实践，注重多练，多积累，为自己的以后工作打下结实的基础。参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，2003致 谢在这次课程设计的撰写过程中，我得到了许多人的鼓励和帮助，在此，我表示衷心的感谢。首先，我要感谢我的指导老师黄同城老师，他在课程设计上给予我的很大的帮助，指导课程设计的具体实现方向。并且为我分析部分比较难懂的地方，让我把此次课程设计做得更加完善。在此期间，我对迷宫问题有了更深刻的认识，而且也明白了很多做课程设计需要注意的地方，让我变得更严谨。然后，我要感谢我们第一大组组员们，在组内讨论时，他们各抒己见，思路发散，讨论时锱铢必较，正是因为这份热情，我们对这次的课程设计充满了激情，方向也很明确。在汇报进程的时候，组内积极讨论，相互竞争，优缺互补，让我们的课程设计更加完美，让我们自己在讨论中知道自己的优点，认识自己的缺点，不断完善自己。最后感谢我的母校邵阳学院，谢谢母校为我们提供了这样一个环境，让同学们能相聚在一起，让我们有这样一起奋斗共同完成目标的经历。附录 具体程序代码实现#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 struct elemtype dataMAXSIZE; int top; Sqstack;typedef 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) /入栈 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->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->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;i<M+2;i+) for(j=0;j<N+2;j+) printf("%2d",aij); 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=-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(mazeij=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 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); 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(!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(maze1ij=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,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;i<M+2;i+) for(j=0;j<N+2;j+) maze2ij=mazeij;printf(" |*迷宫求解系统*|n");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");