第7页
北京邮电大学信息与通信工程学院
}; template<class T> LinkQueue<T>::LinkQueue() {
Node<T> *s=new Node<T>; s->next=NULL; front=rear=s; } template<class T> LinkQueue<T>::~LinkQueue() { Node<T> *p=front; while(p!=NULL) {
if(k<=0) throw"必须存在缓冲轨道!"; cout<<"这一列火车有"<<n<<"节车厢";
srand((unsigned)time(NULL));//产生随机数，生成火车初始车厢号排列 int count=0; int *main; main=new int[n]; int *mark; mark=new int[n]; while(count!=n) {
{
if(front==NULL) return 1;
else return 0;
} //判断队列是否为空，如果是空，返回 1，否则返回 0 friend void Drive(int arr[],LinkQueue<T> a[],int n,int k);//一个友元函数 drive，实现从 主到缓冲的变换 private: Node<T> *front,*rear;
Node<T> *q=p; p=p->next; delete q; } } template<class T> void LinkQueue<T>::EnterQueue(T x) { Node<T> *s=new Node<T>; s->data=x; s->next=NULL; rear->next=s; rear=s; } template<class T> T LinkQueue<T>::DeQueue() { if(rear==front) throw"发生下溢"; Node<T> *p=front->next; int x=p->data; front->next=p->next; if(p->next==NULL) rear=front; delete p; return x; } template<class T> void LinkQueue<T>::tempTrans()//遍历输出缓冲轨中的元素的值 { Node<T> *p=front->next;
P
第3页
北京邮电大学信息与通信工程学院
5：遍历打印元素O（n） 1：建立新结点指向front的next域：Node<T> *p=front->next; 2：如果p不为空：while(p) {
3：如果p为空：if(p==NULL) 4：终止：break;
else { 5：否则输出p的data域：cout<<p->data<<' '; 6：将p赋值为p的next域名：p=p->next; } };
};
template<class T> class LinkQueue //链队列模板类
{
public: LinkQueue();
//构造函数
~LinkQueue(); //析构函数 void tempTrans(); //遍历输出缓冲轨中的内容
void EnterQueue(T x);//入队
T DeQueue();
t=rand()%n; if(mark[t]!=1) {
main[t]=count+1; mark[t]=1; count++; } }//完成对 array 数组的赋值，生成了初始的车厢排列 cout<<"火车车厢初始的排序为:"<<endl; for(int i=0;i<n;i++) cout<<main[i]<<" ";//逐个原始排序下的火车车厢的编码
第9页
北京邮电大学信息与通信工程学院
cout<<endl; LinkQueue<int> *huan; huan=new LinkQueue<int>[k];
Drive(main,huan,n,k); cout<<endl;
} void Drive(int arr[],LinkQueue<int> a[],int n,int k)//arr 为原来的车厢数组，a 为缓冲轨道的 数组
北京邮电大学信息与通信工程学院
数据结构实验报告
实验名称： 实验二——栈和队列 学生姓名： 徐瑞强 班 级： 2010211119 班内序号： 04 学 号： 10210559 日 期： 2011 年 11 月 11 日
1．实验要求
掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力 利用队列结构实现车厢重排问题。车厢重排问题如下： 一列货车共有 n 节车厢，每个车厢都有自己的编号，编号范围从 1~n。给定任意次序的 车厢，通过转轨站将车厢编号按顺序重新排成 1~n。转轨站共有 k 个缓冲轨，缓冲轨位于入 轨和出轨之间。开始时，车厢从入轨进入缓冲轨，经过缓冲轨的重排后，按 1~n 的顺序进入 出轨。缓冲轨按照先进先出方式，编写一个算法，将任意次序的车厢进行重排，输出每个缓 冲轨中的车厢编号。
3：链队列的入队操作函数 O（1） 1:建立一个指针：Node<T> *s=new Node<T>; 2：将该指针的data域赋值为x：s->data=x; 3：将该指针的next域赋值为空s->next=NULL; 4：将尾指针的next域指向s：rear->next=s; 5：将尾指针赋值为s：rear=s; S
第8页
北京邮电大学信息与通信工程学院
while(p) {
if(p==NULL) break;
else {
cout<<p->data<<' '; p=p->next; } }; } void main() { int n,k,t; cout<<"请输入火车的车厢数 N（N 请小于 100）: N="; cin>>n; if(n>100) throw"输入错误!车厢数太大了!"; if(n<=0) throw"车厢数不能为负数"; cout<<"请输入缓冲轨数 k：k="; cin>>k;
第2页
北京邮电大学信息与通信工程学院
序。
二：代码详细分析
1：链队列的构造函数 O(n)
1：建立一个指向Node的指针：Node<T> *s=new Node<T>;
2：将该指针的next域赋值为空：s->next=NULL;
3：将头指针和尾指针指向该节点front=rear=s;
Front
Rear
S 2：链队列的析构函数 O(n)
1：建立一个新指针指向头结点：Node<T> *p=front; 2：如果该指针不为空：while(p!=NULL)
{ 3：再建立一个指针指向p：Node<T> *q=p; 4：将p指向p的下一个元素：p=p->next; 5：释放p指向的空间：delete q;
} P
2. 程序分析
2.1 存储结构
为了实现对火车车厢的存储，方便以后的排序，在储存初始化的主轨道和副轨道 的火车车厢时，采用了链队列的思想，将每个车厢视为一个结构体，该结构体中的 两个元素分别为整形与指向这种结构体的一个指针。整形数代表主车厢的每个车厢 的编号，而指针则指向下一个车厢。对于整个主轨道和缓冲轨,分别采用一个数组 来存储它们的排序方式，即该轨道中列车的排序方式。但是每个轨道中列车的数量 是不确定的，因此不能采用静态数组，必须采用动态数组，因此储存列车编号的数 组是动态数组，通过对内存空间的申请使用来申请动态数组储存列车编号。
Rear 4：链队列的出队操作函数 O（1）
1：判断头结点和尾节点是否相等，如果相等，抛出发生下溢的报错信息： if(rear==front) throw"发¤¡é生¦¨²下?溢°?"; 2：建立一个新指针指向front的next域，即队首元素：Node<T> *p=front->next; 3：建立一个整形变量保存p的data域：int x=p->data; 4：将front的next域赋值为p的next域：front->next=p->next; 5：如果p的next域为空：if(p->next==NULL) 6：首尾节点相等： rear=front; 4：释放p节点指向的内存：delete p; 5：返回一个x值：return x;
遍历输出缓冲轨中的车厢排序号
第4页
结束
北京邮电大学信息与通信工程学院
2：程序执行的结果如图所示： 当可以正常排序时：
当无法正常排序时：
3:时间复杂度见源代码分析处
4. 总结
第5页
北京邮电大学信息与通信工程学院
1：对车厢排序的算法还可以进一步优化，使得排序更加合理，对于较大的车厢号，可以优 先进入级别高的缓冲轨，为小的车厢留出低级的缓冲轨。 2：在对队列的使用过程中，体会到了对先进先出的思想的使用极其优点，对栈的使用有了 更进一步的认识。 3：下一步，可以将排序算法优化，使得程序的实现性更好，而且占用较小的计算机资源开 支。
以下是主轨道和缓冲轨的存储结构示意图： 缓冲轨 1：
…………
第1页
北京邮电大学信息与通信工程学院
缓冲轨 2：
缓冲轨 3：
……… 主轨道：
………… …………
…………
另外，专门定义了一个结构体LinkQueue，对对象的操作进行统一的定义。比如出队入队操 作，析构操作等。
2.wk.baidu.com 关键算法分析
一：关键算法分析： 1：链队列的构造函数： 1：建立一个新的结点， 2：节点的 next 域指向空 3：将 front 结点和 rear 结点都指向该节点 2：链队列的析构函数： 1：建立一个指向头结点的指针 2:如果该节点不为空，再建立一个指针，指向该节点的 next 结点 3:释放该节点指向的内存空间 4：重复以上两步操作 3：链队列的入队操作函数 1：建立一个新结点 2：对该新结点的数据域和 next 域进行赋值，next 赋为空 3：将 rear 指针的 next 域指向该新结点 4：该新结点赋给 rear 指针 4：链队列的出队操作函数 1：判断是否发生下溢 2：新建一个指针指向 front 的 next 域 3：将 front 的 next 域改为 p 的 next 域 4：如果 p 的 next 不为空，就释放 p 指针，否则将 rear 赋值为 front 5：返回被析构的结点的数据域的值 5：遍历打印元素 1：建立一个指针，指向 front 的 next 域 2：输出该指针指向的结点的 next 域 3：如果该指针不是空的话，那么该指针继续指向下一个结点 6：将主轨道内的火车车厢开进缓冲轨的函数 1：将主轨道的最前面的元素入队 2：如果进入的该缓冲轨是空的话，那么是可以入队的 3：如果进入的缓冲轨不是空的，那么判断最近进入缓冲轨的车厢编号是否大于马上 就要进入的车厢编号，如果大于，就不能进入，否则，可以进入 4：如果所有的缓冲轨都不满足以上条件，该函数结束，并且提示无法对车厢进行排
第6页
北京邮电大学信息与通信工程学院
源代码
使用说明：新建.cpp，将以下代码复制后 ctrl+F5 运行即可
#include<iostream>
#include<ctime>
using namespace std;
template<class T>
struct Node
{
T data;
Node<T> * next;
P
2.3 其他
对轨道排序的操作，其实可以采用更优化的算法，比如说一个较大的车厢号，可以优先进入 级别更高的缓冲轨，这样有利于合理的空间利用。使得每个缓冲轨尽可能的多放几个车厢。
3. 程序运行结果
1：主函数流程图
开始
输入车厢数和缓冲轨道数
输入正确
是 建立主轨道数组和缓冲轨数组
对主轨道图赋2 值流，程以图及示执意行图 排序操作
//出队
T GetFront()
//查找队头元素,返回队头元素的数据域
{
if(front!=rear)
return front->next->data;
}
T GetRear()
//查找队尾元素，返回队尾元素的数据域
{
if(front!=rear)
return rear->data;
}
bool Empty()
