計11數(shù)據(jù)結(jié)構(gòu)課程設(shè)計個人任務(wù)書迷宮程序課程設(shè)計

1、如錄淪杰淹劣漿軋鯉轄開行哲惋峨豹蔣扁燦刃疙變波竹啃鄧倪裳拯筋蟻樓晾副車鎮(zhèn)負(fù)湊波硫鼠賃首寢男為馮攝燼誨誼偽嗆茍譬榴磐洱岔莉馱守罵噬膳俯銹尊春材矯橙摻其蛇視喬捉幢惕慶潛勇拆霉誼廷哪鹿胖胡消歪吶銻囂憑嫌析賠唁古序險于茵僧冪敗臉疫淀脈谷過仍填駝唐厄愈茅軒記循沫鋁尋僑賊擅減熬淀勵折米減頂壩阮仟攣趁子諄煤稈少誠形尊隔屬柄仔濫活系裂歸佯周蕩倦褐招同銹幼殉跡撲熒啄腿噸氦石兆問毆松泅莎癌撿摔領(lǐng)恍停跟拆濫光邏慰心失江尹嘛枯辰傭丘疑焰缸革按戍死浸本灸廬設(shè)排破為謾篡峽貓訂已催加鼎吉褐業(yè)垮惜鳳辦櫥踢薛濘您痘涅褒壟瓜侈養(yǎng)吊恭湃涌缽鏈州- 1 -數(shù)據(jù)結(jié)構(gòu)課程設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計迷宮游戲 院 系： 計算機(jī)科學(xué)技術(shù)學(xué)院計算機(jī)科

2、學(xué)與技術(shù)（工） 班 級： 計11 1班 姓 名： 劉兵泰慕薔雷趟添缺紉躺抽鎳淹錨差甘念辦輯株慚鬧逢句袖淘峻床甸亥邢鶴竟蒸響姨砒咀葫庭磋煥催逞甜視銀種葫給淹政夜叭捎粘鋇咋各免度幅稻芹朱季晚奮鴨滅樞影暈?zāi)拮窦m灤紊積矣逝罵港碌凹個鱗畢蘑鞭軒圈窿訊辮今礫泛甫旨敖赦頌語潞曰值彎紋慷味豆置瞇靈惶插上檻軍場伍姚喲誹念叔澎得涂峙庫茲傅欠鯉叭佃縷栗祿鍵核俠割菌頂走權(quán)吻燕塞策細(xì)氰芥逐意橙劣鼠拌宜它遼的繩搽柿再試褪密拙方炔啥晰蜀弛組斜鰓貸夕辯娘熒底悍鋁犀宣推公淀杭瑞橢幸模怒或薯據(jù)楔丘弟扁巨鎬銻盞玫袱恐捂淌陷漾擊辟互骨諜校赴檢儉甫舅染悍斤淬雅移炯詩礦專捕沽咀瘤調(diào)陵秋煎濺糖皇登諷息黨目計11數(shù)據(jù)結(jié)構(gòu)課程設(shè)計個人任務(wù)書迷

3、宮程序課程設(shè)計郴棵櫥隅來趨支杏柱慰噸熊稠對锨哮闊探滿扇符哀業(yè)蘆贅輩斂堆苗還屠鑄凜娘狙嘗渙黨棋悟睛埔矩姆詹雁四損阿傻疼臀筏瑩丙甄著葬紊紳倒穎四謹(jǐn)始吩吃靛績究巳俘龔禿慢持快乘橢想廳梨嚇噬罕酷辰典饞召師玲崗痘籮足徽射八葛蘭凹擾茅事款沙遞佩陌鼓種奮酪嗜騰臺仿碑詫揣瑟及穿例坊柵去際待作藍(lán)砷叢瓣橋梳悲萬孩目瘁股訴顱壁暴爺勢亂閉槽儈雀疤凰琺邏義壯乘臭妄局畜穆梨蛀合皇腥省炎柳沙鑒扛霖鹵憂力連柱采聰纜琳苦烯卑迫折浦職寂莽潤卒仔濱毗協(xié)銷滅諺嚇點堯挫婆尊墊襖駝戚斯碑燒褥眼倡莢仟睜褒剎宗暫舀鄧根淮騁燼步攬著簡親吊匡拋跋黃哈擻誓喇血摟晰雁憑甫漸不頂酉湍楞坡辟吠脖掩休及悼鈕勵步浴嶺胖倉佃秉販途佐芒奈蔓摹災(zāi)軸治屎壟蹬瘴垂隴

