湖南文理学院课程设计报告
课程名称： 计算机技术基础
系 部： 电气与信息工程学院
专业班级：
学 号：学生姓名：指导教师：
完成时间：
报告成绩：
迷宫通路问题
一．设计要求
通过游戏程序设计，提高编程兴趣与编程思路，巩固C语言中所学的知识，合理的运用资料，实现理论与实际相结合。
（1）．收集资料，分析课题，分解问题，形成总体设计思路；
（2）．深入分析各个小问题，列出大纲，编写各部分程序模块；
（3）．对于设计中用到的关键函数，要学会通过查资料，弄懂其用法，要联系问
题进行具体介绍；
（4）．上机调试，查错，逐步分析不能正常运行的原因，确保所设计的程序正确，
并且能正常运行；
（5）．完成课程设计报告，并进行答辩。
二．设计目的
通过游戏程序的设计训练和提高学生的基本技能，掌握字符串的表示方法和字符串函数的功能、Turbo C图形操作的基本知识、键盘上特殊键的获取以及图形方式下光标的显示，提高编程兴趣与编程水平，学会如何正确的书写程序设计说明文档，提高运用C语言解决实际问题的能力，巩固C语言语法规则的理解和掌握，学会通过源程序写出流程图，提高自学以及查阅资料的能力。
三． 问题描述
以一个m x n的长方矩阵表示迷宫，1和0分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出从入口到出口的通路，或者没有通路的结论。
四、 需析求分？
1、 以二维数组migong[M][N]表示迷宫，其中migong[0][j]和
migong[i][0](0
表示通路，0表示障碍，迷宫的大小理论上可以不限制。
2、 迷宫数据由程序提供，用户只需要进行选择迷宫就行。迷宫的
入口和出口由程序提供。
3、 若设定的迷宫存在通路，则以长方形矩阵的形式将迷宫及其通
路输出到标准终端上，其中“0”表示障碍，“2”表示通过的
路径，“3”表示死胡同，没有显示的区域表示没有到达过的
地方。
4、 本程序只求出一条成功的通路。但是只要对函数进行小量的修
改，就可以求出其他全部的路径。
5、 程序执行命令为：（1）、创建迷宫；（2）、求解迷宫；（3）、
输出迷宫。
五、 概要设计
1、 设定栈的抽象数据类型定义：
ADT zhan{
数据对象：D={ai|ai属于yanshu，i=1、2„n，n>0}
数据关系：R={|ai-1,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)
初始条件：栈已经存在
操作结果：判断栈是否为空。若栈为空，返回1，否则返回0
destroy(*s)
初始条件：栈已经存在
操作结果：销毁栈s
}ADT zhan
2、 设定迷宫的抽象数据类型定义
ADT yanshu{
数据对象：D={ai,j|ai,j属于{‘ ’、‘0’、‘2’、
‘3’},0
数据关系：R={ROW,COL}
ROW={|ai-1,j,ai,j属于D，
i=1,2,„M,j=0,1,„N}
COL={|ai,j-1,ai,j属于D,i=0,1,„M，
j=1,2,„N} 基本操作： gouzhaomigong(*migong,m,n) 初始条件：二维数组migong[m][n]已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍，值1表示通路。 操作结果：构造迷宫的字符数组，以空白表示通路，字符‘0’表示障碍，并在迷宫四周加上一圈障碍。 markprint(*seat) 初始条件：迷宫中的所有坐标seat都已经被赋值 操作结果：若迷宫中该坐标能够通过且已经通过，则标记为2，若不能够通过（死胡同），标记为3。 shuchu(*migong,n) 初始条件：迷宫已经存在 操作结果：以字符形式输出迷宫 }ADT yanshu
3、 本程序包括三个模块
a、 主程序模块
void main()
{
初始化；
构造迷宫；
迷宫求解；
迷宫输出；
}
b、 栈模块——实现栈的抽象数据类型
c、 迷宫模块——实现迷宫的抽象数据类型
六、 详细设计
1、 坐标位置类型
#define zuobiao int
zuobiao migong[M][N];
2、 迷宫类型
typedef struct yanshu
{
int xuhao; //序号
zuobiao *seat; //栈元素的坐标
int fangxiang; //要查找的方向
}yanshu;
3、 栈类型
typedef struct zhan
{
yanshu *base; //栈构造之前和销毁之后base的值均为NULL yanshu *top;//栈顶指针
int size; //当前分陪的存储空间的长度，单位：元素
}zhan;
七、 伪代码
1、 主函数
void main()
{
变量的定义；
gouzhaomigong(migong,M,N); //构造一个迷宫
shuchu(migong,M,N); //将该构造好的迷宫输出
tansuo(weizhi,&migong[1][1],&migong[M-2][N-2]); //探
索迷宫
shuchu(migong,M,N); //输出探索出来的迷宫
}
2、 迷宫构造
void gouzhaomigong(zuobiao migong[M][N],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;a
{
for(c=0;c
{
migong[a][c]=0; migong[n-a][c]=0;
migong[a][n-c-1]=0; migong[n-a][n-c-1]=0;
migong[c][a]=0; migong[c][n-c-1]=0;
migong[n-c-1][n-a-1]=0; migong[n-c-1][a]=0;
}
if(a==b-1&&c!=1)
{
migong[a][c]=0; migong[a][n-c-1]=0;
migong[n-c-1][n-a-1]=0; migong[c][n-a-a]=0;
}
}
migong[1][i]=1; migong[k-2][i]=1;
migong[1][n-i-1]=1; migong[i][k+1]=1;
migong[n-2][i]=1; migong[n-i][k+1]=1; migong[n-i][n-2]=1;
}
3、 栈的操作
zhan *gouzhan(zhan *s,zuobiao *migong) //构造一个栈
{
s->base=分配一定空间；
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(栈空) retrun 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(栈为空) return 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) return 1;
else return 0;
}
void popover(zhan *s) //输出栈中的所有元素，同时清空栈
{for(;;)
{
e=pop(s,e)；
if(s->top-s->base==0) return;
}
}
八．系统程序结构及流程图 不规范！还要继续修改。
4、 求解迷宫中的一条路径
void tansuo(yanshu weizhi,zuobiao *rukou,zuobiao *chukou)
{ //若迷宫weizhi中存在从rukou到chukou的通道，则求出其中
一条
定义和初始化所需要的变量；
gouzhan(s,curpos);//
do{
if(pass(curpos))//当前位置可以通过，即未曾走过的模块
{
e=zuhe(curstep,curpos,0);//组合成一个元素
push(s,e);//加入到路径栈中
if(e->seat==chukou) braek; //到达终端
curpos=nestpos1(curpos,0);//下一位置是当前位置的
东临位
curstep++; //探索下一步
}
else{
if(!=stackempty（s）)//如果栈不空
{ e=pop(s,e);
while(e-
{ markprint(e->seat);//留下不能通过标记，退一
步
e=pop(s,e);
}
if(e->fangxiang
{ push(s,e); //探索下一方向
curpos=nextpos1(e->seat,e->fangxiang);
//设定当前位置是新方向上的相邻模块
}
}
}while(!stackempty(s));
return;
}
5、 迷宫的输出显示
void shuchu(zuobiao migong[M][N],intm，int n)
{ //给出迷宫的行列数和首地址，输出迷宫矩阵
for（i=0;i
{ for(j=0;j
if(migong[i][j]==1) printf(“ “)；
else printf(“%d”,migong[i][j]);
printf(“\n”);
}
}
九、 源代码（省略）
十、 调试结果和分析
十一．设计心得体会 整篇文档的字间距应整齐一致！ 课程设计使我学到了很多书本以外的东西，同时也提高了查阅资料的能力以及解决问题的能力，培养培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程。熟练掌握TC集成环境的使用方法。认真编写实习报告和实习总结，描述实习操作和心得体会，总结在这次实习中的业务收获，作出自我评价。熟练掌握并应用TC程序设计的各个知识点。掌握结构体和指针的联合使用，学会链表的构造和常用操作方法，认真编写实习日志和实习体会。并通过各种途径查找所需资料，拓宽视野，培养自学能力。也懂得了理论与实际相结合的重要性，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。
在做这次课程设计的时候，遇到这样那样的麻烦，因此，我也得到了许多宝贵的经验：
1、在设计程序之前,务必要对你所设计的题目和内容有一个系统的了解,知道所设计的题目和内容包含那些资源。
2、设计程序采用什么编程语言并不是非常重要,关键要有一个清晰的思路和一个完整的软件流程图，因而，要先把设计原理与思路搞清楚，再把流程图画出来，这样设计起来就简单多了。
3、在设计程序时,不能妄想一次就将整个程序设计好,“反复修改,不断改进”是程序设计的必经之路，发现错误也是取得成绩的一种。
4、要养成注释程序的好习惯,一个程序的完美与否不仅仅是实现功能,而应该让人一看就能明白你的思路,这样也为资料的保存和交流提供了方便。
5、在设计程序过程中遇到问题是很正常的,但我们应该将每次遇到的问题记录下来,并分析清楚,以免下次再碰到同样的问题。
在14天编程的过程当中弥补了我许多知识上的缺陷，弄清楚了我不懂的地方和似是而非的地方，使我及时补上了欠缺。其次，通过14天综合实训编程使我的知识形成了一个完整的框架结构，而不再是零散的知识个体，使我在使用时更加的方便。在14天的实习结束后，我对做完的习题检查比再是一切的走马观花，而是仔细核对、认真检查。这也改变了我做题时心烦气燥的习惯，现在做题可以平和静气的完成。我的自制能力更强了，基本完全可以控制自己，避免外界的干扰，安心地完成自己的工作。总之，这次实习对我自身有了很大的提高。十二.参考文献
严蔚敏、吴伟民，数据结构题集，清华大学出版社。
湖南文理学院课程设计报告
课程名称： 计算机技术基础
系 部： 电气与信息工程学院
专业班级：
学 号：学生姓名：指导教师：
完成时间：
报告成绩：
迷宫通路问题
一．设计要求
通过游戏程序设计，提高编程兴趣与编程思路，巩固C语言中所学的知识，合理的运用资料，实现理论与实际相结合。
（1）．收集资料，分析课题，分解问题，形成总体设计思路；
（2）．深入分析各个小问题，列出大纲，编写各部分程序模块；
（3）．对于设计中用到的关键函数，要学会通过查资料，弄懂其用法，要联系问
题进行具体介绍；
（4）．上机调试，查错，逐步分析不能正常运行的原因，确保所设计的程序正确，
并且能正常运行；
（5）．完成课程设计报告，并进行答辩。
二．设计目的
通过游戏程序的设计训练和提高学生的基本技能，掌握字符串的表示方法和字符串函数的功能、Turbo C图形操作的基本知识、键盘上特殊键的获取以及图形方式下光标的显示，提高编程兴趣与编程水平，学会如何正确的书写程序设计说明文档，提高运用C语言解决实际问题的能力，巩固C语言语法规则的理解和掌握，学会通过源程序写出流程图，提高自学以及查阅资料的能力。
三． 问题描述
以一个m x n的长方矩阵表示迷宫，1和0分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出从入口到出口的通路，或者没有通路的结论。
四、 需析求分？
1、 以二维数组migong[M][N]表示迷宫，其中migong[0][j]和
migong[i][0](0
表示通路，0表示障碍，迷宫的大小理论上可以不限制。
2、 迷宫数据由程序提供，用户只需要进行选择迷宫就行。迷宫的
入口和出口由程序提供。
3、 若设定的迷宫存在通路，则以长方形矩阵的形式将迷宫及其通
路输出到标准终端上，其中“0”表示障碍，“2”表示通过的
路径，“3”表示死胡同，没有显示的区域表示没有到达过的
地方。
4、 本程序只求出一条成功的通路。但是只要对函数进行小量的修
改，就可以求出其他全部的路径。
5、 程序执行命令为：（1）、创建迷宫；（2）、求解迷宫；（3）、
输出迷宫。
五、 概要设计
1、 设定栈的抽象数据类型定义：
ADT zhan{
数据对象：D={ai|ai属于yanshu，i=1、2„n，n>0}
数据关系：R={|ai-1,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)
初始条件：栈已经存在
操作结果：判断栈是否为空。若栈为空，返回1，否则返回0
destroy(*s)
初始条件：栈已经存在
操作结果：销毁栈s
}ADT zhan
2、 设定迷宫的抽象数据类型定义
ADT yanshu{
数据对象：D={ai,j|ai,j属于{‘ ’、‘0’、‘2’、
‘3’},0
数据关系：R={ROW,COL}
ROW={|ai-1,j,ai,j属于D，
i=1,2,„M,j=0,1,„N}
COL={|ai,j-1,ai,j属于D,i=0,1,„M，
j=1,2,„N} 基本操作： gouzhaomigong(*migong,m,n) 初始条件：二维数组migong[m][n]已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍，值1表示通路。 操作结果：构造迷宫的字符数组，以空白表示通路，字符‘0’表示障碍，并在迷宫四周加上一圈障碍。 markprint(*seat) 初始条件：迷宫中的所有坐标seat都已经被赋值 操作结果：若迷宫中该坐标能够通过且已经通过，则标记为2，若不能够通过（死胡同），标记为3。 shuchu(*migong,n) 初始条件：迷宫已经存在 操作结果：以字符形式输出迷宫 }ADT yanshu
3、 本程序包括三个模块
a、 主程序模块
void main()
{
初始化；
构造迷宫；
迷宫求解；
迷宫输出；
}
b、 栈模块——实现栈的抽象数据类型
c、 迷宫模块——实现迷宫的抽象数据类型
六、 详细设计
1、 坐标位置类型
#define zuobiao int
zuobiao migong[M][N];
2、 迷宫类型
typedef struct yanshu
{
int xuhao; //序号
zuobiao *seat; //栈元素的坐标
int fangxiang; //要查找的方向
}yanshu;
3、 栈类型
typedef struct zhan
{
yanshu *base; //栈构造之前和销毁之后base的值均为NULL yanshu *top;//栈顶指针
int size; //当前分陪的存储空间的长度，单位：元素
}zhan;
七、 伪代码
1、 主函数
void main()
{
变量的定义；
gouzhaomigong(migong,M,N); //构造一个迷宫
shuchu(migong,M,N); //将该构造好的迷宫输出
tansuo(weizhi,&migong[1][1],&migong[M-2][N-2]); //探
索迷宫
shuchu(migong,M,N); //输出探索出来的迷宫
}
2、 迷宫构造
void gouzhaomigong(zuobiao migong[M][N],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;a
{
for(c=0;c
{
migong[a][c]=0; migong[n-a][c]=0;
migong[a][n-c-1]=0; migong[n-a][n-c-1]=0;
migong[c][a]=0; migong[c][n-c-1]=0;
migong[n-c-1][n-a-1]=0; migong[n-c-1][a]=0;
}
if(a==b-1&&c!=1)
{
migong[a][c]=0; migong[a][n-c-1]=0;
migong[n-c-1][n-a-1]=0; migong[c][n-a-a]=0;
}
}
migong[1][i]=1; migong[k-2][i]=1;
migong[1][n-i-1]=1; migong[i][k+1]=1;
migong[n-2][i]=1; migong[n-i][k+1]=1; migong[n-i][n-2]=1;
}
3、 栈的操作
zhan *gouzhan(zhan *s,zuobiao *migong) //构造一个栈
{
s->base=分配一定空间；
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(栈空) retrun 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(栈为空) return 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) return 1;
else return 0;
}
void popover(zhan *s) //输出栈中的所有元素，同时清空栈
{for(;;)
{
e=pop(s,e)；
if(s->top-s->base==0) return;
}
}
八．系统程序结构及流程图 不规范！还要继续修改。
4、 求解迷宫中的一条路径
void tansuo(yanshu weizhi,zuobiao *rukou,zuobiao *chukou)
{ //若迷宫weizhi中存在从rukou到chukou的通道，则求出其中
一条
定义和初始化所需要的变量；
gouzhan(s,curpos);//
do{
if(pass(curpos))//当前位置可以通过，即未曾走过的模块
{
e=zuhe(curstep,curpos,0);//组合成一个元素
push(s,e);//加入到路径栈中
if(e->seat==chukou) braek; //到达终端
curpos=nestpos1(curpos,0);//下一位置是当前位置的
东临位
curstep++; //探索下一步
}
else{
if(!=stackempty（s）)//如果栈不空
{ e=pop(s,e);
while(e-
{ markprint(e->seat);//留下不能通过标记，退一
步
e=pop(s,e);
}
if(e->fangxiang
{ push(s,e); //探索下一方向
curpos=nextpos1(e->seat,e->fangxiang);
//设定当前位置是新方向上的相邻模块
}
}
}while(!stackempty(s));
return;
}
5、 迷宫的输出显示
void shuchu(zuobiao migong[M][N],intm，int n)
{ //给出迷宫的行列数和首地址，输出迷宫矩阵
for（i=0;i
{ for(j=0;j
if(migong[i][j]==1) printf(“ “)；
else printf(“%d”,migong[i][j]);
printf(“\n”);
}
}
九、 源代码（省略）
十、 调试结果和分析
十一．设计心得体会 整篇文档的字间距应整齐一致！ 课程设计使我学到了很多书本以外的东西，同时也提高了查阅资料的能力以及解决问题的能力，培养培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程。熟练掌握TC集成环境的使用方法。认真编写实习报告和实习总结，描述实习操作和心得体会，总结在这次实习中的业务收获，作出自我评价。熟练掌握并应用TC程序设计的各个知识点。掌握结构体和指针的联合使用，学会链表的构造和常用操作方法，认真编写实习日志和实习体会。并通过各种途径查找所需资料，拓宽视野，培养自学能力。也懂得了理论与实际相结合的重要性，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。
在做这次课程设计的时候，遇到这样那样的麻烦，因此，我也得到了许多宝贵的经验：
1、在设计程序之前,务必要对你所设计的题目和内容有一个系统的了解,知道所设计的题目和内容包含那些资源。
2、设计程序采用什么编程语言并不是非常重要,关键要有一个清晰的思路和一个完整的软件流程图，因而，要先把设计原理与思路搞清楚，再把流程图画出来，这样设计起来就简单多了。
3、在设计程序时,不能妄想一次就将整个程序设计好,“反复修改,不断改进”是程序设计的必经之路，发现错误也是取得成绩的一种。
4、要养成注释程序的好习惯,一个程序的完美与否不仅仅是实现功能,而应该让人一看就能明白你的思路,这样也为资料的保存和交流提供了方便。
5、在设计程序过程中遇到问题是很正常的,但我们应该将每次遇到的问题记录下来,并分析清楚,以免下次再碰到同样的问题。
在14天编程的过程当中弥补了我许多知识上的缺陷，弄清楚了我不懂的地方和似是而非的地方，使我及时补上了欠缺。其次，通过14天综合实训编程使我的知识形成了一个完整的框架结构，而不再是零散的知识个体，使我在使用时更加的方便。在14天的实习结束后，我对做完的习题检查比再是一切的走马观花，而是仔细核对、认真检查。这也改变了我做题时心烦气燥的习惯，现在做题可以平和静气的完成。我的自制能力更强了，基本完全可以控制自己，避免外界的干扰，安心地完成自己的工作。总之，这次实习对我自身有了很大的提高。十二.参考文献
严蔚敏、吴伟民，数据结构题集，清华大学出版社。