数据结构迷宫源代码.doc

《数据结构迷宫源代码.doc》由会员分享，可在线阅读，更多相关《数据结构迷宫源代码.doc（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date数据结构迷宫源代码数据结构迷宫源代码#include #include #include #include #include #define OK 1#define ERROR 0#define NULL 0#define OVERFLOW -2 #define STACK_INIT_SIZE 100#define STACKINCREMENT 10/栈的顺序存储表示

2、typedef struct int x;/*列*/ int y;/*行*/PosType;/坐标位置类型typedef struct int ord;/通道块在路径上的序号 PosType seat;/通道块在迷宫中的坐标位置 int di;/从此通道块走向下一通道块的方向SElemType;/栈的元素类型typedef struct SElemType *base;SElemType *top;int stacksize; /当前已分配的存储空间，以元素为单位SqStack;/基本操作int InitStack(SqStack *S) S-base=(SElemType *)malloc(

3、STACK_INIT_SIZE * sizeof(SElemType); if(!S-base) 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-

4、S-base=S-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(SqStack *S,SElemType *e) if(S

5、-top=S-base) return ERROR; *e=*-S-top; return OK;int StackEmpty(SqStack *S) return(S-top=S-base) ;/迷宫程序typedef struct int lie;/*列数*/ int hang;/*行数*/ char a999999;MazeType;/*迷宫类型*/*随机生成迷宫*/int generatemaze( MazeType *maze)int i,j;maze-a00=2; maze-a+maze-hang+maze-lie=3;/*设置外墙*/maze-a0maze-lie=!;maze-

6、amaze-hang0=!;for(j=1;jlie;j+) maze-a0j=!;maze-amaze-hangj=!;for(i=1;ihang;i+) maze-ai0=!;maze-aimaze-lie=!;srand(unsigned)time( NULL );rand(); for(i=1; i hang; i+) for(j=1;jlie;j+) if (rand()=RAND_MAX/4) maze-aij = ; / 暗示出路 else maze-aij =!; /!暗示无出路 return OK;int Pass(MazeType *maze, PosType curpos

7、 )/判断当前位置可否通过if (curpos.x = maze-lie) return ERROR;if (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(MazeType *maze,PosType curpos)/留下不能通过的标记 maze-acurp

8、os.ycurpos.x=; return OK;PosType NextPos(PosType curpos,int di)/返回当前位置的下一位置 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;/若迷宫有解，则求得一条存放在栈中（从栈底到栈顶），并返回OK，否则返回ERRORint MazePath(MazeType *maze,PosType s

9、tart,PosType end) PosType curpos; SqStack *S=(SqStack *)malloc(sizeof(SqStack); InitStack(S); SElemType *e; e=(SElemType *)malloc(sizeof(SElemType); curpos=start;/设定当前位置为入口位置 int curstep = 1;/探索第一步 do if(Pass(maze,curpos)/当前位置可通过 FootPrint(maze,curpos); e-ord=curstep; e-seat=curpos; e-di=1; Push(S,e

10、); 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-didi+;Push(S,e); curpos=e-seat; curpos=NextPos(curpos,e-di); while(!StackEmpty(S);return ERROR;void P

11、rintMaze(MazeType *maze)/打印迷宫 int i,j,k,n; int c999,d999; for(i=0,k=0;ihang;i+)for(j=0;jlie;j+)printf(%c ,maze-aij);if(maze-aij=*)ck=i;dk=j;k+; printf(n); n=k; for(k=0;kn;k+) printf(,ck,dk); printf(n); printf(n);int main() int zmg; char ch; printf( 数据结构课程设计-迷宫问题求解 nn); printf( |-|n); printf( | |n);

12、printf( | |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); /设置迷宫的长宽不含外墙 printf(请输入迷宫的列数（不含外墙时）:); scanf(%d,&maze-lie); printf(请输入迷宫的行数（不含外墙时）:); sc

13、anf(%d,&maze-hang); generatemaze(maze); printf(随机创建迷宫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=MazePath(maze,start,end); if(zmg) printf(此迷宫通路为n); PrintMaze(maze); else printf(此迷宫无通路n); /getchar(); printf(再次尝试？（Y/N）?); scanf(%c,&ch); while(ch=Y|ch=y); return 0;-