迷宮問題 火車車廂重排問題 實(shí)驗(yàn)報(bào)告材料

上傳人:仙*** 文檔編號(hào):85224714 上傳時(shí)間:2022-05-05 格式:DOC 頁數(shù):9 大?。?54.50KB
收藏 版權(quán)申訴 舉報(bào) 下載
迷宮問題 火車車廂重排問題 實(shí)驗(yàn)報(bào)告材料_第1頁
第1頁 / 共9頁
迷宮問題 火車車廂重排問題 實(shí)驗(yàn)報(bào)告材料_第2頁
第2頁 / 共9頁
迷宮問題 火車車廂重排問題 實(shí)驗(yàn)報(bào)告材料_第3頁
第3頁 / 共9頁

下載文檔到電腦,查找使用更方便

10 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《迷宮問題 火車車廂重排問題 實(shí)驗(yàn)報(bào)告材料》由會(huì)員分享,可在線閱讀,更多相關(guān)《迷宮問題 火車車廂重排問題 實(shí)驗(yàn)報(bào)告材料(9頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。

1、word實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱:數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二實(shí)驗(yàn)名稱:棧和隊(duì)列班級(jí):000學(xué)號(hào):000某某:神刀公子時(shí)間:一、問題描述1迷宮問題問題描述這是心理學(xué)中的一個(gè)經(jīng)典問題。心理學(xué)家把一只老鼠從一個(gè)無頂蓋的大盒子的入口處放入,讓老鼠自行找到出口出來。迷宮中設(shè)置很多障礙阻止老鼠前行,迷宮唯一的出口處放有一塊奶酪,吸引老鼠找到出口。簡而言之,迷宮問題是解決從布置了許多障礙的通道中尋找出路的問題。此題設(shè)置的迷宮如圖1所示。圖1 迷宮示意圖迷宮四周設(shè)為墻;無填充處,為可通處。設(shè)每個(gè)點(diǎn)有四個(gè)可通方向,分別為東、南、西、北。左上角為入口。右下角為出口。迷宮有一個(gè)入口,一個(gè)出口。設(shè)計(jì)程序求解迷宮的一條通路。根本要求l 設(shè)

2、計(jì)迷宮的存儲(chǔ)結(jié)構(gòu)。l 設(shè)計(jì)通路的存儲(chǔ)結(jié)構(gòu)。l 設(shè)計(jì)求解通路的算法。l 設(shè)計(jì)迷宮顯示和通路的顯示方式。l 輸入:迷宮、入口與出口可在程序中設(shè)定,也可從鍵盤輸入。l 輸出:迷宮、入口、出口與通路路徑。思考l 假如每個(gè)點(diǎn)有8個(gè)試探方向東、東南、南、西南、西、西北、北、東北,如何修改程序?l 如何求得所有通路?l 如何求得最短通路?2火車車廂重排問題問題描述一列貨運(yùn)列車共有n節(jié)車廂,每節(jié)車廂將停放在不同的車站。假定n個(gè)車站的編號(hào)分別為1n,即貨運(yùn)列車按照第n站至第1站的次序經(jīng)過這些車站。為了便于從列車上卸掉相應(yīng)的車廂,車廂的編號(hào)應(yīng)與車站的編號(hào)一樣,這樣,在每個(gè)車站只要卸掉最后一節(jié)車廂。所以,給定任意次

3、序的車廂,必須重新排列它們。車廂的重排工作可以通過轉(zhuǎn)軌站完成。在轉(zhuǎn)軌站中有一個(gè)入軌、一個(gè)出軌和k個(gè)緩沖軌,緩沖軌位于入軌和出軌之間。假定緩沖軌按先進(jìn)先出的方式運(yùn)作,設(shè)計(jì)算法解決火車車廂重排問題。根本要求l 設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)表示n個(gè)車廂、k個(gè)緩沖軌以與入軌和出軌;l 設(shè)計(jì)并實(shí)現(xiàn)車廂重排算法;l 分析算法的時(shí)間性能。思考l 如果緩沖軌按后進(jìn)先出的方式工作,即用棧表示緩沖軌,應(yīng)如何解決火車車廂重排問題?二、 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)迷宮問題和火車重排問題可以通過棧與隊(duì)列實(shí)現(xiàn)的。迷宮的進(jìn)出和車廂的出入軌和緩沖軌主要是對(duì)棧與隊(duì)列的判斷和操作。 int empty( STLink top,int n) /*判斷是否為空*

4、/ return (topn=NULL); int push(STLink top,int A,int m) /*入棧*/ STLink p;if(!(p=(STLink)malloc(LEN)return 0;else p-data=A;p-link=topm;topm=p;return 1; int pop(STLink top,int m) /*出棧*/ int A;STLink p;p=topm; A=p-data;topm=topm-link;free(p);return A;struct Node /定義隊(duì)列int data;Node* next;三、算法設(shè)計(jì)1.迷宮問題:進(jìn)入格子

5、后,需要判斷此時(shí)格子位置周圍障礙物的位置,對(duì)其進(jìn)展壓棧,判斷,然后看是否滿足條件,滿足就進(jìn)棧,不滿足就彈出,然后輸出不能通過建立迷宮:typedef struct LStack Element elem;struct LStack *next;*PLStack;int InitStack(PLStack &S)S=NULL;return 1;int StackEmpty(PLStack S)if(S=NULL)return 1;elsereturn 0;int Push(PLStack &S, Element e)PLStack p;p=(PLStack)malloc(sizeof(LStac

6、k);p-elem=e;p-next=S;S=p;return 1;int Pop(PLStack &S,Element &e) PLStack p;if(!StackEmpty(S)e=S-elem;p=S;S=S-next;free(p);return 1;elsereturn 0;1迷宮線路的判斷和尋找方法void MazePath(struct mark start,struct mark end,int mazeMN,int diradd42)int i,j,d;int a,b;Element elem,e;PLStack S1, S2;InitStack(S1);InitStack

7、(S2);mazestart.xstart.y=2;elem.x=start.x;elem.y=start.y;elem.d=-1;Push(S1,elem);while(!StackEmpty(S1)Pop(S1,elem);i=elem.x;j=elem.y;d=elem.d+1; while(d(%d,%d,%d),e.x,e.y,e.d);return; if(mazeab=0) mazeab=2; elem.x=i;elem.y=j;elem.d=d;Push(S1,elem); i=a; j=b;d=-1;d+;printf(沒找到走出此迷宮的路徑n);2.火車重排問題1建立火車車

8、廂的隊(duì)列 LinkQueue:LinkQueue()Node* s=new Node;s-next=NULL;front=rear=s;LinkQueue:LinkQueue()Node* p=front;while(p!=NULL) Node*q=p; p=p-next; delete q; void LinkQueue:EnQueue(int x)Node* s=new Node;s-data=x;s-next=NULL;rear-next=s;rear=s;int LinkQueue:DeQueue()if(!empty() /隊(duì)列不空才能出隊(duì)Node* p=new Node;p=fro

9、nt-next;int x=p-data;if(p-next=NULL)rear=front;delete p;return x;void LinkQueue:Trans()Node* p=front-next;while(p) if(p=NULL) break;elsecoutdatanext;2火車進(jìn)入緩沖軌的判斷 void PermuteTrans(int* arr,LinkQueue* a,int n,int k)int i=0;bool flag=true; /設(shè)置標(biāo)志,初始為真while(in & flag) /當(dāng)還有車廂沒有進(jìn)入緩沖軌時(shí)flag=false; /改變標(biāo)志for(i

10、nt j=0;jk;j+)if(aj.GetRear()next=NULL)/如果某條緩沖軌道的第一個(gè)車廂的編號(hào)小于即將進(jìn)來的車廂編號(hào),那么他就可以進(jìn)入軌道/或者某條緩沖軌道空置的時(shí)候也可以進(jìn)入軌道aj.EnQueue(arri); /入隊(duì)列flag=true; /改變標(biāo)志i+; /下標(biāo)加一break;if(flag) /如果全部進(jìn)入軌道,說明可以排cout1endl; for (int j=0;jk;j+) cout第(j+1)個(gè)緩存軌中的列車排序?yàn)閑ndl; aj.Trans(); coutendl; else /否如此排不了cout0endl;四、界面設(shè)計(jì)1.對(duì)迷宮入口的提示輸入,對(duì)迷宮

11、路徑的輸出printf(輸入入口的橫坐標(biāo),縱坐標(biāo)逗號(hào)隔開n);scanf(%d,%d,&start.x,&start.y);printf(n0=東 1=南 2=西 3=北 4為走出迷宮n通路為:(行坐標(biāo),列坐標(biāo),方向)n);cout請輸入車廂數(shù)n和緩沖軌數(shù)k:n;cout請輸入列車排序:k;cout第(j+1)個(gè)緩存軌中的列車排序?yàn)閑ndl; aj.Trans(); coutendl;五、運(yùn)行測試與分析(1) 建立迷宮2.輸出路徑六、實(shí)驗(yàn)收獲與思考通過本次實(shí)驗(yàn),進(jìn)一步增強(qiáng)了對(duì)棧和隊(duì)列的理解,明白的棧的先進(jìn)后出和隊(duì)列先進(jìn)先出的方式,對(duì)壓棧和出入棧與隊(duì)列有了深刻認(rèn)識(shí)。教師評(píng)分:教師簽字:9 / 9

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!