迷宫问题实验报告用栈解决迷宫问题.doc

资源ID：33792446 资源大小：1.09MB 全文页数：13页
资源格式： DOC 下载积分：15金币

快捷下载

会员登录下载

微信登录下载

三方登录下载：

微信扫一扫登录

下载资源需要15金币

邮箱/手机：
温馨提示：	快捷下载时，用户名和密码都是您填写的邮箱或者手机号，方便查询和重复下载（系统自动生成）。如填写123，账号就是123，密码也是123。
支付方式：
验证码：	换一换

账号：
密码：
验证码：	换一换
当日自动登录忘记密码？

友情提示

1、下载资料失败解决办法

2、PDF文件下载后，可能会被浏览器默认打开，此种情况可以点击浏览器菜单，保存网页到桌面，就可以正常下载了。

3、本站不支持迅雷下载，请使用电脑自带的IE浏览器，或者360浏览器、谷歌浏览器下载即可。

4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩，下载后原文更清晰。

5、试题试卷类文档，如果标题没有明确说明有答案则都视为没有答案，请知晓。

网站客服

侵权投诉

迷宫问题实验报告用栈解决迷宫问题.doc

_数据结构实验报告题目：用栈解决迷宫问题一需求分析1 以结构体Maze表示迷宫，其中pos表示该位置是否有障碍； freq记录该位置被经过的次数；数组move表示下一步的方向。2 本程序自动随机生成一个12×12大小的迷宫，字符“H”表示有障碍，空符表示通路。3 迷宫的入口为左上角，出口为右下角。4 本程序只求出一条成功的通路。二概要设计为了实现上述操作，以栈为存储结构。本程序包含三个模块：（1）主程序模块:实现人机交互。（2）迷宫生产模块：随机产生一个12×12的迷宫。（3）路径查找模块：实现通路的查找。（4）求解迷宫中一条通路的伪代码：do 若当前位置可同，则将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东临方块为新的当前位置；否则若栈不空且栈顶位置尚有其他方向未被探索，则设定新的的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空。 while(栈不空)三详细设计栈的设计：typedef struct Node *base,*top;int length;Stack;Stack *initstack(); /初始化栈void printstack(Stack *s); /打印栈Status destroy(Stack *); /销毁整个栈Status deltop(Stack *s); /出栈Status pushelem(Stack *,ElemType ,ElemType); /进栈 1. 主程序模块： int main() printf("随机产生一个12×12的迷宫，X字符表示障碍，空符表示通路：n"); Maze aNN; makemaze(a); printf("输入回车键显示路径,*字符表示路径。n"); getchar(); findpath(a); while(1); return 0;2. 迷宫生产模块； void makemaze(Maze (*p)N) int i,j,conter; for(i=0;i<N;+i) for(j=0;j<N;+j) (*(p+i)+j)->pos=0; (*(p+i)+j)->freq=0; (*(p+i)+j)->move0=0; (*(p+i)+j)->move1=0; (*(p+i)+j)->move2=0; (*(p+i)+j)->move3=0; for(j=0;j<N;+j) (*p+j)->pos='X' (*(p+N-1)+j)->pos='X' for(i=1;i<N-1;+i) (*(p+i)->pos='X' (*(p+i)+N-1)->pos='X' srand(int)time(NULL); for(conter=0;conter<20;+conter) i=rand()%(N-2); j=rand()%(N-2); (*(p+i)+j)->pos='X' if(i=1&&j=1|i=N-1&&j=N-1) (*(p+i)+j)->pos=0; printmaze(p);3.路径查找模块。Maze *testnewpos(Maze (*p)N,Stack *s,int *i,int *j)Maze *q=NULL;int select=0;*i=*j=0;for(;q=NULL&&select<4;+select)/在可行的方向上只选一个 switch(select) case 0: if( (*(p+s->top->x)+s->top->y)->move0!=1 ) (*(p+s->top->x)+s->top->y)->move0=1; q=*(p+s->top->x)+s->top->y+1; *i=s->top->x+0; *j=s->top->y+1; / 退回前一步检查东方向是否可通 break; case 1: if( (*(p+s->top->x)+s->top->y)->move1!=1 ) (*(p+s->top->x)+s->top->y)->move1=1; q=*(p+s->top->x+1)+s->top->y; *i=s->top->x+1; *j=s->top->y+0; / 退回前一步检查南方向是否可通 break; case 2: if( (*(p+s->top->x)+s->top->y)->move2!=1 ) (*(p+s->top->x)+s->top->y)->move2=1; q=*(p+s->top->x)+s->top->y-1; *i=s->top->x+0; *j=s->top->y-1; / 退回前一步检查西方向是否可通 break; case 3: if( (*(p+s->top->x)+s->top->y)->move3!=1 ) (*(p+s->top->x)+s->top->y)->move3=1; q=*(p+s->top->x-1)+s->top->y; *i=s->top->x-1; *j=s->top->y+0; / 退回前一步检查北方向是否可通 return q;void printpath(Stack *s,Maze (*p)N) Node *n;int i,j,conter;conter=0;n=s->base;for(;n;n=n->next) (*(p+n->x)+n->y)->pos='*' for(i=0;i<N;+i) for(j=0;j<N;+j) +conter; printf(FORMAT,(*(p+i)+j)->pos); if(conter%12=0) TURNLINE; TURNLINE; 完整的程序：maze.h#ifndef MAZE_H#define MAZE_H#include "mazepath.h"#include <time.h>#define N 12/10+2#define FORMAT "%2c"#define TURNLINE printf("n")typedef structchar pos;int freq;int move4;Maze;void makemaze(Maze (*p)N);void printmaze(Maze (*p)N);void findpath(Maze (*p)N);Maze *testnewpos(Maze (*p)N,Stack *,int *,int *);void printpath(Stack *s,Maze (*p)N);void makemaze(Maze (*p)N) int i,j,conter; for(i=0;i<N;+i) for(j=0;j<N;+j) (*(p+i)+j)->pos=0; (*(p+i)+j)->freq=0; (*(p+i)+j)->move0=0; (*(p+i)+j)->move1=0; (*(p+i)+j)->move2=0; (*(p+i)+j)->move3=0; for(j=0;j<N;+j) (*p+j)->pos='X' (*(p+N-1)+j)->pos='X' for(i=1;i<N-1;+i) (*(p+i)->pos='X' (*(p+i)+N-1)->pos='X' srand(int)time(NULL); for(conter=0;conter<20;+conter) i=rand()%(N-2); j=rand()%(N-2); (*(p+i)+j)->pos='X' if(i=1&&j=1|i=N-1&&j=N-1) (*(p+i)+j)->pos=0; printmaze(p);void printmaze(Maze (*p)N)int i,j,conter;conter=0;for(i=0;i<N;+i) for(j=0;j<N;+j) +conter; printf(FORMAT,(*(p+i)+j)->pos); if(conter%12=0) TURNLINE; TURNLINE;void findpath(Maze (*p)N) Maze *q=NULL; int i=1,j=1,*pi=&i,*pj=&j,success=0; Stack *s; s=initstack();/初始化用来存储路径的栈 q=*(p+1)+1;/初始化当前位置为入口位置 do if(q->pos!='X'&&!(q->freq)/当前位置通且在当前路径中未被访问过，则入栈 if(i=N-2&&j=N-2) pushelem(s,N-2,N-2); success=1; else if(i=1&&j=1) pushelem(s,i,j); q->freq=1;/当前位置已经进栈，作标记，不能再入栈，不然就只能兜死胡同了 q->move0=1;/切换下一位置为东邻位置,并做标记，东邻位置已经使用 i=s->top->x+0; j=s->top->y+1; q=*(p+i)+j; else pushelem(s,i,j); q->freq=1; q=*(p+i)+j; else/当前位置不通，则在前一步(栈顶)检查是否有其他方向可行 /printf("step here."); if(s->base!=s->top) do/查找新的通路直到新通路出现或者回到初始位置 q=testnewpos(p,s,&i,&j);/返回其它三个方向的其中一个和新的当前位置的坐标 if(q=NULL) deltop(s);/栈顶没有可继续往下走的通路，删除栈顶，在新的栈顶找 while(q=NULL&&s->base!=s->top); while(success!=1); printpath(s,p);Maze *testnewpos(Maze (*p)N,Stack *s,int *i,int *j)Maze *q=NULL;int select=0;*i=*j=0;for(;q=NULL&&select<4;+select)/在可行的方向上只选一个 switch(select) case 0: if( (*(p+s->top->x)+s->top->y)->move0!=1 ) (*(p+s->top->x)+s->top->y)->move0=1; q=*(p+s->top->x)+s->top->y+1; *i=s->top->x+0; *j=s->top->y+1; / 退回前一步检查东方向是否可通 break; case 1: if( (*(p+s->top->x)+s->top->y)->move1!=1 ) (*(p+s->top->x)+s->top->y)->move1=1; q=*(p+s->top->x+1)+s->top->y; *i=s->top->x+1; *j=s->top->y+0; / 退回前一步检查南方向是否可通 break; case 2: if( (*(p+s->top->x)+s->top->y)->move2!=1 ) (*(p+s->top->x)+s->top->y)->move2=1; q=*(p+s->top->x)+s->top->y-1; *i=s->top->x+0; *j=s->top->y-1; / 退回前一步检查西方向是否可通 break; case 3: if( (*(p+s->top->x)+s->top->y)->move3!=1 ) (*(p+s->top->x)+s->top->y)->move3=1; q=*(p+s->top->x-1)+s->top->y; *i=s->top->x-1; *j=s->top->y+0; / 退回前一步检查北方向是否可通 return q;void printpath(Stack *s,Maze (*p)N) Node *n;int i,j,conter;conter=0;n=s->base;for(;n;n=n->next) (*(p+n->x)+n->y)->pos='*' for(i=0;i<N;+i) for(j=0;j<N;+j) +conter; printf(FORMAT,(*(p+i)+j)->pos); if(conter%12=0) TURNLINE; TURNLINE; #endifmazepath.h#ifndef MAZEPATH_H#define MAZEPATH_H#include<stdio.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int ElemType;typedef int Status;typedef struct nodeElemType x;ElemType y;struct node *next;struct node *prior;Node,*Postion;typedef struct Node *base,*top;int length;Stack;Stack *initstack(); /初始化栈void printstack(Stack *s); /打印栈Status destroy(Stack *); /销毁整个栈Status deltop(Stack *s); /出栈Status pushelem(Stack *,ElemType ,ElemType); /进栈Stack *initstack()Stack *s;s=(Stack *)malloc(sizeof(Stack);if(!s) return ERROR;s->base=s->top=NULL; /栈空s->length=0;return s;void printstack(Stack *s) Node *N;N=s->base;for(;N;N=N->next) printf("%2d %2d ",N->x,N->y);printf("nn");Status destroy(Stack *s)Node *p;p=s->base; while(s->base->next) s->base=s->base->next; /N=N->next和free(P)不能倒换位置，当释放p时， free(p); /如果不将N移向下一个位置，将导致N指向的内存释放，N->next不再有效 p=s->base; s->base=s->top=NULL; s->length=0;return OK;Status deltop(Stack *s)Node *p;if(!s->length) printf("Underflown"); /已经是空栈else p=s->top; s->top=p->prior; free(p); -s->length; s->top->next=NULL;return OK; Status pushelem(Stack *s,ElemType i,ElemType j)Node *n;n=(Node *)malloc(sizeof(Node);if(!n) return ERROR;n->x=i;n->y=j；if(s->length=0) s->base=s->top=n; n->prior=NULL;else n->prior=s->top; s->top->next=n; s->top=n;n->next=NULL; +s->length;return OK;#endifMyMain.cpp#include "maze.h"int main() printf("随机产生一个12×12的迷宫，X字符表示障碍，空符表示通路：n"); Maze aNN; makemaze(a); printf("输入回车键显示路径,*字符表示路径。n"); getchar(); findpath(a); while(1); return 0;四调试结果及说明1 说明:本程序的运行环境为VC+6.0，执行文件为MgProblem.exe。2 测试结果实际程序执行过程如下图所示：13_

注意事项

本文（迷宫问题实验报告用栈解决迷宫问题.doc）为本站会员（1595****071）主动上传，淘文阁 - 分享文档赚钱的网站仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若此文所含内容侵犯了您的版权或隐私，请立即通知淘文阁 - 分享文档赚钱的网站（点击联系客服），我们立即给予删除！

温馨提示：如果因为网速或其他原因下载失败请重新下载，重复下载不扣分。