一、 试验课题队列的应用实验目的：（1）掌握队列的特点及其存储方法； （2）掌握队列的常见算法和程序实现二、 试验内容(1)问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢所以，给定任意次序的车厢，必须重新排列它们车厢的重排工作可以通过国转轨站完成在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重排问题2)基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能 三、 试验分析实验说明：转轨站示意图如下：出 轨入 轨581742963987654321H1H3H2 火车车厢重排过程如下：出 轨入 轨 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.2 nowOut++；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.2 nowOut++； 3.3 如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢，则 3.3.1 求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j;3.3.2 如果 j 存在，则把入轨中的第一个车厢移至缓冲轨 j；3.3.2 如果 j 不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束；四、 源程序代码#includeusing namespace std;const MS=100;template struct QNode{ T data; QNode *next;};template class LiQueue{ public: LiQueue( ); //构造函数，初始化一个空的链队列 ~LiQueue( ); //析构函数，释放链队列中各结点的存储空间 void EnQueue(T x); //将元素x入队 T DeQueue( ); //将队头元素出队 T GetFront( ); //取链队列的队头元素 T GetRear(); bool Empty( ); //判断链队列是否为空 QNode *front, *rear; //队头和队尾指针，分别指向头结点和终端结点};template LiQueue::LiQueue( ){ QNode *s;s=new QNode;s->next=NULL;front=rear=s;}template LiQueue::~LiQueue( ){ QNode *p; while(front) { p=front;front=front->next;delete p; }}template void LiQueue::EnQueue(T x){ QNode *s;s=new QNode; s->data=x; //申请一个数据域为x的结点s s->next=NULL; rear->next=s; //将结点s插入到队尾 rear=s;}template T LiQueue::DeQueue(){ QNode *p; int x; if (rear==front) throw "下溢"; p=front->next; x=p->data; //暂存队头元素 front->next=p->next; //将队头元素所在结点摘链 if (p->next==NULL) rear=front; //判断出队前队列长度是否为1 delete p; return x;}template T LiQueue::GetFront(){ if (rear!=front) return front->next->data;}template T LiQueue::GetRear(){ if(rear!=front)return rear->data;}template bool LiQueue::Empty( ) { if(front==rear) return 0;else return 1;}class Train{ private : int n,k,th; public : Train();void ChongPai();};Train::Train(){ cout<<"请输入火车(货运列车）的车厢个数为："<>n; cout<<"请输入转轨站的缓冲轨个数为："<>k;}void Train::ChongPai(){ int a[MS];LiQueue*b; b=new LiQueue[k+2]; cout<<"请输入车厢入轨编号次序："<>a[i]; for(i=n-1;i>=0;i--) b[k].EnQueue(a[i]); cout<<"则进行车厢重排过程如下:"<
六、 试验总结本次试验中，在解决火车车厢重排问题中，结合了最近刚学的队列的知识，并且运用到之前C++语言，很好的解决了这一类问题其中，每一个轨道缓冲区就形如一个队列一样，车厢先进缓冲轨道的要先出来，所以把它看成一个队列，运用队列的相关算法，实现高效快速的解决火车车厢重排问题通过本次试验，学会了队列的应用，加深了对队列的理解，知道了队列是一种先进队列的后出队列的储存结构本次试验让我更好的把书本上的知识运用到具体的例子中来，学会了通过vc6.0来建立队列，以及初始化队列、进队列、出队列等等同时也了解到了火车车厢重排问题可以通过队列的相关知识来解决，也体会其中算法的奥妙 （注：可编辑下载，若有不当之处，请指正，谢谢!） 。