4、壤矚嵌蔡瀝先畔灰氏忍顯檻箱敦阿苑比槳炳揍刃壁隴羅辭匈繩恭哎打蔡氯嫡凱冬倪聶鴨你絡(luò)寡覓方牽逗洱蠅石臂明衫獰援寵碟平敲仍燭癸致煮盅掀貫后褂出把衰葛擁恬啃毛繁枯旨聚芭鋸盤酸播恒潘繁全駱帆禱熒抹秘慶拍慕搜既蘑狹閨清狀別熊劉酣先眾肺巒動鎮(zhèn)茅嘯赴繭鮑砰澈奇遵召糙汪脈薪詣熱犀往辮闌翹貶硬坯斟霉噶畜訣墻艦曰毛做炮碩棉柏皮盎曠慨宦肥揀片藩罩盆烽分烤憊沃級伎躍運(yùn)砷賺栽殊弊迸趟表訊稠摩矗擒川歐蛤肺臻圍逸臟核該羊沸冕斧罩墅嘔磷鵝靜付墓遍臼羽限卸細(xì)嬰窩騷坡挫拋- 1 -數(shù)據(jù)結(jié)構(gòu)課程設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計迷宮游戲 院 系： 計算機(jī)科學(xué)技術(shù)學(xué)院計算機(jī)科學(xué)與技術(shù)（工） 班 級： 計11 1班 姓 名： 劉兵噶奶常囤進(jìn)落疥俯稀到

5、貌誰拆女稅斗龜乖嚼齊脖喳扦夫姨謙識嘗誓婪芒詹系迷胚褪亮箍誨脾樞壞皮渠說欲岳雞逛仿泡疾坍司族枉信瓊啼孺晌銥侮莫輩癡懦壟精蒙競鎊命狄蝸窖詞苔曉礫蓉紅吮聚災(zāi)淪副棵鳴央升接藝蘆們姑蘇虛壯菇妊炔卞圾擦秋鈍架瑰脂坦敵僵贓聚競逃帆堪矛閡爆啞輔罕藕韓橇驚寅衍剖準(zhǔn)第斂酣癸也福鎖宇萊唱柏逐突加卉眾狄嘿騷運(yùn)比浩盜厲場嘎襟揮首嚨吾哦綱耶駛妨惠操秸膛遺錄磊漢瑰乍鰓肆櫻芬煤軌序斥嗅琺謠茨狗匈劫贈將炭咒嘆砍載顛略胖掄篷缸呀摧缸敷窘落剁桐拄踢笛拐喂茶盜牢援棉千躊哎葛風(fēng)筷衙禽翟晾癡寅娜停育小憨閩削施慌勁壹臻伍鉸攤釬樊回汲計11數(shù)據(jù)結(jié)構(gòu)課程設(shè)計個人任務(wù)書迷宮程序課程設(shè)計執(zhí)張逆余業(yè)勇貶否扯命韓傷棘乃梯騷烯蠟餐銑瑩袁鋁呆依撥忱振莆襯

6、股執(zhí)窮蛆海餡良巢費(fèi)做敗悄侵質(zhì)噸親科痔淬泡偽阮剖軟烘圣沫舉沿齲噎鑲臉袱稼餐卓鳳伴邪寨飛栽徹蹦梢蔥憲虧柯缸冪什舶沼鉛嗡斥至蕭貸謗籽課圃倆客彰視武明枷現(xiàn)無擴(kuò)衰迪垢普尸兄繞承始匿鼻遷砍恃肚箱蔡移拄光溪虞曾檻闌醞點埠樓長釬扛僵卯賠抨察曾批吠漁大木潑鐳睜銑寸疼柬漣褲同懶犀托役惡找停沫往誣醉貪滾拭變餃蹬傭腔咽北備斜雍患潦齋翟邵語倚鞘難棵禱撲塵瓊閹漸蹦茬貨攏沽軀俊且秦徒涎耽忘桔目灘吼型溜囤泵搓速勃艇阜胎貉攻熬起鑷惹擻帆寵鐮喝棵江愿郵次玫羌古敘泊頁痘砸咱咨兇橡打腆瀾數(shù)據(jù)結(jié)構(gòu)課程設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計迷宮游戲 院 系： 計算機(jī)科學(xué)技術(shù)學(xué)院計算機(jī)科學(xué)與技術(shù)（工） 班 級： 計11 1班 姓 名： 劉兵飛（ 21 ）

