任务书1(迷宫问题)(共20页)

1、精选优质文档-倾情为你奉上课 程 设 计 报 告课程名称 数据结构课程设计 课题名称 迷宫问题 专 业 信息与计算科学 班 级 1002班 学 号 08 姓 名 田雯 指导教师 刘洞波 ××× 2012年 6月 9日课程设计任务书课程名称 数据结构课程设计 课 题 迷宫问题 专业班级 信科1002班 学生姓名 田雯 学 号 08 指导老师 刘洞波 审 批 任务书下达日期： 2012年 6月 9日任务完成日期： 2012年 6月 16日专心-专注-专业目 录3. 3 各模块的调用关系.2一、设计内容与设计要求1设计内容：1）问题描述以一个M*N的长方阵表示迷宫，0和

2、1分别表示迷宫中的通路和墙壁。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出米有通路的结论。2）基本要求a.实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。b.编写递归形式的算法，求得迷宫中所有可能的通路。3）测试数据迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。0010001000100010000011010111001000010000010001010111100111000101110000004）实现提示计算机解

3、迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则，沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。2设计要求：l 课程设计报告规范1)需求分析（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷

4、宫中的一个坐标，d表示走到下一坐标的方向。否则报告一个无法通过的信息。（2）建立InitStack函数，用于构造一个空栈。（3）建立DestroyStack函数，用于销毁栈。（4）建立Pop函数，用于删除栈顶元素，返回栈顶元素的值。（5）建立Push函数，用于插入新的栈顶元素。（6）建立NextPos函数，用于定位下一个位置。2)概要设计 31抽象数据类型定义（1）栈的抽象数据类型定义InitStack( LStack *S )操作结果：构造一个空栈S。DestroyStack( LStack *S )操作结果：栈S被销毁。Pop( LStack *S，ElemType *e )操作结果：删除

5、S的栈顶元素。用e返回栈顶元素的值。若栈为空则返回0。Push( LStack *S，ElemType e )操作结果：在栈顶之上插入元素e为新的栈顶元素。若栈S为空栈，则返回0。（2）迷宫的抽象数据类型定义 NextPos(unsigned *x，unsigned *y，short di)操作结果：找到下一个位置。32模块划分本程序包括三个模块：（1）主程序模块void main()初始化；构造迷宫；迷宫求解；迷宫输出；（2）栈模块实现栈的抽象数据类型（3）迷宫模块实现迷宫的抽象数据类型各模块的调用关系如下：4）求解迷宫的通路的伪码算法：设定当前位置的处值为入口位置；DO若当前的位置可通。则

6、将当前的位置插入栈顶；若该位置为出口位置，则结束；否则切换当前位置的东邻的为新的当前位置；否则若栈不为空且栈的顶位置尚有其他的方向没有被探索，则设定新的当前位置为沿顺时针方向旋转找到栈顶的位置的下一个相邻块；若栈不空但栈顶的四周均不可通过，则删去栈顶位置；若栈不为空，则重新测试新的栈顶位置；只至找到一个可通过的块至栈空；1 坐标的位置的类型typedef structint line;int row;PosType;2 迷宫类型void CreatMaze(int r,int l)/定义迷宫的墙为*，通路为_，障碍为#int i,j;for(i=0;i<r;i+)mazei0='

7、*'/左面墙mazeil-1='*'/右面墙for(j=1;j<l-1;j+)maze0j='*'/上面墙mazer-1j='*'/下面墙for(i=1;i<r-1;i+)for(j=1;j<l-1;j+)mazeij='_'cout<<"请输入迷宫内障碍物的个数："int num;cin>>num;cout<<"请依次输入障碍物的坐标："<<endl;int x,y;for(i=1;i<=num;i+)cin&

