《迷宫问题课程设计报告》由会员分享，可在线阅读，更多相关《迷宫问题课程设计报告（10页珍藏版）》请在金锄头文库上搜索。
1、湖南文理学院课程设计报告课程名称：计算机技术基础系 部：电气与信息工程学院专业班级：学 号：学生姓名：扌旨导教师：完成时间：扌艮告成绩：迷宫通路问题一设计要求通过游戏程序设计，提高编程兴趣与编程思路，巩固C语言中所学的知识， 合理的运用资料，实现理论与实际相结合。（1）收集资料，分析课题，分解问题，形成总体设计思路；（2）深入分析各个小问题，列出大纲，编写各部分程序模块；（3）对于设计中用到的关键函数，要学会通过查资料，弄懂其用法，要联系问题进行具体介绍；（4）上机调试，查错，逐步分析不能正常运行的原因，确保所设计的程序正确，并且能正常运行；（5）完成课程设计报告，并进行答辩。二设计目的通过游
2、戏程序的设计训练和提高学生的基本技能，掌握字符串的表示方法和 字符串函数的功能、Turbo C图形操作的基本知识、键盘上特殊键的获取以及图 形方式下光标的显示，提高编程兴趣与编程水平，学会如何正确的书写程序设计 说明文档，提高运用C语言解决实际问题的能力，巩固C语言语法规则的理解和 掌握，学会通过源程序写出流程图，提高自学以及查阅资料的能力。三 问题描述以一个 m x n 的长方矩阵表示迷宫， 1 和 0 分别表示迷宫中的通路和障碍。 设计一个程序，对任意设定的迷宫，求出从入口到出口的通路，或者没有通路的 结论。四、需析求分？1、 以二维数组migongMN表示迷宫，其中migong0j和mi
3、gongi0（0二j,i二N）为添加的一圈障碍。数组中以元素1 表示通路， 0 表示障碍，迷宫的大小理论上可以不限制。2、迷宫数据由程序提供，用户只需要进行选择迷宫就行。迷宫的入口和出口由程序提供。3、若设定的迷宫存在通路，则以长方形矩阵的形式将迷宫及其通路输出到标准终端上，其中“0”表示障碍，“2”表示通过的 路径，“3”表示死胡同，没有显示的区域表示没有到达过的 地方。4、本程序只求出一条成功的通路。但是只要对函数进行小量的修 改，就可以求出其他全部的路径。5、程序执行命令为：（1）、创建迷宫；（2）、求解迷宫；（3）、 输出迷宫。五、概要设计1、设定栈的抽象数据类型定义：ADT zhan
4、数据对象：D=ai|ai 属于 yanshu, i=l、2n, n0数据关系：R二|ai-l,ai 属于 D,i=2,3,n基本操作：gouzhan（*s,*migong）操作结果：构造一个空栈push（*s,*e）初始条件：栈已经存在操作结果：将e所指向的数据加入到栈s中pop（*s,*e）初始条件：栈已经存在操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素getpop（*s,*e）初始条件：栈已经存在操作结果：若栈不为空，用e返回栈顶元素popover（*s）初始条件：栈已经存在操作结果：输出栈中的所有元素，同时清空栈stackempty（*s）初始条件：栈已经存在操作结果：判断栈是
5、否为空。若栈为空，返回1，否则返回0destroy（*s）初始条件：栈已经存在操作结果：销毁栈sADT zhan2、设定迷宫的抽象数据类型定义ADT yanshu 数据对象：D=ai,j|ai,j 属于 、0、2、 3,0=i=M,0=j=N数据关系：R=ROW,COLROW二|ail,j, ai,j 属于 D，i=1,2,M,j=0,1,NCOL=|ai,j-1, ai,j 属于 D,i=0,1,M，j=1,2,N 基本操作： gouzhaomigong(*migong,m,n)初始条件：二维数组migongmn已经存在，其中第1至第 m-1 行，每行自第 1 到第 n-1 列的元素已经值，
6、并 以值 0 表示障碍，值 1 表示通路。操作结果：构造迷宫的字符数组，以空白表示通路，字符 0表示障碍，并在迷宫四周加上一圈障碍。 markprint(*seat)初始条件：迷宫中的所有坐标 seat 都已经被赋值 操作结果：若迷宫中该坐标能够通过且已经通过，则标记为 2，若不能够通过(死胡同)，标记为 3。shuchu(*migong,n) 初始条件：迷宫已经存在 操作结果：以字符形式输出迷宫 ADT yanshu3、本程序包括三个模块a、主程序模块void main ()初始化；构造迷宫；迷宫求解；迷宫输出；b、栈模块实现栈的抽象数据类型c、迷宫模块实现迷宫的抽象数据类型六、详细设计1、
7、坐标位置类型#define zuobiao int zuobiao migongMN;2、迷宫类型 typedef struct yanshu int xuhao; /序号 zuobiao *seat; /栈元素的坐标 int fangxiang; /要查找的方向 yanshu;3、栈类型 typedef struct zhan yanshu *base; /栈构造之前和销毁之后 base 的值均为 NULLyanshu *to p;/栈顶指针int size; /当前分陪的存储空间的长度，单位：元素zhan;七、伪代码1、主函数void main()变量的定义；gouzhaomigong(m
8、igong,M,N); /构造一个迷宫 shuchu(migong,M,N); /将该构造好的迷宫输出tansuo(weizhi，&migong1 1, &migongM-2N-2); /探 索迷宫shuchu(migong,M,N); /输出探索出来的迷宫2、迷宫构造void gouzhaomigong(zuobiao migongMN,int M,int N)/ 该函数是用来构造一个迷宫，通过更改还能够构造其他类型迷 宫定义变量 a,b,c,i,k;i=n/3-1;k=/2;a=k-2;if(k*2=n) b=k;else b=k+1;for(a=0;ab;a+)for(c=0;cbase
9、二分配一定空间； s-top=s-base;s-top-seat=s-base-seat=migong; s-top-fangxiang=0; s-top-xuhao=0; return s;void push(zhan *s,yanshu *e) /将 e 所指向的元素加入到栈中 if(空间不足)分配连续空间，给各值赋值；s-top+; s-top-seat=e-seat; s-top-fangxiang=e-fangxiang+1; s-top-xuhao=e-xuhao;yanshu *pop (zhan *s,yanshu *e ) /栈不为空，删除栈顶元素, 用e返回if(栈空)re
10、t run NULL; e-seat=s-top-seat; e-seat-; e-fangxiang=s-top-fangxiang; e-xuhao=s-top-xuhao; s-top-; return e;yanshu *gettop (zhan *s,yanshu *e)/ 用 e 返回栈顶元素， 不删除if(栈为空)ret urn NULL;e-seat=s-top-seat; e-seat=s-top-seat; e-xuhao=s-top-xuhao; return e;int stackempty(zhan *s) /判断栈是否为空if(s-top=s-base) retur
11、n 1;else return 0;void popover(zhan *s) /输出栈中的所有元素，同时清空栈 for(;)e=pop(s,e) ； if(s-top-s-base=0) return;八系统程序结构及 流程图 不规范！还要继续修改。初始化行走方向(下)Nv改变方向退一歩改变方向4、求解迷宫中的一条路径void tansuo(yanshu weizhi,zuobiao *rukou,zuobiao *chukou) / 若迷宫 weizhi 中存在从 rukou 到 chukou 的通道，则求出其中 一条定义和初始化所需要的变量； gouzhan(s,curpos);/ do
12、if(pass(curpos)/当前位置可以通过，即未曾走过的模块 e=zuhe(curs tep,curpos,0);/组合成一个元素 push(s,e);/加入到路径栈中if(e-seat=chukou) braek; /到达终端curpos二nes tposl(curpos,0);/下一位置是当前位置的东临位curstep+; /探索下一步else if(!=stackempty (s) )/如果栈不空 e=pop(s,e); while(e-seat);/留下不能通过标记，退一e=pop(s,e);if(e-fangxiangseat,e-fangxiang);/设定当前位置是新方向上的相邻模块 while(!stackempty(s);return;5、迷宫的输出显示void shuchu(zuobiao migongMN,intm ，int n) /给出迷宫的行列数和首地址，输出迷宫矩阵 for(i=0;iM;i+)for(j=0;jN;j+)if(migongij=1) printf(“ “) else printf(“%d”,migongi
