数据结构迷宫问题课程设计报告格式

《数据结构迷宫问题课程设计报告格式》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构C++课程设计一、设计题目综合实验九迷宫问题一、实验R的：（1）熟练掌握链栈的基木操作及应用。（2）利用链表作为栈的存储结构，设计实现一个求解迷宫的非递归程序。二、实验内容：【问题描述】以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对信任意设定的迷宮，求出一条从入U到出口的通路，或得出没有通路的结论。【基木要求】首先实现一个链表作存储结构的栈类型，然后编写一个求解迷宮的非递归程序。求得的通路以三元组（i,j，d）的形式输出，其中：（i，j）指示迷宫中的一个平标，d表示走到下一平标的方向。如：对于下列数裾

2、的迷宫，输出的一条通路为：（1,1，1）,（1，2,2）,（2,2,2）,（3,2，3），【测试数据】（3，1,2）,•0迷宫的测试数裾如下:左上角（1，1）为入U,右下角（8，9）为出口。12345678001000100010001000001101011100100001000001000101011110011100010111000000【实现提示】计算机解迷宫通常用的是“穷难求解”方法，即从入U出发，顺卷菜一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所奋可能的通路

3、都探索到则未能到达出U,则所没定的迷宫没奋通解。可以二维数组存储迷宫数据，通常设定入口点的不标为（1,1）,出L1点的下标为（n,n）。为处理方便起见，町以迷宫的四周加一圈障碍。对于迷宫任一位置，均町约定有东、南、西、北四个方向可通。【选作内容】（1）编写递归形式的算法，求得迷宫中所冇可能的通路；（2）以方阵形式输出迷宫及艽通路。二、小组成员分工说明基本上是各自独立完成。三、需求分析1)运行环境(软、硬件环境)WindowsXP环境下、MicrosoftvisualC++6.0版、512M内存、80G硬盘容量2)输入的形式和输入值的范围int

4、林GetMaze(int&m,int&n)｛int**maze;//定义二维指针存取迷宫inti=0,j=0;C0Ut〈C请输入迷宫的长和宽＜;inta,b;cin»a»b;//输入迷宫的长和宽cout〈〈〃请输入迷宫内容:〃；ra=a;n=b;//m,n分别代表迷宫的行数和列数maze=newint*[m+2];//申请长度等于行数加2的二级指针for(i=0;i〈m+2;i++)//申请每个二维指针的空间raaze[i]=newint[n+2];}for(i=l;i<=m;i++)//输入迷宫的内容，1代表可通，0代表不通for(j=

5、l;j<=n;j++)cin»maze[i][j];for(i=0;i〈m+2;i++)maze[i][0]=maze[i][n+l]=l;for(i=0;i

6、,方向)，由这些数据可以得到此迷宫的一条通路。cout〈〈’(’〈〈data.x〈〈’，’〈〈data.y〈〈’，’〈〈data.dir〈〈"，"；//输出行坐标，列坐标switch(data,dir)//输出相应的方向｛casel:cout«z，j)^;break;case2:cout«，，->)^;break:case3:cout<

7、前位置的数据类型其公有变量为：x（行坐标）、y（列坐标）、dir（东南西北四个方向）ClassLinkNode链表结点定义其公有变量为：Tdata,next域ClassStack链栈存储定义及功能实现主要函数功能：创建栈、进栈、出栈、取桟顶值、清空栈等。int林GetMaze（int&m,int&n）存取迷宫的二维指针函数，申请11行10列的指针空间，输入二位数组的内容，输入形式如上。完成后返回二维指针，得到二维数组。boolMazepath（int林maze,intm,intn）寻找迷宫maze中从（0,0）到（m,n）的路径，到则返回tr

8、ue,否则返回false。定义两个桟p，q：分别存储比较过程和存储路径，如果x行y列有元素值为0,则xy进浅p,并设maze[x][y]=_l.当没有新元素进栈p时