《迷宮問題 火車車廂重排問題 實驗報告材料》由會員分享，可在線閱讀，更多相關(guān)《迷宮問題 火車車廂重排問題 實驗報告材料（9頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、word
實驗報告
實驗名稱：數(shù)據(jù)結(jié)構(gòu)實驗二
實驗名稱：棧和隊列
班級：000
學(xué)號：000
某某：神刀公子
時間：
一、問題描述
〔1〕迷宮問題
①問題描述
這是心理學(xué)中的一個經(jīng)典問題。心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口處放入，讓老鼠自行找到出口出來。迷宮中設(shè)置很多障礙阻止老鼠前行，迷宮唯一的出口處放有一塊奶酪，吸引老鼠找到出口。
簡而言之，迷宮問題是解決從布置了許多障礙的通道中尋找出路的問題。此題設(shè)置的迷宮如圖1所示。
圖1 迷宮示意圖
迷宮四周設(shè)為墻；無填充處，為可通處。設(shè)每個點有四個可通方向，分別為東、南、西、北。左上角為入口。右下角為出口。迷
2、宮有一個入口，一個出口。設(shè)計程序求解迷宮的一條通路。
②根本要求
l 設(shè)計迷宮的存儲結(jié)構(gòu)。
l 設(shè)計通路的存儲結(jié)構(gòu)。
l 設(shè)計求解通路的算法。
l 設(shè)計迷宮顯示和通路的顯示方式。
l 輸入：迷宮、入口與出口可在程序中設(shè)定，也可從鍵盤輸入。
l 輸出：迷宮、入口、出口與通路路徑。
③思考
l 假如每個點有8個試探方向〔東、東南、南、西南、西、西北、北、東北〕，如何修改程序？
l 如何求得所有通路？
l 如何求得最短通路？
〔2〕火車車廂重排問題
①問題描述
一列貨運列車共有n節(jié)車廂，每節(jié)車廂將停放在不同的車站。假定n個車站的編號分別為1～n，即貨運列車按照第n站至第1
3、站的次序經(jīng)過這些車站。為了便于從列車上卸掉相應(yīng)的車廂，車廂的編號應(yīng)與車站的編號一樣，這樣，在每個車站只要卸掉最后一節(jié)車廂。所以，給定任意次序的車廂，必須重新排列它們。
車廂的重排工作可以通過轉(zhuǎn)軌站完成。在轉(zhuǎn)軌站中有一個入軌、一個出軌和k個緩沖軌，緩沖軌位于入軌和出軌之間。假定緩沖軌按先進(jìn)先出的方式運作，設(shè)計算法解決火車車廂重排問題。
②根本要求
l 設(shè)計存儲結(jié)構(gòu)表示n個車廂、k個緩沖軌以與入軌和出軌；
l 設(shè)計并實現(xiàn)車廂重排算法；
l 分析算法的時間性能。
③思考
l 如果緩沖軌按后進(jìn)先出的方式工作，即用棧表示緩沖軌，應(yīng)如何解決火車車廂重排問題？
二、 數(shù)據(jù)結(jié)構(gòu)設(shè)計
迷宮
4、問題和火車重排問題可以通過棧與隊列實現(xiàn)的。迷宮的進(jìn)出和車廂的出入軌和緩沖軌主要是對棧與隊列的判斷和操作。
int empty( STLink top[],int n) /*判斷是否為空*/
{
return (top[n]==NULL);
}
int push(STLink top[],int A,int m) /*入棧*/
{
STLink p;
if(!(p=(STLink)malloc(LEN)))
return 0;
else
{
p->data=A;
p->link=top[m];
top[m]=p;
ret
5、urn 1;
}
}
int pop(STLink top[],int m) /*出棧*/
{
int A;
STLink p;
p=top[m];
A=p->data;
top[m]=top[m]->link;
free(p);
return A;
}
struct Node{ /定義隊列
int data;
Node* next;
};
三、算法設(shè)計
1.迷宮問題：
進(jìn)入格子后，需要判斷此時格子位置周圍障礙物的位置，對其進(jìn)展壓棧，判斷，然后看是否滿足條件，滿足就進(jìn)棧，不滿足就彈出，然后輸出不能通過
6、建立迷宮：
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;
else
return 0;
}
int Push(PLStack &S, Element e)
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p-
7、>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;
}
else
return 0;
〔1〕迷宮線路的判斷和尋找方法
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
int i,j,d;in
8、t a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.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+diradd[d][0];
b=j+diradd[d][1];
if(a=
9、=end.x && b==end.y && maze[a][b]==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.
10、d);
}
return;
}
if(maze[a][b]==0)
{
maze[a][b]=2;
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
i=a;
j=b;
d=-1;
}
d++;
}
}
printf("沒找到走出此迷宮的路徑\n");
}
2.火車重排問題
〔1〕建立火車車廂的隊列
LinkQueue::LinkQueue(){
Node* s=new Node;
s->next=NULL;
front=rear=s;
}
LinkQueue::~LinkQu
11、eue(){
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()){ ///隊列不空才能出
12、隊
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;
else{
cout<data<<" ";
p=p->next;}
}
〔2〕火車進(jìn)入緩沖軌的判斷
void Pe
13、rmuteTrans(int* arr,LinkQueue* a,int n,int k){
int i=0;
bool flag=true; ///設(shè)置標(biāo)志，初始為真
while(inext==NULL)
///如果某條緩沖軌道的第一個車廂的編號小于即將進(jìn)來的車廂編號，那么他就可以進(jìn)入軌道
///或者
14、某條緩沖軌道空置的時候也可以進(jìn)入軌道
{
a[j].EnQueue(arr[i]); ///入隊列
flag=true; ///改變標(biāo)志
i++; ///下標(biāo)加一
break;
}
}
}
if(flag) ///如果全部進(jìn)入軌道，說明可以排
{cout<<1<
15、 cout<>n;
cout<<"請輸入列車排序："<>k;
{cout<<"第"<<(j+1)<<"個緩存軌中的列車排序為"<
迷宮問題 火車車廂重排問題 實驗報告材料
