【最新编排】迷宫求解C语言版(数据结构书上的算法).doc

/*求迷宫中从入口到出口地所有路径是个经典地程序设计问题！.为了保证在任何位置上都能沿原路返回，显然需要用个后进先出地结构来保存从入口到当前位置地路径!SqStack堆栈可以描述。.从入口到出口，要选择个初始方向，每个通道快包含个位置属性和个方向属性，此方向属性代表下个通道块在当前通道块上地方向。如果需要统计入口到出口地步数，在通道块结构里可以加个步数属性！SElemType和PosType结构可以描述。3.如何描述迷宫？迷宫中通道快用字符表示，墙面用字符#表示。如此来，其实本质上，迷宫就是个二维字符数组。可以用MazeType结构描述！4.main函数包含3个内容，首先生成个迷宫（InitMaze），然后打印此迷宫（PrintMaze），再就是迷宫求解地核心算法（MazePath），最后打印求解之后地迷宫。5.核心算法地中心思想，严蔚敏地数据结构书上第50页5页5页有详细描述。6.以下程序包括头文件和主文件。全部在VC6.0下调试通过。注意这个是C语言版本。 by sunrubben 00.9.8 */头文件/#include#include#include#define TRUE #define FALSE 0#define OVERFLOW 0#define OK #define ERROR 0#define STACK_INIT_SIZE 300/存储空间初始化分配量#define STACK_INCREMENT 0/存储空间分配增量#define MAXLEN 0typedef int Status;typedef struct int r; int c;PosType;typedef struct int ord; PosType seat; int di; SElemType;typedef struct SElemType *base; SElemType *top;/栈底指针 int stacksize;SqStack;/函数声明typedef struct int r; int c; char adr【MAXLEN】【MAXLEN】;MazeType;/迷宫类型Status InitStack(SqStack *S);/初始化Status Push(SqStack *S,SElemType e);/向栈底插入元素Status Pop(SqStack *S);/出栈Status StackEmpty(SqStack *S);Status InitMaze(MazeType *maze);/初始化迷宫Status Pass(MazeType *maze,PosType curpos);/判断当前位置可否通过Status FootPrint(MazeType *maze,PosType curpos);/走过地地方留下足迹PosType NextPos(PosType curpos,int i);/探索下位置并返回下位置地坐标Status MarkPrint(MazeType *maze,PosType curpos);/曾走过但不通留下标记并返回OKStatus MazePath(MazeType *maze,PosType start,PosType end);/迷宫maze存在从入口start到end地通道则求得条存放在栈中void PrintMaze(MazeType *maze);/输出迷宫/主文件/#include #include Maze.hStatus InitStack(SqStack *S) S-base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S-base) exit(OVERFLOW); S-top=S-base; S-stacksize=STACK_INIT_SIZE; return OK;Status Push(SqStack *S,SElemType e) if(S-top-S-base=S-stacksize) S-base=(SElemType*)realloc(S-base,(STACK_INIT_SIZE+STACK_INCREMENT)*sizeof(SElemType); if(!S-base) exit(OVERFLOW); S-top=S-base+S-stacksize; S-stacksize+=STACK_INCREMENT; *S-top+=e; return OK;Status Pop(SqStack *S)SElemType e;if(S-top=S-base) return ERROR;e=*-S-top;return OK;Status StackEmpty(SqStack *S) if(S-top=S-base) return TRUE; else return FALSE;Status InitMaze(MazeType *maze) int i,j; maze-r=8;maze-c=8; /迷宫行和列数 for(i=0;iadr【0】【i】=#; maze-adr【9】【i】=#; for(i=0;iadr【i】【0】=#; maze-adr【i】【9】=#; for(i=;i9;i+) for(j=;jadr【i】【j】=;/初始化迷宫 /设定通道块上地不通地路块 maze-adr【】【3】=#;maze-adr【】【7】=#;maze-adr【】【3】=#;maze-adr【】【7】=#;maze-adr【3】【5】=#;maze-adr【3】【6】=#; maze-adr【4】【】=#;maze-adr【4】【3】=#;maze-adr【4】【4】=#;maze-adr【5】【4】=#;maze-adr【6】【】=#;maze-adr【6】【6】=#; maze-adr【7】【】=#;maze-adr【7】【3】=#;maze-adr【7】【4】=#;maze-adr【7】【6】=#;maze-adr【7】【7】=#;maze-adr【8】【】=#; return OK;Status Pass(MazeType *maze,PosType curpos) if(maze-adr【curpos.r】【curpos.c】=)/可通 return TRUE; else return FALSE;Status FootPrint(MazeType *maze,PosType curpos) maze-adr【curpos.r】【curpos.c】=*;/*表示可通 return OK;PosType NextPos(PosType curpos,int i) PosType cpos; cpos=curpos; switch(i) /.3.4分别表示东,南,西,北方向 case : cpos.c+=; break; case : cpos.r+=; break; case 3 : cpos.c-=; break; case 4 : cpos.r-=; break; default: exit(ERROR); return cpos;Status MarkPrint(MazeType *maze,PosType curpos) maze-adr【curpos.r】【curpos.c】=;/表示曾走过但不通 return OK;Status MazePath(MazeType *maze,PosType start,PosType end) SqStack S; PosType curpos; int curstep;/当前序号 SElemType e; InitStack(&S); curpos=start; /设置当前位置为入口位置 curstep=; /探索第步 do if(Pass(&*maze,curpos) /当前位置可以通过, FootPrint(&*maze,curpos);/留下足迹 e.ord=curstep; e.seat=curpos; e.di=; Push(&S,e); /加入路径 if(curpos.r=end.r& curpos.c=end.c) return TRUE; /到达出口 curpos=NextPos(curpos,); /下位置是当前位置地东邻 curstep+; /探索下步 else /当前位置不通 if(!StackEmpty(&S) Pop(&S); while(e.di=4 & !StackEmpty(&S) MarkPrint(&*maze,e.seat); /留下不能通过地标记,并退步 Pop(&S); /注意pop操作指针地位置！这是关键！ e.di=S.top-di; e.seat=S.top-seat; e.ord=S.top-ord; /while if(e.di 4) e.di+;/换下个方向探索 Push(&S,e); curpos=NextPos(e.seat,e.di);/设定当前位置是该新方向上地相邻 while(!StackEmpty(&S); return OK;void PrintMaze(MazeType *maze) int i,j; printf(用心形代表迷宫地从入口到出口地条路径n); printf(用#代表墙和不通地地方用代表曾走过地通道块但不通n); printf(用笑脸代表可以通过地通道块n); printf( ); for(i=0;i0;i+)/打印列数名 printf(%4d,i); printf(nn); for(i=0;i0;i+) printf(%d,i);/打印行名 for(j=0;jadr【i】【j】);/输出迷宫/当前位置地标记 printf(nn); void main() /主函数 MazeType maze; PosType start,end; InitMaze(&maze);/初始化并创建迷宫 start.r=;start.c=;/迷宫入口坐标 end.c=8;end.r=8; /迷宫出口坐标 PrintMaze(&maze); MazePath(&maze,start,end); PrintMaze(&maze);/打印路径*/ /*求迷宫中从入口到出口地所有路径是个经典地程序设计问题！.为了保证在任何位置上都能沿原路返回，显然需要用个后进先出地结构来保存从入口到当前位置地路径!SqStack堆栈可以描述。.从入口到出口，要选择个初始方向，每个通道快包含个位置属性和个方向属性，此方向属性代表下个通道块在当前通道块上地方向。如果需要统计入口到出口地步数，在通道块结构里可以加个步数属性！SElemType和PosType结构可以描述。3.如何描述迷宫？迷宫中通道快用字符表示，墙面用字符#表示。如此来，其实本质上，迷宫就是个二维字符数组。可以用MazeType结构描述！4.main函数包含3个内容，首先生成个迷宫（InitMaze），然后打印此迷宫（PrintMaze），再就是迷宫求解地核心算法（MazePath），最后打印求解之后地迷宫。5.核心算法地中心思想，严蔚敏地数据结构书上第50页5页5页有详细描述。6.以下程序包括头文件和主文件。全部在VC6.0下调试通过。注意这个是C语言版本。 by sunrubben 00.9.8 */头文件/#include#include#include#define TRUE #define FALSE 0#define OVERFLOW 0#define OK #define ERROR 0#define STACK_INIT_SIZE 300/存储空间初始化分配量#define STACK_INCREMENT 0/存储空间分配增量#define MAXLEN 0typedef int Status;typedef struct int r; int c;PosType;typedef struct int ord; PosType seat; int di; SElemType;typedef struct SElemType *base; SElemType *top;/栈底指针 int stacksize;SqStack;/函数声明typedef struct int r; int c; char adr【MAXLEN】【MAXLEN】;MazeType;/迷宫类型Status InitStack(SqStack *S);/初始化Status Push(SqStack *S,SElemType e);/向栈底插入元素Status Pop(SqStack *S);/出栈Status StackEmpty(SqStack *S);Status InitMaze(MazeType *maze);/初始化迷宫Status Pass(MazeType *maze,PosType curpos);/判断当前位置可否通过Status FootPrint(MazeType *maze,PosType curpos);/走过地地方留下足迹PosType NextPos(PosType curpos,int i);/探索下位置并返回下位置地坐标Status MarkPrint(MazeType *maze,PosType curpos);/曾走过但不通留下标记并返回OKStatus MazePath(MazeType *maze,PosType start,PosType end);/迷宫maze存在从入口start到end地通道则求得条存放在栈中void PrintMaze(MazeType *maze);/输出迷宫/主文件/#include #include Maze.hStatus InitStack(SqStack *S) S-base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S-base) exit(OVERFLOW); S-top=S-base; S-stacksize=STACK_INIT_SIZE; return OK;Status Push(SqStack *S,SElemType e) if(S-top-S-base=S-stacksize) S-base=(SElemType*)realloc(S-base,(STACK_INIT_SIZE+STACK_INCREMENT)*sizeof(SElemType); if(!S-base) exit(OVERFLOW); S-top=S-base+S-stacksize; S-stacksize+=STACK_INCREMENT; *S-top+=e; return OK;Status Pop(SqStack *S)SElemType e;if(S-top=S-base) return ERROR;e=*-S-top;return OK;Status StackEmpty(SqStack *S) if(S-top=S-base) return TRUE; else return FALSE;Status InitMaze(MazeType *maze) int i,j; maze-r=8;maze-c=8; /迷宫行和列数 for(i=0;iadr【0】【i】=#; maze-adr【9】【i】=#; for(i=0;iadr【i】【0】=#; maze-adr【i】【9】=#; for(i=;i9;i+) for(j=;jadr【i】【j】=;/初始化迷宫 /设定通道块上地不通地路块 maze-adr【】【3】=#;maze-adr【】【7】=#;maze-adr【】【3】=#;maze-adr【】【7】=#;maze-adr【3】【5】=#;maze-adr【3】【6】=#; maze-adr【4】【】=#;maze-adr【4】【3】=#;maze-adr【4】【4】=#;maze-adr【5】【4】=#;maze-adr【6】【】=#;maze-adr【6】【6】=#; maze-adr【7】【】=#;maze-adr【7】【3】=#;maze-adr【7】【4】=#;maze-adr【7】【6】=#;maze-adr【7】【7】=#;maze-adr【8】【】=#; return OK;Status Pass(MazeType *maze,PosType curpos) if(maze-adr【curpos.r】【curpos.c】=)/可通 return TRUE; else return FALSE;Status FootPrint(MazeType *maze,PosType curpos) maze-adr【curpos.r】【curpos.c】=*;/*表示可通 return OK;PosType NextPos(PosType curpos,int i) PosType cpos; cpos=curpos; switch(i) /.3.4分别表示东,南,西,北方向 case : cpos.c+=; break; case : cpos.r+=; break; case 3 : cpos.c-=; break; case 4 : cpos.r-=; break; default: exit(ERROR); return cpos;Status MarkPrint(MazeType *maze,PosType curpos) maze-adr【curpos.r】【curpos.c】=;/表示曾走过但不通 return OK;Status MazePath(MazeType *maze,PosType start,PosType end) SqStack S; PosType curpos; int curstep;/当前序号 SElemType e; InitStack(&S); curpos=start; /设置当前位置为入口位置 curstep=; /探索第步 do if(Pass(&*maze,curpos) /当前位置可以通过, FootPrint(&*maze,curpos);/留下足迹 e.ord=curstep; e.seat=curpos; e.di=; Push(&S,e); /加入路径 if(curpos.r=end.r& curpos.c=end.