數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告迷宮算法

參考文獻[1]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學出版社，2007.[2]胡圣榮,周靄如,羅穗萍.數(shù)據(jù)結(jié)構(gòu)教程與題解[M].北京：清華大學出版社，2011.[3]譚浩強.C程序設(shè)計[M].北京：清華大學出版社，2005.[4]袁平波.數(shù)據(jù)結(jié)構(gòu)實驗指導[M].合肥：中國科學技術(shù)大學出版社.2010.[5]殷人昆.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學出版社.2011.[6]寧正元.算法與數(shù)據(jù)結(jié)構(gòu)習題精解和實驗指導[M].北京.清華大學出版社.2007.[7]陳媛.算法與數(shù)據(jù)結(jié)構(gòu).第2版[M].北京.清華大學出版社.2011.附錄（關(guān)鍵部分程序清單）程序代碼#include<stdio.h>#include<stdlib.h>#include<string.h>#include<malloc.h>//迷宮坐標位置類型typedefstruct { intx; //行值 inty; //列值}PosType;#defineMAXLENGTH25//設(shè)迷宮的最大行列為25typedefintMazeType[MAXLENGTH][MAXLENGTH];//迷宮數(shù)組[行][列]typedefstruct//棧的元素類型{ intord;//通道塊在路徑上的＂序號＂ PosTypeseat;//通道塊在迷宮中的＂坐標位置＂ intdi;//從此通道塊走向下一通道塊的＂方向＂(0～3表示東～北)}SElemType;//全局變量MazeTypem;//迷宮數(shù)組intcurstep=1;//當前足跡,初值為1#defineSTACK_INIT_SIZE10 //存儲空間初始分配量#defineSTACKINCREMENT2 //存儲空間分配增量//棧的順序存儲表示typedefstructSqStack{ SElemType*base; //在棧構(gòu)造之前和銷毀之后，base的值為NULL SElemType*top; //棧頂指針 intstacksize; //當前已分配的存儲空間，以元素為單位}SqStack; //順序棧// 構(gòu)造一個空棧SintInitStack(SqStack*S){ //為棧底分配一個指定大小的存儲空間 (*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!(*S).base) exit(0); (*S).top=(*S).base; //棧底與棧頂相同表示一個空棧 (*S).stacksize=STACK_INIT_SIZE; return1;}//若棧S為空棧（棧頂與棧底相同的），則返回1，否則返回0。intStackEmpty(SqStackS){ if(S.top==S.base) return1; else return0;}// 插入元素e為新的棧頂元素。intPush(SqStack*S,SElemTypee){ 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; return1;}// 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回1；否則返回0。intPop(SqStack*S,SElemType*e){ if((*S).top==(*S).base) return0; *e=*--(*S).top;//這個等式的++*優(yōu)先級相同，但是它們的運算方式，是自右向左 return1;}//定義墻元素值為0,可通過路徑為1,不能通過路徑為-1,通過路徑為足跡//當迷宮m的b點的序號為1(可通過路徑)，return1;否則，return0。intPass(PosTypeb){ if(m[b.x][b.y]==1) return1; else return0;}voidFootPrint(PosTypea)//使迷宮m的a點的序號變?yōu)樽阚E(curstep)，表示經(jīng)過{ m[a.x][a.y]=curstep;}//根據(jù)當前位置及移動方向，返回下一位置PosTypeNextPos(PosTypec,intdi){ PosTypedirec[4]={{0,1},{1,0},{0,-1},{-1,0}};//{行增量,列增量} //移動方向,依次為東南西北 c.x+=direc[di].x; c.y+=direc[di].y; returnc;}//使迷宮m的b點的序號變?yōu)?1(不能通過的路徑)voidMarkPrint(PosTypeb){ m[b.x][b.y]=-1;}//若迷宮maze中存在從入口start到出口end的通道，則求得一條//存放在棧中(從棧底到棧頂)，并返回1；否則返回0intMazePath(PosTypestart,PosTypeend){ SqStackS; PosTypecurpos; SElemTypee; InitStack(&S); curpos=start; do { if(Pass(curpos)) {//當前位置可以通過，即是未曾走到過的通道塊 FootPrint(curpos);//留下足跡 e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.y; e.di=0; Push(&S,e);//入棧當前位置及狀態(tài) curstep++;//足跡加1 if(curpos.x==end.x&&curpos.y==end.y)//到達終點(出口) return1; curpos=NextPos(curpos,e.di); } else {//當前位置不能通過 if(!StackEmpty(S)) { Pop(&S,&e);//退棧到前一位置 curstep--; while(e.di==3&&!StackEmpty(S))//前一位置處于最后一個方向(北) { MarkPrint(e.seat);//留下不能通過的標記(-1) Pop(&S,&e);//退回一步 curstep--; } if(e.di<3)//沒到最后一個方向(北) { e.di++;//換下一個方向探索 Push(&S,e);curstep++;//設(shè)定當前位置是該新方向上的相鄰塊 curpos=NextPos(e.seat,e.di); } } } }while(!StackEmpty(S)); return0;}//輸出迷宮的結(jié)構(gòu)voidPrint(intx,inty){ inti,j; for(i=0;i<x;i++) { for(j=0;j<y;j++) printf("%3d",m[i][j]); printf("\n"); }}voidmain(){ PosTypebegin,end; inti,j,x,y,x1,y1,n,k; do{system("cls");//清屏函數(shù)printf("<<<<<<<<<<<<<<<<welcome>>>>>>>>>>>>>>>>\n\n\n");printf("1請輸入迷宮的行數(shù),列數(shù)(包括外墻)\n");printf("2請輸入迷宮內(nèi)墻單元數(shù)\n");printf("3迷宮結(jié)構(gòu)如下\n");printf("4輸入迷宮的起點和終點\n");printf("5輸出結(jié)果\n");printf("0退出\n");printf("\n\n請選擇");scanf("%d",&n);switch(n){case1:{ printf("請輸入迷宮的行數(shù),列數(shù)(包括外墻)：(空格隔開)"); scanf("%d%d",&x,&y); for(i=0;i<x;i++)//定義周邊值為0(同墻) { m[0][i]=0; //迷宮上面行的周邊即上邊墻 m[x-1][i]=0;//迷宮下面行的周邊即下邊墻 } for(j=1;j<y-1;j++) { m[j][0]=0; //迷宮左邊列的周邊即左邊墻 m[j][y-1]=0;//迷宮右邊列的周邊即右邊墻 } for(i=1;i<x-1;i++) for(j=1;j<y-1;j++) m[i][j]=1;//定義通道初值為1 }break;case2: {printf("請輸入迷宮內(nèi)墻單元數(shù)："); scanf("%d",&j); printf("請依次輸入迷宮內(nèi)墻每個單元的行數(shù),列數(shù)：(空格隔開)\n"); for(i=1;i<=j;i++) { scanf("%d%d",&x1,&y1); m[x1][y1]=0; } }break;case3:{ Print(x,y);printf("輸入0退出");scanf("%d",&k);}break;case4:{printf("請輸入起點的行數(shù),列數(shù)：（空格隔開）"); scanf("%d%d",&begin.x,&begin.y); printf("請輸入終點的行數(shù),列數(shù)：（空格隔開）"); scanf("%d%d",&end.x,&end.y);}break;case5:{ if(MazePath(begin,end))//求得一條通路 { printf("此迷宮從入口到出口的一條路徑如下:\n"); Print(x,y);//輸出此通路 } else printf("此迷宮沒有從入口到出口的路徑\n"); printf("輸入0退出");scanf("%d",&k); }break;}}while(n!=0);}沈陽航空航天大學課程設(shè)計報告

課程設(shè)計總結(jié)：本次課程設(shè)計是一個關(guān)于迷宮求解的問題，雖然剛聽到有一些迷茫但是通過老師和同學的幫助最后還是有了結(jié)果，同時有了很多的體會和經(jīng)驗。課程設(shè)計涉及很多的范圍，這就需要我重新的溫習以前學過的C語言的知識和數(shù)據(jù)結(jié)構(gòu)的算法，別且通過這個過程我又發(fā)現(xiàn)了我自身的不足，同時也鞏固了我的C語言和數(shù)據(jù)結(jié)構(gòu)。這對我以后的學習是非常有幫助的。同時在這次程序設(shè)計過程中，我自己有很多不會或者不懂的地方，這時候就會有老師和同學的幫助，幫助我解決問題，同時我也會對