大二数据结构迷宫问题（文档+源代码）.doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.13M 资料格式：doc 举报版权申诉

oyeyuanxinzhizhu1-4933663-4744302543322818155.doc.pdf-第1页.png

第1页 / 共18页

oyeyuanxinzhizhu1-4933663-4744302543322818155.doc.pdf-第2页.png

第2页 / 共18页

oyeyuanxinzhizhu1-4933663-4744302543322818155.doc.pdf-第3页.png

第3页 / 共18页

oyeyuanxinzhizhu1-4933663-4744302543322818155.doc.pdf-第4页.png

第4页 / 共18页

oyeyuanxinzhizhu1-4933663-4744302543322818155.doc.pdf-第5页.png

第5页 / 共18页

oyeyuanxinzhizhu1-4933663-4744302543322818155.doc.pdf-第6页.png

第6页 / 共18页

oyeyuanxinzhizhu1-4933663-4744302543322818155.doc.pdf-第7页.png

第7页 / 共18页

oyeyuanxinzhizhu1-4933663-4744302543322818155.doc.pdf-第8页.png

第8页 / 共18页

文本预览

《数据结构》课程设计报告设计题目迷宫问题专业计算机科学与技术班级计算机科学与技术姓名李亚龙学号 111114050 完成日期 2012.12.27

目录 1. 问题描述………………………………………………2 2. 系统设计………………………………………………2 3. 数据结构与算法描述…………………………………9 4. 测试结果与分析………………………………………9 5. 总结…………………………………………………11 6. 参考文献………………………………………………12 附录程序源代码…………………………………………12 共 4 页第１页

课程设计题目 (要求：正文部分一律用小四号字，宋体，1.5 倍行距。一级标题靠左，四号加粗。二级、三级标题靠左，小四加粗。) 1. 问题描述迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走通迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 2. 系统设计 2.1 设计目标用一个二维数组 maze[i][j]表示迷宫，其中 l<=i<=m，1<=j<=n。数组元素值为 1 表示该位置是墙壁，不能通行；元素值为 0 表示该位置是通路。假定从 maze[l][1]出发，出口位于 maze[m][n]，移动方向可以是 4 个方向(东、南、西、北)。运用栈进行求解 2.2 设计思想在迷宫问题中，一个迷宫用二维数组来存储，对当前位置（探索过程中某一时刻所在的位置）记为 maze[curpos.row][curpos.line]，如果 maze[curpos.row][curpos.line]=0 则有通路，如果 maze[curpos.row][curpos.line]=1 则无通路。从入口 star 出发，可沿四个方向前进。方向向下，用 1 表示，方向向右，用 2 表示，方向向左，共 4 页第２页

用 4 表示，方向向上，用 3 表示。如果遇到 0 则可前进，遇 1 责受阻；按此规则求入口到某一确定出口的一条路径。算法的基本思想是：从迷宫的入口出发，进行判断，若当前位置可通（未走过的），则将当前位置插入栈顶，然后判断此位置是否为出口位置，如果是则结束整个运算，否则，改变当前位置到他的东临位置（即 0 方向）；否则如果当前位置不通，这时若栈不空且栈顶位置尚有其他位置未搜索，则设定新的当前位置为栈顶位置的下一邻块，若栈不空且栈顶位置四周不通，则删去栈顶位置，若栈不空，则重新测试新的栈顶位置，直到找到一个可通的邻块或栈空，如此重复判断，直到找到一条从入口到出口的一条路径或得到无路径的信息。 2.3 系统模块划分 2.3.1 程序用到的类（已用红色标出）： class LinkNode //链表结点 { friend class Stack; public: T data; LinkNode *next; }; class Stack { private: LinkNode *top; //指向第一个结点的栈顶指针 public: Stack(); ~Stack(); //构造函数，置空栈 //析构函数共 4 页第３页

void Push(T e); //把元素 data 压入栈中 T Pop(); T GetPop(); void Clear(); //使栈顶元素出栈 //取出栈顶元素 //把栈清空 bool empty(); //判断栈是否为空，如果为空则返回 1，否则返回 0 }; class T //定义描述迷宫中当前位置的结构类型 { public: int x; int y; //x 代表当前位置的行坐标 //y 代表当前位置的列坐标 int dir; //0:无效,1:东,2:南,3:西,4:北 }; bool Mazepath(int **maze,int m,int n)//寻找迷宫 maze 中从（0，0）到（m,n）的路径 //到则返回 true,否则返回 false { Stack q,p; //定义栈 p、q,分别存探索迷宫的过程和存储路径 T Temp1,Temp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push(Temp1); //将入口位置入栈 p.Push(Temp1); maze[1][1]=-1; //标志入口位置已到达过共 4 页第４页

while(!q.empty()) //栈 q 非空，则反复探索 { Temp2=q.GetPop(); //获取栈顶元素 if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)) p.Push(Temp2); //如果有新位置入栈，则把上一个探索的位置存入栈 p for(loop=0;loop<4;loop++) //探索当前位置的 4 个相邻位置 { x=Temp2.x+move[loop][0]; //计算出新位置 x 位置值 y=Temp2.y+move[loop][1]; //计算出新位置 y 位置值 if(maze[x][y]==0) //判断新位置是否可达 { } Temp1.x=x; Temp1.y=y; maze[x][y]=-1; //标志新位置已到达过 q.Push(Temp1); //新位置入栈 if((x==(m))&&(y==(n))) //成功到达出口 { Temp1.x=m; Temp1.y=n; Temp1.dir=0; p.Push(Temp1); //把最后一个位置入栈 PrintPath(p); //输出路径 Restore(maze,m,n); //恢复路径 return 1; //表示成功找到路径共 4 页第５页

} } int** GetMaze(int &m,int &n)//返回存取迷宫的二维指针 { int **maze; int i=0,j=0; //定义二维指针存取迷宫 cout<<"请输入迷宫的长和宽:"; int a,b;cin>>a>>b; //输入迷宫的长和宽 cout<<"请输入迷宫内容:\n"; m=a; n=b; //m,n 分别代表迷宫的行数和列数 maze=new int *[m+2]; //申请长度等于行数加 2 的二级指针 for(i= 0;i>maze[i][j]; for(i=0;i

void PrintPath(Stack p) //输出路径 { cout<<"迷宫的路径为\n"; cout<<"括号内的内容分别表示为 (行坐标,列坐标, 数字化方向 ,方向)\n"; Stack t; int a,b; T data; //定义一个栈，按从入口到出口存取路径 LinkNode *temp; temp=new LinkNode; //申请空间 temp->data=p.Pop(); //取栈 p 的顶点元素，即第一个位置 t.Push(temp->data); //第一个位置入栈 t delete temp; //释放空间 while(!p.empty()) //栈 p 非空，则反复转移 { temp=new LinkNode; temp->data=p.Pop(); //获取下一个位置 //得到行走方向 a=t.GetPop().x-temp->data.x; //行坐标方向 b=t.GetPop().y-temp->data.y; //列坐标方向 if(a==1) temp->data.dir=1; //方向向下，用 1 表示 else if(b==1) temp->data.dir=2; //方向向右，用 2 表示 else if(a==-1) temp->data.dir=3; //方向向上，用 3 表示 else if(b==-1) temp->data.dir=4; //方向向左，用 4 表示 t.Push(temp->data); //把新位置入栈 delete temp; 共 4 页第７页

分享到：

赞收藏

资料库

大二数据结构迷宫问题（文档+源代码）.doc

相关推荐

课程资源

热门标签

最新资料