利用栈和队列实现迷宫.doc

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.07M 资料格式：doc 举报版权申诉

d505yjw-10489333-4744302543386998275.doc.pdf-第1页.png

第1页 / 共7页

d505yjw-10489333-4744302543386998275.doc.pdf-第2页.png

第2页 / 共7页

d505yjw-10489333-4744302543386998275.doc.pdf-第3页.png

第3页 / 共7页

d505yjw-10489333-4744302543386998275.doc.pdf-第4页.png

第4页 / 共7页

d505yjw-10489333-4744302543386998275.doc.pdf-第5页.png

第5页 / 共7页

d505yjw-10489333-4744302543386998275.doc.pdf-第6页.png

第6页 / 共7页

d505yjw-10489333-4744302543386998275.doc.pdf-第7页.png

第7页 / 共7页

文本预览

分别用栈方法和队列方法实现迷宫的求解，后者求出的是最短路径。两种方法用到的是一个迷宫数组，在使用栈方法实现迷宫的求解时，为避免死循环改变了原来的迷宫数组的个别路径值，因此使用队列求解时不能得到相应的路径解，所以为避免此类情况，可以在用栈方法求解迷宫路径之前将数组赋值给另一个数组，这样队列求解迷宫数组时可以在原来不改变的迷宫数组下进行。代码： for(i=0;i #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 data[MAXSIZE]; int top; }Sqstack; typedef struct { int x,y; }item; typedef struct { int x,y; int pre; }Elemtype; typedef struct //队列的类型定义 { Elemtype elem[MAXSIZE]; 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 full\n"); return; } s->top++; s->data[s->top].x=e.x; s->data[s->top].y=e.y; s->data[s->top].d=e.d; } void pop (Sqstack *s,elemtype *e) //出栈 { if(s->top==-1) {printf("Stack is empty\n"); return;} e->x=s->data[s->top].x; e->y=s->data[s->top].y; e->d=s->data[s->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 empty\n"); else *e=q.elem[q.front]; } void EnQueue(SqQueue *q,Elemtype e) // 入队 { if(q->len==MAXSIZE) printf("Queue is full\n"); else { q->elem[q->rear].x=e.x;q->elem[q->rear].y=e.y; q->elem[q->rear].pre=e.pre;q->rear=q->rear+1; q->len++; } } void DeQueue(SqQueue *q,Elemtype *e) //出队 { if(q->len==0) printf("Queue is empty\n"); else { e->x=q->elem[q->rear].x;e->y=q->elem[q->rear].y; e->pre=q->elem[q->rear].pre;q->front=q->front+1; q->len--; } } void Sprint(int a[M+2][N+2]) { int i,j; printf("迷宫为：\n"); for(i=0;i

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 maze[M+2][N+2],item move[8]) //栈的迷宫求解输出 { 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+move[d].x; j=y+move[d].y; if(maze[i][j]==0) { temp.x=x;temp.y=y;temp.d=d; push(&s,temp); x=i;y=j; maze[x][y]=-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.elem[i]).x,(q.elem[i]).y); i=(q.elem[i]).pre; } while(i!=-1); printf("\n"); } void DLmazepath(int maze1[M+2][N+2],item move[8]) //队列的迷宫求解 { 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); maze1[1][1]=-1; while(!QueueEmpty (q)) { GetHead(q,&head); x=head.x;y=head.y; for(v=0;v<8;v++) { i=x+move[v].x; j=y+move[v].y; if(maze1[i][j]==0) { e.x=i;e.y=j;e.pre=q.front; EnQueue(&q,e); maze1[x][y]=-1; } //if if(i==M&&j==N) { DLprintpath(q); return ; } }//for DeQueue(&q,&head); }//while printf("迷宫无路径!\n"); return; }

void main() {int a,i,j,maze2[M+2][N+2]; int maze[M+2][N+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 move[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; ;/*构造一个迷宫*/ /*坐标增量数组 move 的初始化*/ for(i=0;i

分享到：

赞收藏

资料库

利用栈和队列实现迷宫.doc

相关推荐

开发技术

热门标签

最新资料