數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)說(shuō)明書(shū)迷宮問(wèn)題求解

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)說(shuō)明書(shū)迷宮問(wèn)題求解學(xué)生姓名學(xué)號(hào)班級(jí)成績(jī)指導(dǎo)教師計(jì)算機(jī)科學(xué)與技術(shù)系2011年 9 月 9 日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)評(píng)閱書(shū)題 目迷宮問(wèn)題求解學(xué)生姓名學(xué)號(hào)指導(dǎo)教師評(píng)語(yǔ)及成績(jī)成績(jī)： 教師簽名： 年 月 日答辯教師評(píng)語(yǔ)及成績(jī)成績(jī)： 教師簽名： 年 月 日教研室意見(jiàn)總成績(jī)： 室主任簽名： 年 月 日注：指導(dǎo)教師成績(jī)60%，答辯成績(jī)40%，總成績(jī)合成后按五級(jí)制記入。課程設(shè)計(jì)任務(wù)書(shū)2011 2012 學(xué)年第 一 學(xué)期專業(yè)： 學(xué)號(hào)： 姓名： 課程設(shè)計(jì)名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè)計(jì)題目： 迷宮問(wèn)題求解 完成期限：自 2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周設(shè)計(jì)依據(jù)、要

2、求及主要內(nèi)容（可另加附頁(yè)）： 輸入一個(gè)任意大小的迷宮數(shù)據(jù)，設(shè)置入口、出口及障礙，借助棧結(jié)構(gòu)求解走出迷宮的路徑并輸出。1.遵循結(jié)構(gòu)化程序設(shè)計(jì)思想，采用c/c+實(shí)現(xiàn)。 2.界面友好，操作簡(jiǎn)便，容錯(cuò)性。 基本要求如下： 1）問(wèn)題分析和任務(wù)定義：根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問(wèn)題，明確問(wèn)題要求做什么？（而不是怎么做？）限制條件是什么？確定問(wèn)題的輸入數(shù)據(jù)集合。2）邏輯設(shè)計(jì)：對(duì)問(wèn)題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類(lèi)型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類(lèi)型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫(xiě)出每個(gè)抽象數(shù)據(jù)類(lèi)型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說(shuō)明），各個(gè)主要模塊的算法，并

3、畫(huà)出模塊之間的調(diào)用關(guān)系圖；3）詳細(xì)設(shè)計(jì)：定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)。在這個(gè)過(guò)程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試，抽象數(shù)據(jù)類(lèi)型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說(shuō)明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作做出進(jìn)一步的求精，寫(xiě)出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類(lèi)型定義；4）程序編碼：把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言程序。同時(shí)加入一些注解和斷言，使程序中邏輯概念清楚；5）程序調(diào)試與測(cè)試：能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測(cè)試數(shù)據(jù)確保程序正確。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；6）結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和

4、含有錯(cuò)誤的輸入及其輸出結(jié)果；7）編寫(xiě)課程設(shè)計(jì)報(bào)告；以上要求中前三個(gè)階段的任務(wù)完成后，先將設(shè)計(jì)說(shuō)明書(shū)的草稿交指導(dǎo)老師面審，審查合格后方可進(jìn)入后續(xù)階段的工作。設(shè)計(jì)工作結(jié)束后，經(jīng)指導(dǎo)老師驗(yàn)收合格后將設(shè)計(jì)說(shuō)明書(shū)打印裝訂，并進(jìn)行答辯。指導(dǎo)教師（簽字）： 教研室主任（簽字）： 批準(zhǔn)日期： 2011年 8 月 29 日摘 要設(shè)計(jì)了一個(gè)尋找迷宮出口路徑的程序，該程序具有設(shè)置任意大小的迷宮數(shù)據(jù)，通過(guò)設(shè)置的迷宮入口出口及障礙，探索出一條簡(jiǎn)單路徑并輸出的功能。該程序采用vc作為軟件開(kāi)發(fā)環(huán)境，借助棧先入后出的特點(diǎn)，先將入口作為檢索的起點(diǎn)，順著某個(gè)方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路返回，換個(gè)方向在繼續(xù)探索

