《迷宮問題 火車車廂重排問題 實(shí)驗(yàn)報(bào)告》由會(huì)員分享，可在線閱讀，更多相關(guān)《迷宮問題 火車車廂重排問題 實(shí)驗(yàn)報(bào)告（11頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、. .
實(shí)驗(yàn)報(bào)告
實(shí)驗(yàn)名稱：數(shù)據(jù)構(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è)可通方向，分別為東、南、西、北
2、。左上角為入口。右下角為出口。迷宮有一個(gè)入口，一個(gè)出口。設(shè)計(jì)程序求解迷宮的一條通路。
②根本要求
l 設(shè)計(jì)迷宮的存儲(chǔ)構(gòu)造。
l 設(shè)計(jì)通路的存儲(chǔ)構(gòu)造。
l 設(shè)計(jì)求解通路的算法。
l 設(shè)計(jì)迷宮顯示和通路的顯示方式。
l 輸入：迷宮、入口及出口可在程序中設(shè)定，也可從鍵盤輸入。
l 輸出：迷宮、入口、出口及通路路徑。
③思考
l 假設(shè)每個(gè)點(diǎn)有8個(gè)試探方向〔東、東南、南、西南、西、西北、北、東北〕，如何修改程序.
l 如何求得所有通路.
l 如何求得最短通路.
〔2〕火車車廂重排問題
①問題描述
一列貨運(yùn)列車共有n節(jié)車廂，每節(jié)車廂將停放在不同的車站。假定n個(gè)車站的編號(hào)分別為1
3、～n，即貨運(yùn)列車按照第n站至第1站的次序經(jīng)過這些車站。為了便于從列車上卸掉相應(yīng)的車廂，車廂的編號(hào)應(yīng)與車站的編號(hào)一樣，這樣，在每個(gè)車站只要卸掉最后一節(jié)車廂。所以，給定任意次序的車廂，必須重新排列它們。
車廂的重排工作可以通過轉(zhuǎn)軌站完成。在轉(zhuǎn)軌站中有一個(gè)入軌、一個(gè)出軌和k個(gè)緩沖軌，緩沖軌位于入軌和出軌之間。假定緩沖軌按先進(jìn)先出的方式運(yùn)作，設(shè)計(jì)算法解決火車車廂重排問題。
②根本要求
l 設(shè)計(jì)存儲(chǔ)構(gòu)造表示n個(gè)車廂、k個(gè)緩沖軌以及入軌和出軌；
l 設(shè)計(jì)并實(shí)現(xiàn)車廂重排算法；
l 分析算法的時(shí)間性能。
③思考
l 如果緩沖軌按后進(jìn)先出的方式工作，即用棧表示緩沖軌，應(yīng)如何解決火車車廂重排問題.
4、
二、 數(shù)據(jù)構(gòu)造設(shè)計(jì)
迷宮問題和火車重排問題可以通過棧與隊(duì)列實(shí)現(xiàn)的。迷宮的進(jìn)出和車廂的出入軌和緩沖軌主要是對(duì)棧與隊(duì)列的判斷和操作。
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{ /定義隊(duì)列
int data;
Node* next;
};
三、算法設(shè)計(jì)
1.迷宮問題：
進(jìn)入格子后，需要判斷此時(shí)格子位置周圍障礙物的位置，對(duì)其進(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(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通路為:(行坐標(biāo),列坐標(biāo),方向)\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〕建立火車車廂的隊(duì)列
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、{ ///隊(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;
else{
cout<data<<" ";
p=p->next;}
}
〔2〕火車進(jìn)入緩沖軌
13、的判斷
void PermuteTrans(int* arr,LinkQueue* a,int n,int k){
int i=0;
bool flag=true; ///設(shè)置標(biāo)志，初始為真
while(inext==NULL)
///如果某條緩沖軌道的第一個(gè)車廂的編號(hào)小于即將進(jìn)來的車廂編號(hào)，那么他就可以進(jìn)入軌
14、道
///或者某條緩沖軌道空置的時(shí)候也可以進(jìn)入軌道
{
a[j].EnQueue(arr[i]); ///入隊(duì)列
flag=true; ///改變標(biāo)志
i++; ///下標(biāo)加一
break;
}
}
}
if(flag) ///如果全部進(jìn)入軌道，說明可以排
{cout<<1<
15、.Trans();
cout<
16、l;
cin>>n;
cout<<"請(qǐng)輸入列車排序："<>k;
{cout<<"第"<<(j+1)<<"個(gè)緩存軌中的列車排序?yàn)?<
迷宮問題 火車車廂重排問題 實(shí)驗(yàn)報(bào)告
