數(shù)據(jù)結(jié)構(gòu)迷宮源代碼7頁

1、#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <string.h>#include <time.h>#define OK 1#define ERROR 0#define NULL 0#define OVERFLOW -2 #define STACK_INIT_SIZE 100#define STACKINCREMENT 10/棧的順序存儲表示typedef struct int x;/*列*/ int y;/*行*/PosType;/坐標(biāo)位置類型typ

2、edef struct int ord;/通道塊在路徑上的序號 PosType seat;/通道塊在迷宮中的坐標(biāo)位置 int di;/從此通道塊走向下一通道塊的方向SElemType;/棧的元素類型typedef struct SElemType *base;SElemType *top;int stacksize; /當(dāng)前已分配的存儲空間，以元素為單位SqStack;/基本操作int InitStack(SqStack *S) S->base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType); if(!S->base)

3、 exit(OVERFLOW); S->top=S->base; S->stacksize=STACK_INIT_SIZE; return OK;/若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERRORint GetTop(SqStack *S,SElemType *e) if(S->top=S->base) return ERROR; *e=*(S->top-1); return OK;int Push(SqStack *S,SElemType *e)/插入元素e作為新的棧頂元素 if(S->top-S->base>=S->

4、;stacksize)/*棧滿，追加存儲空間*/ S->base = (SElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT) * sizeof(SElemType); if(!S->base) exit(OVERFLOW);S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT; *S->top+=*e; return OK;/若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERRORint Pop(S

5、qStack *S,SElemType *e) if(S->top=S->base) return ERROR; *e=*-S->top; return OK;int StackEmpty(SqStack *S) return(S->top=S->base) ;/迷宮程序typedef struct int lie;/*列數(shù)*/ int hang;/*行數(shù)*/ char a999999;MazeType;/*迷宮類型*/*隨機生成迷宮*/int generatemaze( MazeType *maze)int i,j;maze->a00=2; maze-&g

6、t;a+maze->hang+maze->lie=3;/*設(shè)置外墻*/maze->a0maze->lie='!'maze->amaze->hang0='!'for(j=1;j<maze->lie;j+) maze->a0j='!'maze->amaze->hangj='!'for(i=1;i<maze->hang;i+) maze->ai0='!'maze->aimaze->lie='!'srand(un

7、signed)time( NULL );rand(); for(i=1; i <maze->hang; i+) for(j=1;j<maze->lie;j+) if (rand()>=RAND_MAX/4) maze->aij =' ' /' ' 暗示出路 else maze->aij ='!' /'!'暗示無出路 return OK;int Pass(MazeType *maze, PosType curpos )/判斷當(dāng)前位置可否通過if (curpos.x < 1) | (cu

8、rpos.x >= maze->lie) return ERROR;if (curpos.y < 1) | (curpos.y >= maze->hang) return ERROR;if (maze->acurpos.ycurpos.x=' ') return OK; else return ERROR;int FootPrint(MazeType *maze,PosType curpos)/留下足跡 maze->acurpos.ycurpos.x='*' return OK;int MarkPrint(MazeTyp

9、e *maze,PosType curpos)/留下不能通過的標(biāo)記 maze->acurpos.ycurpos.x='' return OK;PosType NextPos(PosType curpos,int di)/返回當(dāng)前位置的下一位置 PosType pos=curpos; switch(di) case 1:/右東 pos.x+; break; case 2:/下南 pos.y+; break; case 3:/左西 pos.x-; break; case 4:/上北 pos.y-; break; return pos;/若迷宮有解，則求得一條存放在棧中（從棧底

10、到棧頂），并返回OK，否則返回ERRORint MazePath(MazeType *maze,PosType start,PosType end) PosType curpos; SqStack *S=(SqStack *)malloc(sizeof(SqStack); InitStack(S); SElemType *e; e=(SElemType *)malloc(sizeof(SElemType); curpos=start;/設(shè)定當(dāng)前位置為入口位置 int curstep = 1;/探索第一步 do if(Pass(maze,curpos)/當(dāng)前位置可通過 FootPrint(maz

11、e,curpos); e->ord=curstep; e->seat=curpos; e->di=1; Push(S,e); if(curpos.x=end.x&&curpos.y=end.y) return (OK); curpos=NextPos(curpos,1); curstep+; else if(!StackEmpty(S) Pop(S,e); while(e->di=4&&!StackEmpty(S)/棧不空但棧頂位置四周均不通 MarkPrint(maze,e->seat);Pop(S,e); if(e->di

12、<4)/棧不空且棧頂位置四周有其他位置未探索 e->di+;Push(S,e); curpos=e->seat; curpos=NextPos(curpos,e->di); while(!StackEmpty(S);return ERROR;void PrintMaze(MazeType *maze)/打印迷宮 int i,j,k,n; int c999,d999; for(i=0,k=0;i<=maze->hang;i+)for(j=0;j<=maze->lie;j+)printf("%c ",maze->aij);i

13、f(maze->aij='*')ck=i;dk=j;k+; printf("n"); n=k; for(k=0;k<n;k+) printf("<%d,%d>",ck,dk); printf("n"); printf("n");int main() int zmg; char ch; printf(" 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-迷宮問題求解 nn"); printf(" |-|n"); printf(" | |n"); pr

14、intf(" | |n"); printf(" | |n"); printf(" | |n"); printf(" | XXXX XXXXXXXXXXXXXX |n"); printf(" | XXXXXXX |n"); printf(" |-|n"); getchar(); do system("cls"); fflush(stdin); MazeType *maze=(MazeType *)malloc(sizeof(MazeType); /設(shè)置迷宮的

15、長寬不含外墻 printf("請輸入迷宮的列數(shù)（不含外墻時）:"); scanf("%d",&maze->lie); printf("請輸入迷宮的行數(shù)（不含外墻時）:"); scanf("%d",&maze->hang); generatemaze(maze); printf("隨機創(chuàng)建迷宮n"); PrintMaze(maze); getchar(); getchar(); PosType start,end; start.x=1;start.y=1; end.x=maze->lie-1;end.y=maze->hang-1; zmg