实验报告04

计算机科学与工程学院《算法与数据结构》实验报告(四)专业班级2016级3E软件工程实验地点8号机房学生学号1605121007指导教师姚峰学生姓名董婉清实验时间2018-05-18实验项目队列的应用实验类别基础性（√）设计性（）综合性（）其它（）实验目的及要求（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明：评阅教师：姚峰日期：20年月日计算机科学与工程学院《算法与数据结构》实验报告2出轨入轨581H1H3H2963742出轨入轨58H1H3H29674321出轨入轨5H1H3H2968754321出轨入轨H1H3H2987654321(a)将369、247依次入缓冲轨(b)将1移至出轨，234移至出轨(c)将8入缓冲轨，5移至出轨(d)将6789移至出轨实验内容实验内容：火车车厢重排问题。实验说明：转轨站示意图如下：火车车厢重排过程如下：火车车厢重排算法伪代码如下：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不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束；出轨入轨581742963987654321H1H3H2计算机科学与工程学院《算法与数据结构》实验报告3#includestdlib.h#includeiostreamusingnamespacestd;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造¨¬函¡¥数ºy{Node*s=newNode;s-next=NULL;first=rear=s;}LinkQueue::~LinkQueue()//析?构1函¡¥数ºy释º¨ª放¤?空?间?{while(first){Node*p;p=first-next;deletefirst;first=p;}}voidLinkQueue::EnQueue(intx)//队¨®尾2入¨?队¨®{Node*s=newNode;计算机科学与工程学院《算法与数据结构》实验报告4s-data=x;s-next=NULL;rear-next=s;rear=s;}intLinkQueue::DeQueue()//队¨®头ª¡¤出?队¨®{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第̨²一°?个?元a素?的Ì?数ºy据Y{if(first!=rear)return(first-next-data);}intLinkQueue::GetQueue_rear()//取¨?得Ì?队¨®列¢D最Á?后¨®一°?个?元a素?的Ì?数ºy据Y{if(first!=rear)return(rear-data);}intLinkQueue::Vide_Queue()//判D断?队¨®列¢D是º?否¤?为a空?，ê?若¨?为a空?返¤¦Ì回?0，ê?若¨?不?为a空?返¤¦Ì回?1{if(first==rear)return0;elsereturn1;}voidLinkQueue::Print_Queue()//输º?出?队¨®列¢D中D所¨´有®D元a素?{Node*p=first-next;while(p){计算机科学与工程学院《算法与数据结构》实验报告5coutp-data;p=p-next;}}constintk=3;//假¨´设¦¨¨有®D三¨y个?缓o冲?轨¨¬intTrainMain(){LinkQueueQ[k];//k个?缓o冲?轨¨¬LinkQueueA;//入¨?轨¨¬LinkQueueC;//出?轨¨¬cout请?输º?入¨?1~9:endl;intx;for(inti=0;i9;i++){cinx;A.EnQueue(x);//入¨?队¨®}cout入¨?轨¨¬中D的Ì?车¦Ì厢¨¢序¨°列¢D如¨?下?:endl;A.Print_Queue();//输º?出?入¨?轨¨¬中D的Ì?车¦Ì厢¨¢序¨°列¢Dcoutendl;intnowOut=1;//初?始º?化¡¥下?一°?个?要°a输º?出?的Ì?车¦Ì厢¨¢编À¨¤号?nowOut=1while(nowOut!=10){inttemp=nowOut;if(A.GetQueue_head()==nowOut)//如¨?果?入¨?轨¨¬A中D的Ì?头ª¡¤车¦Ì厢¨¢等̨¨于®¨²nowOut，ê?就¨ª直¡À接¨®输º?出?该?车¦Ì厢¨¢，ê?把ã?该?车¦Ì厢¨¢放¤?入¨?出?轨¨¬C{A.DeQueue();coutA:;A.Print_Queue();coutendl;C.EnQueue(nowOut);coutC:;C.Print_Queue();coutendl;nowOut++;continue;}else//否¤?则¨°考?察¨¬每?一°?个?缓o冲?轨¨¬队¨®列¢D{计算机科学与工程学院《算法与数据结构》实验报告6for(inti=0;ik;i++){if((Q[i].Vide_Queue()==1)&&(Q[i].GetQueue_head()==nowOut))//如¨?果?第̨²i个?缓o冲?轨¨¬中D头ª¡¤车¦Ì厢¨¢等̨¨于®¨²nowOut，ê?就¨ª直¡À接¨®输º?出?该?车¦Ì厢¨¢，ê?把ã?该?车¦Ì厢¨¢放¤?入¨?出?轨¨¬C{Q[i].DeQueue();coutQ[i]:;Q[i].Print_Queue();coutendl;C.EnQueue(nowOut);coutC:;C.Print_Queue();coutendl;nowOut++;continue;}}}if(temp==nowOut)//如¨?果?nowOut没?有®D发¤¡é生¦¨²变À?化¡¥说¦Ì明¡Â前¡ã两¢?种?情¨¦况?都?没?有®D发¤¡é生¦¨²，ê?只?好?开a始º?第̨²三¨y种?情¨¦况?的Ì?判D断?{inty=A.GetQueue_head();intnum=-1;intmax=0;for(inti=0;ik;i++)//求¨®小?于®¨²入¨?轨¨¬中D第̨²一°?个?车¦Ì厢¨¢编À¨¤号?的Ì?最Á?大䨮队¨®尾2元a素?所¨´在¨²队¨®列¢D编À¨¤号?i{if((Q[i].Vide_Queue()==1)&&(Q[i].GetQueue_rear()y)&&(maxQ[i].GetQueue_rear())){max=Q[i].GetQueue_rear();num=i;}}if(num!=-1)//如¨?果?找¨°到Ì?该?编À¨¤号?i的Ì?缓o冲?轨¨¬则¨°把ã?入¨?轨¨¬A中D头ª¡¤车¦Ì厢¨¢放¤?入¨?第̨²i号?缓o冲?轨¨¬中D{A.DeQueue();coutA:;A.Print_Queue();coutendl;Q[num].EnQueue(y);coutQ[num]:;计算机科学与工程学院《算法与数据结构》实验报告7Q[num].Print_Queue();coutendl;continue;}else//否¤?则¨°，ê?判D断?是º?否¤?有®D缓o冲?轨¨¬为a空?，ê?如¨?有®D空?缓o冲?轨¨¬，ê?把ã?入¨?轨¨¬A的Ì?头ª¡¤车¦Ì厢¨¢放¤?入¨?空?缓o冲?轨¨¬中D{for(inti=0;ik;i++){if(Q[i].Vide_Queue()==0){A.DeQueue();coutA:;A.Print_Queue();coutendl;Q[i].EnQueue(y);coutQ[i]:;Q[i].Print_Queue();coutendl;continue;}}}return-1;//如¨?果?以°?上¦?所¨´有®D情¨¦况?都?不?行D，ê?则¨°该?序¨°列¢D无T法¤¡§重?排?，ê?输º?出?-1}}return1;//否¤?则¨°可¨¦以°?进?行D重?排?，ê?输º?出?1}voidmain(){if(TrainMain()==1)coutOKendl;elsecoutNOendl;system(pause);}实验内容计算机科学与工程学院《算法与数据结构》实验报告8实验内容计算机科学与工程学院《算法与数据结构》实验报告9实验总结本次试验较难，大量借鉴了网上的资源，感觉到算法很重要。