迷宫问答课程教学设计.docx
《迷宫问答课程教学设计.docx》由会员分享，可在线阅读，更多相关《迷宫问答课程教学设计.docx（25页珍藏版）》请在冰点文库上搜索。
迷宫问答课程教学设计
第一部分引言……………………………………………………………………
第二部分课程设计报告…………………………………………………………
第一节课程设计目的…………………………………………………
第二节课程设计内容和要求…………………………………………
2.1问题描述………………………………………………
2.2设计要求………………………………………………
第3节课程设计总体方案及分析……………………………………
3.1问题分析………………………………………………
3.2概要设计………………………………………………
3.3详细设计………………………………………………
3.4测试结果……………………………………………
3.5参考文献………………………………………………
第三部分课程设计总结…………………………………………………………
附录（源代码）……………………………………………………………………
第一部分引言
数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。
该课程的先行课程是计算机基础、程序设计语言、离散数学等，后续课程有操作系统、编译原理、数据库原理、软件工程等。
通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。
数据结构是软件工程专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。
学习数据结构的最终目的是为了获得求解问题的能力。
对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。
基于此原因，暑期我们开设了数据结构课程设计。
针对数据结构课程的特点，着眼于培养我们的实践能力。
实习课程是为了加强编程能力的培养，鼓励学生使用新兴的编程语言。
相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，同学们都会有不同程度上的提高。
第二部分课程设计报告
第一节课程设计目的
仅仅认识到栈和队列是一种特殊的线性表是远远不够的，本次实习的目的在于使学生深入了解栈和队列的特征，以便在实际问题背景下灵活运用它，同时还将巩固这种数据结构的构造方法。
第二节 课程设计内容和要求
2.1问题描述：
迷宫问题是取自心理学的一个古典实验。
在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。
盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。
对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。
老鼠经过多次试验最终学会走通迷宫的路线。
设计一个计算机程序对任意设定的矩形迷宫,求出一条从入口到出口的通路，或得出没有通路的结果。
2.2设计要求：
要求设计程序输出如下：
（1）建立一个大小为m×m的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来；
（2）在屏幕上输出迷宫和通路；
第三节 课程设计总体方案及分析
3.1问题分析：
1.迷宫的建立：
迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，#表示墙壁，这样迷宫就可以用0、1矩阵来描述，
2.迷宫的存储：
迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][M+2],然后用它的前m行m列来存放元素，即可得到一个m×m的二维数组，这样（0,0）表示迷宫入口位置，（m-1,m-1）表示迷宫出口位置。
注：
其中M，M分别表示迷宫最大行、列数，本程序M的最大值为9，当然用户也可根据需要，调整其大小。
3.迷宫路径的搜索：
首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。
否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。
为防止搜索重复出现，则将已搜索过的位置用函数进行判断和标记，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。
这实现的是广度优先遍历的算法，如果找到路径，则最短路径。
搜索算法流程图如下所示：
3.2概要设计
1.①构建一个二维数组maze[M+2][M+2]用于存储迷宫矩阵
②自动或手动生成迷宫，即为二维数组maze[M+2][M+2]赋值
③构建一个队列用于存储迷宫路径
④建立迷宫节点,用于存储迷宫中每个节点的访问情况
⑤实现搜索算法
⑥屏幕上显示操作菜单
2.本程序包含12个函数：
（1）主函数main（）
（2）StatusInitStack（SqStack&S）;//创建一个空栈S
（3）StatusPush（SqStack&S,SElemType&a）;//插入新元素a
（4）StatusPop（SqStack&S,SElemType&a）;//删除栈顶元素，a返回其值
（5）StatusStackEmpty（SqStackS）;//检查是否空栈
（6）StatusMazePath（intmaze[12][12],SqStack&S,PosTypestart,PosTypeend）;//找通路
（7）voidInitmaze（intmaze[12][12],intsize）;//初始化迷宫
（8）voidprintmaze（intmaze[12][12],intsize）;//显示迷宫
（9）StatusPass（intmaze[12][12],PosTypeCurPos）;//判断当前位置是否可通
（10）voidMarkfoot（intmaze[12][12],PosTypeCurPos）;//标记当前位置不可通
（11）PosTypeNextPos（PosTypeCurPos,intDir）;//进入下一位置
（12）voidprintpath（intmaze[12][12],SqStackS,intsize）;//显示通路
3.3详细设计
程序设计的基本思想，原理和算法描述：
此算法最大的优点是支持图形化输入与输出，观察效果好
迷宫求解问题主要运用了堆栈的性质
求迷宫中一条从入口到出口的路径的算法描述：
do
{
若当前位置可通
则{
将当前位置插入栈顶;
若该位置时出口位置，则结束；
否则切换当前位置为东邻方块为新的当前位置;
}
否则
{
若栈不空且栈顶位置尚有其他方向未经探索，
则设定新的当前位置为沿顺时针方向旋转的栈顶位置的下一相邻模块
若栈不空但栈顶位置的四周均不可通
则{
删去栈顶位置;
若栈不空，则重新测试新的栈顶位置
直至找到一个可通的相邻模块或出栈至栈空；
}
}
}while（栈不空）
实现的函数为
/**************************************************************
若迷宫maze中从入口start到出口end的通道，则求得一条存放在栈中
**************************************************************/
StatusMazePath（intmaze[12][12],SqStack&S,PosTypestart,PosTypeend）
{
PosTypecurpos;
intcurstep;
SElemTypee;
InitStack（S）;
curpos=start;//设定"当前位置"为"入口位置
curstep=1;//探索第一步
do
{
if（Pass（maze,curpos））//当前位置可通过，即是未曾走到过的通道块
{
Markfoot（maze,curpos）;//留下足迹
e.di=1;
e.ord=curstep;
e.seat=curpos;
Push（S,e）;//加入路径
if（curpos.row==end.row&&curpos.line==end.line）
returnOK;//到达终点（出口）
curpos=NextPos（curpos,1）;//下一位置是当前位置的东邻
curstep++;//探索下一步
}
else//当前位置不能通过
{
if（!
StackEmpty（S））
{
Pop（S,e）;
while（e.di==4&&!
StackEmpty（S））
{
Markfoot（maze,e.seat）;//留下不能通过的标记，并退回一步
Pop（S,e）;
}
if（e.di<4）
{
e.di++;//换下一个方向探索
Push（S,e）;
curpos=NextPos（e.seat,e.di）;//当前位置设为新方向的
//相邻块
}
}
}
}while（!
StackEmpty（S））;
returnERROR;
}
围绕这个函数需要定义一些相关的函数操作，由以下函数实现
/**************************************************************
函数原型说明
**************************************************************/
StatusInitStack（SqStack&S）;//创建一个空栈S
StatusPush（SqStack&S,SElemType&a）;//插入新元素a
StatusPop（SqStack&S,SElemType&a）;//删除栈顶元素，a返回其值
StatusStackEmpty（SqStackS）;//检查是否空栈
StatusMazePath（intmaze[12][12],SqStack&S,PosTypestart,PosTypeend）;
//找通路
voidInitmaze（intmaze[12][12],intsize）;//初始化迷宫
voidprintmaze（intmaze[12][12],intsize）;//显示迷宫
StatusPass（intmaze[12][12],PosTypeCurPos）;//判断当前位置是否可通
voidMarkfoot（intmaze[12][12],PosTypeCurPos）;//标记当前位置不可通
PosTypeNextPos（PosTypeCurPos,intDir）;//进入下一位置
voidprintpath（intmaze[12][12],SqStackS,intsize）;//显示通路
算法中我用正方形迷宫，即行数等于列数。
迷宫的存储我用了一个整形二维数组表示,
intsize;//正方形迷宫尺寸
intmaze[12][12];//存储迷宫内路径可通情况
二维数组存储的数字表示对应迷宫位置处可通与否，0表示可通，1表示不可通。
尺寸大小size可以设置，但是不能超过10，因为二维数组第一行，最后一行，第一列，最后一列一定要是不可通的，这是算法中用到的一个技巧。
迷宫内通道块位置变量类型定义为PosType
typedefstruct
{
introw;//row表示“行”号
intline;//line表示“列”号
}PosType;//位置的元素类型
这样判断其可通与否的语句为
if（maze[CurPos.row][CurPos.line]==0）
1.迷宫的初始化
voidInitmaze（intmaze[12][12],intsize）;//初始化迷宫
迷宫的初始化有两种方法，一是随即生成，一是手动设置，由用户选择。
随即生成的方法是程序生成随机数，除以2取余
maze[i][j]=rand（）%2;
手动设置是用户输入0,1由程序读取
scanf（"%d",&maze[i][j]）;
见部分程序
2.显示迷宫
voidprintmaze（intmaze[12][12],intsize）;//显示迷宫
只需要整齐打印出0，1即可，可以看到很好的效果
显示初始化的迷宫
程序见第三部分。
3.显示通路
voidprintpath（intmaze[12][12],SqStackS,intsize）;//显示通路
用到了一个技巧，只要是纳入堆栈的位置元素即为通路上的路径，将其迷宫对应位置
值变为2，
while（p!
=S.top）
{
maze[p->seat.row][p->seat.line]=2;//标记为路径中的点
p++;
}
然后显示通路时只要等于2的地方就打印一个0，否则打印空格。
if（maze[i][j]==2）printf（"%c",'0'）;
elseprintf（""）;
4.进入下一位置
PosTypeNextPos（PosTypeCurPos,intDir）;//进入下一位置时按顺时针方向
//向下一位置探索
5.堆栈操作，包括创建，入栈，出栈，判空。
StatusInitStack（SqStack&S）;//创建一个空栈S
StatusPush（SqStack&S,SElemType&a）;//插入新元素a
StatusPop（SqStack&S,SElemType&a）;//删除栈顶元素，a返回其值
StatusStackEmpty（SqStackS）;//检查是否空栈
3.3测试结果
BuildLog--------------------Configuration:
迷宫求解-Win32Debug--------------------
CommandLines
Results
迷宫求解.exe-0error（s）,0warning（s）
错误输入
正确路径
3.5参考文献
1.谭浩强<>[M].北京：
清华大学出版社，2006.
2.严蔚敏<<数据结构（C语言版）>>[M].北京：
清华大学出版社
3.王华,叶爱亮等.<>[M].北京：
机械工业出版社
4.钱新贤,程兆炜等.<>[M].北京：
人民邮电出版社，2000.
第三部分课程设计总结
通过这段时间的课程设计，本人对软件专业的应用，数据结构的作用以及C语言的使用都有了更深的了解。
尤其是C语言的进步让我深刻的感受到任何所学的知识都需要实践，没有实践就无法真正理解这些知识以及掌握它们，使其成为自己的财富。
在理论学习和上机实践的各个环节中，通过自主学习和请教老师，我收获了不少。
当然也遇到不少的问题，也正是因为这些问题引发的思考给我带了收获。
从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不只如何下手到现在知道如何分析问题，如何用专业知识解决实际问题的转变，我发现无论是专业知识还是动手能力，自己都有很大程度的提高。
在这段时间里，我对forwhile等的循环函数用法更加熟悉，逐渐形成了较好的编程习惯。
在老师的指导帮助下，同学们课余时间的讨论中，这些问题都一一得到了解决。
在程序的调试能力上，无形中得到了许多的提高。
例如：
头文件的使用，变量和数组的范围问题，定义变量时出现的问题等等。
在实际的上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。
在这次短短的课程实践里，我们得到了邓彬老师的关心和帮助。
她给了我们很多的信息，与我们一起探讨问题，询问我们遇到了哪些问题并耐心给予指导。
当我们遇到技术上难以解决的问题时，她就会指导我们解决问题，她把自己多年来积累的经验教给我们，使我们顺利地完成了课程实践任务。
时间过得真快，大学生活不知不觉就走过了一年，一年的大学学习和课程实践阶段的提高，使我们本身知识得到提高的同时，也增强了我们对未来工作的信心，我们相信自己未来三年的学习更使我们有能力胜任将来的工作。
附录：
（原程序代码）
#include
#include
/**************************************************************
数据定义
**************************************************************/
typedefenum{ERROR,OK}Status;
typedefstruct
{
introw;//row表示“行”号
intline;//line表示“列”号
}PosType;//位置的元素类型
typedefstruct
{
intord;//该通道在路径上的“序号”
PosTypeseat;//通道块在迷宫中的“坐标位置”
intdi;//从此通道走向下以通道块的“方向”
}SElemType;//栈的元素类型
typedefstruct
{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
/**************************************************************
函数原型说明
**************************************************************/
StatusInitStack（SqStack&S）;//创建一个空栈S
StatusPush（SqStack&S,SElemType&a）;//插入新元素a
StatusPop（SqStack&S,SElemType&a）;//删除栈顶元素，a返回其值
StatusStackEmpty（SqStackS）;//检查是否空栈
StatusMazePath（intmaze[12][12],SqStack&S,PosTypestart,PosTypeend）;//找通路
voidInitmaze（intmaze[12][12],intsize）;//初始化迷宫
voidprintmaze（intmaze[12][12],intsize）;//显示迷宫
StatusPass（intmaze[12][12],PosTypeCurPos）;//判断当前位置是否可通
voidMarkfoot（intmaze[12][12],PosTypeCurPos）;//标记当前位置不可通
PosTypeNextPos（PosTypeCurPos,intDir）;//进入下一位置
voidprintpath（intmaze[12][12],SqStackS,intsize）;//显示通路
/**************************************************************
主函数
**************************************************************/
voidmain（void）
{
SqStackS;
intsize;//正方形迷宫尺寸
intmaze[12][12];//存储迷宫内路径可通情况
for（intn=0;n<10;n++）
{
printf（"创建一个正方形迷宫，请输入迷宫尺寸（注意不要大于10）:
\n"）;//设置迷宫大小
scanf（"%d",&size）;if（size<1||size>10）{printf（"输入错误!
"）;return;}
Initmaze（maze,size）;//初始化迷宫
printmaze（maze,size）;//显示所创建的迷宫
PosTypestart,end;//设置入口和出口
printf（"输入入口行坐标和列坐标:
"）;scanf（"%d",&start.row）;scanf（"%d",&start.line）;
printf（"输入出口行坐标和列坐标:
"）;scanf（"%d",&end.row）;scanf（"%d",&end.line）;
if（MazePath（maze,S,start,end））//若有通路，显示通路
printpath（maze,S,size）;
elseprintf（"找不到通路!
\n\n"）;
}
}
/**************************************************************
若迷宫maze中从入口start到出口end的通道，则求得一条存放在栈中
**************************************************************/
StatusMazePath（intmaze[12][12],SqStack&S,PosTypestart,PosTypeend）
{
PosTypecurpos;
intcurstep;
SElemTypee;
InitStack（S）;
curpos=start;//设定"当前位置"为"入口位置
curstep=1;//探索第一步
do
{
if（Pass（maze,curpos））//当前位置可通过，即是未曾走到过的通道块
{Markfoot（maze,curpos）;//留下足迹
e.di=1;
e.ord=curstep;
e.seat=curpos;
Push（S,e）;//加入路径
if（curpos.row==end.row&&curpos.line==end.line
升级会员 