1305080xxx_姓名_实验报告04.docVIP

计算机科学与工程学院 《算法与数据结构》实验报告(四) 专业班级 2013网络工程01 实验地点 423机房 学生学号 指导教师 赵卿松 学生姓名 实验时间 实验项目 队列的应用 实验类别 基础性（√） 设计性（） 综合性（） 其它（ ） 实验目的及要求 （1）掌握队列的特点及其存储方法； （2）掌握队列的常见算法和程序实现 日 期： 2015 年 5 月 2 日 实 验 内 容 实验内容：火车车厢重排问题。 实验说明：转轨站示意图如下： 火车车厢重排过程如下： 火车车厢重排算法伪代码如下： #includeiostream using namespace std; const MS = 100; template class T struct QNode { T data; QNode T *next; }; template class T class LiQueue { public : LiQueue(); //构造函数，是初始化一个空的链队列 ~LiQueue(); //析构函数，释放链队列中个结点的存储空间 void EnQueue(T x); //将元素x入队 T DeQueue (); //将队头元素出队 T GetFront (); //取链队列的队头元素 T GetRear(); bool Empty(); //判断链队列是否为空 QNode T *front ,*next; //队头和队尾指针，分别指向结点和终端结点 }； template class T LiQueue T::LiQueue() { QNode T *s; s = new QNodeT; s-next = NULL; front = rear = s; } template class T LiQueueT::~LiQueue() { QNode T *p; while (front) { p = front; front = front-next; delete p; } } template class T void LiQueueT::EnQueue(T x) { QNode T *s; s = new QNodeT; s-data = x; //申请一个数据域为X的结点s s-next = NULL; rear-next = s; //将结点s插入到队尾rear=s； } template class T T LiQueue T::DeQueue() { QNode T *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 class T T LiQueueT::GetFront() { if(rear != front) return front-next-data; } template class T T LiQueueT::GetRear() { if(rear != front) return rear-data; } template class T bool LiQueueT::Empty() { if (front == rear) return 0; else return 1; } class Train { private : int n,k ,th; public : Train(); void ChongPai(); }; Train::Train() { cout请输入火车（货运列车）的车厢个数为：endl; cinn; cout请输入转轨站的缓冲轨个数为：endl; cink; } void Train::ChongPai() { int a[MS]; LiQueueint *b; b = new LiQueueint [k+2]; cout请输入车厢入轨编号次序：endl; for(int i=0;in;i++) cina[i]; for(i = n-1;i=0;i--) b[k].EnQueue(a[i]); cout则进行车厢重排过程如下：endl; th = 1;