任务书1(迷宫问题)

任务书1(迷宫问题)任务书1(迷宫问题)任务书1(迷宫问题)任务书1(迷宫问题)编制仅供参考审核批准生效日期地址：电话：传真:邮编:课程设计报告课程名称数据结构课程设计课题名称迷宫问题专业信息与计算科学班级1002班学号08姓名田雯指导教师刘洞波×××201

课程设计任务书课程名称数据结构课程设计课题迷宫问题专业班级信科1002班学生姓名田雯学号08指导老师刘洞波审批任务书下达日期：2012年任务完成日期：2012年6月16日 目录 TOC\o"1-2"\h\z\u1问题描述 12需求分析 13概要设计 13．1抽象数据类型定义 13．2模块划分 23.3各模块的调用关系….24详细设计 24．1数据类型的定义 24．2主要模块的算法描述 35测试分析 66课程设计总结 7参考文献 8附录（源程序清单） 9一、设计内容与设计要求1．设计内容：1）问题描述以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和墙壁。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出米有通路的结论。2）基本要求a.实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。b.编写递归形式的算法，求得迷宫中所有可能的通路。3）测试数据迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。0010001000100010000011010111001000010000010001010111100111000101110000004）实现提示计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则，沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。2．设计要求：课程设计报告规范1)需求分析（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。否则报告一个无法通过的信息。（2）建立InitStack函数，用于构造一个空栈。（3）建立DestroyStack函数，用于销毁栈。（4）建立Pop函数，用于删除栈顶元素，返回栈顶元素的值。（5）建立Push函数，用于插入新的栈顶元素。（6）建立NextPos函数，用于定位下一个位置。2)概要设计3．1抽象数据类型定义（1）栈的抽象数据类型定义InitStack(LStack*S)操作结果：构造一个空栈S。DestroyStack(LStack*S)操作结果：栈S被销毁。Pop(LStack*S，ElemType*e)操作结果：删除S的栈顶元素。用e返回栈顶元素的值。若栈为空则返回0。Push(LStack*S，ElemTypee)操作结果：在栈顶之上插入元素e为新的栈顶元素。若栈S为空栈，则返回0。（2）迷宫的抽象数据类型定义NextPos(unsigned*x，unsigned*y，shortdi)操作结果：找到下一个位置。3．2模块划分本程序包括三个模块：（1）主程序模块voidmain(){初始化；构造迷宫；迷宫求解；迷宫输出；}（2）栈模块——实现栈的抽象数据类型（3）迷宫模块——实现迷宫的抽象数据类型各模块的调用关系如下：4）求解迷宫的通路的伪码算法：设定当前位置的处值为入口位置；DO{若当前的位置可通。则{将当前的位置插入栈顶；若该位置为出口位置，则结束；否则切换当前位置的东邻的为新的当前位置；}否则{若栈不为空且栈的顶位置尚有其他的方向没有被探索，则设定新的当前位置为沿顺时针方向旋转找到栈顶的位置的下一个相邻块；若栈不空但栈顶的四周均不可通过，则{删去栈顶位置；若栈不为空，则重新测试新的栈顶位置；只至找到一个可通过的块至栈空；}1坐标的位置的类型typedefstruct{ intline; introw;}PosType;2迷宫类型voidCreatMaze(intr,intl)YNYNYYNNdi=1di=2di=3di=4Break；指针x自增；Break；指针y自增；BreakYNYNYYNNdi=1di=2di=3di=4Break；指针x自增；Break；指针y自增；Break；指针x自减；Break；指针y自减；Break；开始结束YNLinkListq；判断栈的top释放栈s的空间；出栈；开始结束YNLinkListq；栈s为空出栈；Return1；Return0；开始结束YN生成结点p；!p入栈；Return1；Return0；开始结束建立栈S和T；输出迷宫图形；迷宫求解；输出出迷宫顺序；结束开始[1]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2002[2]刘振鹏，张晓莉，郝杰．数据结构[M]．北京：中国铁道出版社，2003b.源程序清单（带注释）#include<>#include<>typedefstruct{ unsignedord,x,y;/*通道块在路径上的序号和在迷宫中的坐标位置*/ shortdi;/*从此通道块走向下一通道块的"方向"*/}ElemType;typedefstructNode{/*定义单链表*/ ElemTypedata; structNode*next;}Node,*LinkList;typedefstruct{/*定义链栈结构*/ LinkListtop;/*栈顶指针*/ unsignedlength;/*栈中元素个数*/}LStack;voidDestroyStack(LStack*S)/*销毁栈*/{ LinkListq; while(S->top) { q=S->top; S->top=S->top->next;/*修改栈顶指针*/ free(q);/*释放被删除的结点空间*/ } S->length=0;}voidInitStack(LStack*S)/*构造空栈*/{ S->top=NULL;/*栈顶指针初值为空*/ S->length=0;/*空栈中元素个数为0*/}intPop(LStack*S,ElemType*e){/*若栈不空,则删除S的栈顶元素,用e返回栈顶元素的值。*/ LinkListq; if(!S->top) { return0; } *e=S->top->data;/*返回栈顶元素*/ q=S->top; S->top=S->top->next;/*修改栈顶指针*/ --S->length;/*栈的长度减1*/ free(q);/*释放被删除的结点空间*/ return1;}intPush(LStack*S,ElemTypee){/*在栈顶之上插入元素e为新的栈顶元素*/ LinkListp=malloc(sizeof*p);/*建新的结点*/ if(!p) { return0;/*存储分配失败*/ } p->data=e; p->next=S->top;/*链接到原来的栈顶*/ S->top=p;/*移动栈顶指针*/ ++S->length;/*栈的长度增1*/ return1;}voidNextPos(unsigned*,unsigned*,short);/*定位下一个位置*/intmain(void){ LStackS,T; unsignedx,y,curstep,i=0;/*迷宫坐标,探索步数*/ ElemTypee; charmaze[10][10]= { {'#','','#','#','#','#','#','#','#','#'}, {'#','','','#','','','','#','','#'}, {'#','','','#','','','','#','','#'}, {'#','','','','','#','#','','','#'}, {'#','','#','#','#','','','','','#'}, {'#','','','','#','','','','','#'}, {'#','','#','','','','#','','','#'}, {'#','','#','#','#','#','#','#','','#'}, {'#','#','','','','','','','','#'}, {'#','#','#','#','#','#','#','#','','#'}, }; InitStack(&S); InitStack(&T); printf("迷宫图形,#号代表墙壁,空格代表通路:\n"); for(x=0;x<10;x++) { for(y=0;y<10;y++) printf("%c",maze[x][y]); printf("\n"); } x=1;/*迷宫起点*/ y=0; curstep=1;/*探索第一步*/ do{/*进入迷宫*/ if(maze[y][x]=='') {/*如果当前位置可以通过*/ maze[y][x]='1';/*留下足迹*/ =x; =y; =1; =curstep; if(!Push(&S,e)) {/*加入路径,即压栈*/ fprintf(stderr,"内存不足。\n"); } if(x==8&&y==9) {/*到达终点*/ break; } NextPos(&x,&y,1);/*下一位置是当前位置的东邻*/ curstep++; } else{/*如果当前位置不能通过*/ if!=0) { Pop(&S,&e); while==4&&!=0) { maze[][]='0';/*留下不能通过足迹*/ Pop(&S,&e);/*退回一步,即出栈*/ } if<4) { ++; if(!Push(&S,e)) {/*加入路径,即压栈*/ fprintf(stderr,"内存不足。\n"); } x=;/*重置坐标*/ y=; NextPos(&x,&y,;/*寻找下一位置*/ } } } } while!=0); printf("走出迷宫路线,1代表走过的路,0代表试探过的路径\n"); for(x=0;x<10;x++) { for(y=0;y<10;y++) { printf("%c",maze[x][y]); if(maze[x][y]=='1') i++; } printf("\n"); } for(x=0;x<i;x++) { Pop(&S,&e); Push(&T,e); } printf("出迷宫顺序,（X坐标,Y坐标,前进方向）:\n"); while!=0) { printf("(%d,%d,%d)\t",>,>,>; Pop(&T,&e); } DestroyStack(&S); getchar(); return0;}voidNextPos(unsigned*x,unsigned*y,shortdi)/*定位下一个位置*/{ switch(di) { case1:++(*x); break; case2:++(*y); break; case3:--(*x); break; case4:--(*y); break; default: break; }}考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几