数据结构课程设计报告迷宫.doc

《数据结构课程设计报告迷宫.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告迷宫.doc（14页珍藏版）》请在三一办公上搜索。

1、 数据结构课程设计报告题目：迷宫问题姓名：学号：班级：指导教师： 2012年6月6日1. 问题描述输入任意大小的迷宫数据，用递归和非递归方法求出一条走出迷宫的路径，并将路径输出。2. 设计思路 以 0和1分别表示迷宫中的通路和障碍，没有通路则不显示。未显示为得出没有通路的结论；走迷宫的方式是一个一个的线路去试 如果是死路的话就退回去，类似数据结构中栈的先进后出，所以可以用栈这种结构表示迷宫，通过不断的试验当试出最后的路线时输出栈即可，由于它是不断循环的实验，所以可以采用链栈实现迷宫的求解。同时因为迷宫需要不断重复的试验，可以看成反复的调用“迷宫“这个函数，这是典型的递归问题，所以也可以使用递归

2、解决问题。另外由于数据对象是迷宫所以可以用0和1构建不同类型的迷宫更符合实际也更有乐趣。3. 数据结构设计前面提到要用到链栈和递归两种方式操作；为了更好的以链表作存储结构的栈，可以用二维数组存储迷宫信息，同时通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。这样是路径更加明显，具体的数据结构为： #define maxsize 100#define NULL 0typedef struct/定义迷宫 int Mazemaxsizemaxsize;/二维数组存放迷宫信息 int maze_x,maze_y;/迷宫的行数和列数maze;type

3、def struct point/链栈的每个结点定义int vex_x,vex_y;/结点的横纵坐标 int direction;/下一个结点的方向 struct point *next;/指向下一个结点Point;递归法像一位手握大权的领导。当他站在迷宫入口处时，他才懒得亲自去走，这时这位领导会吩咐他的手下，让他们分别向着迷宫的各个方向去探索；当遇到岔路口时留一个人守在这里，再分出几股人，朝着每个方向继续探索；最后总会有一个人发现出口。发现出口的这个人将出口的位置报告给离他最近的路口处留守的人，再由这个人报告给上一个路口的人，依次层层上报，最后消息传到了领导那里，于是这位领导就顺着这条画好的

4、通路大摇大摆地通过了迷宫。所以具体的数据结构为：#include#include#define maxsize 100#define NULL 0typedef struct/定义迷宫int Mazemaxsizemaxsize;/二维数组存放迷宫信息int maze_x,maze_y;/迷宫的行数和列数maze;maze a;typedef struct point/链栈的每个结点定义int vex_x,vex_y;/结点的横纵坐标int direction;/下一个结点的方向struct point *next;/指向下一个结点Point;4.功能函数设计一个用于存放迷宫信息的二维数组ma

5、ze相关操作：a.二维数组的初始化maze creat()b.数组以指针形式在各个函数中传递。c.可以改变数组中的行数和列数。结构体point *next：指向下一个结点结构体printmazepath：输出迷宫路径。结构体secret：搜索迷宫路径。5.编码实现非递归：#include#include#define maxsize 100#define NULL 0typedef struct int Mazemaxsizemaxsize; int maze_x,maze_y;maze;typedef struct point int vex_x,vex_y; int direction;