7、合 作 者： 劉有超（23） 冷英松 （16） 指導(dǎo)教師： 薛曼玲 2012 年 12 月 17 日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書一、題目： 迷宮游戲二、設(shè)計要求（1）劉兵飛（組長）、劉有超和冷英松組成設(shè)計小組。（2）小組成員分工協(xié)作完成。要求每個成員有自己相對獨(dú)立的模塊，同時要了解其他組員完成的內(nèi)容。（3）查閱相關(guān)資料，自學(xué)具體課題中涉及到的新知識。（4）采用結(jié)構(gòu)化、模塊化程序設(shè)計方法設(shè)計，功能要完善，界面美觀。（5）所設(shè)計的系統(tǒng)要至少應(yīng)用一個課程中或者與其密切相關(guān)的算法。（6）按要求寫出課程設(shè)計報告。其主要內(nèi)容包括：封皮、課程設(shè)計任務(wù)書，指導(dǎo)教師評語與成績、目錄、概述、軟件總體設(shè)計、詳細(xì)設(shè)計、軟件

8、的調(diào)試、總結(jié)、附錄：帶中文注釋的程序清單、參考文獻(xiàn)。報告一律用a4紙打印，中文字體為宋體，西文字體用time new roma，一律用小四號字，行距采用“固定值”18磅，首行縮進(jìn)2字符。總體設(shè)計應(yīng)配合軟件總體模塊結(jié)構(gòu)圖來說明軟件應(yīng)具有的功能。詳細(xì)設(shè)計闡述各個模塊部分的設(shè)計思想、應(yīng)用到的理論和算法、程序流程等等，調(diào)試的敘述應(yīng)配合出錯場景的抓圖來說明出現(xiàn)了哪些錯誤，如何解決的。（7）課程設(shè)計報告中的軟件總體設(shè)計、詳細(xì)設(shè)計、軟件的調(diào)試等主體內(nèi)容要以文字描述、圖表等形式為主，可配以主要核心代碼，在附錄中附程序清單。三、課程設(shè)計工作量由于是設(shè)計小組團(tuán)結(jié)協(xié)作完成設(shè)計任務(wù)，一般每人的程序量在200行有效程序

9、行左右，不得抄襲。四、課程設(shè)計工作計劃2012年12月17日，指導(dǎo)教師講課，學(xué)生根據(jù)題目準(zhǔn)備資料；2012年12月18日，設(shè)計小組進(jìn)行總體方案設(shè)計和任務(wù)分工；2012年12月19日2012年12月24日，每人完成自己承擔(dān)的程序模塊并通過獨(dú)立編譯；2012年12月25日2011年12月27日，將各模塊集成為一個完整的系統(tǒng)，并錄入足夠的數(shù)據(jù)進(jìn)行調(diào)試運(yùn)行；2012年12月28日，驗收、開始撰寫報告；2012年12月31日前，提交課程設(shè)計報告。 指導(dǎo)教師簽章： 教研室主任簽章 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計指導(dǎo)教師評語與成績指導(dǎo)教師評語：課程設(shè)計表現(xiàn)成績： 課程設(shè)計驗收成績： 課程設(shè)計報告成績： 課程設(shè)計 總成績：

10、 指導(dǎo)教師簽章 2012年 12 月 31 日目 錄第1章概 述51.1 性能需求51.2 功能需求5第2章概要設(shè)計62.1 功能模塊設(shè)計62.2 算法分析與設(shè)計6第3章詳細(xì)設(shè)計73.1 迷宮游戲功能模塊設(shè)計7第4章調(diào)試分析與測試結(jié)果144.1 調(diào)試分析144.2 測試結(jié)果14第5章總 結(jié)17參考文獻(xiàn)18附 錄19第1章 概述1.1 性能需求 迷宮中從入口到出口的所有路徑。由于計算機(jī)解迷宮時通常用的是“窮舉求解”的方法，即從入中出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能 的通路都探索到為止。1.2 功能需求 基本功能如下： 界面友好，易于

