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

数据结构课程设计报告题目：迷宫问题姓名：学号：班级：指导教师： 2012年6月6日1. 问题描述输入任意大小的迷宫数据，用递归和非递归方法求出一条走出迷宫的路径，并将路径输出。2. 设计思路 以 0和1分别表示迷宫中的通路和障碍，没有通路则不显示。未显示为得出没有通路的结论；走迷宫的方式是一个一个的线路去试 如果是死路的话就退回去，类似数据结构中栈的先进后出，所以可以用栈这种结构表示迷宫，通过不断的试验当试出最后的路线时输出栈即可，由于它是不断循环的实验，所以可以采用链栈实现迷宫的求解。同时因为迷宫需要不断重复的试验，可以看成反复的调用“迷宫“这个函数，这是典型的递归问题，所以也可以使用递归解决问题。另外由于数据对象是迷宫所以可以用0和1构建不同类型的迷宫更符合实际也更有乐趣。3. 数据结构设计前面提到要用到链栈和递归两种方式操作；为了更好的以链表作存储结构的栈，可以用二维数组存储迷宫信息，同时通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。这样是路径更加明显，具体的数据结构为： #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;/下一个结点的方向 struct point *next;/指向下一个结点point;递归法像一位手握大权的领导。当他站在迷宫入口处时，他才懒得亲自去走，这时这位领导会吩咐他的手下，让他们分别向着迷宫的各个方向去探索；当遇到岔路口时留一个人守在这里，再分出几股人，朝着每个方向继续探索；最后总会有一个人发现出口。发现出口的这个人将出口的位置报告给离他最近的路口处留守的人，再由这个人报告给上一个路口的人，依次层层上报，最后消息传到了领导那里，于是这位领导就顺着这条画好的通路大摇大摆地通过了迷宫。所以具体的数据结构为：#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.功能函数设计一个用于存放迷宫信息的二维数组maze相关操作：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; 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(point); 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; 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_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),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(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; 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(jroad.maze_y)printf( ); else printf(n); void main() maze road; point *p; road=creat(); p=secret(road); if(print(p)printmazepath(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_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+); while(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 :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_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(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(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 dao da chu koun); getch(); 6.运行与测试非递归：首先输入行数和列数，然后按行输入迷宫信息我输入的是：行数6，列