8、gt;>x>>y;mazexy='#'cout<<endl<<"创建的迷宫的如下："<<endl<<endl;PrintMaze(r,l);cout<<endl;4 迷宫的路径的算法int MazePath(PosType start,PosType end)InitStack(S);curpos=start;/ 设定当前位置为入口位置curstep=1;/第一步doif(Pass(curpos)/当前位置可以通过（未曾走过）FootPrint(curpos);/留下足迹e.ord

9、=curstep;e.seat=curpos;e.di=1;Push(S,e);/加入路径if(curpos.row=end.row&&curpos.line=end.line)/到达终点return TRUE;curpos=NextPos(curpos,1);/下一位置是当前位置的东邻curstep+;/探索下一步/ifelse/当前位置不能通过if(!StackEmpty(S)Pop(S,e);while(e.di=4&&!StackEmpty(S)MarkPrint(e.seat);/留下不能通过的标志Pop(S,e);/退回一步/curstep-;/wh

10、ileif(e.di<4)e.di+;/换下一个方向探索Push(S,e);curpos=NextPos(e.seat,e.di);/设定当前位置是该新方向上的相邻块/if/if/elsewhile(!StackEmpty(S);return FALSE;3)详细设计 41数据类型的定义（1）迷宫类型typedef struct unsigned ord, x, y；short di； ElemType；unsigned x, y, curstep,i=0；char maze1010；（2）栈类型typedef struct Node ElemType data；struct Node*

11、 next； Node, *LinkList；typedef struct LinkList top；unsigned length； LStack；LinkList q；LStack S,T；ElemType e；42主要模块的算法描述4.1函数寻找下一个位置流程图此函数的功能是寻找下一个位置。首先判断di的值，如果di=1，指针x+，退出。如果di=2，指针y+，退出。如果di=3，指针x-，退出。如果di=4，指针y-，退出。如果di为其它值，则直接退出。见图4.1。YNYNYYNNdi=1di=2di=3di=4Break；指针x自增；Break；指针y自增；Break；指针x自减；B

12、reak；指针y自减；Break；开始结束图4.1 函数寻找下一个位置流程图4.2 函数销毁栈流程图此函数的功能是销毁栈，首先建立单链表q，判断top指针是否为空，若为空则释放s的空间，否则出栈，直到top指针为空，释放s的空间。见图4.2。YNLinkList q；判断栈的top释放栈s的空间；出栈；开 始结 束图4.2 函数销毁栈流程图4.3 函数出栈流程图此函数的功能是出栈。首先建立单链表q，如果栈s为空则返回0，若栈s不为空，则出栈，修改指针。返回1。见图4.3。YNLinkList q；栈s为空出栈；Return 1；Return 0；开 始结 束图4.3 函数出栈流程图4.4 函数

13、入栈流程图此函数的功能是入栈。首先在链表中生成结点p，判断p是否为空。若为空则返回0，若非空，则入栈，修改指针，返回0。见图4.4。YN生成结点p；!p入栈；Return 1；Return 0；开 始结 束图4.4 函数入栈流程图4.5 主函数流程图主函数实现了求解迷宫，首先建立栈s和t，输出迷宫图形，然后探索路径，实现迷宫求解，最后输出出迷宫顺序。如果有完整路径则输出完整路径，如果没有完整路径则输出无法通过信息。见图4.5。 建立栈S和T； 输出迷宫图形； 迷宫求解； 输出出迷宫顺序；结 束 开 始图4.5 主函数流程4)调试分析（1）有一条完整路径通过迷宫的测试数据及结果。见图5.1。图5

14、.1 有一条完整路径通过迷宫的测试数据及结果从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。输出通路的坐标，即出迷宫的顺序。（2）没有路径能通过迷宫的测试数据及结果。见图5.2。图5.2 没有路径能通过迷宫的测试数据及结果从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至前面没有路径。输出此时无法通过，没有能够通过迷宫的路径的信息！ 5)课程设计总结通过这次课程设计使我充分的理解了用栈实现迷宫问题的基本原理，知道了栈存储结构的定义和算法描述，同时也学会了编写简单的迷

15、宫问题的程序。虽然此次的程序不是很完备，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。在刚开始编程的时候，错误百出，不知道怎么样改正，但是通过自己的仔细的分析和老师的细心的指导，在认真分析了原程序后，终于认识并理解了自己错误的地方，使自己加以改正，汲取教训。为以后知识水平的提高，做了最好的准备。在此我非常要感谢的是我们的指导老师申寿云老师，同时也要感谢我们的成娅辉老师平时上课的教导，和编程时细心认真的辅导，教给我许多知识。这次课程设计能够顺利的完成，当然有我个人的努力，但同时更离不开指导老师的答疑解惑。6)使用说明 先初始化栈，然后增加栈顶，撤销栈顶，再

16、输出栈，想出迷宫路径，最后撤出栈s，制造迷宫7)书写格式见附带说明。8)附录a.参考书目1 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20022 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，2003b.源程序清单（带注释）#include <stdio.h>#include <stdlib.h>typedef struct unsigned ord,x,y;/*通道块在路径上的序号和在迷宫中的坐标位置*/short di;/* 从此通道块走向下一通道块的"方向" */ElemType;typedef struct No

