C++数据结构迷宫问题

1、隼察关通土号课程设计(论文)任务书软件学院软件工程+电子商务2009专业2班一、课程设计(论文)题目迷宫问题二、课程设计(论文)工作自2010年12月27日起至2011年1月2日止三、课程设计(论文)地点：创新大楼实训中心四、课程设计(论文)内容要求：1 .本课程设计的目的(1)巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。(2)使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。(3)使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。2 .课程设计的任务及要求1)基本要求:(1)对系统进行功能模块分析、控制模块分析；(2)系

2、统设计要能完成题目所要求的功能；(3)编程简练，可用，尽可能的使系统的功能更加完善和全面;(4)说明书、流程图要清楚；(5)提高学生的论文写作能力；一(6)特别要求自己独立完成；2)创新要求:在基本要求达到后，可进行创新设计，如改善算法性能、友好的人机界面。3)课程设计论文编写要求(1)要按照书稿的规格打印与写课程设计论文(2)论文包括目录、正文、小结、参考文献、附录等(3)课程设计论文装订按学校的统一要求完成4）课程设计进度安排天数构思及收集资料1图书馆编码与调试3实验室撰写论文1图书馆、实验室学生签名：20011年1月3日课程设计（论文）评审意见（1）基本算法（20分）优（）、良（）、中（

