数据结构 车厢问题 实验报告
数据结构实验报告
实验名称： 实验二——题目5
学生姓名：
班 级：
班内序号：
学 号：
日 期： 2011年11月7日
1．实验要求
利用队列结构实现车厢重排问题。车厢重排问题如下：
一列货车共有n节车厢，每个车厢都有自己的编号，编号范围从1~n。给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。转轨站共有k个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按1~n的顺序进入出轨。缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓冲轨中的车厢编号。
2. 程序分析
将每个轨道视为一个队列，每一个车厢视为一个结构体的结点，结点存储车厢编号以及下一节车厢的地址。用尾插法建立队列，并根据队列队尾入队，队头出队的特点实现结点的出队以及入队。由于车厢在重排过程中将会频繁进行入队以及出队的操作，如果采用顺序存储结构，则在结点出入队时是操作将会十分不方便，还会占用大量多余的空间和时间，故选用链式存储结构，可以直接调动结点，十分简洁。
重排过程比如：编号为3的车厢进入缓冲轨1，则下一个编号小于3的车厢则必须进入下一个缓冲轨2，而编号大于3的车厢则进入缓冲轨1，排在3号车厢的后面。在把车厢c移至缓冲轨是，车厢c应该移动到这样的缓冲轨中：该缓冲轨中队尾车厢的编号小于c；如果有多个缓冲轨满足这一条件，则选择对位车厢编号最大的缓冲轨，否则选择一个空的缓冲轨。这样，出轨的时候才可以按照从小到大的顺序重新编排。
2.1 存储结构
2.2 关键算法分析
1. 移动车厢算法（车厢要从a队列移至b队列）
·自然语言描述
（1） 判断a队列是否为空，为空则输出“队列下溢”，提示出错。
