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

《任务书1(迷宫问题)(共20页).doc》由会员分享，可在线阅读，更多相关《任务书1(迷宫问题)(共20页).doc（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出米有通路的结论。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）指示迷宫中的一个坐标，d表示走到下一坐标的方

4、向。否则报告一个无法通过的信息。（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 )操作结果：删除S的栈顶元素。用e返回栈顶元素的值。若

5、栈为空则返回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;ir;i+)mazei0=*;/左面墙mazeil-1=*;/右面墙for(j=1

7、;jl-1;j+)maze0j=*;/上面墙mazer-1j=*;/下面墙for(i=1;ir-1;i+)for(j=1;jl-1;j+)mazeij=_;coutnum;cout请依次输入障碍物的坐标：endl;int x,y;for(i=1;ixy;mazexy=#;coutendl创建的迷宫的如下：endlendl;PrintMaze(r,l);coutendl;4 迷宫的路径的算法int MazePath(PosType start,PosType end)InitStack(S);curpos=start;/ 设定当前位置为入口位置curstep=1;/第一步doif(Pass(cu

8、rpos)/当前位置可以通过（未曾走过）FootPrint(curpos);/留下足迹e.ord=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);/留下不能通过

9、的标志Pop(S,e);/退回一步/curstep-;/whileif(e.di4)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

10、ElemType data；struct Node* 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自增

11、；Break；指针y自增；Break；指针x自减；Break；指针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

12、0；开 始结 束图4.3 函数出栈流程图4.4 函数入栈流程图此函数的功能是入栈。首先在链表中生成结点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）有一

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

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

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

16、mType 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 );/* 释放被删除的结点空间 */S-length = 0; void InitStack( LSta

17、ck *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-next; /* 修改栈顶指针 */-S-length;/* 栈的长度减1 */free(q);/* 释放被删除的结点空间 */return 1; i

18、nt 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; /* 栈的长度增1 */return 1; void NextPos(unsigned *,unsigned *,short); /* 定位下一个位置 */int main(void)LStack S

19、,T;unsigned x,y,curstep,i=0;/* 迷宫坐标,探索步数 */ElemType e;char maze1010 = #, ,#,#,#,#,#,#,#,#,#, , ,#, , , ,#, ,#,#, , ,#, , , ,#, ,#,#, , , , ,#,#, , ,#,#, ,#,#,#, , , , ,#,#, , , ,#, , , , ,#,#, ,#, , , ,#, , ,#,#, ,#,#,#,#,#,#, ,#,#,#, , , , , , , ,#,#,#,#,#,#,#,#,#, ,#,;InitStack(&S);InitStack(&T);p

20、rintf(迷宫图形,#号代表墙壁,空格代表通路:n);for(x=0;x10;x+) for(y=0;y10;y+) printf(%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) /* 到达终点 */b

21、reak;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.di4)e.di+;if(!Push(&S,e) /* 加入路径,即压栈 */fprintf(stderr,内存不足。n);x=e.x; /* 重置坐标 */y=e.y;NextPos(&x,&y,e.di); /*

22、 寻找下一位置 */while(S.length!=0);printf(走出迷宫路线,1代表走过的路,0代表试探过的路径n);for(x=0;x10;x+) for(y=0;y10;y+) printf(%c,mazexy);if(mazexy=1)i+;printf(n);for(x=0;xdata.x,T.top-data.y,T.top-data.di);Pop(&T,&e);DestroyStack(&S);getchar();return 0;void NextPos(unsigned *x,unsigned *y,short di) /* 定位下一个位置 */switch(di)

23、case 1:+(*x);break;case 2:+(*y);break;case 3:-(*x);break;case 4:-(*y);break;default:break;l 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分： 平时出勤 （占10%） 系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%） 程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%） 设计报告（占30%）注意：不得抄袭他人的

24、报告（或给他人抄袭），一旦发现，成绩为零分。 独立完成情况（占10%）。l 课程验收要求 运行所设计的系统。 回答有关问题。 提交课程设计报告纸质稿。 提交源程序、设计报告文档电子稿。 依内容的创新程度，完善程序情况及对程序讲解情况打分。二、进度安排附：课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在5000字以上（不含程序原代码）。计算机与通信学院课程设计评分表课题名称： 迷宫问题 项 目评 价设计方案的合理性与创造性设计与调试结果设计说明书的质量答辩陈述与回答问题情况课程设计周表现情况综合成绩 教师签名： 日 期：