云南大学数据结构实验 迷宫求解.doc

云南大学软件学院 数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助） 实验难度： A B C 序号学号姓名成绩1 20121120150迟学成2 20121120162 徐学桢3指导教师 （签名）学期：2013年秋季学期 任课教师: 秦江龙老师 实验题目: 迷宫求解 小 组 长: 徐学桢 联系电话: 20121120162 电子邮件:1017657708 完成提交时间： 2012年 11月 11日云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号： 20121120162 姓名： 徐学桢 本人承担角色： 构思、设计 、结果分析 评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日（注：此表在难度为C时使用，每个成员一份。）云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号： 20121120150 姓名： 迟学成 本人承担角色： 实验设计、实现、报告撰写 评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日（注：此表在难度为C时使用，每个成员一份。）一、【实验构思（Conceive）】(10%)实验构思：1.迷宫的建立：采用2为数组建立迷宫；具体方法：用一个指向指针的指针来动态的建立2为数组，来存储迷宫中的通路1阻路0，墙3；具体分配方法如下：N，M分别是输入的迷宫行数+2和列数+2，因为还有围墙。migong=new int *N; for(i=0;inext; delete p; p=NULL; int StackEmpty(); int GetTop(ElemType &e); int Push(ElemType &e); int Pop(ElemType& e);二、【实验设计(Design)】(20%)程序构建迷宫部分的代码：#includestdlib.h#includestdio.h#define N 39#define M 39int X;int mazeN+2M+2;struct pointint row,col,predecessor;queue512;int head=0,tail=0;void shoudong_maze(int m,int n)int i,j;printf(nn);printf(开始建造迷宫，1表示砖块，0表示通到nn);for(i=0;im;i+)for(j=0;jn;j+) scanf(%d,&mazeij); printf(=n);void zidong_maze(int m,int n)int i,j;printf(=n);system(pause);for(i=0;im;i+)for(j=0;jn;j+)mazeij=rand()%2;/由于rand()产生的随机数是从0到RAND_MAX/RAND_MAX是定义在stdlib.h中的,其值至少为32767)/要产生从X到Y的数,只需要这样写：k=rand()%(Y-X+1)+X; void print_maze(int m,int n)int i,j;printf(迷宫建造成功:nn);printf(入口n);printf();for(i=0;im;i+)printf(n);for(j=0;jn;j+) if(mazeij=0) printf(); if(mazeij=1) printf();printf(出口n);void result_maze(int m,int n)int i,j;printf(迷宫路径图如下所示：nt);for(i=0;im;i+)printf(n); for(j=0;j); void enqueue(struct point p)queuetail=p;tail+;struct point dequeue()head+;return queuehead-1;int is_empty()return head=tail;void visit(int row,int col,int maze4141)struct point visit_point=row,col,head-1;mazerowcol=2;enqueue(visit_point);int mgpath(int maze4141,int m,int n)X=1;struct point p=0,0,-1;if(mazep.rowp.col=1)printf(n=n);printf(此迷宫无解！nn);X=0;return 0;mazep.rowp.col=2;enqueue(p);while(!is_empty()p=dequeue();if(p.row=m-1)&(p.col=n-1) break;if(p.col+1n)&(mazep.rowp.col+1=0) visit(p.row,p.col+1,maze);if(p.row+1=0)&(mazep.rowp.col-1=0) visit(p.row,p.col-1,maze);if(p.row-1=0)&(mazep.row-1p.col=0) visit(p.row-1,p.col,maze);if(p.row=m-1&p.col=n-1)printf(n=n);printf(迷宫路径为：n);printf(%d,%d)n,p.row,p.col);mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.predecessor;printf(%d,%d)n,p.row,p.col);mazep.rowp.col=3;else printf(n=n); printf(糟糕！这个迷宫没有出口！nn);X=0; return 0;int main()int i,m,n,cycle=0;while(cycle!=(-1) printf(=n); printf( 闯迷宫游戏：nn); printf( 程序设计员：学成/学桢 n); printf(=n); printf( 【1】自己建造迷宫.（1）nn); printf( 【2】自动建造迷宫.（2）nn); printf( 【3】退出.（3）nn); printf(=n); printf(n); printf( 请选择菜单代号：); scanf(%d,&i); switch(i) case 1:printf(n请输入行数：);scanf(%d,&m); printf(n); printf(请输入列数：);scanf(%d,&n); while(m39)|(n39) printf(n系统消息！您的迷宫行数和列数不能超过39 ！nn); printf(请输入行数：);scanf(%d,&m); printf(n); printf(请输入列数：);scanf(%d,&n); shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); printf(nn按任意键继续游戏!n);getchar();while(getchar()!=n);break; case 2:printf(n请输入行数：);scanf(%d,&m); printf(n); printf(请输入列数：);scanf(%d,&n); while(m39)|(n39) printf(n系统消息！您的迷宫行数和列数不能超过39 ！nn); printf(请输入行数：);scanf(%d,&m); printf(n); printf(请输入列数：);scanf(%d,&n); zidong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); printf(nn按任意键继续游戏!n);getchar();while(getchar()!=n);break; case 3:cycle=(-1);break; default:printf(n);printf(你的输入有误!n);printf(n按任意键继续游戏!n);getchar();while(getchar()!=n);break; return 0;程序求解迷宫部分的代码 #includestdlib.h#includestdio.h#include#define N 39#define M 39int X;int mazeN+2M+2;struct pointint row,col,predecessor;queue512;int head=0,tail=0;void shoudong_maze(int m,int n)int i,j;printf(nn);printf(开始建造迷宫，1表示砖块，0表示通到nn);for(i=0;im;i+)for(j=0;jn;j+) scanf(%d,&mazeij); printf(=n);void zidong_maze(int m,int n)/printf(=n);system(pause);/!srand(time(NULL);int x1,a1,b1; for(a1=0;a1m;a1+) /自动生成迷宫 for(b1=0;b1n;b1+) x1=rand()%2; if(a1=0&b1=0) mazea1b1=0; else if(a1=m-1&b1=n-1) mazea1b1=0; else if(a1=0) mazea1b1=1; else if(a1=m-1) mazea1b1=1; else if(b1=0) mazea1b1=1; else if(b1=n-1) mazea1b1=1; else mazea1b1=x1; /测试点 void print_maze(int m,int n)int i,j;printf(=n);printf(迷宫建造成功:nn);printf(入口n);printf();for(i=0;im;i+)printf(n);for(j=0;jn;j+) if(mazeij=0) printf(); if(mazeij=1) printf();printf(出口n);void result_maze(int m,int n)int i,j;printf(=n);printf(迷宫路径图如下所示：nt);for(i=0;im;i+)printf(n); for(j=0;j); void enqueue(struct point p)queuetail=p;tail+;struct point dequeue()head+;return queuehead-1;int is_empty()return head=tail;void visit(int row,int col,int maze4141)struct point visit_point=row,col,head-1;mazerowcol=2;enqueue(visit_point);int mgpath(int maze4141,int m,int n)X=1;struct point p=0,0,-1;if(mazep.rowp.col=1)printf(n=n);printf(此迷宫无解！nn);X=0;return 0;mazep.rowp.col=2;enqueue(p);while(!is_empty()p=dequeue();if(p.row=m-1)&(p.col=n-1) break;if(p.col+1n)&(mazep.rowp.col+1=0) visit(p.row,p.col+1,maze);if(p.row+1=0)&(mazep.rowp.col-1=0) visit(p.row,p.col-1,maze);if(p.row-1=0)&(mazep.row-1p.col=0) visit(p.row-1,p.col,maze);if(p.row=m-1&p.col=n-1)printf(n=n);printf(迷宫路径为：n);printf(%d,%d)n,p.row,p.col);mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.predecessor;printf(%d,%d)n,p.row,p.col);mazep.rowp.col=3;else printf(n=n); printf(糟糕！这个迷宫没有出口！nn);X=0; return 0;int main()int i,m,n,cycle=0;while(cycle!=(-1) printf(=n); printf( 闯迷宫游戏：nn); printf( 程序设计员：学成/学桢 n); printf(=n); printf( 【1】自己建造迷宫.（1）nn); printf( 【2】自动建造迷宫.（2）nn); printf( 【3】退出.（3）nn); printf(=n); printf(n); printf( 请选择菜单代号：); scanf(%d,&i); switch(i) case 1:printf(n请输入行数：);scanf(%d,&m); printf(n); printf(请输入列数：);scanf(%d,&n); printf(=n); while(m39)|(n39) printf(n系统消息！您的迷宫行数和列数不能超过39 ！nn); printf(请输入行数：);scanf(%d,&m); printf(n); printf(请输入列数：);scanf(%d,&n); printf(=n); shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); printf(nn按任意键继续游戏!n);getchar();while(getchar()!=n);break; case 2:printf(n请输入行数：);scanf(%d,&m); printf(n); printf(请输入列数：); scanf(%d,&n); printf(=n); while(m39)|(n39) printf(n系统消息！您的迷宫行数和列数不能超过39 ！nn); printf(请输入行数：);scanf(%d,&m); printf(n); printf(请输入列数：);scanf(%d,&n); printf(=n); zidong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); printf(nn按任意键继续游戏!n);getchar();while(getchar()!=n);break; case 3:cycle=(-1); break; default:printf(n); printf(你的输入有误!n);printf(n按任意键继续游戏!n);getchar();while(getchar()!=n);break; printf(=n);return 0;三、【实现描述（Implement）】(30%)Stack 成员函数实现/构造一个空栈Stack:Stack() top=NULL;StackSize = 0;/若栈S为空栈,返回true,否则返回falseint Stack:StackEmpty()if(top=NULL)return OK;return ERROR;/若栈不空,则用e返回S的栈顶元素,并返回ok;否则返回errorint Stack:GetTop(ElemType &e)if(top=NULL)return ERROR;e.di=top-di;e.ord=top-ord;e.seat=top-seat;return OK;/插入新元素e为新的栈顶元素int Stack:Push(ElemType &e)ElemType *p;p=new ElemType;if(p)p-next=top;top=p;top-di=e.di;top-ord=e.ord;top-seat=e.seat;StackSize+;elseexit(1);return OK;/若栈不空,删除S的栈顶元素,并用e返回其值,并返回true,否则返回falseint Stack:Pop(ElemType &e)ElemType *p;if(top=NULL)return ERROR;e.di=top-di;e.ord=top-ord;e.seat=top-seat;p=top;top=top-next;delete p;p=NULL;return OK;CmigongView 核心成员函数实现/ CmigongView 构造/析构CmigongView:CmigongView()/ TODO: 在此处添加构造代码int i;canshu luo1;luo1.DoModal();N=luo1.hangshu+2;M=luo1.lieshu+2;migong=new int *N; for(i=0;iN;i+)migongi=new int M;initial(migong);/初始化迷宫void CmigongView:initial(int *migong)int i,j,suiji;for(i=0;iN;i+)for(j=0;j0&jM-1)suiji=abs(rand()%12);if(suiji=0|suiji=5|suiji=6|suiji=1|suiji=8|suiji=3|suiji=11|suiji=9|suiji=7)suiji=1;elsesuiji=0;migongij=suiji;elsemigongij=2;/判断道路是否可通int CmigongView:Pass(PosType &seat)if(migongseat.rseat.c=1|migongseat.rseat.c=6)return OK;return ERROR;/给可通道路留下足迹void CmigongView:FootPrint(PosType &seat)migongseat.rseat.c=4;/判断迷宫是否已走出int CmigongView:jieshu(PosType &seat)if(seat.r=N-1&seat.c=M-2)return OK;return ERROR;/将当前的位置向下一个位置移动void CmigongView:NextPos(ElemType &cur,ElemType &e)cur.di+; e.ord=cur.ord+1;switch(cur.di)case 1:e.seat.c=cur.seat.c+1;e.seat.r=cur.seat.r;break;case 2:e.seat.r=cur.seat.r+1;e.seat.c=cur.seat.c;break;case 3:e.seat.c=cur.seat.c-1;e.seat.r=cur.seat.r;break;case 4:e.seat.r=cur.seat.r-1;e.seat.c=cur.seat.c;break;default:/exit(1);break;e.di=0;/复制数据e=curvoid CmigongView:Copy(ElemType &cur,ElemType &e)e.ord=cur.ord;e.seat.r=cur.seat.r;e.seat.c=cur.seat.c;e.di=cur.di;/标记死胡同void Cm