5、，直到所有可能的通路都探索到為止，最后把探索到的路徑輸出。關(guān)鍵詞：迷宮路徑；探索；輸出目 錄1.課題描述12.問(wèn)題分析和任務(wù)定義23.邏輯設(shè)計(jì)34.詳細(xì)設(shè)計(jì)44.1迷宮數(shù)據(jù)的存儲(chǔ)44.2當(dāng)前位置可通性的判斷及探索方向的改變54.3無(wú)通路時(shí)沿原路返回64.4路徑信息入棧和出棧74.5 當(dāng)前探索位置的切換84.6最終探索路徑的輸出及標(biāo)記94.7打印迷宮信息105.程序代碼115.1文件包含和結(jié)構(gòu)體的定義115.2棧的初始化及入棧出棧函數(shù)115.3申請(qǐng)迷宮大小及障礙的設(shè)置125.4通道可通性測(cè)試135.5為走過(guò)的通道留下足跡135.6探索位置的切換135.7入口到出口的路徑探索145.8打印迷宮信息

6、155.9主函數(shù)166.程序測(cè)試18總結(jié)21參考文獻(xiàn)221.課題描述本次課題是實(shí)現(xiàn)迷宮問(wèn)題的求解，利用c語(yǔ)言設(shè)計(jì)一個(gè)能實(shí)現(xiàn)輸入一個(gè)任意大小的迷宮數(shù)據(jù)，利用二維數(shù)組來(lái)儲(chǔ)存設(shè)置的入口、出口及障礙，借助棧先入后出的結(jié)構(gòu)特性保存迷宮探索過(guò)程中留下的路徑信息，以便在遇到障礙時(shí)沿原路返回，在探索結(jié)束后輸出棧中保存的最終路徑。2.問(wèn)題分析和任務(wù)定義迷宮求解的實(shí)現(xiàn)依賴于路徑探索的算法，路徑探索的算法采用的是“窮舉求解”的方法。因此有以下問(wèn)題：(1)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的選擇。(2)當(dāng)前位置的可通性判斷及探索方向的改變。(3)道路不通時(shí)沿原路返回的算法。(4)路徑信息的入棧和出棧。(5)最終路徑的輸出。3.邏輯設(shè)計(jì)程序

7、要實(shí)現(xiàn)路徑探索及輸出即要實(shí)現(xiàn)當(dāng)前位置可通性的判斷；路徑可通時(shí)朝默認(rèn)方向繼續(xù)向前探索，路徑不可通時(shí)沿原路返回改變探索方向，輸出最終探索結(jié)果。其關(guān)系如圖3.1 所示。圖3.1 迷宮路徑探索功能結(jié)構(gòu)4.詳細(xì)設(shè)計(jì)4.1迷宮數(shù)據(jù)的存儲(chǔ)maze是指向指針的指針，用行h和列l(wèi)來(lái)存儲(chǔ)迷宮的大小，使用malloc申請(qǐng)一個(gè)二維數(shù)組，根據(jù)用戶輸入的障礙坐標(biāo)在maze數(shù)組的相應(yīng)位置存入1作為障礙標(biāo)記，直到用戶輸入0 0結(jié)束障礙的設(shè)置。該模塊的執(zhí)行過(guò)程如圖4.1 所示。圖4.1 迷宮數(shù)據(jù)的存儲(chǔ)4.2當(dāng)前位置可通性的判斷及探索方向的改變當(dāng)前位置curpos的坐標(biāo)在maze數(shù)組中對(duì)應(yīng)位置儲(chǔ)存的數(shù)據(jù)若非1和8即為可通在此留下

