迷宫课程设计报告.doc

西安郵電大學数据结构课程设计报告题 目： 迷宫问题院系名称： 计算机学院 专业名称： 软件工程班 级： 1101 学生姓名： 武妍娜学号（8位）： 04113027指导教师： 李培 设计起止时间：2012年12月3日2012年12月14日一. 设计目的1.熟悉C语言程序的编辑、编译链接和运行的过程，能够熟练地编辑、编译及调试程序。2.掌握文件和文件指针的概念以及文件的定义方法，学会熟练使用文件打开、关闭、读、写 等基本操作。3.熟练掌握结构体、链表、指针的使用，及函数间的调用。4.能够熟练运用所学栈的相关知识及操作，顺利完成题目的要求。二. 设计内容迷宫是实验心理学中一个古典问题。用计算机解迷宫路径的程序，就是仿照人走迷宫。计算机解迷宫时，通常用的是穷举求解的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。 1.功能与数据需求 迷宫求解问题描述：以一个MN的矩阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。1.1 题目要求的功能 （1）基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以二元组（i,j）的形式输出，其中：（i,j）指迷宫中对应的坐标。 （2）测试数据：左上角（1,1）为入口，右下角（9,8）为出口。左上角（1,1）为入口，右上角（1,8）为出口。（3） 如下图所示： 1.2 扩展功能（1）编写非递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路2.界面需求（1）在菜单中选择要执行的操作（2）输出方阵迷宫（3）用户自己输入迷宫起始位置（4）输出所走的迷宫路径（5）输出方阵路径，并保存到文件中3.开发环境与运行需求Microsoft Visual C+6.0Ubuntu 三概要设计主模块1功能模块图；本程序包含三个模块（1）主程序模块：void main（）文件模块栈模块迷宫模块初始化；do接受命令；处理命令；while（命令！=“退出”）；（2）栈模块实现栈抽象数据类型（3） 迷宫模块实现迷宫抽象数据类型2 各个模块详细的功能描述。（1）菜单：从菜单中选择要执行的操作（2）文件模块：实现文件的各项基本操作a）打开文件b）关闭文件c）从文件读信息d）向文件中写入内容（3）栈模块：实现栈的各项基本操作a）初始化栈b）入栈c）出栈d）取栈顶元素(4）迷宫模块：求解迷宫问题a）显示迷宫b)获取迷宫路径c）判断当前路径是否走过d）获得下一个可走的位置e）获得东面，南面，西面，北面相邻的位置4 详细设计1功能函数的调用关系图打开源文件输出迷宫路径判断当前路径是否走过显示迷宫主函数 入栈 出栈获得迷宫路径初始化栈菜单获得下一个可走的位置显示迷宫路线保存迷宫路线取栈顶元素开始2.各功能函数的数据流程图MStackElem start,cur;p2=head;（1） 获得迷宫路径函数cur= start; do while (cur.x != chukou0 | cur.y != chukou1)当前位置是否走过Push(&realPath,cur)Push(&path,cur);cur = GetNext(cur);cur=GetNext(cur); 是 否 else ifcur.val=-1Push(&realPath,cur)Push(&path,cur);return 1; ifcur.x=chukou0&cur.y=chukou1 Pop(&realPath);cur=GetTop(&realPath) 开始(2) 获得下一个可通行的位置GetEast(cur).val=&UnPass(path,GetEast(cur)GetWest(cur).val=&UnPass(path,GetWest(cur)MStackElem next;next.x=next.y=next.val = -1; if else if GetNorth(cur).val=&UnPass(path,GetNorth(cur)GetSouth(cur).val=&UnPass(path,GetSouth(cur) else if else ifnext= GetSouth(cur);next= North(cur);next= GetEast(cur);next= GetEast(cur);3.重点设计及编码获得迷宫路径的函数：int GetMazePath() MStackElem start,cur; start.x = rukou0;start.y = rukou1; start.val = Mazerukou0rukou1; cur = start; do if (UnPass(path,cur) Push(&realPath,cur); Push(&path,cur); cur = GetNext(cur); if (cur.x = chukou0 & cur.y = chukou1) Push(&realPath,cur); Push(&path,cur); return 1; else if(cur.val = -1) Pop(&realPath); cur = GetTop(&realPath); else cur = GetNext(cur); if (cur.val = -1) Pop(&realPath); cur = GetTop(&realPath); while (cur.x != chukou0 | cur.y != chukou1);return 0;五测试数据及运行结果1正常测试数据和运行结果 2.异常测试数据及运行结果 六调试情况，设计技巧及体会1改进方案在迷宫问题中，由于走的方向顺序不同，存在着多条路径的结果。因此就出现了一个最大的问题，哪条路径最短，即求最短路径。由于时间有限和难度问题，我没能及时解决这个问题，这也是在这次的迷宫课程设计中，我唯一的不足之处。不过我并没有放弃，课程设计结束后，我还会继续努力，解决掉这个问题。在以后的生活中，我也会不断督促自己，提高编程能力。2体会刚开始，头脑里没有任何思路，不知道如何下手，经过仔细研读课本和上网查资料后，终于有了思绪。先将整个程序划分为三个大模块：主模块，栈模块和迷宫模块。然后再依次实现每个大模块中的小操作。最后将所有的程序拼接起来，进行调试。我觉得所有模块中最难编的就是查找迷宫路径函数，经过苦思冥想，再加上老师和同学的帮助，总算做出来了，但是非常复杂。在编译的过程中总会出现五花八门的错误，比如：从文件里读不出信息，又或者是存不进去文件，或者是乱码等。后来才发现原来是源文件中存的信息类型和程序中定义的类型不匹配，经过改正之后果然正确了。改正完后，当把所有的小块连接在一起时，虽然没有错误，但是总有许多警告语句，运行的结果也不尽人意。通过上网查资料后，发现这都是一些格式问题。看来编程格式很重要啊！经过两个星期的上机实践学习，我才发现我的C语言上机实践能力还有待加强，有待进步。以后不但要重视课本与习题，更要重视上机实践。七参考文献1. 耿国华主编，数据结构C语言描述，高等教育出版社，2005年2. 陈锐，数据结构（C语言版），清华大学出版社 2012年八附录#include #include #include #define M 11/迷宫行数#define N 10/迷宫列数#define STACK_INIT_SIZE 100#define STACKINCREMENT 10char MazeMN=0;/迷宫char sMN=0;/迷宫路线图int rukou2,chukou2;/定义栈元素类型typedef struct int x;/x坐标 int y;/y坐标 char val;/Mazexy的值MStackElem;/定义栈typedef struct MStackElem * base; MStackElem * top; int StackSize;MStack; /初始化栈InitStack(MStack *S) S-base = (MStackElem *)malloc(STACK_INIT_SIZE * sizeof(MStackElem); if (!S-base) printf(初始化栈失败!n); exit(-1);/存储分配失败 S-top = S-base; S-StackSize = STACK_INIT_SIZE;/入栈Push(MStack *S,MStackElem e) /向栈中添加元素前先判断栈是否还有空间容纳新元素 if (S-top - S-base = S-StackSize)/栈满,追加元素 S-base = (MStackElem *)realloc(S-base, (STACK_INIT_SIZE+STACKINCREMENT) * sizeof(MStackElem); if (!S-base) printf(空间不足，入栈失败!n);exit(-1);/存储分配失败 S-top = S-base + S-StackSize; /因为是重新分配了空间,所以base的值其实已经改变,所以top的值也就相应的改变,才能指向新的迷宫栈 S-StackSize += STACKINCREMENT; *(S-top+) = e;/将新元素加到栈顶 /获得栈顶元素MStackElem GetTop(MStack *S) if (S-top = S-base)printf(n对不起，没有出路!nn);exit(0);elsereturn *(S-top - 1); /出栈Pop(MStack *S)/若栈不为空,则删除s的栈顶元素 if (S-top = S-base) printf(栈为空，出栈失败!n); exit(0); else -(S-top); MStack realPath,path;/构造两个栈,一个用来保存探索中的全部路径,一个用来保存有效路径 /判断当前位置是否走过int UnPass(MStack path,MStackElem cur)/这里不能传path的地址,否则在遍历过程中它的top值就被改了 int flag = 1;/未走过 while(path.top != path.base) MStackElem e = *(path.top - 1); if (e.x = cur.x& e.y = cur.y)flag = 0;/曾走过 (path.top)-;/每循环一次令头指针下移一个位置 return flag; /获得东面(即右边)相邻的位置MStackElem GetEast(MStackElem cur)if(cur.y != N-2)/当y=N-2时已到了迷宫右边界,不能再向东(右)行了 cur.y += 1; cur.val = Mazecur.xcur.y; return cur;/当y=N-2时返回的是它本身 /获得南面(即下边)相邻的位置MStackElem GetSouth(MStackElem cur)if(cur.x != M-2)/当x=M-2时已到了迷宫下边界,不能再向南(下)行了 cur.x += 1; cur.val = Mazecur.xcur.y; return cur;/当x=M-2时返回的是它本身/获得西面(即左边)相邻的位置MStackElem GetWest(MStackElem cur)if(cur.y != 1)/当y=1时已到了迷宫左边界,不能再向西(左)行了 cur.y -= 1; cur.val = Mazecur.xcur.y; return cur;/当y=1时返回的是它本身/获得北面(即上边)相邻的位置MStackElem GetNorth(MStackElem cur) if(cur.x != 1)/当cur.x=1时表示在迷宫的上边界,不能再向北(上)行了 cur.x -= 1; cur.val = Mazecur.xcur.y; return cur;/当cur.x=1时返回的还是它本身 /获得下一个可通行的位置,按东南西北(即顺时针)的方向试探MStackElem GetNext(MStackElem cur) MStackElem next;next.x = next.y=next.val = -1;if(GetEast(cur).val = & UnPass(path,GetEast(cur) next = GetEast(cur);else if(GetSouth(cur).val = & UnPass(path,GetSouth(cur) next = GetSouth(cur);else if(GetWest(cur).val = & UnPass(path,GetWest(cur) next = GetWest(cur);else if(GetNorth(cur).val = & UnPass(path,GetNorth(cur) next = GetNorth(cur); return next;/如果当前位置的四面或为墙或已走过,则返回的next的val值为-1 /获得迷宫路径的函数int GetMazePath() MStackElem start,cur; start.x = rukou0;start.y = rukou1; start.val = Mazerukou0rukou1;/入口坐标的值 cur = start; /设定当前位置为入口位置 do if (UnPass(path,cur)/如果当前位置未曾走到过 Push(&realPath,cur); Push(&path,cur); cur = GetNext(cur); if (cur.x = chukou0 & cur.y = chukou1)/到达出口 Push(&realPath,cur);/把出口结点放入路径中 Push(&path,cur); return 1; else if(cur.val = -1)/当前位置的四面都为墙 Pop(&realPath);/删除真实路径的栈顶元素 cur = GetTop(&realPath);/令cur指向栈顶元素 else/如果当前位置已经走过,说明原来测试的方向不对,现在尝试其它方向 cur = GetNext(cur); if (cur.val = -1) Pop(&realPath);/仍不通,删除真实路径的栈顶元素 cur = GetTop(&realPath);/令cur指向栈顶元素 while (cur.x != chukou0 | cur.y != chukou1);return 0; /输出迷宫路径PrintMazePath(MStack *S)/为了安全,这里不传MStack的地址,以防在遍历的过程中把它们的top或base的值也修改了 MStackElem e;int i,j;for(i=0;iM;i+)for(j=0;jbase top-1) e = *(S-base);/先指向栈底元素,以后依次向上增1se.xe.y=.;printf(%d,%d) - ,e.x,e.y);(S-base)+; /最后一个结点没有后继,所以不再输出- e = *(S-base);se.xe.y=.; printf(%d,%d),e.x,e.y);/打开文件，获取迷宫OpenFile() FILE *fp;int i,j,c;system(cls);if(fp=fopen(in.txt,rt)=NULL)/打开迷宫文件in.txtprintf(打开文件失败！n);exit(1);for(i=0;iM;i+)/将文件中的迷宫存放到Maze中for(j=0;jN;j+)fscanf(fp,%c,&Mazeij); fscanf(fp,%c,&c);/换行fclose(fp); /保存迷宫路线图SaveFile()FILE *fp;int i,j;char strMN+1;for(i=0;iM;i+)for(j=0;jN;j+)strij=sij;strij=n;strM-1N=0;/结束符if