17、de /* 定义单链表 */ElemType data;struct Node* next;Node,*LinkList;typedef struct /* 定义链栈结构 */LinkList top; /* 栈顶指针 */unsigned length; /* 栈中元素个数 */LStack;void DestroyStack( LStack *S ) /* 销毁栈 */LinkList q;while ( S->top ) q = S->top;S->top = S->top->next; /* 修改栈顶指针 */free( q );/* 释放被删除的结点空间

18、 */S->length = 0; void InitStack( LStack *S ) /* 构造空栈 */S->top = NULL; /* 栈顶指针初值为空 */S->length = 0; /* 空栈中元素个数为 0 */ int Pop( LStack *S,ElemType *e ) /* 若栈不空,则删除 S 的栈顶元素,用 e 返回栈顶元素的值。*/LinkList q;if (!S->top ) return 0;*e=S->top->data; /* 返回栈顶元素 */q=S->top;S->top=S->top-&g

19、t;next; /* 修改栈顶指针 */-S->length;/* 栈的长度减1 */free(q);/* 释放被删除的结点空间 */return 1; int Push( LStack *S,ElemType e ) /* 在栈顶之上插入元素 e 为新的栈顶元素 */LinkList p=malloc(sizeof *p); /* 建新的结点 */if(!p) return 0; /* 存储分配失败 */p->data=e;p->next = S->top; /* 链接到原来的栈顶 */S->top = p; /* 移动栈顶指针 */+S->length;

20、 /* 栈的长度增1 */return 1; void NextPos(unsigned *,unsigned *,short); /* 定位下一个位置 */int main(void)LStack S,T;unsigned x,y,curstep,i=0;/* 迷宫坐标,探索步数 */ElemType e;char maze1010 = '#',' ','#','#','#','#','#','#','#','#','#

21、9;,' ',' ','#',' ',' ',' ','#',' ','#','#',' ',' ','#',' ',' ',' ','#',' ','#','#',' ',' ',' ',' ','#

22、9;,'#',' ',' ','#','#',' ','#','#','#',' ',' ',' ',' ','#','#',' ',' ',' ','#',' ',' ',' ',' ','#','#

23、9;,' ','#',' ',' ',' ','#',' ',' ','#','#',' ','#','#','#','#','#','#',' ','#','#','#',' ',' ',' ',' 

24、9;,' ',' ',' ','#','#','#','#','#','#','#','#','#',' ','#',;InitStack(&S);InitStack(&T);printf("迷宫图形,#号代表墙壁,空格代表通路:n");for(x=0;x<10;x+) for(y=0;y<10;y+) printf(&quo

25、t;%c",mazexy);printf("n");x=1; /*迷宫起点*/y=0;curstep=1; /* 探索第一步 */do /* 进入迷宫 */if(mazeyx=' ') /* 如果当前位置可以通过 */mazeyx='1'/* 留下足迹 */e.x=x;e.y=y;e.di=1;e.ord = curstep;if(!Push(&S,e) /* 加入路径,即压栈 */fprintf( stderr,"内存不足。n" );if(x=8&&y=9) /* 到达终点 */brea

26、k;NextPos(&x, &y, 1); /* 下一位置是当前位置的东邻 */curstep+; else /* 如果当前位置不能通过 */if (S.length!=0) Pop(&S,&e);while(e.di = 4 && S.length!=0) mazee.ye.x='0' /* 留下不能通过足迹 */Pop(&S, &e); /* 退回一步,即出栈 */if(e.di<4)e.di+;if(!Push(&S,e) /* 加入路径,即压栈 */fprintf(stderr,"内

27、存不足。n");x=e.x; /* 重置坐标 */y=e.y;NextPos(&x,&y,e.di); /* 寻找下一位置 */while(S.length!=0);printf("走出迷宫路线,1代表走过的路,0代表试探过的路径n");for(x=0;x<10;x+) for(y=0;y<10;y+) printf("%c",mazexy);if(mazexy='1')i+;printf("n");for(x=0;x<i;x+)Pop(&S,&e);Push(&T,e);printf("出迷宫顺序,（X坐标,Y坐标,前进方向）:n");while(T.length!=0)printf("(%d,%d,%d)t",T.top->