8、足跡，由變量di來(lái)記錄下一個(gè)探索方向，把下一個(gè)位置作為當(dāng)前位置并繼續(xù)探索，若當(dāng)前位置不可通，則后退一步按順時(shí)針?lè)较蚋淖兲剿鞣较?。操作流程如圖4.2所示。圖4.2 可通性的判斷及探索方向的改變4.3無(wú)通路時(shí)沿原路返回借助棧先入后出的特性，把探索過(guò)的路徑信息e壓入棧s中。若當(dāng)前位置curpos的下一個(gè)探索方向的變量值di為4時(shí)，表示當(dāng)前位置周?chē)膫€(gè)方向均無(wú)通道，沿原路退回一步將路徑信息e逐個(gè)出棧，一退直到di4，改變方向繼續(xù)探索。該模塊的執(zhí)行過(guò)程如圖4.3所示。圖4.3 無(wú)通路時(shí)沿原路返回4.4路徑信息入棧和出棧當(dāng)前位置curpos可通時(shí)maze數(shù)組中的對(duì)應(yīng)位置留下足跡，標(biāo)記下一個(gè)探索方向，若棧s

9、滿則追加?？臻g，路徑信息入e棧*s.top=e，s.top+。若當(dāng)前位置不可通且棧不為空則后退一步，路徑信息e出棧e=*-s.top并改變探索方向。程序的操作流程如圖4.4所示。圖4.4路徑信息入棧和出棧4.5 當(dāng)前探索位置的切換利用二維數(shù)組來(lái)確定當(dāng)前探索位置curpos。方向變量e.di的數(shù)值為1時(shí)，則橫坐標(biāo)加1；e.di的數(shù)值為2時(shí)，則縱坐標(biāo)加1；e.di的數(shù)值為3時(shí)，則橫坐標(biāo)減1；e.di的數(shù)值為4時(shí)，則縱坐標(biāo)減1。程序的操作流程如圖4.5所示。圖4.5當(dāng)前探索位置的切換4.6最終探索路徑的輸出及標(biāo)記迷宮探索結(jié)束時(shí)若找不到出口則輸出尋找不到路徑。若成功找到出口則根據(jù)棧s儲(chǔ)存的路徑坐標(biāo)信息

10、e在迷宮數(shù)據(jù)maze數(shù)組的相應(yīng)位置標(biāo)記2。程序的操作流程如圖4.6所示。圖4.6最終探索路徑的輸出及標(biāo)記4.7打印迷宮信息根據(jù)棧s儲(chǔ)存的路徑坐標(biāo)信息在迷宮數(shù)據(jù)mazexx的不同輸出不同的符號(hào)，分別表示迷宮的障礙和走出迷宮的路徑。程序的操作流程如圖4.7所示。圖4.7打印迷宮信息5.程序代碼5.1文件包含和結(jié)構(gòu)體的定義#include#include#include#define stack_init_size 10int h,l;/保存迷宮大小的行數(shù)和列數(shù)typedef structint x;int y;point;/定義坐標(biāo)變量結(jié)構(gòu)體typedef structpoint pos;/保存當(dāng)

