当前位置：文档之家 › 迷宫求解 数据结构实训报告 附源代码 迷宫与栈 小老鼠吃奶酪穷举求解

迷宫求解 数据结构实训报告 附源代码 迷宫与栈 小老鼠吃奶酪穷举求解

  • 格式：doc
  • 大小：139.00 KB
  • 文档页数：21

数据结构实训报告 设 计 题 目： 迷宫的求解（B） 系 别： XXXXXXXXXX 专 业 (方 向)： XXXXXXXX 年 级、 班： XXXXXXXXXXXX 学 生 姓 名： XXX 学 生 学 号： XXXXXX 指 导 教 师： XXX 日 期： XXXX年XX月XX号 目录 一、系统开发的背景 ................................................................................................................ 1 二、系统分析与设计 ................................................................................................................ 1 （一）系统的分析 .................................................................................................................... 1 （二）系统的具体分析设计 .................................................................................................... 2

三、系统的功能要求 .............................................................................................................................. 2、3 （一）系统模块结构设计 ........................................................................................................ 3 四、系统的设计与实现 ................................................................................................................................ 4 （一）在栈中实现迷宫的具体操作 ................................................................................. 4、7 （二）栈的生成 ................................................................................................................. 7、8 （三）整个系统的生成流程图………………………………………………………… 9、10

五、程序测试与步骤 ............................................................................................................. 10 （一）测试迷宫与栈问题可通的程序设计…………..……………………………………10、11

（二）测试迷宫与栈问题不可通的程序设计…………………………………………..…..12 六、 总结………………………………………………………………………………………….12、13

七、附件（代码、部分图表） ...................................................................................... 14、19 1

迷宫的求解 一、系统开发的背景 迷宫求解其实就是迷宫与栈的问题，训练老鼠在迷宫中寻找食物。于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用 “栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。为了使迷宫更佳富有趣味性，按照设计要求，我还设置地雷，如果老鼠在前进的过程中踩到地雷，则要重新回到入口，继续寻找能吃到奶酪的通路。求解迷宫问题，即找出从入口到出口的路径。而数据结构则是数据的组织形式，可以用来表示特定的对象数据，在计算机中对数据的一种存储和组织形式，因此选用栈思想实现迷宫游戏的基本操作，也是我设计迷宫求解的基本背景。

二、 系统分析与设计 (一) 系统分析： 迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某个方向进行搜索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。另外附加的老鼠踩地雷则类似于是在通路上埋藏的隐形墙，如果踩到到雷则返回起点，寻找下一条 2

通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。定义迷宫类型来存储迷宫数据，通常设定入口点的下标，出口点的下标，为处理方便起见，在迷宫的周围加一圈障碍，对于迷宫任何一个位置均约定为东、西、南、北四个方向，而东北、东南、西北、西南则是需要利用到两个下标进行移动。 (二) 系统具体设计 在某个点上，按照一定的顺序（在本程序中顺序为上、右、下、左，而东北、东南、西北、西南利用的是两个下标移动）对周围的墙、路进行判断（在本程序中分别用1、0代替），若周围某个位置为0，则移动到该点上，再进行下一次判断；若周围的位置都为1（即没有通路），则一步步原路返回并判断有无其他通路，然后再次进行相同的判断，直到走到终点为止，或者确认没有任何通路后终止程序，附加踩雷（在本程序中用5代替）则返回到起点重新寻找下一条通路，并显示踩雷路线。 要实现上述算法，需要用到栈的思想。栈里面压的是走过的路径，若遇到死路，则将该位置（在栈的顶层）弹出，再进行下一次判断；若遇到通路，则将该位置压栈并进行下一次判断。如此反复循环，直到程序结束。此时，若迷宫有通路，则栈中存储的是迷宫通路坐标的倒序排列，再把所有坐标顺序打印后，即可得到正确的迷宫通路，附加的踩雷则是相当于在通路上隐形了一道墙，踩雷，则从栈顶弹出，返回起点，再进行二次判断另一条通路。

