數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--迷宮問題-資料下載頁
2025-01-18 06:40本頁面
【正文】 IT_SIZE*sizeof(SElemType))。 if( !(*S).base ) exit(0)。 (*S).top = (*S).base。 // 棧底與棧頂相同表示一個(gè)空棧 (*S).stacksize = STACK_INIT_SIZE。 return 1。}// 若棧S為空棧（棧頂與棧底相同的），則返回1，否則返回0。int StackEmpty(SqStack S){ if( == ) return 1。 else return 0。}// 插入元素e為新的棧頂元素。int Push(SqStack *S, SElemType e){ if((*S).top (*S).base = (*S).stacksize) // 棧滿，追加存儲空間 { (*S).base = (SElemType *)realloc((*S).base , ((*S).stacksize + STACKINCREMENT) * sizeof(SElemType))。 if( !(*S).base ) exit(0)。 (*S).top = (*S).base+(*S).stacksize。 (*S).stacksize += STACKINCREMENT。 } *((*S).top)++=e。 // 這個(gè)等式的++ * 優(yōu)先級相同，但是它們的運(yùn)算方式，是自右向左 return 1。}// 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1；否則返回0。int Pop(SqStack *S,SElemType *e){ if((*S).top == (*S).base) return 0。 *e = *(*S).top。 // 這個(gè)等式的++ * 優(yōu)先級相同，但是它們的運(yùn)算方式，是自右向左 return 1。}// 定義墻元素值為0,可通過路徑為1,不能通過路徑為1,通過路徑為足跡 // 當(dāng)迷宮m的b點(diǎn)的序號為1(可通過路徑)，return 1。 否則，return 0。int Pass(PosType b){ if(m[][]==1) return 1。 else return 0。}// 使迷宮m的a點(diǎn)的序號變?yōu)樽阚E(curstep)，表示經(jīng)過 void FootPrint(PosType a){ m[][]=curstep。}// 根據(jù)當(dāng)前位置及移動(dòng)方向，返回下一位置 PosType NextPos(PosType c,int di){ PosType direc[4]={{0,1},{1,0},{0,1},{1,0}}。 // {行增量,列增量} // 移動(dòng)方向,依次為東南西北 +=direc[di].x。 +=direc[di].y。 return c。}// 使迷宮m的b點(diǎn)的序號變?yōu)?(不能通過的路徑)void MarkPrint(PosType b){ m[][]=1。}// P51// 若迷宮maze中存在從入口start到出口end的通道，則求得一條 // 存放在棧中(從棧底到棧頂)，并返回1；否則返回0 int MazePath(PosType start,PosType end) { SqStack S。 PosType curpos。 SElemType e。 InitStack(amp。S)。 curpos=start。 do { if(Pass(curpos)) { // 當(dāng)前位置可以通過，即是未曾走到過的通道塊 FootPrint(curpos)。 // 留下足跡 =curstep。 =。 =。 =0。 Push(amp。S,e)。 // 入棧當(dāng)前位置及狀態(tài) curstep++。 // 足跡加1 if(==amp。amp。==) // 到達(dá)終點(diǎn)(出口) return 1。 curpos=NextPos(curpos,)。 } else { // 當(dāng)前位置不能通過 if(!StackEmpty(S)) { Pop(amp。S,amp。e)。 // 退棧到前一位置 curstep。 // 前一位置處于最后一個(gè)方向(北) while(==3amp。amp。!StackEmpty(S)) { MarkPrint()。 // 留下不能通過的標(biāo)記(1) Pop(amp。S,amp。e)。 // 退回一步 curstep。 } if(3) // 沒到最后一個(gè)方向(北) { ++。 // 換下一個(gè)方向探索 Push(amp。S,e)。 curstep++。 // 設(shè)定當(dāng)前位置是該新方向上的相鄰塊 curpos=NextPos(,)。 } } } }while(!StackEmpty(S))。 return 0。}// 輸出迷宮的結(jié)構(gòu) void Print(int x,int y){ int i,j。 for(i=0。ix。i++) { for(j=0。jy。j++) printf(%3d,m[i][j])。 printf(\n)。 } }int main(){ PosType begin,end。 int i,j,x,y,x1,y1。 printf(請輸入迷宮的行數(shù),列數(shù)(包括外墻)：(空格隔開))。 scanf(%d%d, amp。x, amp。y)。 for(i=0。ix。i++) // 定義周邊值為0(同墻) { m[0][i]=0。 // 迷宮上面行的周邊即上邊墻 m[x1][i]=0。// 迷宮下面行的周邊即下邊墻 } for(j=1。jy1。j++) { m[j][0]=0。 // 迷宮左邊列的周邊即左邊墻 m[j][y1]=0。// 迷宮右邊列的周邊即右邊墻 } for(i=1。ix1。i++) for(j=1。jy1。j++) m[i][j]=1。 // 定義通道初值為1 printf(請輸入迷宮內(nèi)墻單元數(shù)：)。 scanf(%d,amp。j)。 printf(請依次輸入迷宮內(nèi)墻每個(gè)單元的行數(shù),列數(shù)：(空格隔開)\n)。 for(i=1。i=j。i++) { scanf(%d%d,amp。x1,amp。y1)。 m[x1][y1]=0。 // 定義墻的值為0 } printf(迷宮結(jié)構(gòu)如下:\n)。 Print(x,y)。 printf(請輸入起點(diǎn)的行數(shù),列數(shù)：（空格隔開）)。 scanf(%d%d,amp。,amp。)。 printf(請輸入終點(diǎn)的行數(shù),列數(shù)：（空格隔開）)。 scanf(%d%d,amp。,amp。)。 if(MazePath(begin,end)) // 求得一條通路 { printf(此迷宮從入口到出口的一條路徑如下:\n)。 Print(x,y)。 // 輸出此通路 } else printf(此迷宮沒有從入口到出口的路徑\n)。 system(pause)。 return 0。}30
試題試卷相關(guān)推薦
鄂ICP備17016276號-1