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

《C++数据结构火车缓冲轨问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京邮电大学信息与通信工程学院数据结构实验报告1．实验要求i.实验目的:（1）通过上机编程，学会数据结构中栈和队列的使用。（2）熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法，熟练改错方法。（3）熟悉设计算法的过程（4）进一步掌握指针、模板类、异常处理的使用（5）掌握栈的操作的实现方法（6）掌握队列的操作的实现方法（7）学习使用栈解决实际问题的能力（8）学习使用队列解决实际问题的能力ii.实验内容：利用队列结构实现车厢重排问题。车厢重排问题如下：一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。给定任意次序的车厢，通过转轨站将车厢

2、编号按顺序重新排成1~n。转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1~n的顺序进入出轨。缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。提示：一列火车的每个车厢按顺序从入轨进入不同缓冲轨，缓冲轨重排后的进入出轨，重新编排成一列货车。比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面，这样，出轨的时候才可以按照从小到大的顺序重新编排。iii.代码要求：1、必须要有异常处

3、理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能3、递归程序注意调用的过程，防止栈溢出2.程序分析火车缓冲问题描述的是一列乱序的火车，经过K个缓冲轨之后实现顺序排列。在这个程第9页北京邮电大学信息与通信工程学院序中，我首先联想到了队列具有先入先出的特点，可以将K个缓冲轨道设计为K条链队列或者循环队列。当前的轨道若为空，则火车的一节车厢可按目前的顺序进入一个，若当前车厢的序号大于后面一节的，若两节车厢在同一缓冲轨则依队列的特点出

4、列是将不能实现从大到小排列，故下一列车应该进入下一个缓冲轨。每节车厢都按照上述进行判断再安排进入缓冲轨。缓冲轨数量k是一个确定数，当算法中所需要的缓冲轨数大于k时将无法实现重新排列，故需要提醒设计者多安排几条缓冲轨道。若实际所需轨道数小于k则会有空的缓冲轨道。出轨的时候应按照由小至大的顺序依次出轨，需要在各条缓冲轨道之间查找相应的列车节数。（但是其实可以边入轨，当该车厢在缓冲轨中的后一节车厢入轨后可以直接出轨，不一定要等到全部都入轨再出轨。）2.1存储结构链队列的存储示意图：缓冲轨道1:……缓冲轨道2……``````缓冲轨道k：……2.2关键算法分析：a

5、)设定并初始化计数器j=0，have=1（这是一个bool型变量，用来判断当初循环是否还具有缓冲轨可用。）b) 用while判断是否入轨，用i

6、实现一次，j++；可以实现入轨，令have=1.跳出for循环并进入while循环.（3）判断是否还能继续排轨。① have=0无法实现重新排列，故需要提醒设计者多安排几条缓冲轨道。②have=1有合适的缓冲轨，则遍历缓冲轨，排列完毕后由小至大输出。时间复杂度的计算：o（n2）第9页北京邮电大学信息与通信工程学院代码如下：voidchange(intq[],LinkQueued[],intn,intk){intj=0;//已经重排车厢的数目boolhave=1;//还有缓冲轨道可以使用while((j

7、{have=0;//在后面的程序中改变have的值，若不变则说明没有排这节车厢for(inti=0;i

8、-1].read();cout<