三、 系统功能要求 3

（1） 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。 （2） 编写递归形式的算法，求得迷宫中所有可能的通路。 （3） 以方阵形式输出迷宫及其通路。 （一）系统模块结构设计 通过对系统功能的分析，迷宫与栈问题的功能如图1所示。

图1： 迷宫实现的主函数功能图 通过上图的功能分析，把整个系统划分为2个模块：

1、 通过栈后进先出的结构，实现栈判断，首先判断栈是否为空，如果不为空，则实现栈中基本的入栈，出栈的实现。顺序栈是用一组地址连续

主函数 初始化栈 入栈 出栈 判断栈是否为空

判断方向 留下足迹 判断能否通过，是否踩雷 初始化迷宫 求解所有路径 输出迷宫 留下标记 4

的 内存单元依次保存栈中的运算规则，在链式存储中链表首部head指针所指向元素为栈顶元素，栈表尾部指向地址为NULL为栈底。 2、 借助函数的嵌套与使用，由while语句对整体进行控制，return语句控制跳出函数，判断在迷宫中是否有出路，如果有出路，则通过东，西，南，北的方向进行路径的输出；如果无出路，则说明此迷宫不能走出。 四、 系统的设计与实现 （一） 在栈中实现迷宫的基本操作 分析：首先输出表头，然后依次输入想要实现的步骤。功能图如图2所示。

入口，出口位置传人方法里

判断当前是否通过 循环不结束，无解迷宫

将元素入栈

是否到达迷宫出口 右边是否存在通路 上边是否存在通路 下边是否存在通路 左边是否存在通路 5

