数据结构课程设计迷宫

1、课程设计报告数据结构课程设计报告设计题目：迷宫 年 级 计科09级 班 级 092 ，093 姓 名 学 号 指导教师 起止时间 2011.12.9 2011 年 第2 学期 五C语言源代码#include<malloc.h>#include<stdlib.h>#include<stdio.h>int m,n;int *maze = NULL;struct Element int i;int j;int di;typedef struct LinkStack struct Element element;struct LinkStack * next;str

2、uct 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; i<m+2; i+)for(j=0; j<n+2; j+)printf("%4d",mazeij);printf("n");printf

3、("n*n");void addWall(int * maze)int i,j;for(i=0; i<m+2; i+) for(j=0; j<n+2; j+) if(i=0)mazeij = 1;if(i>0 && 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); p

4、rintf("请输入迷宫的列数 n="); scanf("%d",&n); maze = (int *)malloc(sizeof(int *) * (m+2); printf("n*n");for(i=0; i<n+2; i+) *(maze+i) = (int *)malloc(sizeof(int)*(n+2); addWall(maze);/给迷宫加墙 printf("n请输入迷宫的各行各列(注意:最后一个数需要是0):n用空格隔开,0代表路,1代表墙nn");for(i=1;i<=m;

5、i+) for(j=1;j<=n;j+) scanf("%d",&mazeij); printf("n*n");printMaze(maze); return maze;void mazePath() if(top = head && head != NULL) return;while(top != head |head = NULL)int k = 0;int find = 0;int i = 0,j=0;int di = -1;if(top != NULL)di=top->element.di; LinkStac

6、k *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.

7、di = -1;top->next = node;node->next = NULL;node->prior = top; top = node; di = top->element.di;while(di<4 && find = 0) di+;switch(di) case 0:i = top->prior->element.i - 1;j = top->prior->element.j;break;case 1:i = top->prior->element.i;j = top->prior->e

8、lement.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->ele

9、ment.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&qu

10、ot;);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

11、; 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-

12、>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!=

13、 NULL)find=0;di=top->element.di;while(di<4&&find=0)di+;switch(di)case 0:i=top->element.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;d

14、efault: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

15、=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=

16、(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;六测试分析（运行结果）