C++數(shù)據(jù)結(jié)構(gòu) 迷宮問(wèn)題

課程設(shè)計(jì)(論文)任務(wù)書(shū)軟件學(xué)院軟件工程+電子商務(wù)2009專業(yè)2班一、課程設(shè)計(jì)(論文)題目宮問(wèn)題二、課程設(shè)計(jì)(論文)工作自2010年12月27日起至2011年1月2日止三、課程設(shè)計(jì)(論文)地點(diǎn):四、課程設(shè)計(jì)(論文)內(nèi)容要求：1本課程設(shè)計(jì)的目的(1) 鞏固和加深對(duì)數(shù)據(jù)結(jié)構(gòu)基本知識(shí)的理解，提高綜合運(yùn)用課程知識(shí)的能力。(2) 使學(xué)生掌握軟件設(shè)計(jì)的基本內(nèi)容和設(shè)計(jì)方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)范化軟件設(shè)計(jì)的能力。(3) 使學(xué)生掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計(jì)的基本能力。2課程設(shè)計(jì)的任務(wù)及要求1) 基本要求:(1) 對(duì)系統(tǒng)進(jìn)行功能模塊分析、控制模塊分析；-"""(2)系統(tǒng)設(shè)計(jì)要能完成題目所要求的功能;(3) 編程簡(jiǎn)練，可用，盡可能的使系統(tǒng)的功能更加完善和全面；(4) 說(shuō)明書(shū)、流程圖要清楚;(5) 提高學(xué)生的論文寫作能力；(6) 特別要求自己獨(dú)立完成；2) 創(chuàng)新要求：在基本要求達(dá)到后，可進(jìn)行創(chuàng)新設(shè)計(jì)，如改善算法性能、友好的人機(jī)界面。3) 課程設(shè)計(jì)論文編寫要求(1)要按照書(shū)稿的規(guī)格打印與寫課程設(shè)計(jì)論文"""(2)論文包括目錄、正文、小結(jié)、參考文獻(xiàn)、附錄等"""(3)課程設(shè)計(jì)論文裝訂按學(xué)校的統(tǒng)一要求完成4）課程設(shè)計(jì)進(jìn)度安卻乍內(nèi)容天數(shù)地點(diǎn)構(gòu)思及收集資料1圖書(shū)館編碼與調(diào)試3實(shí)驗(yàn)室撰寫論文1圖書(shū)館、實(shí)驗(yàn)室學(xué)生簽名：20011年1月3日課程設(shè)計(jì)（論文）評(píng)審意見(jiàn)（1）基本算法（20分）：優(yōu)（）、良（）、中（）、一般（、差（）；（2）設(shè)計(jì)分析（20分）：優(yōu)（）、良（）、中（）、一般（、差（）；（3）調(diào)試分析（20分）：優(yōu)（）、良（）、中（）、一般（、差（）；（4）論文內(nèi)容（20分）：優(yōu)（）、良（）、中（）、一般（、差（）；（5）答辯分析（20分）：優(yōu)（）、良（）、中（）、一般（、差（）；（6）格式規(guī)范性及考勤是否降等級(jí)：是（）、否（）目錄一、需求分析1二、概要設(shè)計(jì)2三、詳細(xì)設(shè)計(jì)5四、調(diào)試分析及測(cè)試15五、個(gè)人工作及創(chuàng)新18六、小結(jié)19參考文獻(xiàn)20數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)一、需求分析1. 選題理由本次課設(shè)我選擇了迷宮問(wèn)題，迷宮求解是數(shù)據(jù)結(jié)構(gòu)課程的一個(gè)經(jīng)典問(wèn)題，迷宮問(wèn)題要求尋找一條從入口到出口的路徑。通常用的是“窮舉求解”的方法。為了保證在任何位置上都能原路退回，顯然需要用一個(gè)后進(jìn)先出的結(jié)構(gòu)來(lái)保存從入口到當(dāng)前位置的路徑。因此，在求解迷宮通路的算法中要應(yīng)用“?！钡乃枷?。對(duì)于棧的內(nèi)容在整個(gè)學(xué)期的學(xué)習(xí)中我也有了一定的了解，所以選擇了迷宮這一經(jīng)典問(wèn)題作為本次課設(shè)的內(nèi)容。2. 基本原理分析迷宮問(wèn)題通常是用“窮舉求解”方法解決，即從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前走；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒(méi)有通路。棧是一個(gè)后進(jìn)先出的結(jié)構(gòu)，可以用來(lái)保存從入口到當(dāng)前位置的路徑。以二維數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（n,n）。為處理方便起見(jiàn)，在迷宮的四周加一圈障礙。對(duì)于迷宮任何一個(gè)位置，均約定東、南、西、北四個(gè)方向可通。3. 功能要求（1）以一個(gè)二維數(shù)組Mazem+2n+2表示迷宮，其中：MazeOj和Mazem+1j（0<=j<=n+1）及MazeiO和Mazein+1（0<=i<=m+1）為做外層的一圈障礙。數(shù)組中以0表示通路，1表示障礙，限定迷宮的大小為：m,n<=10。（2）用戶需用文件的形式輸入迷宮的數(shù)據(jù)：文件中第一行的數(shù)據(jù)為迷宮的行數(shù)m和列數(shù)n；從第2行至第m+1行（每行n個(gè)數(shù)）為迷宮值，用0，1輸入，同行中的兩個(gè)數(shù)字之間用空白字符相隔。（3）迷宮的入口位置和出口位置可由用戶隨時(shí)設(shè)定。（4）若設(shè)定的迷宮存在通路，則以長(zhǎng)方陣形式將迷宮及其通路輸出到標(biāo)準(zhǔn)輸出文件上，其中字符“#”表示障礙，“*”表示路徑，“”表示曾途經(jīng)該位置但不能到達(dá)出口，其余位置用空格符表示。若設(shè)定迷宮不存在通路則報(bào)告相應(yīng)信息（5）本程序只求出一條成功的通路。（6）程序執(zhí)行的命令為：1，創(chuàng)建迷宮；2，求解迷宮；3，輸出迷宮的解。二、概要設(shè)計(jì)1、數(shù)據(jù)結(jié)構(gòu)及其抽象數(shù)據(jù)類型的定義。(1)棧的抽象數(shù)據(jù)類型ADTStack數(shù)據(jù)對(duì)象：D=ai|aiCharSet,i=l,2n,n>=0數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,ai$D,i=2,口基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：銷毀棧S。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將S清為空棧。StackLength(S)初始條件：棧S已存在。操作結(jié)果：返回棧S的長(zhǎng)度。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。GetTop(S，&e)初始條件：棧S已存在。操作結(jié)果：若棧S不空，則以e返回棧頂元素。Push(&S，e)初始條件：棧S已存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。Pop(&S，&e)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素，并以e返回其值。StackTraverse(S，visit()初始條件：棧S已存在。操作結(jié)果：從棧底到棧頂依次對(duì)S中的每個(gè)元素調(diào)用函數(shù)visit()。ADTStack2)迷宮的抽象數(shù)據(jù)類型ADTmaze數(shù)據(jù)對(duì)象：D=ai,j|ai,je','#','','*',0<=i<=m+1,0<=j<=n+1,m,n<=10數(shù)據(jù)關(guān)系：R=ROW,COL基本操作：InitMaze（&M,a,row,col）初始條件：二維數(shù)組arow+2col+2已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障礙。操作結(jié)果：構(gòu)成迷宮的字符型數(shù)組，以空白字符表示通路，以字符#'表示障礙，并在迷宮四周加上一圈障礙。MazePath（&M）初始條件：迷宮M已被賦值。操作結(jié)果：若迷宮M中存在一條通路，則按以下規(guī)定改變迷宮M的狀態(tài):以字符'*'表示路徑上的位置，字符'表示“死胡同”，否則迷宮的狀態(tài)不變。PrintMaze（M）初始條件：迷宮M已存在。操作結(jié)果：以字符形式輸出迷宮。ADTmaze2、整體框架本程序包含三個(gè)模塊（1）棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類型（2）迷宮模塊實(shí)現(xiàn)迷宮抽象數(shù)據(jù)類型（3）主程序模塊：voidmian（）初始化；Do接受命令；處理命令；while（命令!二“退出”）；各模塊之間的調(diào)用關(guān)系如圖一:主程序?？烀詫m權(quán)塊棧模塊圖一：調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖反映了程序的層次結(jié)構(gòu)如圖二:RcaflCemmatidInterpretMazcPiitlLPrintMaE19StackTraverselnitStackPishPoptackEmptyFflfttPrintMarkPrintPassNf*itPn>Same圖二：函數(shù)的調(diào)用關(guān)系圖三、詳細(xì)設(shè)計(jì)源程序:#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXLEN10/迷宮包括外墻最大行列數(shù)目#defineTRUE1#defineFALSE0#defineOK1#defineERROR0typedefintStatus;/坐標(biāo)位置類型typedefstructintr,c;PosType;/迷宮中r行c列的位置/迷宮類型typedefstructintr;intc;chararrMAXLENMAXLEN;/可取''，'MazeType;typedefstruct/intstep;/當(dāng)前位置在路徑上的“序號(hào)”PosTypeseat;/當(dāng)前的坐標(biāo)位置intdi;/往下一坐標(biāo)位置的方向SElemType;/結(jié)點(diǎn)類型typedefstructNodeTypeSElemTypedata;NodeType*next;NodeType,*LinkType;/棧類型typedefstructLinkTypetop;intstacksize;SqStack;PosTypestart;PosTypeend;MazeTypemaze;boolfound;/創(chuàng)建棧StatusInitStack(SqStack&S)S.top=(LinkType)malloc(sizeof(NodeType);S.top->next=NULL;S.stacksize=0;returnOK;/進(jìn)棧StatusPush(SqStack&S,SElemType&e)LinkTypep;p=(NodeType*)malloc(sizeof(NodeType);p->data=e;p->next=S.top;S.top=p;S.stacksize+;returnOK;/判斷是否為棧空StatusStackEmpty(SqStackS)if(S.top->next=NULL)returnOK;returnERROR;/出棧StatusPop(SqStack&S,SElemType&e)LinkTypep;if(StackEmpty(S)returnERROR;p=S.top;e=p->data;S.top=S.top->next;S.stacksize-;free(p);returnOK;/銷毀棧StatusDestroyStack(SqStack&S)LinkTypep;while(S.top!=NULL)p=S.top;S.top=S.top->next;free(p);/一個(gè)一個(gè)刪除if(S.top=NULL)returnOK;elsereturnERROR;/曾走過(guò)但不是通路標(biāo)記并返回OKStatusMarkPrint(MazeType&maze,PosTypecurpos)maze.arrcurpos.rcurpos.c=''/""表示曾走過(guò)但不通returnOK;/曾走過(guò)而且是通路標(biāo)記并返回OKStatusFootPrint(MazeType&maze,PosTypecurpos)maze.arrcurpos.rcurpos.c二'*'/"*"表示可通returnOK;/選擇下一步的方向PosTypeNextPos(PosType&curpos,inti)PosTypecpos;cpos=curpos;switch(i)/1.2.3.4分別表示東,南,西,北方向case1:cpos.c+=1;break;case2:cpos.r+=1;break;case3:cpos.c-=1;break;case4:cpos.r-=1;break;returncpos;/判斷當(dāng)前位置是否可通StatusPass(MazeType&maze,PosTypecurpos)if(maze.arrcurpos.rcurpos.c='')returnTRUE;elsereturnFALSE;/創(chuàng)建迷宮/按照用戶輸入的二維數(shù)組(0或1),設(shè)置迷宮maze的初值，包括加上邊緣一圈的值voidInitMaze(MazeType&maze,charaMAXLENMAXLEN,introw,intcol)maze.r=row;maze.c=col;for(inti=0;i<=col+1;i+)a0i='1'arow+1i='1'for(i=0;i<=row+1;i+)ai0='1'aicol+1='1'for(i=0;i<=maze.r+2;i+)for(intj=0;j<maze.c+2;j+)if(aij='1')maze.arrij='#'elsemaze.arrij=''/求迷宮路徑的偽碼算法：StatusMazePath(MazeType&maze,PosTypestart,PosTypeend)/求解迷宮maze中，從入口start到出口end的一條路徑，若存在，返回TRUE,否則返回FALSEPosTypecurpos;SqStackS;SElemTypee;InitStack(S);curpos二start;/設(shè)定“當(dāng)前位置"為“入口位置"/curstep=1;/探索第一步found=false;doif(Pass(maze,curpos)/當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊留下足跡FootPrint(maze,curpos);/做可以通過(guò)的標(biāo)識(shí)/e.step=curstep;e.seat=curpos;e.di=1;/為棧頂元素賦值Push(S,e);/加入路徑if(curpos.r二二end.r&&curpos.c二二end.c)found二true;/如口果到達(dá)終點(diǎn)返回trueelsecurpos二NextPos(curpos,l);/下一位置是當(dāng)前位置的東鄰else/當(dāng)前位置不能通過(guò)if(!StackEmpty(S)Pop(S,e);while(e.di=4&&!StackEmpty(S)MarkPrint(maze,e.seat);/留下不能通過(guò)的標(biāo)記Pop(S,e);if(e.di<4)e.di+;/換下個(gè)方向Push(S,e);/curpos=NextPos(e.seat,e.di);/進(jìn)行探索while(!StackEmpty(S)&&!found);DestroyStack(S);returnfound;/將標(biāo)記路徑信息的迷宮（字符型方陣）輸出到終端（包括外墻）voidPrintMaze(MazeType&maze)for(inti=0;i<=maze.r+2;i+)for(intj=0;j<=maze.c+2;j+)printf(“c",maze.arrij);/輸出迷宮printf("n");/系統(tǒng)初始化voidInitialization()system("cls");printf("welcometothegame");printf("n*");printf("n*創(chuàng)建迷宮一c執(zhí)行迷宮一m輸出迷宮-p退出一q*");printf("n*");printf("nn操作:-");/讀入操作命令符，顯示提示信息voidReadCommand(char&cmd)doif(cmd='c')printf("n*");printf("n*選擇操作：執(zhí)行迷宮-m*");printf("n*退出-:q*");printf("n*");printf("nn操作：-");elseif(cmd='m')printf("n*");printf("n*選擇操作：輸出迷宮-p*");printf("n*退出-：q*");printf("n*");printf("nn操作:-")；elseif(cmd='p')printf("n*")；printf("n*選擇操作：執(zhí)行迷宮-c*");printf("n*退出-:q*")；printf("n*");printf("nn操作:-");cmd=getchar();while(!(cmd='c'|cmd='m'|cmd='p'|cmd='q');/解釋cmd-具體執(zhí)行voidInterpre(charcmd)switch(cmd)，fcase'c':intrnum,cnum,i=0,m=1,n=1;chara2MAXLENMAXLEN;charinput1;chardata1000;printf("n請(qǐng)輸入迷宮數(shù)據(jù)文件名！n");scanf("%s",input);FILE*fp;fp=fopen(input,"r");if(!fp)printf("n不能打開(kāi)文件n");break;while(!feof(fp)fscanf(fp,"%s",&datai);if(i=0)rnum=(int)datai-(int)'0'if(i=1)cnum=(int)datai-(int)'0'if(i>=2)if(n>cnum)m+;n=1;a2mn=datai;n+;i+;fclose(fp);InitMaze(maze,a2,rnum,cnum);printf("n迷宮建立完成！n");break;，fcase'm':printf("n請(qǐng)輸入迷宮入口的坐標(biāo)，以空格為間隔：-");scanf("%d%d",&start.r,&start.c);printf("n請(qǐng)輸入迷宮出口的坐標(biāo)，以空格為間隔：-");scanf("%d%d",&end.r,&end.c);MazePath(maze,start,end);break;，fcase'p'：if(found)printf("n求解迷宮的結(jié)果如下-n");PrintMaze(maze);elseprintf("n找不到路徑！n");voidmain()charcmd;Initialization();do/讀入一個(gè)操作符命令/解釋執(zhí)行命令操作符ReadCommand(cmd);Interpre(cmd);while(cmd!='q');調(diào)試分析及測(cè)試1、調(diào)試分析：(1) 本程序有一個(gè)核心算法，即求迷宮的路徑，在調(diào)試的時(shí)候，出現(xiàn)了兩個(gè)問(wèn)題：沒(méi)有想到要用''記號(hào)，導(dǎo)致迷宮走不出來(lái)；沒(méi)有設(shè)置'found',不知何時(shí)跳出。(2) 原本棧的元素e中除了di往下一坐標(biāo)位置的方向和seat當(dāng)前的坐標(biāo)位置，還有一個(gè)step當(dāng)前位置在路徑上的序號(hào)，后來(lái)發(fā)現(xiàn)step沒(méi)什么用，就刪掉了。(3) 函數(shù)ReadCommand中，cmd=getchar();的位置找不準(zhǔn)，最后是試出來(lái)的。(4) 調(diào)試的時(shí)候多次出現(xiàn)，沒(méi)有錯(cuò)誤，但是dos環(huán)境下就是執(zhí)行不起來(lái)，所以采用了一些輸出變量，判斷到底是哪里出了問(wèn)題。(5) 本程序中三個(gè)主要的算法：InitMaze,MazePath和MarkPrint的時(shí)間復(fù)雜度均為O(m*n),本程序的空間復(fù)雜度也為O(m*n)(棧所占最大空間)2、使用說(shuō)明和運(yùn)行結(jié)果:(1)首先以文件形式輸入迷宮數(shù)據(jù)，如圖三:12-記事本丨回文1中E探輯E13式衛(wèi))樂(lè)也耳和(HJEFULU1U0C110-LUL-1)11C0:1n1n劃FJ圖三(2)進(jìn)入演示程序后，會(huì)出現(xiàn)以下界面如圖四:圖四(3) 進(jìn)入“創(chuàng)建迷宮”的命令后，即提示輸入迷宮數(shù)據(jù)的文件名，結(jié)束符為“回車符”，該命令執(zhí)行之后輸出“迷宮建立完成”，且輸出下面可執(zhí)行的操作。如圖五：圖五(4) 進(jìn)入“執(zhí)行迷宮”的命令后，即提示輸入迷宮入口，出口的坐標(biāo)，結(jié)束符為“回車符”，該命令執(zhí)行之后表示迷宮路徑已尋找完成或未找到路徑。請(qǐng)注意：若迷宮中存在路徑，執(zhí)行此命令后，迷宮狀態(tài)已經(jīng)改變，若要重復(fù)執(zhí)行此命令，需重新輸入迷宮數(shù)據(jù)。如圖六：圖六(5) 進(jìn)入“輸出迷宮”的命令后，即輸出迷宮求出路徑之后的狀態(tài)。'#'表示障礙，''表示曾走過(guò)但不通，'*'表示路徑。如圖七：圖七(6) 進(jìn)入“退出”的命令后，按任意鍵結(jié)束。如圖八:圖八3、缺點(diǎn)與改進(jìn)：(1) 在定義函數(shù)Mazepath的時(shí)候，開(kāi)始的循環(huán)語(yǔ)句的結(jié)束條件不對(duì)，沒(méi)有出路時(shí)，導(dǎo)致一直出現(xiàn)了不正確的結(jié)果，最后沒(méi)有新位置入棧，則返回上一個(gè)位置，否則沒(méi)有路徑。(2) 只是以文件形式輸入迷宮，如果迷宮數(shù)據(jù)量大時(shí)，要先建好文件還是很浪費(fèi)時(shí)間，如果以隨機(jī)產(chǎn)生函數(shù)自動(dòng)產(chǎn)生迷宮會(huì)更好。五、個(gè)人工作及創(chuàng)新為了準(zhǔn)備這次課程設(shè)計(jì)我查找了很多的資料，對(duì)于迷宮問(wèn)題的求解中迷宮的產(chǎn)生方式有很多的不同，有的是直接輸入迷宮，有的是用文件輸入，有的是隨機(jī)函數(shù)產(chǎn)生，我的課設(shè)是參考了用文件輸入的方法，這樣做相比直接輸入迷宮操作要更簡(jiǎn)單。當(dāng)然用隨機(jī)函數(shù)產(chǎn)生迷宮比如用：for(i=0;i<MAX_ROW;i+)for(j=0;j<MAX_COL;j+)mazeij=(int)(rand()%2);maze10=1;/*startpoint*/mazeMAX_ROW-1MAX_COL-2=1;/*endpoint*/這樣產(chǎn)生迷宮要更加的方便。結(jié)果也有不確定性，可能可以有通路也可能沒(méi)有。對(duì)于迷宮的求解都是采用的“窮舉求解”的方法，用到了一些棧的知識(shí)。把以前學(xué)過(guò)的棧的基本操作實(shí)際應(yīng)用了一番也使有了更加清楚的認(rèn)識(shí)。在求解迷宮的算法中，先設(shè)定當(dāng)前位置的初值為入口位置，然后Do若當(dāng)前位置可通，則將當(dāng)前位置插入棧頂；若該位置是出口位置，則結(jié)束；否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；否則若棧不為空且棧頂位置尚有其它方向未被探索，則設(shè)定新的當(dāng)前位置為延順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置四周均不通，則刪去棧頂位置；若棧不為空，則重新測(cè)試新的棧頂位置，直至找到一個(gè)可通的相鄰塊或出棧至?？眨磺蠼饷詫m的算法大概就是這么個(gè)思路。六、小結(jié)要能很好的掌握編程，僅僅通過(guò)幾個(gè)簡(jiǎn)單的程序的編寫是無(wú)法達(dá)成的，更需要的是大量的積累和深入研究才可能。在程序的編寫中也不能一味的向已有的程序進(jìn)行模仿，而要自己去探索，去尋找最好的解決方法，只有帶著問(wèn)題去反復(fù)實(shí)踐，才能更熟練的掌握和運(yùn)用，當(dāng)然，對(duì)現(xiàn)有的程序也要多去接觸，因?yàn)橛行┏绦蚴俏覀冊(cè)诙虝r(shí)間內(nèi)無(wú)法想出來(lái)的，我們也應(yīng)該去參考別人的作品，這樣可以節(jié)約時(shí)間獲得更多的知識(shí)。最重要的是持之以恒，要經(jīng)常性的復(fù)習(xí)原來(lái)接觸到的程序，這樣才能保證我們有足夠的經(jīng)驗(yàn)去面對(duì)程序問(wèn)題。參考文獻(xiàn)1 .嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）清華大學(xué)出版社.20072 .嚴(yán)蔚敏，數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）清華大學(xué)出版社.20073 .譚浩強(qiáng)，C程序設(shè)計(jì)（第四版）清華大學(xué)出版社.2007