word實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二實(shí)驗(yàn)名稱(chēng)：棧和隊(duì)列班級(jí)：000學(xué)號(hào)：000某某：神刀公子時(shí)間：一、問(wèn)題描述1迷宮問(wèn)題問(wèn)題描述這是心理學(xué)中的一個(gè)經(jīng)典問(wèn)題。心理學(xué)家把一只老鼠從一個(gè)無(wú)頂蓋的大盒子的入口處放入，讓老鼠自行找到出口出來(lái)。迷宮中設(shè)置很多障礙阻止老鼠前行，迷宮唯一的出口處放有一塊奶酪，吸引老鼠找到出口。簡(jiǎn)而言之，迷宮問(wèn)題是解決從布置了許多障礙的通道中尋找出路的問(wèn)題。此題設(shè)置的迷宮如圖1所示。圖1 迷宮示意圖迷宮四周設(shè)為墻；無(wú)填充處，為可通處。設(shè)每個(gè)點(diǎn)有四個(gè)可通方向，分別為東、南、西、北。左上角為入口。右下角為出口。迷宮有一個(gè)入口，一個(gè)出口。設(shè)計(jì)程序求解迷宮的一條通路。根本要求l 設(shè)計(jì)迷宮的存儲(chǔ)結(jié)構(gòu)。l 設(shè)計(jì)通路的存儲(chǔ)結(jié)構(gòu)。l 設(shè)計(jì)求解通路的算法。l 設(shè)計(jì)迷宮顯示和通路的顯示方式。l 輸入：迷宮、入口與出口可在程序中設(shè)定，也可從鍵盤(pán)輸入。l 輸出：迷宮、入口、出口與通路路徑。思考l 假如每個(gè)點(diǎn)有8個(gè)試探方向東、東南、南、西南、西、西北、北、東北，如何修改程序？l 如何求得所有通路？l 如何求得最短通路？2火車(chē)車(chē)廂重排問(wèn)題問(wèn)題描述一列貨運(yùn)列車(chē)共有n節(jié)車(chē)廂，每節(jié)車(chē)廂將停放在不同的車(chē)站。假定n個(gè)車(chē)站的編號(hào)分別為1n，即貨運(yùn)列車(chē)按照第n站至第1站的次序經(jīng)過(guò)這些車(chē)站。為了便于從列車(chē)上卸掉相應(yīng)的車(chē)廂，車(chē)廂的編號(hào)應(yīng)與車(chē)站的編號(hào)一樣，這樣，在每個(gè)車(chē)站只要卸掉最后一節(jié)車(chē)廂。所以，給定任意次序的車(chē)廂，必須重新排列它們。車(chē)廂的重排工作可以通過(guò)轉(zhuǎn)軌站完成。在轉(zhuǎn)軌站中有一個(gè)入軌、一個(gè)出軌和k個(gè)緩沖軌，緩沖軌位于入軌和出軌之間。假定緩沖軌按先進(jìn)先出的方式運(yùn)作，設(shè)計(jì)算法解決火車(chē)車(chē)廂重排問(wèn)題。根本要求l 設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)表示n個(gè)車(chē)廂、k個(gè)緩沖軌以與入軌和出軌；l 設(shè)計(jì)并實(shí)現(xiàn)車(chē)廂重排算法；l 分析算法的時(shí)間性能。思考l 如果緩沖軌按后進(jìn)先出的方式工作，即用棧表示緩沖軌，應(yīng)如何解決火車(chē)車(chē)廂重排問(wèn)題？二、 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)迷宮問(wèn)題和火車(chē)重排問(wèn)題可以通過(guò)棧與隊(duì)列實(shí)現(xiàn)的。迷宮的進(jìn)出和車(chē)廂的出入軌和緩沖軌主要是對(duì)棧與隊(duì)列的判斷和操作。 int empty( STLink top,int n) /*判斷是否為空*/ 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.迷宮問(wèn)題：進(jìn)入格子后，需要判斷此時(shí)格子位置周?chē)系K物的位置，對(duì)其進(jìn)展壓棧，判斷，然后看是否滿足條件，滿足就進(jìn)棧，不滿足就彈出，然后輸出不能通過(guò)建立迷宮：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(LStack);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(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<4) a=i+diraddd0;b=j+diraddd1;if(a=end.x && b=end.y && mazeab=0) elem.x=i;elem.y=j;elem.d=d;Push(S1,elem);elem.x=a;elem.y=b;elem.d=4; Push(S1,elem);printf("n0=東 1=南 2=西 3=北 4為走出迷宮n通路為:(行坐標(biāo),列坐標(biāo),方向)n");while(S1) Pop(S1,e);Push(S2,e);while(S2)Pop(S2,e);printf(">(%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("沒(méi)找到走出此迷宮的路徑n");2.火車(chē)重排問(wèn)題1建立火車(chē)車(chē)廂的隊(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=front->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;elsecout<<p->data<<" "p=p->next;2火車(chē)進(jìn)入緩沖軌的判斷 void PermuteTrans(int* arr,LinkQueue* a,int n,int k)int i=0;bool flag=true; /設(shè)置標(biāo)志，初始為真while(i<n && flag) /當(dāng)還有車(chē)廂沒(méi)有進(jìn)入緩沖軌時(shí)flag=false; /改變標(biāo)志for(int j=0;j<k;j+)if(aj.GetRear()<arri | aj.front->next=NULL)/如果某條緩沖軌道的第一個(gè)車(chē)廂的編號(hào)小于即將進(jìn)來(lái)的車(chē)廂編號(hào)，那么他就可以進(jìn)入軌道/或者某條緩沖軌道空置的時(shí)候也可以進(jìn)入軌道aj.EnQueue(arri); /入隊(duì)列flag=true; /改變標(biāo)志i+; /下標(biāo)加一break;if(flag) /如果全部進(jìn)入軌道，說(shuō)明可以排cout<<1<<endl; for (int j=0;j<k;j+) cout<<"第"<<(j+1)<<"個(gè)緩存軌中的列車(chē)排序?yàn)?quot;<<endl; aj.Trans(); cout<<endl; else /否如此排不了cout<<0<<endl;四、界面設(shè)計(jì)1.對(duì)迷宮入口的提示輸入，對(duì)迷宮路徑的輸出printf("輸入入口的橫坐標(biāo),縱坐標(biāo)逗號(hào)隔開(kāi)n");scanf("%d,%d",&start.x,&start.y);printf("n0=東 1=南 2=西 3=北 4為走出迷宮n通路為:(行坐標(biāo),列坐標(biāo),方向)n")；cout<<"請(qǐng)輸入車(chē)廂數(shù)n和緩沖軌數(shù)k："<<endl;cin>>n;cout<<"請(qǐng)輸入列車(chē)排序："<<endl; cin>>k;cout<<"第"<<(j+1)<<"個(gè)緩存軌中的列車(chē)排序?yàn)?quot;<<endl; aj.Trans(); cout<<endl;五、運(yùn)行測(cè)試與分析（1） 建立迷宮2.輸出路徑六、實(shí)驗(yàn)收獲與思考通過(guò)本次實(shí)驗(yàn)，進(jìn)一步增強(qiáng)了對(duì)棧和隊(duì)列的理解，明白的棧的先進(jìn)后出和隊(duì)列先進(jìn)先出的方式，對(duì)壓棧和出入棧與隊(duì)列有了深刻認(rèn)識(shí)。教師評(píng)分：教師簽字：9 / 9