11、前路徑的坐標(biāo)int di;/保存下一個(gè)探索方向的標(biāo)記值selemtype;/定義路徑信息結(jié)構(gòu)體typedef structselemtype *base;/棧頂selemtype *top;/棧底int stacksize;/棧的容量sqstack;/棧的定義point start,end;/迷宮出入口的聲明5.2棧的初始化及入棧出棧函數(shù)/棧的初始化int initstack(sqstack &s)/申請(qǐng)棧的空間s.base=(selemtype *)malloc(stack_init_size*sizeof(selemtype);if(!s.base)/判斷棧是否申請(qǐng)成功exit(-2);s

12、.top=s.base;/使棧為空s.stacksize=stack_init_size;/給棧的容量賦值return 1;/入棧函數(shù)int push(sqstack &s,selemtype e)if(s.top-s.base=s.stacksize)/判斷棧是否已滿s.base=(selemtype *)realloc(s.base,(s.stacksize+10)*sizeof(selemtype);/棧滿時(shí)追加申請(qǐng)空間if(!s.base) exit(0);s.top=s.base+s.stacksize;s.stacksize+=10;*s.top=e;/元素入棧s.top+;ret

13、urn 1;/出棧函數(shù)int pop(sqstack &s,selemtype &e)/棧不為空時(shí)元素出棧if(s.top=s.base)exit(0);e=*-s.top;return 1;5.3申請(qǐng)迷宮大小及障礙的設(shè)置/迷宮大小初始化int *initmaze()int *maze;/指向二維數(shù)組的指針printf(設(shè)置迷宮的行和列(如3 3);scanf(%d%d,&h,&l);/用malloc函數(shù)動(dòng)態(tài)申請(qǐng)一個(gè)二維數(shù)組maze=(int*)malloc(sizeof(int)*h);for(int i=0;ih;i+)mazei=(int*)malloc(sizeof(int)*l);r

14、eturn maze;/迷宮障礙設(shè)置函數(shù)void setza(int *maze)char n,m;int x,y;printf(設(shè)置入口的坐標(biāo)(如1 1);scanf(%d%d,&y,&x);/設(shè)置入口坐標(biāo)while(!(y=h|y=1|x=l|x=1)&(x=l&y=h)&(x!=0&y!=0)printf(請(qǐng)把入口設(shè)置在迷宮的邊緣n);scanf(%d%d,&y,&x);/設(shè)置入口坐標(biāo)start.x=x-1;start.y=y-1;printf(設(shè)置出口的坐標(biāo)(如2 3); scanf(%d%d,&y,&x);/設(shè)置出口坐標(biāo)while(!(y=h|y=1|x=l|x=1)&(x=l&y=

15、h)&(x!=0&y!=0)&!(y=start.y+1&x=start.x+1)printf(請(qǐng)把出口設(shè)置在迷宮的邊緣,不要與入口重合n);scanf(%d%d,&y,&x);/設(shè)置出口坐標(biāo)end.x=x-1;end.y=y-1;printf(設(shè)置障礙的坐標(biāo)n);scanf(%d%d,&n,&m);/設(shè)置障礙坐標(biāo)/當(dāng)輸入# #時(shí)結(jié)束障礙設(shè)置while(!(n=0&m=0)mazen-1m-1=1;scanf(%d%d,&n,&m);5.4通道可通性測(cè)試/當(dāng)前位置可通性測(cè)試int pass(int *maze,point curpos)/根據(jù)maze二維數(shù)組儲(chǔ)存的數(shù)值判斷當(dāng)前位置是否可通if(

16、mazecurpos.ycurpos.x!=1&mazecurpos.ycurpos.x!=8)return (true);else return(false);5.5為走過(guò)的通道留下足跡/留下足跡void footprint(int *maze,point curpos)mazecurpos.ycurpos.x=8;5.6探索位置的切換/當(dāng)前探索位置到下一個(gè)探索位置坐標(biāo)的切換point nextpos(point curpos,int a)switch(a)case 1:/向右移動(dòng)if(curpos.xl-1)curpos.x+;break;case 2:/向下移動(dòng)if(curpos.y0)

17、curpos.x-;break;case 4:/向上移動(dòng)if(curpos.y0)curpos.y-;break;return curpos;5.7入口到出口的路徑探索/路徑探索函數(shù)int mazepath(int *maze,point start,point end,sqstack &s,selemtype e)initstack(s);/棧的初始化為路徑信息入棧做準(zhǔn)備point curpos=start;/把迷宮入口作為探索的起始位置doif(pass(maze,curpos)footprint(maze,curpos);/若當(dāng)前位置可通，則留下足跡e.pos=curpos;/把當(dāng)前位置

18、的坐標(biāo)賦值給路徑信息元素e.pose.di=1;/標(biāo)記下一個(gè)探索位置的方向push(s,e);/當(dāng)前路徑信息入棧/若當(dāng)前位置為迷宮出口則返回true結(jié)束探索if(curpos.x=end.x&curpos.y=end.y)return (true);curpos=nextpos(curpos,e.di);/切換當(dāng)前位置繼續(xù)判斷可通性else/當(dāng)前位置不可通if(s.top!=s.base)/棧不為空pop(s,e);/路徑信息出棧while(e.di=4&s.top!=s.base)/退回一步后，檢查一下個(gè)探索位置的方向標(biāo)記值/若e.di=4且棧不為空，則將路徑信息元素不斷出棧，/直到e.di

19、小于4為止pop(s,e);if(e.di4)/若當(dāng)前位置標(biāo)記的下一個(gè)探索方向的值小于4e.di+;/e.di自增改變探索方向push(s,e);/改變下一個(gè)探索方向后將元素信息再次入棧curpos=nextpos(e.pos ,e.di);/切換當(dāng)前位置繼續(xù)判斷可通性while(s.top!=s.base);/若棧不為空則繼續(xù)執(zhí)行路徑探索循環(huán)return (false);/尋找不到路徑返回false5.8打印迷宮信息/打印迷宮信息void printmaze(int *maze)int k;char b=1;/把迷宮障礙和最終路徑分別標(biāo)記為a和b兩種字符/逐行輸出迷宮信息for(k=0;kl

20、+2;k+)if(start.y=0&start.x+1=k)|(end.y=0&end.x+1=k)printf(- );else printf();printf(n);for(int i=0;ih;i+)if(start.x=0&start.y=i&start.y!=0&start.y!=h-1)|(end.x=0&end.y=i&end.y!=0&end.y!=h-1)printf(- );else printf();for(int j=0;jl;j+)if(mazeij=1)/mazexx的值為1則輸出方塊printf();else if(mazeij=2)/否則mazexx的值為2則

21、輸出b字符printf(%c ,b);elseprintf( );/mazexx的值為不為1也不為2則輸出空格if(start.x=l-1&start.y=i&start.y!=0&start.y!=h-1)|(end.x=l-1&end.y=i&end.y!=0&end.y!=h-1)printf(- );else printf();printf(n);for(k=0;kl+2;k+)if(start.y+1=h&start.x+1=k)|(end.y+1=h&end.x+1=k)printf(- );else printf();printf(n);5.9主函數(shù)void main()sqst

22、ack s;/棧的聲明selemtype e;/路徑信息元素聲明int *maze;/指向迷宮信息的指針聲明bool flag=1;/程序循環(huán)使用的旗幟while(flag)printf( 尋找迷宮的出口n);printf( n);printf( * *n);printf( * 程序使用說(shuō)明: *n);printf( * *n);printf( * 輸入橫縱坐標(biāo)請(qǐng)用整數(shù),并用空格將其分開(kāi) *n);printf( * *n);printf( * 障礙物的設(shè)置以0 0作為結(jié)束標(biāo)志 *n);printf( * *n);printf( * 歡迎使用! *n);printf( * *n);printf(

23、 n);maze=initmaze();/迷宮大小初始化setza(maze,start,end);/迷宮障礙和出入口的設(shè)置printf(開(kāi)始尋找出路?(entrt)n);getchar();/程序暫停getchar();system(cls);/清屏/打印迷宮信息printf(迷宮大小為%d行%d列n,h,l);printf(入口坐標(biāo)為:%d,%d,start.y+1,start.x+1);printf(出口坐標(biāo)為:%d,%dn,end.y+1,end.x+1);printf(設(shè)置的迷宮如下圖所示:n);printmaze(maze);/當(dāng)成功探索到路徑是輸出路徑if(mazepath(maze,s,e)=true)printf(從出口到入口的路徑坐標(biāo)依次為:n); /當(dāng)棧不為空時(shí)把探索到的路徑信息依次出棧while(s.top!=s.base)pop(s,e);mazee.pos.ye.pos.x=2;/在maze數(shù)組的對(duì)應(yīng)數(shù)據(jù)為最終路徑標(biāo)記記號(hào)printf(%d,%d),e.pos.y+1,e.pos.x+1);/輸出路徑坐標(biāo)printf(n);printf(迷宮出路如下圖所示:n);printmaze(maze);/打印迷宮信息及最終探索到的路徑else printf(尋找不到路徑n);printf(繼續(xù)請(qǐng)按1,退出請(qǐng)按0.n選擇:);