图2：迷宫的实现功能图 该模块的具体代码如下所示。 void Maze::lujing() { int i, j, d; int a, b; lianzhan elem, e;

PLStack S1, S2, S3; InitStack(S1); InitStack(S2); InitStack(S3);

maze[start.x][start.y] = 2; //入口点作上标记 elem.x = start.x; elem.y = start.y; elem.d = -1; //开始为-1 Push(S1, elem); again: while (!StackEmpty(S1)) //栈不为空 有路径可走 { Pop(S1, elem); i = elem.x; j = elem.y; d = elem.d + 1; //下一个方向 while (d<4) //试探东南西北各个方向 { a = i + diradd[d][0]; b = j + diradd[d][1]; if (maze[a][b] == 5) {

while (S1) //逆置序列 并输出迷宫路径序列

存在结点入栈 有解迷宫

合集下载

数据结构毕业课程设计报告—迷宫求解问题

数据结构毕业课程设计报告—迷宫求解问题

课题设计1：迷宫求解一. 需求分析：本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。

首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。

二、概要设计：1.抽象数据类型定义：ADT Find{数据对象：D={ai?ai ∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={<ai-1,ai>?ai-1, ai∈D }基本操作：find (&S)初始条件：已初始化栈S，且栈为空操作结果：从栈Ｓ中找出相对应的数据关系，并输出结果}ADT Find2. 主程序的流程以及各程序模块之间的调用关系：(1).定义变量i、j、w、z为整形变量(2).输入迷宫二维数组maze(0:m,0:n)(3).调用子程序find ()(4).结束程序三、相应的源程序如下：#include<stdio.h>#include<stdlib.h>typedef enum { ERROR, OK } Status;typedef struct{int row, line;}PosType;typedef struct{int di, ord;PosType seat;}SElemType;typedef struct{SElemType * base;SElemType * top;int stacksize;}SqStack;Status InitStack(SqStack &S);Status Push(SqStack &S,SElemType &a);Status Pop(SqStack &S,SElemType &a);Status StackEmpty(SqStack S);Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end);void Initmaze(int maze[12][12],int size);void printmaze(int maze[12][12],int size);Status Pass(int maze[12][12],PosType CurPos);void Markfoot(int maze[12][12], PosType CurPos);PosType NextPos(PosType CurPos, int Dir);void printpath(int maze[12][12],SqStack S,int size);void main (void){SqStack S;int size,maze[12][12];for(int n=0;n<10;n++){printf("创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于50):\n");scanf("%d",&size);if(size<1 || size>10){printf("输入错误!");return;}Initmaze(maze,size);printmaze(maze,size);PosType start,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);else printf("找不到通路!\n\n");}}Status MazePath(int maze[12][12],SqStack &S, PosType start, PosType end){PosType curpos;int curstep;SElemType e;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)return OK;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));return ERROR;}void Initmaze(int maze[12][12],int size){char select;printf("选择创建方式A:自动生成B:手动创建\n");label:scanf("%c",&select);if(select=='a'||select=='A'){for(int i=0;i<size+2;i++)maze[0][i]=1;for( i=1;i<size+1;i++){maze[i][0]=1;for(int j=1;j<size+1;j++)maze[i][j]=rand()%2;maze[i][size+1]=1;}for(i=0;i<size+2;i++)maze[size+1][i]=1;}else if(select=='b'||select=='B'){printf("按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):\n",size,size);for(int i=0;i<size+2;i++)maze[0][i]=1;for( i=1;i<size+1;i++){maze[i][0]=1;for(int j=1;j<size+1;j++)scanf("%d",&maze[i][j]);maze[i][size+1]=1;}for(i=0;i<size+2;i++)maze[size+1][i]=1;}else if(select=='\n')goto label;else printf("输入错误!");}void printmaze(int maze[12][12],int size){printf("\n\n");printf("显示所建的迷宫(#表示外面的墙):\n");for(int i=0;i<size+2;i++)printf("%c ",'#');printf("\n");for(i=1;i<size+1;i++){printf("%c ",'#');for(int j=1;j<size+1;j++){printf("%d ",maze[i][j]);}printf("%c",'#');printf("\n");}for(i=0;i<size+2;i++)printf("%c ",'#');printf("\n");}void printpath(int maze[12][12],SqStack S,int size){printf("\n\n通路路径为:\n");SElemType * p=S.base;while(p!=S.top){maze[p->seat.row][p->seat.line]=2;p++;}for(int i=0;i<size+2;i++)printf("%c ",'#');printf("\n");for(i=1;i<size+1;i++){printf("%c ",'#');for(int j=1;j<size+1;j++){if(maze[i][j]==2) printf("%c ",'0');else printf(" ");}printf("%c",'#');printf("\n");}for(i=0;i<size+2;i++)printf("%c ",'#');printf("\n\n"); }Status Pass(int maze[12][12],PosType CurPos){if (maze[CurPos.row][CurPos.line]==0)return OK;else return ERROR;}void Markfoot(int maze[12][12],PosType CurPos){maze[CurPos.row][CurPos.line]=1;}PosType NextPos(PosType CurPos, int Dir){PosType ReturnPos;switch (Dir){case 1:ReturnPos.row=CurPos.row;ReturnPos.line=CurPos.line+1;break;case 2:ReturnPos.row=CurPos.row+1;ReturnPos.line=CurPos.line;break;case 3:ReturnPos.row=CurPos.row;ReturnPos.line=CurPos.line-1;break;case 4:ReturnPos.row=CurPos.row-1;ReturnPos.line=CurPos.line;break;}return ReturnPos;}Status InitStack(SqStack &S){S.base=(SElemType *)malloc(100*sizeof(SElemType));if(!S.base)return ERROR;S.top=S.base;S.stacksize=100;return OK;}Status Push(SqStack &S,SElemType &a){*S.top++=a;return OK;}Status Pop(SqStack &S,SElemType &a){if(S.top==S.base)return ERROR;a=*--S.top;return OK;}Status StackEmpty(SqStack S){if(S.top==S.base)return OK;return ERROR;}以下为测试数据：输入一个矩阵，例如：1 0 0 1 10 0 1 1 11 0 0 0 10 1 0 1 11 1 0 0 0输入入口行坐标和列坐标：1 2输入出口行坐标和列坐标：5 5通路路径为：课题设计3：joseph环一. 需求分析：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

数据结构迷宫求解课程设计报告

数据结构迷宫求解课程设计报告

课程设计报告课程名称：数据结构报告题目：迷宫求解学生姓名：XX所在学院：信息科学与工程专业班级：软件工程学生学号：XXXXXXXXXXX指导教师：XXX课程设计任务书摘要本程序主若是求迷宫中从人口到出口的所有途径是一个经典的程序设计问题。

运算机解迷宫时，通经常使用的是“穷举求解”的方式，即从入口动身，顺某一方向向前探讨，假设能走通，那么继续往前走；不然沿原路返回，换一个方向在继续探讨，直至所有可能的通路都探讨完为止。

当前位置“可通”，那么纳入“当前途径”，并继续朝“下一名置”探讨，即切换为“下一名置”为“当前位置”，如此重复直至抵达出口；假设当前位置“不可通”，那么应顺着“来的方向”退回到“前一通道块”，假设该通道块的周围4个方块均“不可通”那么应从当前途径删除该通道块。

所谓“下一名置”指的是“当前位置”周围4个方向（东、南、西、北）上相邻的方块。

以栈S来记录“当前途径”，那么栈顶中寄存的是“当前途径上最后一个通道块”。

因此即为“当前途径入栈”；“从当前途径上删除前一通道块”为“出栈”。

在那个进程中能够输出迷宫所走通的途径，在这次课程设计中迷宫是由数组预先概念好的，不能由用户概念生成，能够加入随机函数，自动生成二维数组，还能够用户自己输入迷宫。

关键词：栈；存储结构；数组目录目录 (3)一、课题分析 (1)二、需求分析 (1)1. 主模块功能描述 (1)2. 子程序模块设计 (1)三、设计方案 (1)1.类设计 (1)int point_x; 序模块设计 (2)设计方案与实施与整体设计思想 (2)3. 主模块 (3)子模块 (4)主菜单 (5)功能A模块 (5)功能B模块 (5)功能C模块 (6)四、详细设计 (7)1.用结构体构建栈 (7)SElemType *top; 建类 (7)int point_x; 数组构建一个迷宫 (7)case 1: 戏移动操纵指令 (8)}戏移动操纵指令四个方向的实现 (8)else if ((map[point_x - 1][point_y] == 0 && direction != 5) || map[point_x - 1][point_y] == 3) 戏移动进程中假设是未找到通路，需要返回的指令 (9)}戏的主循环 (9)}戏的开始于终止 (10)if (map[point_x][point_y] == 3) 宫地图的查看与通关后的途径查询 (10)五、设计总结 (11)结论与心得 (11)五、参考文献 (12)一、课题分析（1）该题目为迷宫求解。

