迷宫问题、liu.doc

1数据结构课程设计报告报告题目： 迷宫问题、 所在专业： 信息与计算科学所在班级： 10信息 学 号： 201010520111姓 名： 刘良福指导教师： 杨利华 完成时间： 目 录第一章 绪论111 课程设计的目的112 课程设计的背景和意义1121 课程设计的背景1122 课程设计的意义113 课程设计环境1第二章 需求分析121 问题描述1211 迷宫问题222 功能要求2221 迷宫问题的功能要求223 问题的解决方案2第三章 系统设计331 数据设计3311 迷宫问题的数据设计3第四章 系统实现341 结构体实现3411 迷宫问题的结构体定义342 函数实现4421 迷宫问题的函数定义443 主函数实现7421 迷宫问题的测试函数定义7第五章 系统测试951 模块测试9511 迷宫问题的测试9附录第一章 绪论11 课程设计的目的12 课程设计的背景和意义121 课程设计的背景1. 理论研究基础（1）c+语言的基本知识和技能，如：结构体应用，输入和输出，文本文件的建立和保存等。（2）数据结构的基本思想，各种算法。2. 技术层面的支持Microsoft Visual C+ 6.0编译平台122 课程设计的意义本文利用Microsoft Visual C+ 6.0编写程序，实现了迷宫问题求所有路径；程序简单明了，容易操作。13 课程设计环境软件：Windows XP professional SP2操作系统 Microsoft Visual C+ 6.0第二章 需求分析21 问题描述可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出。211 迷宫问题系统总体说明：这是一个心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对进方向形成了多处障碍心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。22 功能要求221 迷宫问题的功能要求完成功能的详细说明：1迷宫中不能使用递归算法查找路径。2试探方向限定为上、下、左、右四个方向。3迷宫要随机生成。4生成从迷宫入口到出口的所有路径。23 问题的解决方案根据系统功能要求，可以将问题解决分为以下步骤： 1）应用系统分析，建立该系统的功能模块框图以及界面的组织和设计；2）分析系统中的各个实体及它们之间的关系； 3）根据问题描述，设计系统的数据结构层次，完成数据结构层次中各个结构体的描述； 4）完成各个函数的定义； 5）完成系统的应用模块并进行功能调试； 6）完成系统总结报告。第三章 系统设计31 数据设计311 迷宫问题的数据设计数据类型及函数设计如下：typedef structint x;int y;Item;typedef struct /定义各点数据类型,x和y表示坐标,d表示方向int x,y,d; DataType;typedef struct /栈DataType dataMAXSIZE;int top;Seqstack;Seqstack *init_Seqstack();int Empty_Seqstack (Seqstack *); /判断栈是否为空int Push_Seqstack(Seqstack *,DataType ); /入栈算法int Pop_Seqstack(Seqstack *,DataType &); /出栈算法 int Output(Seqstack *,int ,int ); /输出路径int Path(int mazeMAXSIZEMAXSIZE,Item move,int,int); /计算路径第四章 系统实现41 结构体实现411 迷宫问题的结构体定义typedef structint x;int y;Item;typedef struct /定义各点数据类型,x和y表示坐标,d表示方向int x,y,d; DataType;typedef struct /栈DataType dataMAXSIZE;int top;Seqstack; 42 函数实现421 迷宫问题的函数定义Seqstack *init_Seqstack()Seqstack *s;s=new Seqstack;s-top=-1;if(!s)cout空间不足 top=-1;return s;/判空int Empty_Seqstack(Seqstack *s)if(s-top=-1)return 1;elsereturn 0;/入栈算法int Push_Seqstack(Seqstack *s,DataType x)if(s-top=MAXSIZE-1)return 0;elses-top+;s-datas-top.x=x.x; s-datas-top.y=x.y;s-datas-top.d=x.d;return 1;/出栈算法 int Pop_Seqstack(Seqstack *s,DataType &x)if(Empty_Seqstack(s)return 0; elsex=s-datas-top;s-top-;return 1;/输出路径int Output(Seqstack *s,int row,int line)int i=s-top;cout(row,line) ;while(i!=-1)cout(datai.x,datai.y) ;i-;coutendl;return 1;int Path(int mazeMAXSIZEMAXSIZE,Item move,int row,int line)Seqstack *s=init_Seqstack();DataType temp;int x=1, y=1,d,j,i,k=0;temp.x=1;temp.y=1;temp.d=-1;Push_Seqstack(s,temp);while(!Empty_Seqstack(s) mazexy=0;if(x=1&y=1)maze11=-1;Pop_Seqstack(s,temp);x=temp.x;y=temp.y;d=temp.d+1; while(d4)i=x+moved.x;j=y+moved.y;if(mazeij=0)temp.x=x; temp.y=y;temp.d=d;Push_Seqstack(s,temp);x=i;y=j;mazexy=-1;if(x=row&y=line)cout第k+1条路径为：endl;Output(s,row,line);k+;break;elsed=0;elsed+;return k;43 主函数实现421 迷宫问题的测试函数定义int main()int row; /迷宫的行数int line; /迷宫的列数int a,p=0;cout欢迎进入迷宫系统endl;while(1)Item move4=-1,0,0,1,1,0,0,-1; /定义各方向移动数组cout请选择是否进入迷宫:endl;cout1.进入 2.不进入a;switch(a)case 1:int i,j;cout请依次输入迷宫的行和列row;cinline;int mazeMAXSIZEMAXSIZE; /迷宫定义cout正在生成迷宫迷宫,请稍候.endl;while(p!=-1)srand(unsigned)time(NULL); /生成迷宫,-1表示起点,/1代表路障,0代表通行,/随机产生0或1这两个随机数for(i=1;i=row;i+)for(j=1;j=line;j+)mazeij=rand()%2;for(i=0;iline+2;i+) /将迷宫的四周都变为1maze0i=1;for(i=0;iline+2;i+)mazerow+1i=1;for(i=0;irow+2;i+)mazei0=1;for(i=0;irow+2;i+)mazeiline+1=1;maze11=0;mazerowline=0;if(Path(maze,move,row,line)!=0)for(i=0;irow+2;i+) /输出迷宫for(j=0;jline+2;j+)cout mazeij;coutendl;cout总共有Path(maze,move,row,line)条路径endl;p=-1;break;case 2:return 0;default:cout输入错误,请重新输入!endl;break;return 0;第五章 系统测试51 模块测试511 迷宫问题的测试如图5-1-1和图5-2-2，显示随机生成一个4行4列的迷宫并求解求解路 图5-1-1 迷宫问题附录迷宫问题程序代码：头文件：#include #include #include #include using namespace std;#define MAXSIZE 100using namespace std;typedef structint x;int y;Item;typedef struct /定义各点数据类型,x和y表示坐标,d表示方向int x,y,d; DataType;typedef struct /栈DataType dataMAXSIZE;int top;Seqstack;Seqstack *init_Seqstack();int Empty_Seqstack (Seqstack *); /判断栈是否为空int Push_Seqstack(Seqstack *,DataType ); /入栈算法int Pop_Seqstack(Seqstack *,DataType &); /出栈算法 int Output(Seqstack *,int ,int ); /输出路径int Path(int mazeMAXSIZEMAXSIZE,Item move,int,int); /计算路径函数文件：#includemigong.hSeqstack *init_Seqstack()Seqstack *s;s=new Seqstack;s-top=-1;if(!s)cout空间不足 top=-1;return s;/判空int Empty_Seqstack(Seqstack *s)if(s-top=-1)return 1;elsereturn 0;/入栈算法int Push_Seqstack(Seqstack *s,DataType x)if(s-top=MAXSIZE-1)return 0;elses-top+;s-datas-top.x=x.x; s-datas-top.y=x.y;s-datas-top.d=x.d;return 1;/出栈算法 int Pop_Seqstack(Seqstack *s,DataType &x)if(Empty_Seqstack(s)return 0; elsex=s-datas-top;s-top-;return 1;/输出路径int Output(Seqstack *s,int row,int line)int i=s-top;cout(row,line) ;while(i!=-1)cout(datai.x,datai.y) ;i-;coutendl;return 1;int Path(int mazeMAXSIZEMAXSIZE,Item move,int row,int line)Seqstack *s=init_Seqstack();DataType temp;int x=1, y=1,d,j,i,k=0;temp.x=1;temp.y=1;temp.d=-1;Push_Seqstack(s,temp);while(!Empty_Seqstack(s) mazexy=0;if(x=1&y=1)maze11=-1;Pop_Seqstack(s,temp);x=temp.x;y=temp.y;d=temp.d+1; while(d4)i=x+moved.x;j=y+moved.y;if(mazeij=0)temp.x=x; temp.y=y;temp.d=d;Push_Seqstack(s,temp);x=i;y=j;mazexy=-1;if(x=row&y=line)cout第k+1条路径为：endl;Output(s,row,line);k+;break;elsed=0;elsed+;return k;测试文件：#includemigong.hint main()int row; /迷宫的行数int line; /迷宫的列数int a,p=0;cout欢迎进入迷宫系统endl;while(1)Item move4=-1,0,0,1,1,0,0,-1; /定义各方向移动数组cout请选择是否进入迷宫:endl;cout1.进入 2.不进入a;switch(a)case 1:int i,j;cout请依次输入迷宫的行和列row;cinline;int mazeMAXSIZEMAXSIZE; /迷宫定义cout正在生成迷宫迷宫,请稍候.endl;while(p!=-1)srand(unsigned)time(NULL); /生成迷宫,-1表示起点,1代表路障,0代表通行,随机产生0或1这两个随机数for(i=1;i=row;i+)for(j=1;j=line;j+)mazeij=rand()%2;for(i=0;iline+2;i+) /将迷宫的四周都变为1maze0i=1;for(i=0;iline+2;i+)mazero