C++数据结构火车缓冲轨问题.docxVIP

数据结构实验报告实验要求实验目的:通过上机编程，学会数据结构中栈和队列的使用。熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法，熟练改错方 法。熟悉设计算法的过程进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力实验内容：利用队列结构实现车厢重排问题。车厢重排问题如下：一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1~n的顺序进入出轨。缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。提示：一列火车的每个车厢按顺序从入轨进入不同缓冲轨，缓冲轨重排后的进入出轨，重新编排成一列货车。比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面，这样，出轨的时候才可以按照从小到大的顺序重新编排。代码要求：1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出2. 程序分析 火车缓冲问题描述的是一列乱序的火车，经过K个缓冲轨之后实现顺序排列。在这个程序中，我首先联想到了队列具有先入先出的特点，可以将K个缓冲轨道设计为K条链队列或者循环队列。当前的轨道若为空，则火车的一节车厢可按目前的顺序进入一个，若当前车厢的序号大于后面一节的，若两节车厢在同一缓冲轨则依队列的特点出列是将不能实现从大到小排列，故下一列车应该进入下一个缓冲轨。 每节车厢都按照上述进行判断再安排进入缓冲轨。缓冲轨数量k是一个确定数，当算法中所需要的缓冲轨数大于k时将无法实现重新排列，故需要提醒设计者多安排几条缓冲轨道。若实际所需轨道数小于k则会有空的缓冲轨道。 出轨的时候应按照由小至大的顺序依次出轨，需要在各条缓冲轨道之间查找相应的列车节数。（但是其实可以边入轨，当该车厢在缓冲轨中的后一节车厢入轨后可以直接出轨，不一定要等到全部都入轨再出轨。）2.1 存储结构链队列的存储示意图：缓冲轨道1: ……缓冲轨道2 ……``````缓冲轨道k： ……2.2 关键算法分析：设定并初始化计数器j=0 ，have=1（这是一个bool型变量，用来判断当初循环是否还具有缓冲轨可用。）?用while判断是否入轨，用in判断是否还有车厢需要进入缓冲轨，have判断是否还有剩余缓冲轨，只有二者同时成立时才可以进行下一步排序。在循环中现将have=0；for循环中，重新排列车厢使之进入缓冲轨道 ；若缓冲轨中最后一个元素比此时将被排序的车厢序号小，则车厢可以进入该缓冲轨；? 排序实现一次，j++； 可以实现入轨，令have=1.? 跳出for循环并进入while循环.若缓冲轨为空，则车厢直接入内，成为第一个元素。排序实现一次，j++；可以实现入轨，令have=1.跳出for循环并进入while循环.（3）判断是否还能继续排轨。① have=0无法实现重新排列，故需要提醒设计者多安排几条缓冲轨道。② have=1有合适的缓冲轨，则遍历缓冲轨，排列完毕后由小至大输出。时间复杂度的计算：o（） 代码如下：void change(int q[], LinkQueueint d[], int n, int k){int j = 0;//已经重排车厢的数目bool have = 1;//还有缓冲轨道可以使用while ((jn) (have))//当入轨中有车厢时{have = 0;//在后面的程序中改变have的值，若不变则说明没有排这节车厢for (int i = 0; ik; i++){if (d[i].GetRear()q[j]) //若所需加入的数据大于目前缓冲轨道中的数据就可以在此缓冲轨道加入{d[i].inQ(q[j]);j++;have = 1;break;}}}if (have == 0)//说明没有办法排这节车厢{cout 车厢重排失败，请试试安排更多的缓冲轨道 endl;}else //全部n节车厢都重排完毕{for (int l = 1; lk + 1; l++){cout 序号为 l 的缓冲轨道停有;d[l - 1].read();cout endl;} }}2.3 其他关于链队列的基本操作：构造链队列：在本程序中，先使用构造函数将链队列初始化为空队列。rear=front=Nul