数据结构严蔚敏C语言版 迷宫

#include <stdio.h> #include <stdlib.h> #include "seqStack.h" typedef char mazeType[10][10]; //mazeType maze; //mazeType maze={/* 0 1 2 3 4 5 6 7 8 9*/ // /*0*/ {'1','1','1','1','1','1','1','1','1','1'}, // /*1*/ {'1','0','0','1','0','0','0','1','0','1'}, // /*2*/ {'1','0','0','1','0','0','0','1','0','1'}, // /*3*/ {'1','0','0','0','0','1','1','0','0','1'}, // /*4*/ {'1','0','1','1','1','0','0','0','0','1'}, // /*5*/ {'1','0','0','0','1','0','0','0','0','1'}, // /*6*/ {'1','0','1','0','0','0','1','0','0','1'}, // /*7*/ {'1','0','1','1','1','0','1','1','0','1'}, // /*8*/ {'1','1','0','0','0','0','0','0','0','1'}, // /*9*/ {'1','1','1','1','1','1','1','1','1','1'} // }; //mazeType maze; mazeType maze={/* 0 1 2 3 4 5 6 7 8 9*/ /*0*/ {'1','1','1','1','1','1','1','1','1','1'}, /*1*/ {'1','0','0','1','0','0','0','1','0','1'}, /*2*/ {'1','0','1','1','0','0','0','1','0','1'}, //(2,2)=1 /*3*/ {'1','0','0','1','0','1','1','0','0','1'}, //(3,3)=1 /*4*/ {'1','0','1','1','1','0','0','0','0','1'}, /*5*/ {'1','0','0','0','1','0','0','0','0','1'}, /*6*/ {'1','0','1','0','0','0','0','0','0','1'}, //(6,6)=0 /*7*/ {'1','0','1','1','1','0','1','1','0','1'}, /*8*/ {'1','1','0','0','0','0','0','0','0','1'}, /*9*/ {'1','1','1','1','1','1','1','1','1','1'} }; //current position is accessed or not status pass(posType curPos) { int x = curPos.xPos; int y = curPos.yPos; if(maze[x][y] == '0') { return TRUE; } else //if(maze[x][y] == '1') { return FALSE; } } //print the current position accessed footprint status footPrint(posType curPos) { int x = curPos.xPos; int y = curPos.yPos; maze[x][y] = '@'; return OK; } //next position posType nextPos(posType curPos, int dir) { switch(dir) { case 1: //turn right curPos.xPos = curPos.xPos; curPos.yPos = curPos.yPos + 1; break; case 2: //turn down curPos.xPos = curPos.xPos + 1; curPos.yPos = curPos.yPos; break; case 3: //turn left curPos.xPos = curPos.xPos; curPos.yPos = curPos.yPos - 1; break; case 4: //turn up curPos.xPos = curPos.xPos - 1; curPos.yPos = curPos.yPos; default: //printf("error in nextPos\n"); break; } return curPos; } //mark the unused position status markPrint(posType seat) { int x = seat.xPos; int y = seat.yPos; maze[x][y] = '#'; return OK; } //maze path algorithm status mazePath(seqStack *S, posType start, posType end) { posType curPos; //current positon int curStep; //the ordinary number sElemType e; curPos = start; curStep = 1; do { if(pass(curPos)) //the current position is "accessed" { footPrint(curPos); e.ord = curStep; e.seat = curPos; e.di = 1; push(S, e); if(curPos.xPos == end.xPos && curPos.yPos == end.yPos) { return OK; //arrive at the final } curPos = nextPos(curPos, 1); curStep++; }//end of if(pass(curPos)) else //the current position is not "accessed" { if(!stackEmpty(*S)) //the stack is not empty { pop(S,&e); while(e.di == 4 && !stackEmpty(*S)) { markPrint(e.seat); //the current position must be marked by '#' pop(S,&e); }//end while if(e.di < 4) { e.di++; push(S,e); curPos = nextPos(e.seat, e.di); } }//end of if(!stackEmpty(*S)) }//end of else }while(!stackEmpty(*S)); } status main() { printf("Output the orginal maze path:\n\n"); int i,j; for(i = 0; i < 10; i++) { printf(" "); for(j = 0; j < 10; j++) { printf("%c",maze[i][j]); } printf("\n"); } printf("\n\n"); //begin maze algorithm seqStack sqStac; initStack(&sqStac); posType start = {1,1}; posType end = {8,8}; mazePath(&sqStac, start, end); printf("Output the result maze path:\n\n"); for(i = 0; i < 10; i++) { printf(" "); for(j = 0; j < 10; j++) { printf("%c",maze[i][j]); } printf("\n"); } printf("\n\n"); printf("the path is:\n"); for(i = 1; i <= sqStac.stackSize; i++) { if(i % 3 != 0) { //printf("["); //printf(" %d, (",sqStac.base[i-1].ord); printf("( %d,%d )",sqStac.base[i-1].seat.xPos,sqStac.base[i-1].seat.yPos); printf(" "); } else { //printf("["); //printf(" %d, (",sqStac.base[i-1].ord); printf("( %d,%d )",sqStac.base[i-1].seat.xPos,sqStac.base[i-1].seat.yPos); printf("\n"); } } printf("\n\n"); return OK; }