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

课程设计报告数据结构课程设计报告设计题目：迷宫 年 级 计科09级 班 级 092 ，093 姓 名 学 号 指导教师 起止时间 2011.12.9 2011 年 第2 学期 五C语言源代码#include#include#includeint m,n;int *maze = NULL;struct Element int i;int j;int di;typedef struct LinkStack struct Element element;struct LinkStack * next;struct LinkStack * prior;LinkStack;LinkStack *top = NULL;LinkStack *head = NULL;int count=0; int mgpath(int xi,int yi,int xe,int ye);void printMaze(int * maze)int i,j;printf(您的迷宫图如下所示:n); for(i=0; im+2; i+)for(j=0; jn+2; j+)printf(%4d,mazeij);printf(n);printf(n*n);void addWall(int * maze)int i,j;for(i=0; im+2; i+) for(j=0; j0 & i(m+2-1) mazei0=1;mazein+2-1=1;break;if(i=m+2-1) mazeij=1; int * initMaze() int i,j;int flag = 0;printf(请输入迷宫的行数 m=); scanf(%d,&m); printf(请输入迷宫的列数 n=); scanf(%d,&n); maze = (int *)malloc(sizeof(int *) * (m+2); printf(n*n);for(i=0; in+2; i+) *(maze+i) = (int *)malloc(sizeof(int)*(n+2); addWall(maze);/给迷宫加墙 printf(n请输入迷宫的各行各列(注意:最后一个数需要是0):n用空格隔开,0代表路,1代表墙nn);for(i=1;i=m;i+) for(j=1;jelement.di; LinkStack *node= (LinkStack *) malloc(sizeof(LinkStack); node-element.di = di;if(top = NULL)head = (LinkStack *) malloc(sizeof(LinkStack);head-element.i = 1;head-element.j = 0;head-element.di = 1;head-prior = NULL;top = head;node-element.i = 1;node-element.j = 1;node-element.di = -1;top-next = node;node-next = NULL;node-prior = top; top = node; di = top-element.di;while(diprior-element.i - 1;j = top-prior-element.j;break;case 1:i = top-prior-element.i;j = top-prior-element.j + 1;break;case 2:i = top-prior-element.i + 1;j = top-prior-element.j;break; case 3: i = top-prior-element.i;j = top-prior-element.j - 1;break; if(mazeij = 0)find = 1; if(i = m & j = n) top-element.i = m;top-element.j = n;top-prior-element.di = di;printf(%4d:,+count);LinkStack * n = head-next;while(n != NULL) printf(%d,%d,%d ) ,n-element.i,n-element.j,n-element.di);printf( - );if(k + 1)%5 = 0) printf(nt);k+;n = n-next;printf(出口);printf(n);mazetop-element.itop-element.j = 0;top = top-prior; free(node);mazePath();elseif(find = 1)top-prior-element.di = di; top-element.i = i;top-element.j = j; top-element.di = -1;mazeij = -1;mazePath();elsemazetop-prior-element.itop-prior-element.j = 0; top = top-prior-prior; free(node);mazePath();int mgpath(int xi,int yi,int xe,int ye)printf(非递归通路：n);int i,j;int find;int di;LinkStack *node= (LinkStack *) malloc(sizeof(LinkStack); head = (LinkStack *) malloc(sizeof(LinkStack);head-element.i = 1;head-element.j = 0;head-element.di = 1;head-prior = NULL;top = head;node-element.i = xi; node-element.j = yi;node-element.di = -1;maze11=1; top-next = node;head-next=node;node-next = NULL;node-prior = top;di=node-element.di;top=node;LinkStack * n = head-next;while(top-prior!= NULL)find=0;di=top-element.di;while(dielement.i-1;j=top-element.j;break;case 1:i=top-element.i;j=top-element.j+1;break;case 2:i=top-element.i+1;j=top-element.j;break;case 3:i=top-element.i,j=top-element.j-1;break;default:if(mazeij=0)find=1;top-element.di=di;printf(find找到的点%d,%d,%d,i,j);if(find=1)if(i=xe&j=ye&mazeij=0) LinkStack *node1= (LinkStack *) malloc(sizeof(LinkStack); top-element.di=di;node1-element.i=i;node1-element.j=j;node1-element.di=-1;top-next=node1;node1-next=NULL;node1-prior=top;top=node1;mazeij=1;printf( );while(n!=NULL)printf(%d,%d,%d),n-element.i,n-element.j,n-element.di);printf( - );n=n-next;printf(出口);printf(n);return(0);elseLinkStack *node1= (LinkStack *) malloc(sizeof(LinkStack);top-element.di=di;node1-element.i=i;node1-element.j=j;node1-element.di=-1;top-next=node1;node1-next=NULL;node1-prior=top;top=node1;mazeij=1;printf(找到的节点有%d,%d,%d,node1-element.i,node1-element.j,node1-element.di);elsemazetop-element.itop-element.j=0;top = top-prior;free(top-next);return(0); int main()int i;initMaze();mazePath();if(count=0)printf(*);printf(n该迷宫没有通路n);return 0; printf(n*n);mgpath(1,1,m,n);if(head != NULL) free(head);return 0;六测试分析（运行结果） 迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。输入数据：0 1 0 10 0 0 10 0 0 00 0