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