3、）、f(）、差(）；（2）设计分析（20分）优（）、良（）、中（）、f(）、差(）；（3）调试分析（20分）优（）、良（）、中（）、f(）、差(）；（4）论文内容（20分）优（）、良（）、中（）、f(）、差(）；（5）答辩分析（20分）优（）、良（）、中（）、f(）、差(）；（6）格式规范性及考勤是否降等级:是（）、否（)评阅人：职称：讲师2011年1月4日目录一、需求分析1二、概要设计23、 详细设计54、 调试分析及测试15五、个人工作及创新18六、小结19参考文献20需求分析1 .选题理由本次课设我选择了迷宫问题，迷宫求解是数据结构课程的一个经典问题,迷宫问题要求寻找一条从入口到出口的路

4、径。通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫通路的算法中要应用“栈”的思想。对于栈的内容在整个学期的学习中我也有了一定的了解，所以选择了迷宫这一经典问题作为本次课设的内容。2 .基本原理分析迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。以二维数组存储迷宫数

5、据，通常设定入口点的下标为(1,1),出口点的下标为(n,n)。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。3 .功能要求(1)以一个二维数组Mazem+2n+2表示迷宫，其中：Maze0j和Mazem+1j(0<=j<=n+1)及Mazei0和Mazein+1(0<=i<=m+1)为做外层的一圈障碍。数组中以0表示通路，1表示障碍，限定迷宫的大小为：m,n<=1Q(2)用户需用文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n；从第2行至第m+1行(每行n个数)为迷宫值，用0,1输入，同行中的两

6、个数字之间用空白字符相隔。(3)迷宫的入口位置和出口位置可由用户随时设定。(4)若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件上，其中字符“#”表示障碍，“*”表示路径，”表示曾途经该位置但不能到达出口，其余位置用空格符表示。若设定迷宫不存在通路则报告相应信息(5)本程序只求出一条成功的通路。(6)程序执行白命令为：1,创建迷宫；2,求解迷宫；3,输出迷宫的概要设计1、数据结构及其抽象数据类型的定义。(1)栈的抽象数据类型ADTStack数据对象：D=ai|aiCharSet,i=1,2,n,n>=0数据关系:R1=<ai-1,ai>|ai-1,aiCD

7、,i=2,n基本操作：InitStack(&S)操作结果：构造一个空栈SoDestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈SoClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE否则返回FALSEGetTop(S,&e)初始条件：栈S已存在。操作结果：若栈S不空，则以e返回栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的

8、栈顶元素e。Pop(&S,&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse(S,visit()初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit()ADTStack(2)迷宫的抽象数据类型ADTmaze数据对象：D=ai,j|ai,jC'','#','','*',O<=i<=m+1,0<=j<=n+1,m,n<=10数据关系：R=ROW,COL基本操作：InitMaze(&M,a,row,col)

9、初始条件：二维数组arow+2col+2已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。操作结果：构成迷宫的字符型数组，以空白字符表示通路，以字符#'表示障碍，并在迷宫四周加上一圈障碍。MazePath(&M)初始条件：迷宫M已被赋值。操作结果：若迷宫M中存在一条通路，则按以下规定改变迷宫M的状态：以字符表示路径上的位置，字符表示“死胡同”，否则迷宫的状态不变。PrintMaze(M初始条件：迷宫M已存在。操作结果：以字符形式输出迷宫。ADTmaze2、整体框架本程序包含三个模块(1)栈模块一一实现栈抽象数据

10、类型(2)迷宫模块一一实现迷宫抽象数据类型(3)主程序模块：voidmian()初始化；Do接受命令；处理命令；while(命令!=“退出”);各模块之间的调用关系如图一：主程序模块迷宫模块林蟆块图一：调用关系图函数的调用关系图反映了程序的层次结构如图二：主程殍一clniri»h>4(ionRcadCommendInlcrprctInitMazeMasathPrirrtMaze.rniIItiitStackKushHopSrack£mptyStackTreverserriJIFootPrintMarkPrintPassNEitPnsSarne图二：函数的调用关系图三、

11、详细设计源程序：#include<stdio.h>#include<stdlib.h>#include<string.h># defineMAXLEN10/迷宫包括外墙最大行列数目# defineTRUE1# defineFALSE0# defineOK1#defineERROR0typedefintStatus;/坐标位置类型typedefstructintr,c;PosType;/迷宫中r行c列的位置/迷宫类型typedefstructintr;intc;chararrMAXLENMAXLEN;/可取'','*','

12、;','#'MazeType;typedefstruct/intstep;/当前位置在路径上的“序号”PosTypeseat;/当前的坐标位置intdi;/往下一坐标位置的方向SElemType;/结点类型typedefstructNodeTypeSElemTypedata;NodeType*next;NodeType,*LinkType;/栈类型typedefstructLinkTypetop;intstacksize;SqStack;PosTypestart;PosTypeend;MazeTypemaze;boolfound;/创建栈StatusInitStack(

13、SqStack&S)S.top=(LinkType)malloc(sizeof(NodeType);S.top->next=NULL;S.stacksize=0;returnOK;/进栈StatusPush(SqStack&S,SElemType&e)LinkTypep;p=(NodeType*)malloc(sizeof(NodeType);p->data=e;p->next=S.top;S.top=p;S.stacksize+;returnOK;/判断是否为栈空StatusStackEmpty(SqStackS)if(S.top->next=

14、NULL)returnOK;returnERROR;)/出栈StatusPop(SqStack&S,SElemType&e)(LinkTypep;if(StackEmpty(S)returnERROR;p=S.top;e=p->data;S.top=S.top->next;S.stacksize-;free(p);returnOK;)/销毁栈StatusDestroyStack(SqStack&S)(LinkTypep;while(S.top!=NULL)(p=S.top;S.top=S.top->next;free(p);/一个一个删除if(S.to

15、p=NULL)returnOK;elsereturnERROR;/曾走过但不是通路标记并返回OKStatusMarkPrint(MazeType&maze,PosTypecurpos)(maze.arrcurpos.rcurpos.c=''/""表示曾走过但不通returnOK;/曾走过而且是通路标记并返回OKStatusFootPrint(MazeType&maze,PosTypecurpos)(表示可通maze.arrcurpos.rcurpos.c='*'/"*"returnOK;/选择下一步的方向P

16、osTypeNextPos(PosType&curpos,inti)(PosTypecpos;cpos=curpos;switch(i)/1.2.3.4分别表示东，南，西,北方向case 1 :cpos.c+=1;break;case 2 :cpos.r+=1;break;case 3 :cpos.c-=1;break;case 4 :cpos.r-=1;break;returncpos;/判断当前位置是否可通StatusPass(MazeType&maze,PosTypecurpos)if(maze.arrcurpos.rcurpos.c='')returnT

17、RUE;elsereturnFALSE;/创建迷宫/按照用户输入的二维数组（0或1）,设置迷宫maze的初值，包括加上边缘一圈的值voidInitMaze（MazeType&maze,charaMAXLENMAXLENintrow,intcol)maze.r=row;maze.c=col;for(inti=0;i<=col+1;i+)a0i='1'arow+1i='1'for(i=0;i<=row+1;i+)ai0='1'aicol+1='1'for(i=0;i<=maze.r+2;i+)for(intj

18、=0;j<maze.c+2;j+)if(aij='1')maze.arrij='#'elsemaze.arrij=''/求迷宫路径的伪码算法：StatusMazePath(MazeType&maze,PosTypestart,PosTypeend)/求解迷宫maze中，从入口start到出口end的一条路径，若存在，返回TRUE否则返回FALSEPosTypecurpos;SqStackS;SElemTypee;InitStack(S);curpos=start;/设定“当前位置”为“入口位置”/curstep=1;/探索第一步fo

19、und=false;doif(Pass(maze,curpos)/当前位置可以通过，即是未曾走到过的通道块留下足迹FootPrint(maze,curpos);/做可以通过的标识/e.step=curstep;e.seat=curpos;e.di=1;/为栈顶元素赋值Push(S,e);/加入路径if(curpos.r=end.r&&curpos.c=end.c)found=true;/终点返回trueelsecurpos=NextPos(curpos,1);/else/当前位置不能通过if(!StackEmpty(S)Pop(S,e);while(e.di=4&&am

20、p;!StackEmpty(S)MarkPrint(maze,e.seat);/Pop(S,e);if(e.di<4)e.di+;/换下个方向Push(S,e);/curpos=NextPos(e.seat,e.di);/while(!StackEmpty(S)&&!found);DestroyStack(S);returnfound;如果到达下一位置是当前位置的东邻留下不能通过的标记进行探索/将标记路径信息的迷宫(字符型方阵)输出到终端(包括外墙)voidPrintMaze(MazeType&maze)for(inti=0;i<=maze.r+2;i+)f

21、or(intj=0;j<=maze.c+2;j+)printf("%c",maze.arrij);/输出迷宫/系统初始化voidInitialization()(system("cls");printf("welcometothegame!");printf("nprintf("n*创建迷宫-c执行迷宫-m输出迷宫-p退出-q*");printf("nprintf("nn操作:-");/读入操作命令符，显示提示信息voidReadCommand(char&cmd

22、)doif(cmd='c')printf("n*"):printf("n*选择操作：执行迷宫-m*");printf("n*退出-:q*");printf("n*");printf("nn)elseif(cmd='m')操作:-");printf("n*");printf("n*printf("n*选择操作：输出迷宫-p*");退出-:q*");printf("n*");printf(

23、"nn操作:-");elseif(cmd='p')printf("n*");printf("n*选择操作：执行迷宫-c*");printf("n*退出-:q*");printf("n*H);printf("nn操作:-");)cmd=getchar();while(!(cmd='c'|cmd='m'|cmd='p'|cmd='q');)/解释cmd-具体执行voidInterpre(charcmd)swit

24、ch(cmd)case'c':intrnum,cnum,i=0,m=1,n=1;chara2MAXLENMAXLEN;charinput1;chardata1000;printf("n请输入迷宫数据文件名！n");scanf("%s",input);FILE*fp;fp=fopen(input,"r");if(!fp)printf("n不能打开文件n");break;while(!feof(fp)fscanf(fp,"%s",&datai);if(i=0)rnum=(in

25、t)datai-(int)'0'if(i=1)cnum=(int)datai-(int)'0'if(i>=2)(if(n>cnum)m+;n=1;a2mn=datai;n+;i+;fclose(fp);InitMaze(maze,a2,rnum,cnum);printf("n迷宫建立完成！n");break;case'm':printf("n请输入迷宫入口的坐标，以空格为间隔:-");scanf("%d%d",&start.r,&start.c);printf

26、("n请输入迷宫出口的坐标，以空格为间隔:-");scanf("%d%d",&end.r,&end.c);MazePath(maze,start,end);break;case'p':if(found)printf("n求解迷宫的结果如下-n");PrintMaze(maze);elseprintf("n找不到路径！n");voidmain()charcmd;Initialization();doReadCommand(cmd);/Interpre(cmd);/while(cmd!=

27、'q');)读入一个操作符命令解释执行命令操作符四、调试分析及测试1、调试分析：(1)本程序有一个核心算法，即求迷宫的路径，在调试的时候，出现了两个问题：没有想到要用记号，导致迷宫走不出来；没有设置found',不知何时跳出。(2)原本栈的元素e中除了di一往下一坐标位置的方向和seat一当前的坐标位置，还有一个step一当前位置在路径上的序号，后来发现step没什么用，就删掉了。(3)函数ReadCommarfd,cmd=getchar();的位置找不准，最后是试出来的。(4)调试的时候多次出现，没有错误，但是dos环境下就是执行不起来，所以采用了一些输出变量，判断到

28、底是哪里出了问题。(5)本程序中三个主要的算法：InitMaze,MazePath和MarkPrint的时间复杂度均为O(m*n),本程序的空间复杂度也为O(m*n)(栈所占最大空问)2、使用说明和运行结果：(1)首先以文件形式输入迷宫数据，如图三：Qle.透本回文件遍耨。格式qMM幅助时图三(2)进入演示程序后，会出现以下界面如图四:OO1OQO1oO11±ooO11nVnV1i_图四(3)进入“创建迷宫”的命令后，即提示输入迷宫数据的文件名，结束符为“回车符”，该命令执行之后输出“迷宫建立完成”，且输出下面可执行的操作。如图五：冬五(4)进入“执行迷宫”的命令后，即提示输入迷宫入口，出口的坐标,结束符为“回车符”，该命令执行之后表示迷宫路径已寻找完成或未找到路径。请注意：若迷宫中存在路径，执行此命令后，迷宫状态已经改变，若要重复执行此命令，需重新输入迷宫数据。如图六：图六(5)进入“输出迷宫”的命令后，即输出迷宫求出路径之后的状态。#表示障碍，表示曾走过但不通，'*'表示路径。如图七：图七(6)进入“退出”的命令后，按任意键结束。如图八:图八3、缺点与改进：(1)在定义函数Mazepath的时候，开始的循环语句的结束条件不对，没有出路时，导致一直出现了不正确的结果，最后没有新位置入栈，则返回上一个位置，否则没有路径。(2