6、struct point *next; Point;maze creat() int i,j; maze a; printf(hang shu he lei shu:); scanf(%d%d,&a.maze_x,&a.maze_y); for(i=1;i=a.maze_x;i+) printf(shu ru %d hang:,i); for(j=1;jvex_x&y=p-vex_y) return 1; p=p-next; return 0;Point *secret(maze a) Point *top,*p; int j,m,x,y; p=(Point *)malloc(sizeof(P

7、oint); p-vex_x=1; p-vex_y=1; p-next=NULL; top=p; j=1; do while(jvex_x; y=top-vex_y; switch(j) case 1:if(y+1vex_x=x;p-vex_y=y+1; p-next=top; top-direction=j; top=p;m=1; break; case 2:if(x+1vex_x=x+1;p-vex_y=y; p-next=top; top-direction=j; top=p;m=1; break; case 3:if(y-1vex_x=x;p-vex_y=y-1; p-next=top

8、; top-direction=j; top=p;m=1; break; case 4:if(x-1vex_x=x-1;p-vex_y=y; p-next=top; top-direction=j; top=p;m=1; break; if(m!=0) j=1;break; else j+; if(j4) if(top!=NULL) top=top-next; if(top=NULL)return NULL; j=top-direction+1;top-direction=j; while(top-vex_x!=a.maze_x|top-vex_y!=a.maze_y); if(top-vex

9、_x=a.maze_x&top-vex_y=a.maze_y)top-direction=0; return top;int print(Point *p) int i=0,top=0; Point *stackmaxsize; if(p=NULL) printf(bu neng dao da lu kou!n); return 0; else printf(shu chu lu jing（san yuan zu biao shi）：n); while(p!=NULL) stacktop+=p; p=p-next; while(top0) top-; printf(%d,%d,%d),stac

10、ktop-vex_x,stacktop-vex_y,stacktop-direction); i+; if(i%8=0)printf(n); printf(n); return 1;void printmazepath(Point *p,maze road) int i,j; char mmaxsizemaxsize; printf(lu jing tu shi:n); for(i=1;i=road.maze_x;i+) for(j=1;jdirection) case 0:mp-vex_xp-vex_y=1;break; case 1:mp-vex_xp-vex_y=26;break; ca

11、se 2:mp-vex_xp-vex_y=25;break; case 3:mp-vex_xp-vex_y=27;break; case 4:mp-vex_xp-vex_y=24;break; p=p-next; for(i=1;i=road.maze_x;i+) for(j=1;j=road.maze_y;j+) printf(%c,mij); if(jroad.maze_y)printf( ); else printf(n); void main() maze road; Point *p; road=creat(); p=secret(road); if(print(p)printmaz

12、epath(p,road);getch(); 递归 #include#include#define maxsize 100#define NULL 0typedef struct int Mazemaxsizemaxsize; int maze_x,maze_y;maze;maze a;typedef struct point int vex_x,vex_y; int direction; struct point *next;Point;maze creat() int i,j; maze a; printf(shu ru hang he lie:); scanf(%d%d,&a.maze_

13、x,&a.maze_y); for(i=1;i=a.maze_x;i+) printf(shu ru di %d hang:,i); for(j=1;jvex_x&y=p-vex_y) return 1; p=p-next; return 0;int k=1;int print(Point *p) int i=0,top=0; Point *stackmaxsize; if(p=NULL) printf(bu neng dao da!n);return 0; else printf(shu chu di %d tiao mi gong lu jing(san yuan zu):n,k+); w

14、hile(p!=NULL) stacktop+=p;if(top=1)stacktop-1-direction=0; p=p-next; while(top0) top-; printf(%d,%d,%d),stacktop-vex_x,stacktop-vex_y,stacktop-direction); i+; if(i%8=0)printf(n); printf(n); return 1;void printmazepath(Point *p,maze road) int i,j; char mmaxsizemaxsize; printf(mi gong lu jing tu shi :

15、n); for(i=1;i=road.maze_x;i+) for(j=1;jdirection) case 0:mp-vex_xp-vex_y=1;break; case 1:mp-vex_xp-vex_y=26;break; case 2:mp-vex_xp-vex_y=25;break; case 3:mp-vex_xp-vex_y=27;break; case 4:mp-vex_xp-vex_y=24;break; p=p-next; for(i=1;i=road.maze_x;i+) for(j=1;j=road.maze_y;j+) printf(%c,mij); if(jvex_

16、x;y=p-vex_y; switch(j) case 1: if(y+1vex_x=x;q-vex_y=y+1;q-next=p; p-direction=j; if(q-vex_x=a.maze_x&q-vex_y=a.maze_y) if(print(q)printmazepath(q,a);sign=1; else for(i=1;i=4;i+) mazepath(q,i); break; case 2: if(x+1vex_x=x+1;q-vex_y=y;q-next=p; p-direction=j; if(q-vex_x=a.maze_x&q-vex_y=a.maze_y) if

17、(print(q)printmazepath(q,a);sign=1; else for(i=1;i=1&!found(x,y-1,p)&!a.Mazexy-1) q=(Point*)malloc(sizeof(Point); q-vex_x=x;q-vex_y=y-1;q-next=p; p-direction=j; if(q-vex_x=a.maze_x&q-vex_y=a.maze_y) if(print(q)printmazepath(q,a);sign=1; else for(i=1;i=1&!found(x-1,y,p)&!a.Mazex-1y) q=(Point*)malloc(

18、sizeof(Point); q-vex_x=x-1;q-vex_y=y;q-next=p; p-direction=j; if(q-vex_x=a.maze_x&q-vex_y=a.maze_y) if(print(q)printmazepath(q,a);sign=1; else for(i=1;ivex_x=1;p-vex_y=1;p-next=NULL; printf(n di gui qiu de mi gong mei you ke neng de lu xiann); for(i=1;i=4;i+) mazepath(p,i); if(sign=0) printf(bu neng

19、 dao da chu koun); getch(); 6.运行与测试非递归：首先输入行数和列数，然后按行输入迷宫信息我输入的是：行数6，列数8:；迷宫信息为：0 1 1 1 0 1 1 1；0 0 0 0 1 1 1 1；0 1 0 0 0 0 0 1；0 1 1 1 0 0 1 1；1 0 0 1 1 0 0 0；0 1 1 0 0 1 1 0； 运行结果为：、 递归：首先输入行数和列数，然后按行输入迷宫信息我输入的是：输入6行8列的迷宫信息：0 1 1 1 0 1 1 1；0 0 0 0 1 1 1 1；0 1 0 0 0 0 0 1；0 1 1 1 0 0 1 1；1 0 0 1 1 0 0 0；0 1 1 0 0 1 1 0； 运行结果为： 当输入的迷宫信息不能找到合适的出路时，则显示为：