計算機科學與工程學院

計算機科學與工程學院《算法與數(shù)據(jù)構造》試驗匯報(四)專業(yè)班級級3E軟件工程試驗地點8號機房學生學號指導教師姚峰學生姓名董婉清試驗時間-05-18試驗項目隊列的應用試驗類別基礎性（√）設計性（）綜合性（）其他（）試驗目的及規(guī)定（1）掌握隊列的特點及其存儲措施；（2）掌握隊列的常見算法和程序?qū)崿F(xiàn)。成績評定表類別評分標準分值得分合計上機體現(xiàn)積極出勤、遵守紀律按規(guī)定完畢設計任務30分程序與匯報程序代碼規(guī)范、功能對的匯報詳實完整、體現(xiàn)收獲70分闡明：評閱教師：姚峰

日期：20年月日實驗內(nèi)容試驗內(nèi)容：火車車廂重排問題。試驗闡明：轉(zhuǎn)軌站示意圖如下：出軌出軌入軌H1H3H2火車車廂重排過程如下：出軌出軌入軌581H1H3H2963742出軌入軌58H1H3H29674321出軌入軌5H1H3H2968754321出軌入軌H1H3H2(a)將369、247依次入緩沖軌(b)將1移至出軌，234移至出軌(c)將8入緩沖軌，5移至出軌(d)將6789移至出軌火車車廂重排算法偽代碼如下：1.分別對k個隊列初始化；1.分別對k個隊列初始化；2.初始化下一種要輸出的車廂編號nowOut=1;3.依次取入軌中的每一種車廂的編號；3.1假如入軌中的車廂編號等于nowOut，則3.1.1輸出該車廂；3.1.2nowOut++；3.2否則，考察每一種緩沖軌隊列for(j=1;j<=k;j++)3.2.1取隊列j的隊頭元素c；3.2.2假如c=nowOut，則3.2.2.1將隊列j的隊頭元素出隊并輸出；3.2.2.2nowOut++；3.3假如入軌和緩沖軌的隊頭元素沒有編號為nowOut的車廂，則3.3.1求不不小于入軌中第一種車廂編號的最大隊尾元素所在隊列編號j;3.3.2假如j存在，則把入軌中的第一種車廂移至緩沖軌j；3.3.3假如j不存在,但有多出一種空緩沖軌,則把入軌中的第一種車廂移至一種空緩沖結束3.3.2假如j不存在，但有多于一種空緩沖軌，則把入軌中的第一種車廂移至一種空緩沖軌；否則車廂無法重排，算法結束；#include<stdlib.h>#include<iostream>usingnamespacestd;structNode{intdata;Node*next;};//LinkQueue.hclassLinkQueue{private:Node*first,*rear;public:LinkQueue();~LinkQueue();voidEnQueue(int);intDeQueue();intGetQueue_head();intGetQueue_rear();intVide_Queue();voidPrint_Queue();};//LinkQueue.cppLinkQueue::LinkQueue()//無T慘¨°構1造¨?函?￥數(shù)oy{Node*s=newNode;s->next=NULL;first=rear=s;}LinkQueue::~LinkQueue()//析?構1函?￥數(shù)oy釋o¨a放¤?空?間?{while(first){Node*p;p=first->next;deletefirst;first=p;}}voidLinkQueue::EnQueue(intx)//隊¨?尾2入¨?隊¨?{Node*s=newNode;s->data=x;s->next=NULL;rear->next=s;rear=s;}intLinkQueue::DeQueue()//隊¨?頭a?¤出?隊¨?{intx;x=first->next->data;Node*p=first->next;first->next=p->next;if(p->next==NULL)rear=first;deletep;returnx;}intLinkQueue::GetQueue_head()//取¨?得ì?隊¨?列￠D第ì¨2一°?個?元a素?的ì?數(shù)oy據(jù)Y{if(first!=rear)return(first->next->data);}intLinkQueue::GetQueue_rear()//取¨?得ì?隊¨?列￠D最á?后¨?一°?個?元a素?的ì?數(shù)oy據(jù)Y{if(first!=rear)return(rear->data);}intLinkQueue::Vide_Queue()//判D斷?隊¨?列￠D是o?否¤?為a空?，ê?若¨?為a空?返¤|ì回?0，ê?若¨?不?為a空?返¤|ì回?1{if(first==rear)return0;elsereturn1;}voidLinkQueue::Print_Queue()//輸o?出?隊¨?列￠D中D所¨′有?D元a素?{Node*p=first->next;while(p){cout<<p->data<<"";p=p->next;}}constintk=3;//假¨′設|¨¨有?D三¨y個?緩o沖?軌¨?intTrainMain(){LinkQueueQ[k];//k個?緩o沖?軌¨?LinkQueueA;//入¨?軌¨?LinkQueueC;//出?軌¨?cout<<"請?輸o?入¨?1~9:"<<endl;intx;for(inti=0;i<9;i++){cin>>x;A.EnQueue(x);//入¨?隊¨?}cout<<"入¨?軌¨?中D的ì?車|ì廂¨￠序¨°列￠D如¨?下?:"<<endl;A.Print_Queue();//輸o?出?入¨?軌¨?中D的ì?車|ì廂¨￠序¨°列￠Dcout<<endl;intnowOut=1;//初?始o?化?￥下?一°?個?要°a輸o?出?的ì?車|ì廂¨￠編ਤ號?nowOut=1while(nowOut!=10){inttemp=nowOut;if(A.GetQueue_head()==nowOut)//如¨?果?入¨?軌¨?A中D的ì?頭a?¤車|ì廂¨￠等쨨于?¨2nowOut，ê?就¨a直?à接¨?輸o?出?該?車|ì廂¨￠，ê?把??該?車|ì廂¨￠放¤?入¨?出?軌¨?C{A.DeQueue();cout<<"A:";A.Print_Queue();cout<<endl;C.EnQueue(nowOut);cout<<"C:";C.Print_Queue();cout<<endl;nowOut++;continue;}else//否¤?則¨°考?察¨?每?一°?個?緩o沖?軌¨?隊¨?列￠D{for(inti=0;i<k;i++){if((Q[i].Vide_Queue()==1)&&(Q[i].GetQueue_head()==nowOut))//如¨?果?第ì¨2i個?緩o沖?軌¨?中D頭a?¤車|ì廂¨￠等쨨于?¨2nowOut，ê?就¨a直?à接¨?輸o?出?該?車|ì廂¨￠，ê?把??該?車|ì廂¨￠放¤?入¨?出?軌¨?C{Q[i].DeQueue();cout<<"Q["<<i<<"]:";Q[i].Print_Queue();cout<<endl;C.EnQueue(nowOut);cout<<"C:";C.Print_Queue();cout<<endl;nowOut++;continue;}}}if(temp==nowOut)//如¨?果?nowOut沒?有?D發(fā)¤?é生|¨2變à?化?￥說|ì明??前??兩￠?種?情¨|況?都?沒?有?D發(fā)¤?é生|¨2，ê?只?好?開a始o?第ì¨2三¨y種?情¨|況?的ì?判D斷?{inty=A.GetQueue_head();intnum=-1;intmax=0;for(inti=0;i<k;i++)//求¨?小?于?¨2入¨?軌¨?中D第ì¨2一°?個?車|ì廂¨￠編ਤ號?的ì?最á?大?¨?隊¨?尾2元a素?所¨′在¨2隊¨?列￠D編ਤ號?i{if((Q[i].Vide_Queue()==1)&&(Q[i].GetQueue_rear()<y)&&(max<Q[i].GetQueue_rear())){max=Q[i].GetQueue_rear();num=i;}}if(num!=-1)//如¨?果?找¨°到ì?該?編ਤ號?i的ì?緩o沖?軌¨?則¨°把??入¨?軌¨?A中D頭a?¤車|ì廂¨￠放¤?入¨?第ì¨2i號?緩o沖?軌¨?中D{A.DeQueue();cout<<"A:";A.Print_Queue();cout<<endl;Q[num].EnQueue(y);cout<<"Q["<<num<<"]:";Q[num].Print_Queue();cout<<endl;continue;}else//否¤?則¨°，ê?判D斷?是o?否¤?有?D緩o沖?軌¨?為a空?，ê?如¨?有?D空?緩o沖?軌¨?，ê?把??入¨?軌¨?A的ì?頭a?¤車|ì廂¨￠放¤?入¨?空?緩o沖?軌¨?中D{for(inti=0;i<k;i++){if(Q[i].Vide_Queue()==0){A.DeQueue();cout<<"A:";A.Print_Queue();cout<<endl;Q[i].EnQueue(y);cout<<"Q["<<i<<"]:";Q[i].Print_Queue();cout<<endl;continue;}}}return-1;//如¨?果?以°?上|?所¨′有?D