C语言课程设计报告题目：迷宫问题
姓名：
班级：
学号：
组员：
指导教师：
学院：
专业：
课程设计（报告）任务及评语
目录
第1章课程设计的目的与要求 (1)
1.1 课程设计目的 (1)
1.2 课程设计的实验环境 (1)
1.3 课程设计的预备知识 (1)
1.4 课程设计要求 (1)
第2章课程设计内容 (2)
2.1程序功能介绍 (2)
2.2程序整体设计说明 (2)
2.2.1设计思路 (2)
2.2.2数据结构设计及用法说明 (3)
2.2.3程序结构（流程图） (4)
2.2.4各模块的功能及程序说明 (6)
2.2.5程序结果 (7)
2.3程序源代码及注释 (7)
第3章课程设计总结 (17)
参考资料 (18)
第1章课程设计的目的与要求
1.1 课程设计目的
本课程设计是计算机科学与技术专业重要的实践性环节之一，是在学生学习完《程序设计语言(C)》课程后进行的一次全面的综合练习。本课程设计的目的和任务：
1. 巩固和加深学生对C语言课程的基本知识的理解和掌握
2. 掌握C语言编程和程序调试的基本技能
3. 利用C语言进行基本的软件设计
4. 掌握书写程序设计说明文档的能力
5. 提高运用C语言解决实际问题的能力
1.2 课程设计的实验环境
硬件要求能运行Windows 2000/XP操作系统的微机系统。C语言程序设计及相应的开发环境。
1.3 课程设计的预备知识
熟悉C语言及C语言开发工具。
1.4 课程设计要求
1. 分析课程设计题目的要求
2. 写出详细设计说明
3. 编写程序代码，调试程序使其能正确运行
4. 设计完成的软件要便于操作和使用
5. 设计完成后提交课程设计报告
第2章课程设计内容
2.1程序功能介绍
迷宫是深受大家喜爱的游戏之一，本课题要求随机生成一个美观逼真的迷宫图，它是随机生成的且迷宫大小可以改变，迷宫的大小为N*N，N预定义为常数，修改N的值可以改变迷宫的大小（只要不超过屏幕显示范围），而程序不必做修改。程序采用了两种运行方式：一种通过自动探索，这是用递归方法实现；一种是由人工操作探索通过，这利用了手动操作8个代表不同的方向的键位来实现。用白色表示可走的路，蓝色表示墙壁不可以通过。
2.2程序整体设计说明
2.2.1设计思路
一般的迷宫为二维平面图形,将迷宫的左上角作入口，右下角作出口，求出从入口点到出口点的一条通路，作为线性结构的典型应用，大多用非递归方法实现，输出用0代表通路，1代表墙壁。程序采用了一个美观逼真的迷宫图，而且是随机生成，迷宫的大小为N×N，N预定义为常数，修改N的值可以改变迷宫的大小（只要不超过屏幕显示范围），而程序不必做修改。用白色表示可走的路，蓝色表示墙壁不可以通过。程序还设计了两种运行方式：
一种是由系统自动运行探索，用递归方法实现；
一种是由人工操作探索通路。系统运行首先出现提示字符串“Please select hand(1) else auto”，询问是选择人工探索还是系统自动探索，当用户输入字符1按回车键后出现一个迷宫图，红色矩形块（表示探索物）出现在左上角，这是可以代表4个方向的字符选择通路，遇到墙壁不能通行，按回车键结束探索，如果这时探索物移动到右下角出口，则显示找到通路信息，否则显示没找到通路信息。在提示信息后，如果输入的字符不是1，则系统自动查找通路，如果没有找到通路，则显示没有找到通路信息。如果找到通路，则用红色标记走过的路径。程序首先要考虑迷宫的表示，这是一个二维关系图，典型的存贮储方式是选择二维数组，数组元素的值只有两种状态，所以取值为0或1，0表示通路，1表示墙壁，这里取名为map。图形的显示就可以根据数组元素的值来确定，如果是人工探索，则根据按键来确定探索物的位置坐标，利用循环语句即可实现，如果是系统自动探索，并且在4个方向进行递归算法，即可实现寻找路径。
2.2.2数据结构设计及用法说明 .
用m行n列的m*n个正方格表示一个迷宫，其中划有斜线的方格表示不可通行，未划有斜线的方格表示可以通行。请编写寻找从入口到出口的一条最短路径的程序。
（1）迷宫的规格（即行数与列数）,状态设置(即各方格能否通行的状态)，以及入口和出口的位置，均应由输入随机确定。
（2）求得的最短路径，应该以从入口到出口的路径上的各个方格的坐标的线性序列输出。当无通路时，应该报告无路径的信息。
(3)尽量采用结构化程序设计方法，要求对各个模块的功能及参数作必要的说明
提示(1)迷宫可以采用matrix类型的二维数组A表示。A.rownum与A.colnum分别表示迷宫的实际的行数与列数。而A.maze[i][j]表示迷宫中第i行第j列的一个方格，用
A.maze[i][j]=0表示该方格可以通行，用A.maze[i][j]=1表示该方格不可以通行。
(2)由于要寻找从入口到出口的一条最短路径，最好将迷宫看作是一个图结构。则问题转化为寻找从对应于入口顶点到对应于出口顶点的一条最短路径的问题。该问题可以采用从入口顶点出发，进行广度优先搜索遍历，直到遇到出口顶点或者遍历完毕也没有遇到出口顶点为止。这二种情况分别对应于最短路径探索成功与查无通路的事实。
(3)基于上述分析，涉及到数据结构的转换，即将二维数组表示的迷宫A转换为以adjlist 类型的邻接表表示的图结构G。在图结构中，将迷宫中的每个方格看作是一个顶点。不可通行的方格都是孤立顶点；相邻的可通行的方格所对应的顶点之间看作是有边相连。因此迷宫可以看作是由m*n个顶点及无向边构成的一个非连通的无向图。尽管图是不连通的，但不影响本问题的求解，而且本问题有解的条件是：入口顶点与出口顶点在同一个连通分量中。图结构G中，G.adj[k]表示编号为k的顶点的邻接情况的单链表的头指针；G.vexnum表示图G中的实际顶点数，而且具有如下关系：
G.vexnum=A.rownum*A.colnum
(4)为了避免迷宫数据的重复输入，我们期望A能够自动地转换为G。因此应该设计一个转换算法create_adjlist(A,G)。而图结构中顶点是要编号的，我们约定以行为序，顺序给迷宫A中的方格所对应的顶点编号。这样迷宫中方格的坐标（即行row和列col）与图G中所对应的顶点的编号（即verno）之间具有如下关系：
verno=（row-1）* n + col
row=（verno-1）/ n + 1
col=（verno-1）% n + 1
(5)在广度优先搜索遍历求解最短路径过程中，应该设置一个队列queue作为辅助数据结构；路径采用一个整数数组pred来表示。这二个数据结构的存储结构类型均为list类型，其说明定义如下：
typedef int list[MAXVER]；
队列queue应该设置front和rear分别指示列首与列尾，queue[k]表示第k个入列的顶点编号。采用pred记录路径，pred[i]表示顶点i在广度优先搜索遍历过程中的前趋顶点的编号，它表明是经过边（pred[i]，i）达到顶点i的。这样，当路径探索成功时，我们可以从出口顶点倒推出从入口到出口的一条路径来。当然要涉及到从顶点编号向方格坐标的反转换，这个公式在上面已经给出了。
2.2.3程序结构（流程图）
程序结构设计流程图如图2.1所示
图2.1流程图
2.2.4各模块的功能及程序说明
程序用二维数组表示迷宫
第一个模块—主函数main()的功能是：首先确定是人工还是系统自动探索，通过输入字符选定。选定后调用图形初始化函数，接着调用迷宫生成函数及迷宫显示函数。然后根据输入的字符调用人工探索函数或自动探索函数，探索完毕进行结果处理，最后关闭图形系统，程序结束。
第二个模块—初始化函数Init()的功能是：由于迷宫是在图形方式下显示的，所以要进行图形初始化。
第三个模块—迷宫生成函数MapRand()的功能是：用数组map表示一个迷宫，要随机生成迷宫，数组元素的值利用随机函数生成0或1的数。
第四个模块—迷宫显示函数PrMap()的功能：根据数组map的值输出迷宫图，利用函数setfillstyle()设置图形实体填充样式bar（）函数输出矩形块。数组元素的下标为矩形块的中心坐标，利用两重循环语句可以完成迷宫图的显示。
第五个模块—系统自动5FindWay()的功能：从下标（1，1）开始探索，依次按照右下、下、右、右上、左、左下、左上的顺序前进，若该方向上的值为0，则前进一步。
第六个模块—人工探索PeopleFind（）的功能：首先输出迷宫图以及人工控制操作图示，红色探索出现在左上角，采用人工控制8个方向的移动，由于是8个方向，用光标键只能控制4个方向，为了统一采用了临近的8个字符，Q，W，E，A，D，Z，X，C代表8个方向，按了字符后，对应方向不是墙壁，可以将红色探索物移到相应的位置，按回车表示结果人工操作。如果此时map数组元素的坐标是出口，则yes的值为1，探索成功，否则值为0。由于探索物不停的移动，要在新位置显示，并将走过的路恢复为白色通路，可以调用DrawPeople（&x,&y,n）完成.参数x和y代表所在的行坐标和列坐标,n代表所选的方向,根据n的值,将x和y进行相应的变化.
第七个模块—结果处理函数Result（）：最终结果是找到和没找到两种情况，在程序中设计全局变量yes，根据yes的值进行处理。如果yes为0，调用函数NotFind（），显示找到通路信息，否则调用函数Find（）。如果是系统自动探索，Find（）会显示出所走过的路径，如果是人工探索，没有记录走过的路径，只显示找到通路的信息。
第八个模块—图形关闭函数Close（）的功能：调用Closegraph（）关闭图形系统，程序结束。
2.2.5程序结果
程序编译连接成功后，首先出现提示字符串“please select hard（1） else auto”询问是选择人工探索还是选择系统自动探索，其中1是人工探索。
图2.2结果
当输入字符1时，此时是人工探索。按回车键后出现一个迷宫图，红色矩形块出项在左上角，这时可以按代表8个方向的字符选择通路，若可以找到通路，则走的路都由红色标记，当遇到墙壁是则不能通行，此时按回车键结束探索，屏幕出现“not find a way”提示信息。如果输入的字符不是1，则系统自动查找通路。如果没有找通路，则显示没有找到通路的信息“not find a way”，如果找到通路，则用红色标记走过的路径，回车后结束探索。
图2.3戏图片
找到出路，屏幕显示Find a way！
2.3程序源代码及注释
#include
#include
#include
#include
#include
#define N 20/*迷宫的大小，可改变*/
int oldmap[N][N];/*递归用的数组,用全局变量节约时间*/
int yes=0;/*yes是判断是否找到路的标志,1找到，0没找到*/
int way[100][2],wayn=0;/*way数组是显示路线用的,wayn是统计走了几个格子*/ void Init(void);/*图形初始化*/
void Close(void);/*图形关闭*/
void DrawPeople(int *x,int *y,int n);/*画人工探索物图*/
void PeopleFind(int (*x)[N]);/*人工探索*/
void WayCopy(int (*x)[N],int (*y)[N]);/*为了8个方向的递归，把旧迷宫图拷贝给新数组*/
int FindWay(int (*x)[N],int i,int j);/*自动探索函数*/
void MapRand(int (*x)[N]);/*随机生成迷宫函数*/
void PrMap(int (*x)[N]);/*输出迷宫图函数*/
void Result(void);/*输出结果处理*/
void Find(void);/*成功处理*/
void NotFind(void);/*失败处理*/
void main(void)/*主函数*/
{
int map[N][N]; /*迷宫数组*/
char ch;
clrscr();
printf("\n Please select hand(1) else auto\n");/*选择探索方式*/
scanf("%c",&ch);
Init(); /*初始化*/
MapRand(map);/*生成迷宫*/
PrMap(map);/*显示迷宫图*/
if(ch=='1')
PeopleFind(map);/*人工探索*/
else
FindWay(map,1,1);/*系统自动从下标1,1的地方开始探索*/
Result();/*输出结果*/
Close();
}
void Init(void)/*图形初始化*/
{
int gd=DETECT,gm;
initgraph(&gd,&gm,"c:\\tc");
}
void DrawPeople(int *x,int *y,int n)/*画人工控制图*/
{/*如果将以下两句注释掉，则显示人工走过的路径，*/
setfillstyle(SOLID_FILL,WHITE); /*设置白色实体填充样式*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
/*恢复原通路*/
switch(n)/*判断x,y的变化，8个方向的变化*/
{
case 1: (*x)--;break; /*上*/
case 2: (*x)--;(*y)++;break ;/*右上*/
case 3: (*y)++;break; /*右*/
case 4: (*x)++;(*y)++;break; /*右下*/
case 5: (*x)++;break; /*下*/
case 6: (*x)++;(*y)--;break; /*左下*/
case 7: (*y)--;break; /*左*/
case 8: (*x)--;(*y)--;break; /*左上*/
}
setfillstyle(SOLID_FILL,RED);/*新位置显示探索物*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
}
void PeopleFind(int (*map)[N])/*人工手动查找*/
{
int x,y;
char c=0;/*接收按键的变量*/
x=y=1;/*人工查找的初始位置*/
setcolor(11);
line(500,200,550,200);
outtextxy(570,197,"d");
line(500,200,450,200);
outtextxy(430,197,"a");
line(500,200,500,150);
outtextxy(497,130,"w");
line(500,200,500,250);
outtextxy(497,270,"x");
line(500,200,450,150);
outtextxy(445,130,"q");
line(500,200,550,150);
outtextxy(550,130,"e");
line(500,200,450,250);
outtextxy(445,270,"z");
line(500,200,550,250);
outtextxy(550,270,"c");/*以上是画8个方向的控制介绍*/
setcolor(YELLOW);
outtextxy(420,290,"Press 'Enter' to end");/*压回车键结束*/
setfillstyle(SOLID_FILL,RED);
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);/*入口位置显示*/ while(c!=13)/*如果按下的不是回车键*/
{
c=getch();/*接收字符后开始各个方向的探索*/
if(c=='w'&&map[x-1][y]!=1)
DrawPeople(&x,&y,1);/*上*/
else
if(c=='e'&&map[x-1][y+1]!=1)
DrawPeople(&x,&y,2);/*右上*/
else
if(c=='d'&&map[x][y+1]!=1)
DrawPeople(&x,&y,3);/*右*/
else
if(c=='c'&&map[x+1][y+1]!=1)
DrawPeople(&x,&y,4);/*右下*/
else
if(c=='x'&&map[x+1][y]!=1)
DrawPeople(&x,&y,5);/*下*/
else
if(c=='z'&&map[x+1][y-1]!=1)
Dr awPeople(&x,&y,6); /*左下*/
else
if (c=='a'&&map[x][y-1]!=1)
DrawPeople(&x,&y,7); /*左*/
el se if(c=='q'&&map[x-1][y-1]!=1)
DrawPeople(&x,&y,8); /*左上*/
}
setfillstyle(SOLID_FILL,WHITE); /*消去红色探索物，恢复原迷宫图*/
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);
if(x==N-2&&y==N-2)/*人工控制找成功的话*/
yes=1; /*如果成功标志为1*/
}
void WayCopy(int (*oldmap)[N],int (*map)[N])/*拷贝迷宫数组 */
{
int i,j;
for(i=0;i for(j=0;j oldmap[i][j]=map[i][j]; } int FindWay(int (*map)[N],int i,int j)/*递归找路*/ { if(i==N-2&&j==N-2)/*走到出口*/ { yes=1;/*标志为1,表示成功*/ return; } map[i][j]=1;/*走过的地方变为1*/ WayCopy(oldmap,map); /*拷贝迷宫图*/ if(oldmap[i+1][j+1]==0&&!yes)/*判断右下方是否可走*/ { FindWay(oldmap,i+1,j+1); if(yes)/*如果到达出口了，再把值赋给显示路线的way数组,也正是这个原因,所以具体路线是从最后开始保存*/ { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i+1][j]==0&&!yes)/*判断下方是否可以走,如果标志yes已经是1也不用找下去了*/ { FindWay(oldmap,i+1,j); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i][j+1]==0&&!yes)/*判断右方是否可以走*/ { FindWay(oldmap,i,j+1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i-1][j]==0&&!yes)/*判断上方是否可以走*/ { FindWay(oldmap,i-1,j); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i-1][j+1]==0&&!yes)/*判断右上方是否可以走*/ { FindWay(oldmap,i-1,j+1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i+1][j-1]==0&&!yes)/*判断左下方是否可以走*/ { FindWay(oldmap,i+1,j-1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i][j-1]==0&&!yes)/*判断左方是否可以走*/ { FindWay(oldmap,i,j-1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } WayCopy(oldmap,map); if(oldmap[i-1][j-1]==0&&!yes)/*判断左上方是否可以走*/ { FindWay(oldmap,i-1,j-1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } } return; } void MapRand(int (*map)[N])/*开始的随机迷宫图*/ { int i,j; cleardevice();/*清屏*/ randomize(); /*随机数发生器*/ for(i=0;i { for(j=0;j { if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈为墙壁*/ map[i][j]=1; else if(i==1&&j==1||i==N-2&&j==N-2)/*出发点与终点表示为可走的*/ map[i][j]=0; else map[i][j]=random(2);/*其它的随机生成0或1*/ } } } void PrMap(int (*map)[N])/*输出迷宫图*/ { int i,j; for(i=0;i for(j=0;j if(map[i][j]==0) { setfillstyle(SOLID_FILL,WHITE);/*白色为可走的路*/ bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6); } else { setfillstyle(SOLID_FILL,BLUE);/*蓝色为墙壁*/ bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6); } } void Find(void)/*找到通路*/ { int i; setfillstyle(SOLID_FILL,RED);/*红色输出走的具体路线*/ wayn--; for(i=wayn;i>=0;i--) { bar(100+way[i][1]*15-6,50+way[i][0]*15-6,100+ way[i][1]*15+6,50+way[i][0]*15+6); sleep(1);/*控制显示时间*/ } bar(100+(N-2)*15-6,50+(N-2)*15-6,100+ (N -2)*15+6,50+(N-2)*15+6); /*在目标点标红色*/ setcolor(GREEN); settextstyle(0,0,2);/*设置字体大小*/ outtextxy(130,400,"Find a way!"); } void NotFind(void)/*没找到通路*/ { setcolor(GREEN); settextstyle(0,0,2);/*设置字体大小*/ outtextxy(130,400,"Not find a way!"); } void Result(void)/*结果处理*/ { if(yes)/*如果找到*/ Find(); else/*没找到路*/ NotFind(); getch(); } void Close(void)/*图形关闭*/ { closegraph(); 第3章课程设计总结 通过这段时间的课程设计，我认识到C语言是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.回顾起此次C语言课程设计，至今我仍感慨颇多，的确，从课题到定稿，从理论到实践，在整整两星期的日子里，可以说得是苦多于甜，但是可以学到很多很多的东西，同时不仅可以巩固了上课所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，弥补了上课所学的知识。 我认为它是一个团队的工作，团队需要个人，个人也离不开团队，必须发扬团结协作的精神。某个人的离群都可能导致整项工作的失败.只有一个人知道原理是远远不够的，必须让每个人都知道，否则一个人的错误，就有可能导致整个工作失败.团结协作是我们实习成功的一项非常重要的保证。而这次实习也正好锻炼我们这一点，这也是非常宝贵的.我很清楚的知道团结协作的力量是伟大的，如果是我一个人孤军奋战的话，肯定不能在规定时间内完成这次课程设计的要求内容，因此我很怀念这两个星期的合作，想起我们一起查阅资料，一起讨论设计程序的思路，成功的时候一起分享喜悦.让我们懂得,科学的精神是一个大学生尤其是我们一个学工科的学生是不可缺少的.也“粗略”的懂得了以前赵老师说的奋战几天几夜的辛酸和不容易,人是在逆境中锻炼自身,在逆境中成材的。 这次课程设计不仅可以使我们巩固了以前所学过的知识，而且让我们学到了很多在书本上所没有学到过的知识。在设计的过程中遇到过各种各样的问题，但是我们没有放弃，我们借助了老师、同学、网络的力量终于完成程序，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体……我们收获很多，感谢老师，感谢领导给我们这次实战演练的机会，这次程序设计让我们受益匪浅。
相关主题
文本预览