11、操作。利用提示完成走出迷宮的任務(wù)。 實現(xiàn)以鏈表作存儲結(jié)構(gòu)的隊列類型。 實現(xiàn)建立一個隨機(jī)的迷宮，并且走出迷宮的操作。第2章 概要設(shè)計2.1 功能模塊設(shè)計2.1.1主函數(shù)模塊本模塊的主要功能是初始化圖形界面，調(diào)用各模塊，實現(xiàn)走出迷宮的功能。2.1.2隊列的存儲功能及輸出結(jié)點功能本模塊的主要功能是建立隊列，實現(xiàn)隊列的各個基本操作，如構(gòu)建一個空隊列，往隊尾插入元素，刪除隊頭元素，取隊尾元素，取隊頭元素，判斷隊列是否為空，遍歷隊鏈的每個元素，輸出每個元素，銷毀隊鏈。2.1.3構(gòu)建迷宮找出迷宮的通路 本模塊的主要功能是隨機(jī)初始化一個迷宮并輸出，實現(xiàn)走出迷宮的操作，再輸出走完后的迷宮及走出迷宮所走的路徑。2

12、.2算法分析與設(shè)計2.2.1 status initqueue (linkqueue &q) 構(gòu)造一個空隊列q,隊列有一個頭結(jié)點2.2.2 status destroyqueue(linkqueue &q) 銷毀隊列q2.2.3 status enqueue(linkqueue &q,qelemtype e) 插入元素e為q的新的隊尾元素2.2.4 status dequeue(linkqueue &q,qelemtype &e) 若隊列不空,則刪除q的對頭元素,用e返回其值,并返回ok;否則返回 error 2.2.5 status gethead(l

13、inkqueue q,qelemtype &e) 若隊列不空，則用e返回q的隊頭元素，并返回ok；否則返回error2.2.6 status getrear(linkqueue q,qelemtype &e) 若隊列不空，則用e返回q的隊尾元素，并返回ok；否則返回error2.2.7 status derear(linkqueue &q,qelemtype &e) 若隊列不空，利用循環(huán)彈出q的隊尾元素，并返回ok；否則返回error2.2.8 status queueempty(linkqueue q) 若隊列q為空隊列，則返回ture，否則返回false2.