迷宫求解实验报告

迷宫求解实验报告

数据结构（迷宫求解实验报告）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）实验实现基本思路：若当前位置可通，则纳入当前路径，并继续朝下一个位置探索，即切换下一位置为当前位置，如此重复直至到达出口；若当前位置不可通，则应顺着来向退回到前一通道块，然后朝着除来向之外的其他方向继续探索；若该通道块的四周4个方块均不可通，则应从当前路径上删除该通道块。

设以栈记录当前路径，则栈顶中存放的是当前路径上最后一个通道块。

由此，纳入路径的操作即为当前位置入栈；从当前路径上删除前一通道块的才操作即为出栈。

二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）抽象数据类型：typedef struct{int x; //当前位置的横坐标int y; //当前位置的纵坐标char type; //当前位置的属性：墙壁或通道(0/1)bool isfoot; //判断当位置是否已走过, true代表已走过}Position; //当前位置信息typedef struct{int order; //脚步在地图上的序号Position seat; //行走的当前位置int aspect; //下一步的方向}Block; //脚步typedef struct{int width; //地图的长度int height; //地图的宽度Position* site; //地图内的各个位置}Maze; //地图typedef struct{Block* base;Block* top;int length;int stacksize;}Stack;主程序模块：int main(int argc, _TCHAR* argv[]){Position start,end;Block blk;Stack S;int width,height;printf("输入迷宫比例X*Y\n");printf("输入X:");scanf("%d",&width);printf("输入Y:");scanf("%d",&height);Maze* maze=GreatMaze(width,height);PrintMaze(maze);printf("\n");printf("请输入入口坐标X:");scanf(" %d",&start.x);printf("请输入入口坐标Y:");scanf(" %d",&start.y);printf("请输入出后坐标X:");scanf(" %d",&end.x);printf("请输入出口坐标Y:");scanf(" %d",&end.y);MazePath(maze,start,end,S);printf("走完所需路径长度为:%d",S.length);printf("\n");Stack Sa;InitStack(Sa);while(S.length!=0){Pop(S,blk);Push(Sa,blk);}while(Sa.length!=0){Pop(Sa,blk);if(Sa.length!=0)printf("[%d,%d]->",blk.seat.x,blk.seat.y); //打印足迹elseprintf("[%d,%d]",blk.seat.x,blk.seat.y); //打印最后一步}}各子程序函数：Maze* GreatMaze(int width,int height) //创建地图void PrintMaze(Maze* maze) //打印地图int PositionComparison(Position maze,Position pos) //判断当前位置是否合法int Pass(Maze* maze,Position curpos)//判断当前位置是否可以前进或者是否走过void FootSet(Maze* maze,Position site) //留下足迹Position NextPos(Position &cur,int aspect)//判断方向Int MazePath(Maze* maze,Position start,Position end,Stack &S)//搜索从入口到出口的路径三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。

小鼠迷宫实验报告.doc

小鼠迷宫实验报告.doc

小鼠迷宫实验报告
篇一：迷宫实验
《迷宫》实验报告
篇二：小鼠走迷宫获取食物的学习行为
小鼠走迷宫获取食物的学习行为
（1）提出问题：小鼠走迷宫获取食物是学习行为吗？（2）做出假设：小鼠走迷宫获取食物是学习行为
（3）实验的目的：理解学习行为对与动物生存的重要意义
（4）实验材料：小鼠、纸板（用于制作“迷宫”）、制作“迷宫”的各种工具，小鼠食物，笼子几个。

（5）方法步骤；①从迷宫的入口放入小鼠，同时在出口放置食品。

②记录小鼠“尝试与错误”的次数。

③重复上述实验过程5~7次，记录实验数据。

（6）注意事项. ①通道的宽度要便于小鼠反折。

②实验前使小鼠处于饥饿状态。

（7）试验计划：认真统计小鼠需要经过几次“尝试与错误”才能通过“迷宫”，吃到食物。

（8）实验结论：小鼠走迷宫获取食物是学习行为
学校：花都区三和庄中学
姓名：卢婉仪利静琪
班级：八年级三班
指导老师：黄炽成
篇三：生物实验报告
探究小鼠走迷宫获取食物的学习行为
实验报告
提出问题：小鼠是否能经过训练，在很短的时间内形成一种新的行为？作出假设：仓鼠能够在短时间内形成一种新的行为。

制定计划：1.准备硬纸板、剪刀、透明胶、铅笔等工具用来制作迷宫。

2.准备坚果、花生等食物放在迷宫的尽头。

3.准备一只仓鼠从固定地点放好食物，让仓鼠在迷宫中自由活动，必要时可引一下。

若仓鼠去到食物存放地点，让其进食一段时间后放回饲养笼中。

4、数次训练，直至仓鼠可以进入迷宫就直奔食物存放点为止。

实验过程：
结论：仓鼠在经过训练后能在短时间内形成一种新的行为。