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