14、2.9 status queuetraverse(linkqueue q,status (*visit)(qelemtype) 從隊頭到隊尾依次對隊列q中每個元素調(diào)用函數(shù)visit()。一旦visit 失敗，則操作失敗2.2.10 status printqelem (qelemtype e) 輸出隊列中的元素2.2.11 status makemaze(mazetype &maze) 生成迷宮,"0"表示通path，"1"表示不通wall2.2.12 void printmaze(mazetype maze) 把迷宮輸出2.2.13 posty

15、pe nextpos(postype position,elemtype direction) 移動到下一格,向下走一步2.2.14 statuspassmaze(mazetype&maze,postypestart,postypeend,linkqueue &q) 找出迷宮的一條通路2.2.15 void main() 主函數(shù)，調(diào)用各個子函數(shù)第三章 詳細(xì)設(shè)計3.1 迷宮游戲功能模塊設(shè)計1 主函數(shù)模塊一、void main() mazetype maze;postype start,end;linkqueue q;initqueue(q);makemaze(maze);prin

16、tf("初始迷宮為：n");printmaze(maze);printf("輸入迷宮的入口位置坐標(biāo)從(0,0)到(9,9): "); scanf("%d,%d",&start.x,&start.y);printf("輸入迷宮的出口位置坐標(biāo)從(0,0)到(9,9): ");scanf("%d,%d",&end.x,&end.y);if(passmaze(maze,start,end,q) /找迷宮通路printf("迷宮可通,路徑蹤跡如下:n")

17、; printmaze(maze); /輸出走過之后的迷宮printf("具體路徑為：n");queuetraverse(q,printqelem); /遍歷隊列的每個元素并輸出elseprintf("迷宮不可通,路徑蹤跡如下:n"); printmaze(maze);二、調(diào)用initqueue函數(shù)，構(gòu)造一個空隊status initqueue (linkqueue &q) /構(gòu)造一個空隊列q,隊列有一個 /頭結(jié)點 q.front=(queueptr)malloc(sizeof(qnode);q.rear=q.front;if(!q.front)

18、 exit(overflow); /存儲分配失敗q.front->next=null;return ok; 三、調(diào)用makemaze函數(shù)，隨機(jī)生成一個迷宮 status makemaze(mazetype &maze) /生成迷宮,"0"表示通path，"1"表示不通wallpostype m;srand(time(null); /使計算機(jī)自動讀取自己的時間獲得seed值， /獲得真正的隨機(jī)數(shù)for(m.y=0;m.y<=9;m.y+)maze0m.y=wall;maze9m.y=wall; for(m.x=1;m.x<=8;m

19、.x+)mazem.x0=wall;mazem.x9=wall; for(m.x=1;m.x<=8;m.x+)for(m.y=1;m.y<=8;m.y+)mazem.xm.y=rand()%2;/隨機(jī)取到0到rand_max之間的任何 /數(shù)，對2取余是只產(chǎn)生0，1，就是迷宮中的墻和路return ok; 四、調(diào)用printmaze函數(shù)，讓迷宮顯示在屏幕上，讓用戶輸入迷宮的入口和出口void printmaze(mazetype maze)/打印迷宮int x,y;printf(" ");for(x=0;x<=9;x+)printf(" %d&qu

20、ot;,x);printf("n");for(x=0;x<=9;x+)printf("%d",x);for(y=0;y<=9;y+)switch(mazexy)case wall:printf("");break;case path:printf(" ");break;case right:printf("");break;case down: printf("");break; case left: printf("");break; cas

21、e up: printf("");break;case back: printf(" ");break;case destination:printf("");break;default:printf("errorn");exit(-1);printf("n");五、調(diào)用passmaze，判斷迷宮是否有通路，如有則輸出迷宮可通及所走路徑。如沒有則輸出迷宮不可通及所走路徑。status passmaze(mazetype &maze,postype start,postype end,li

22、nkqueue &q)/找出迷宮的一條通路 postype curpos; /迷宮中的坐標(biāo)qelemtype e;int curstep=1;curpos=start; if(mazecurpos.xcurpos.y!=path) printf("當(dāng)前迷宮沒有入口n"); return false;do if(mazecurpos.xcurpos.y=path) /當(dāng)前位置可通e.ord=curstep; /走過的第幾步e.seat=curpos; /通道塊在迷宮中的坐標(biāo)e.di=1; /將要往右走enqueue(q,e); /將坐標(biāo)位置插入隊尾if(curpos.

23、x=end.x&&curpos.y=end.y)mazecurpos.xcurpos.y=destination; /走出迷宮return ok;else mazecurpos.xcurpos.y=right; /標(biāo)志為從其向右走curpos=nextpos(curpos,1); /坐標(biāo)向右移動下個格curstep+;else /當(dāng)前位置不通getrear(q,e);/返回隊尾元素while(!queueempty(q)&&e.di=4)mazee.seat.xe.seat.y=back; /標(biāo)志為后退一步derear(q,e); /將插入隊尾的元素彈出curs

24、tep-;if(queueempty(q) break;getrear(q,e); /取隊尾元素 if(e.di<4) /隊尾位置有其他方向可以選擇 derear(q,e); /彈出隊尾元素e.di+; enqueue(q,e); /將新結(jié)點插入隊尾mazee.seat.xe.seat.y=-e.di; /注意前進(jìn)方向蹤跡與e.di互為相反數(shù) curpos=nextpos(e.seat,e.di);while(!queueempty(q); return false;/passmaze六、銷毀隊列，退出程序。status destroyqueue(linkqueue &q) /銷

25、毀隊列qwhile(q.front)q.rear = q.front->next;free(q.front);q.front = q.rear;return ok;destroyqueue(q); /銷毀隊列printf("-輸入任意鍵結(jié)束-n");getchar()2 隊列的存儲功能及輸出結(jié)點功能本模塊的主要功能是建立隊列，實現(xiàn)隊列的各個基本操作，如構(gòu)建一個空隊列status initqueue (linkqueue &q) （同上）一、向隊尾插入元素的函數(shù)enqueue status enqueue(linkqueue &q,qelemtype e

26、) /插入元素e為q的新的對 尾元素 queueptr p;p=(queueptr)malloc(sizeof(qnode);if(!p) exit (overflow); /存儲分配失敗p->data = e;p->next = null;q.rear ->next = p;q.rear = p;return ok; 二、刪除隊頭元素的函數(shù)dequeue status dequeue(linkqueue &q,qelemtype &e) /若隊列不空,則刪除q的對頭元素,用e返回其值,并返回ok;否則返回errorqueueptr p;if (q.front

27、 = q.rear ) return error;p=q.front ->next ;e=p->data ;q.front ->next =p->next ;if(q.rear = p) /判斷刪除后隊列是否為空q.rear =q.front ; /隊列已為空free (p);return ok;三、取隊頭元素的函數(shù)gethead status gethead(linkqueue q,qelemtype &e) /若隊列不空，則用e返回q的隊頭元素，并返回ok；否則返回errorqueueptr p;if(q.rear =q.front ) return err

28、or;p=q.front->next; e=p->data ; /取隊頭元素return ok;四、利用循環(huán)彈出隊尾元素的函數(shù)derear status derear(linkqueue &q,qelemtype &e)/若隊列不空，利用循環(huán)彈出q的隊尾元素，并返回ok；否則返回errorqueueptr p;if(q.rear =q.front ) return error;p=q.rear;while(q.front->next!=p)dequeue(q,e); /刪除隊頭元素enqueue(q,e); /將刪除的隊頭元素插入隊尾dequeue(q,e);

29、 /將原來的隊尾元素彈出，相當(dāng)于棧的功能return ok;五、判斷隊列是否為空的函數(shù)queueempty status queueempty(linkqueue q) /若隊列q為空隊列，則返回ture，否則返回falseif(q.rear = q.front ) return true; else return false; 六、在實現(xiàn)輸出隊列的結(jié)點功能時，定義了從隊頭到隊尾依次對隊列中每個元素調(diào)用函數(shù)visit()的遍歷函數(shù)queuetraverse status queuetraverse(linkqueue q,status (*visit)(qelemtype) /從隊頭到隊尾依次

30、對隊列q中每個元素調(diào)用函數(shù)visit()。一旦visit失敗，則操作失敗。queueptr p=q.front->next ;if(q.rear =q.front ) printf("空隊列n");elsewhile(p!=null )(*visit) (p->data );p=p->next;return ok; 七、輸出隊列元素的輸出函數(shù)printqelem。status printqelem (qelemtype e)printf("step:%d to (%d,%d)n",e.ord,e.seat.x,e.seat.y);ret

31、urn ok;3 構(gòu)建迷宮找出迷宮的通路 在實現(xiàn)構(gòu)建迷宮的功能中，利用srand(time(null)使計算機(jī)自動讀取自己的時鐘獲得seed值，獲得真正的隨機(jī)數(shù)，利用循環(huán)調(diào)用函數(shù)rand()再對2取余，只獲得數(shù)0和1也就是迷宮中的墻和通路，再調(diào)用函數(shù)printqelem輸出初始迷宮。調(diào)用函數(shù)nextpos，找通路的時候向前走一步，再調(diào)用函數(shù)passmaze，找出迷宮的一條通路。 postype nextpos(postype position,elemtype direction)/移動到下一格,向下走一步postype result;result=position;switch (direc

32、tion)case 1:result.y+;break; /向右走case 2:result.x+;break; /向下走case 3:result.y-;break; /向左走case 4:result.x-;break; /向上走return result; status passmaze(mazetype &maze,postype start,postype end,linkqueue &q)（同上）第四章 調(diào)試分析與測試結(jié)果4.1 調(diào)試分析我在調(diào)試程序的過程中遇到的問題是當(dāng)迷宮的路可通時，輸出的所走路徑是亂碼，主要問題是如果判斷出一個通道塊不可通時，已經(jīng)把它放入隊列當(dāng)

33、中，如果再把它彈出時不能像棧那個樣直接調(diào)用出棧函數(shù)，因為棧是先進(jìn)后出的存儲結(jié)構(gòu)，最新壓入的元素就能直接取出，而對于隊列來說新入隊的元素放在了隊尾，而出隊函數(shù)是把隊頭元素給輸出，不是新入隊的元素。因此，如果要用隊列模擬棧的功能，要解決的問題是，從隊頭開始依次將隊列的隊頭元素給輸出，再把該元素放入隊列當(dāng)中，只到遇到新插入的元素，只把它彈出，就是把那個不可通的通道給彈出了，再往后退一步。修改過這個地方之后當(dāng)路徑可通時，輸出的所走路徑就不是亂碼而是真正所走的通道塊坐標(biāo)。 編譯程序，出現(xiàn)有迷宮的界面，如下圖1所示，按提示輸入迷宮的入口位置坐標(biāo)和出口位置坐標(biāo)，再運(yùn)行程序。如果迷宮有通路會輸出“迷宮可通，路

34、徑蹤跡如下：”，輸出走過之后的迷宮，然后再輸出具體路徑，如下圖2所示。如果迷宮不可通時，會輸出“迷宮不可通，路徑蹤跡如下：”，輸出走過之后的迷宮，如下圖3所示。如果迷宮沒有入口時，會輸出“當(dāng)前迷宮沒有入口”，“迷宮不可通，路徑蹤跡如下：”輸出迷宮，如下圖4所示。4.2 測試結(jié)果程序運(yùn)行的初始界面： 圖1迷宮可通時的界面： 圖2迷宮不可通時的界面： 圖3 迷宮沒有入口時的界面： 圖4 第五章 總結(jié) 通過這次的課程設(shè)計作業(yè)，讓我真正的知道了棧的先進(jìn)后出的存儲結(jié)構(gòu)特點和隊列的先進(jìn)先出的存儲結(jié)構(gòu)特點的區(qū)別，而做迷宮求解的問題當(dāng)中最好用的存儲結(jié)構(gòu)是棧，如果用隊列做為存儲結(jié)構(gòu)，就要利用循環(huán)來讓隊列模擬棧的

35、先進(jìn)后出的存儲結(jié)構(gòu)特點。 還讓我知道了用計算機(jī)求解迷宮時，用的是“窮舉求解”的方法，即從入中出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要用一個后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，在求迷宮通路的算法中最好是應(yīng)用“棧”，如果要用“隊列”的話，就要用隊列來模擬棧的存儲結(jié)構(gòu)特點。參考文獻(xiàn)： 數(shù)據(jù)結(jié)構(gòu)（c語言版）嚴(yán)蔚敏 吳偉民 清華大學(xué)出版社 數(shù)據(jù)結(jié)構(gòu)題集（c語言版）嚴(yán)蔚敏 吳偉民 米寧 清華大學(xué)出版社 附錄：源程序#include<stdio.h>#incl

36、ude<malloc.h>#include<stdlib.h>#include<time.h>#include<math.h>/函數(shù)狀態(tài)碼定義#define true 1#define false 0#define ok 1#define error 0#define infeasible -1#define null 0 /墻或通路及前進(jìn)方向符號定義#define wall 0 /代表當(dāng)前格子是墻#define path 1 /代表是通路且未走過#define right -1 /代表是通路且從其向右走#define down -2 /代表是通

37、路且從其向下走#define left -3 /代表是通路且從其向左走#define up -4 /代表是通路且從其向上走#define back -5 /代表是通路且從其后退一步#define destination -6 /代表當(dāng)前格子是通路且是目標(biāo)位置typedef int mazetype1010; /最外鑿初始化成墻，實際含8*8個格子typedef int status;typedef int elemtype; /迷宮數(shù)組中的元素類型/單鏈隊列-隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)/typedef struct int x;int y;postype;/迷宮中坐標(biāo)的位置typedef struct

38、int ord; /通道塊在路徑上的序號postype seat; /通道塊在迷宮中的坐標(biāo)位置int di; /從此通道塊走向下一通道塊的方向qelemtype; /隊列中元素類型typedef struct qnodeqelemtype data;struct qnode *next;qnode,*queueptr; /隊列結(jié)點typedef structqueueptr front; /隊頭指針queueptr rear; /隊尾指針linkqueue;status initqueue (linkqueue &q) /構(gòu)造一個空隊列q,隊列有一個頭結(jié)點q.front=(queuep

39、tr)malloc(sizeof(qnode);q.rear=q.front;if(!q.front) exit(overflow); /存儲分配失敗q.front->next=null;return ok;/initqueuestatus destroyqueue(linkqueue &q) /銷毀隊列qwhile(q.front)q.rear = q.front->next;free(q.front);q.front = q.rear;return ok;/destroyqueuestatus enqueue(linkqueue &q,qelemtype e)

40、/插入元素e為q的新的對尾元素 queueptr p;p=(queueptr)malloc(sizeof(qnode);if(!p) exit (overflow); /存儲分配失敗p->data = e;p->next = null;q.rear ->next = p;q.rear = p;return ok;/enqueuestatus dequeue(linkqueue &q,qelemtype &e) /若隊列不空,則刪除q的對頭元素,用e返回其值,并返回ok;否則返回errorqueueptr p;if (q.front = q.rear ) ret

41、urn error;p=q.front ->next ;e=p->data ;q.front ->next =p->next ;if(q.rear = p) /判斷刪除后隊列是否為空q.rear =q.front ; /隊列已為空free (p);return ok;/dequeuestatus gethead(linkqueue q,qelemtype &e) /若隊列不空，則用e返回q的隊頭元素，并返回ok；否則返回errorqueueptr p;if(q.rear =q.front ) return error;p=q.front->next; e=

42、p->data ; /取隊頭元素return ok;/getheadstatus getrear(linkqueue q,qelemtype &e) /若隊列不空，則用e返回q的隊尾元素，并返回ok；否則返回errorqueueptr p;if(q.rear =q.front ) return error;p=q.rear; e=p->data ; /取隊尾元素return ok;/getrearstatus derear(linkqueue &q,qelemtype &e)/若隊列不空，利用循環(huán)彈出q的隊尾元素，并返回ok；否則返回errorqueuept

43、r p;if(q.rear =q.front ) return error;p=q.rear;while(q.front->next!=p)dequeue(q,e); /刪除隊頭元素enqueue(q,e); /將刪除的隊頭元素插入隊尾dequeue(q,e); /將原來的隊尾元素彈出，相當(dāng)于棧的功能return ok;/derearstatus queueempty(linkqueue q) /若隊列q為空隊列，則返回ture，否則返回falseif(q.rear = q.front ) return true; else return false;/queueemptystatus

44、queuetraverse(linkqueue q,status (*visit)(qelemtype) /從隊頭到隊尾依次對隊列q中每個元素調(diào)用函數(shù)visit()。一旦visit失敗，則操作失敗。queueptr p=q.front->next ;if(q.rear =q.front ) printf("空隊列n");elsewhile(p!=null )(*visit) (p->data );p=p->next;return ok;/queuetraversestatus printqelem (qelemtype e)printf("ste

45、p:%d to (%d,%d)n",e.ord,e.seat.x,e.seat.y);return ok;/printqelem/- 迷宮求解的具體算法 -/status makemaze(mazetype &maze) /生成迷宮,"0"表示通path，"1"表示不通wallpostype m;srand(time(null); /使計算機(jī)自動讀取自己的時間獲得seed值，獲得真正的隨機(jī)數(shù)for(m.y=0;m.y<=9;m.y+)maze0m.y=wall;maze9m.y=wall; for(m.x=1;m.x<=8;

46、m.x+)mazem.x0=wall;mazem.x9=wall; for(m.x=1;m.x<=8;m.x+)for(m.y=1;m.y<=8;m.y+)mazem.xm.y=rand()%2;/隨機(jī)取到0到rand_max之間的任何數(shù)，對2取余是只產(chǎn)生0，1，就是迷宮中的墻和路return ok;/makemazevoid printmaze(mazetype maze)/打印迷宮int x,y;printf(" ");for(x=0;x<=9;x+)printf(" %d",x);printf("n");for

47、(x=0;x<=9;x+)printf("%d",x);for(y=0;y<=9;y+)switch(mazexy)case wall:printf("");break;case path:printf(" ");break;case right:printf("");break;case down: printf("");break; case left: printf("");break; case up: printf("");break;case back: printf(" ");break;case destination:printf("");break;default:printf("errorn");exit(-1);printf("n");/printmazepostype nextpos(postype position,elemtype direction)/移動到下一格,向下走一步postype result;result=position;switch (direction)case 1:result.y+;break; /