數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--迷宮問(wèn)題隊(duì)列(已修改)
2025-01-30 06:22 本頁(yè)面
【正文】 合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告2012 ～2013 學(xué)年第 二 學(xué)期課程數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱(chēng)迷宮問(wèn)題（隊(duì)列）學(xué)生姓名朱鵬飛學(xué)號(hào)1104011011專(zhuān)業(yè)班級(jí)計(jì)算機(jī)科學(xué)與技術(shù)11級(jí)（3）班指導(dǎo)教師李紅2013 年 3 月題目：迷宮問(wèn)題（隊(duì)列）以一個(gè)m*n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。要求：首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的隊(duì)列，然后編寫(xiě)一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向，如：對(duì)于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。測(cè)試數(shù)據(jù)：迷宮的測(cè)試數(shù)據(jù)如下：左下角（1，1）為入口，右下角（8，9）為出口。選做內(nèi)容：（1）編寫(xiě)遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路一、 問(wèn)題分析和任務(wù)定義：從題目可知，迷宮問(wèn)題主要是考察隊(duì)列操作和圖的遍歷算法?？梢苑纸獬梢韵聨讉€(gè)問(wèn)題：，若是一個(gè)個(gè)的將數(shù)據(jù)輸入，那么一個(gè) m*n的二維數(shù)組要想快速的輸入進(jìn)去是很麻煩的，那么就應(yīng)該讓計(jì)算機(jī)自動(dòng)生成一個(gè)這樣的迷宮。，這樣就會(huì)遇到一個(gè)比較大的問(wèn)題。那就是，在尋找的過(guò)程當(dāng)中，當(dāng)前隊(duì)尾節(jié)點(diǎn)的其余三個(gè)方向上均都是墻，這樣就無(wú)法再走下去了，必須要返回。由于是用隊(duì)列存儲(chǔ)的，不能直接將隊(duì)尾元素刪除，那就應(yīng)該讓其他元素從隊(duì)頭出隊(duì)構(gòu)成另外一條隊(duì)列。這樣，就可以將該結(jié)點(diǎn)從隊(duì)列當(dāng)中刪除了。，要輸出經(jīng)過(guò)結(jié)點(diǎn)的方向，對(duì)于任意的一個(gè)位置有四個(gè)方向，所以對(duì)于隊(duì)列中的么每一個(gè)結(jié)點(diǎn)設(shè)置一個(gè)方向的標(biāo)記量，表示走向下一結(jié)點(diǎn)的方向，當(dāng)前加到隊(duì)尾的元素的方向設(shè)置為0，一旦有新元素入隊(duì)，就對(duì)隊(duì)尾元素的方向進(jìn)行修改。：因?yàn)楫?dāng)沿著每個(gè)方向前進(jìn)到某一位置時(shí)，不再有通路之后，就會(huì)把該節(jié)點(diǎn)從隊(duì)列中刪除，同時(shí)會(huì)將該位置上的值修改，從而保證下次改位置上的結(jié)點(diǎn)不會(huì)再入隊(duì)。如果不存在通路，必然會(huì)一直返回到初始狀態(tài)（隊(duì)列為空）。，所以一旦找到終點(diǎn)，就可以結(jié)束需找了。二、 數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)：（一）數(shù)據(jù)結(jié)構(gòu)的選擇：（根據(jù)實(shí)驗(yàn)的要求）：typedef struct { int x。 int y。}Weizhi。//迷宮中每一個(gè)結(jié)點(diǎn)的位置：typedef struct{ Weizhi wz。 int fangxiang。//對(duì)方向的選定，對(duì)不同的方向設(shè)置不同的數(shù)值}Yuansu。//隊(duì)列當(dāng)中元素：typedef struct Node{ Yuansu data。 struct Node *next。}Jiedian。//鏈隊(duì)列中的結(jié)點(diǎn)數(shù)據(jù)類(lèi)型：typedef struct { Jiedian *front。//隊(duì)頭指針 Jiedian *rear。//隊(duì)尾指針}Liandui。（二）概要設(shè)計(jì)：設(shè)計(jì)思路：首先構(gòu)建一個(gè)空隊(duì)列，同時(shí)由計(jì)算機(jī)產(chǎn)生一個(gè)迷宮；在判斷迷宮的指定出入口是否存在，若不存在，則結(jié)束這次查找并輸出提示信息；若存在，則進(jìn)行下一步，搜索通路，有通路直至到達(dá)終點(diǎn)，無(wú)通路就退回到起點(diǎn)。收索過(guò)程中，遇到前面不再有出口的時(shí)候，就要使當(dāng)前隊(duì)尾結(jié)點(diǎn)出隊(duì)，于是就要對(duì)當(dāng)前隊(duì)列從隊(duì)頭到倒數(shù)第二個(gè)結(jié)點(diǎn)依次轉(zhuǎn)移，釋放出隊(duì)尾結(jié)點(diǎn)。從完成的功能上看，1. 實(shí)現(xiàn)程序與用戶(hù)操作的界面設(shè)計(jì)；2. 用非遞歸算法實(shí)現(xiàn)以鏈隊(duì)列來(lái)存儲(chǔ)訪(fǎng)問(wèn)過(guò)的通路結(jié)點(diǎn)，找出通路；3. 構(gòu)建迷宮，顯示迷宮。于是，就構(gòu)建出以下幾個(gè)模塊之間的關(guān)系架構(gòu)： 主模塊 隊(duì)列存儲(chǔ)功能 迷宮搜索功能 建空對(duì)列 出隊(duì)、入隊(duì)、修改隊(duì)列 構(gòu)建、輸出迷宮 從迷宮的起點(diǎn)開(kāi)始尋找通路 圖1. 模塊間的關(guān)系三、 詳細(xì)設(shè)計(jì)和編碼：從上面的概要設(shè)計(jì)可以看出，要具體的實(shí)現(xiàn)這些功能，為實(shí)現(xiàn)方便構(gòu)造以下幾個(gè)全局變量：int m=0,n=0。//用來(lái)設(shè)置長(zhǎng)方陣迷宮的大小int a[12][12]。//用來(lái)存放迷宮中每一個(gè)結(jié)點(diǎn)的信息Liandui *S。//存放結(jié)點(diǎn)信息的隊(duì)列同時(shí)，必須要構(gòu)造這些相應(yīng)的函數(shù)：（一） 隊(duì)列操作1. //建空隊(duì)
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1