车厢重排.doc

题目:
利用队列结构实现车厢重排问题。车厢重排问题如下:
一列火车共有n节车厢,每个车厢都有自己的编号,编号范围从1~n。给定任意次序的车厢,通过转轨站将车厢编号按顺序重新排成1~n。转轨站共有k个缓冲轨,缓冲轨位于入轨和出轨之间。开始时,车厢从入轨进入缓冲轨,经过缓冲轨的重排后,按1~n的顺序进入出轨。缓冲轨按照先进先出的方式,编写一个算法,将任意次序的车厢进行重排,输出每个缓冲轨中的车厢编号。
提示:一列火车的每个车厢按顺序从入轨进入不同缓冲轨,缓冲轨重排后进入出轨,重新编排成一列火车。比如:编号为3的车厢进入缓冲轨1,则下一个编号小于3的车厢必须进入下一个缓冲轨2,而编号大于3的车厢则进入缓冲轨1,排在3号车厢的后面。这样,出轨的时候才可以按照从小到大的顺序重新编排。
设计思路:
1 按题目要求缓冲轨的工作方式是先进先出(FIFO),因此是队列,由于每条缓冲轨进入的车厢数不定,采用链式队列
2 考虑数据的扩展性,队列以及队列元素都采用模板定义
3 用随机数函数生成车厢原始序列
4 链式队列没有可遍历结构
5 _getch()函数用于接收一个键盘字符,但不回显在屏幕上
定义与实现:
1 定义节点
template <class T>
struct Node
{
T data;
Node* next;
};
结构体模板,将单链表节点
数据域
指针域
2 定义链式队列
template <class T>
class LinkQueue
{
public:
LinkQueue();
~LinkQueue();
void EnQueue(const T &x);
T DeQueue();
bool Empty();
T Get_rear();
private:
Node<T>*front;
Node<T>*rear;
};
链式队列类
构造函数
析构函数
元素T从队尾入队
元素T从队首出队
判断队列是否为空,如果为空返回True
获得队尾元素T,用以比较缓冲轨车厢
Node类型的队首指针
Node类型的队尾指针
3 代码注意事项
#ifndef CACHE
#define CACHE
……
#include ""
#endif
条件预编译
包含编译模型,链接所需
4 队列实现
template <class T>
LinkQueue<T>::LinkQueue()
{
front=rear=NULL;
}
template <class T>
LinkQueue<T>::~LinkQueue()
{
while(front!=NULL)
{
rear=front->next;
delete front;
front=rear;
}
}
构造函数创建一个空队列
从队首开始,逐个释放
template <class T>
void LinkQueue<T>::EnQueue(const T &data)
{
Node<T> *enNode;
enNode=new Node<T>;
enNode->data=data;
enNode->ne