火车车厢重排实验报告
时间:2020-09-13 10:46:03 来源:勤学考试网 本文已影响 人
东华理工大学长江学院
数据结构课程设计报告
学号: 姓名: 刘 曹 杰
指导老师:刘自强
2011年1月3日
队列的应用举例——火车车厢重排
一、实验分析
一列货运列车共有n节车厢,每节车厢将停放在不同的车站。假定n个车站的编号分别为1 ~ n,即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢,车厢的编号应与车站(目的地)的编号相同,使各车厢从前至后按编号1到n的次序排列,这样,在每个车站只需卸掉最后一节车厢即可。所以,给定任意次序的车厢,必须重新排列他们。可以通过转轨站完成车厢的重排工作,在转轨站中有一个入轨、一个出轨和k个缓冲轨,缓冲轨位于入轨和出轨之间。开始时,n节车厢从入轨进入转轨站,转轨结束时各车厢按照编号1至n的次序离开转轨站进入出轨。假定缓冲轨按先进先出的方式运作,因此可将它们视为队列,并且禁止将车厢从缓冲轨移至入轨,也禁止从出轨移至缓冲轨。图中给出了一个转轨站,其中有3个缓冲轨H1,H2和H3。
为了重排车厢,若有k个缓冲轨,缓冲轨Hk为可直接将车厢从入轨移动到出轨的通道,则可用来暂存车厢的缓冲轨的数目为k-1。假定重排9节车厢,其初始次序为5, 8, 1, 7, 4, 2, 9, 6, 3,同时令k=3,如图3-23所示。3号车厢不能直接移动到出轨,因为1号车厢和2号车厢必须排在3号车厢之前,因此,把3号车厢移动至H1。6号车厢可放在H1中3号车厢之后,因为6号车厢将在3号车厢之后输出。9号车厢可以继续放在H1中6号车厢之后,而接下来的2号车厢不能放在9号车厢之后,因为2号车厢必须在9号车厢之前输出。因此,应把2号车厢放在H2的队头。4号车厢可以放在H2中2号车厢之后,7号车厢可以继续放在4号车厢之后。如图3-24(a)所示。至此,1号车厢可通过H3直接移至出轨,然后从H2移动2号车厢至出轨,从H1移动3号车厢至出轨,从H2移动4号车厢至出轨,如图3-24(b)所示。由于5号车厢此时仍在入轨中,所以把8号车厢移动至H2,这样就可以把5号车厢直接从入轨移至出轨。如图3-24(c)所示。此后,可依次从缓冲轨中移出6号、7号、8号和9号车厢。如图所示。
在把车厢c移至缓冲轨时,车厢c应移动到这样的缓冲轨中:该缓冲轨中队尾车厢的编号小于c;如果有多个缓冲轨满足这一条件,则选择队尾车厢编号最大的缓冲轨;否则选择一个空的缓冲轨。
假定重排n个车厢,可使用k个缓冲轨,将每个缓冲轨看成是一个队列,用nowOut表示下一个输出至出轨的车厢编号。火车车厢重排的算法用伪代码描述如下:
1. 分别对k个队列初始化;
2. 初始化下一个有爱输出的车厢编号nowOut=1;
3. 依次取入轨中的每一个车厢编号;
3.1如果入轨中的车厢编号等于nowOut,则
3.1.1输出该车厢;
3.1.2nowOut++;
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.2nowOut++;
3.3如果入轨和缓冲轨的对头元素没有编号为nowOut的车厢,则
3.3.1求小雨入轨中第一个车厢编号的最大队尾元素所在队列编号j;
3.3.2如果j存在,则把入轨中的第一个车厢移至缓冲轨j;
3.3.2 如果j不存在,但有多余一个空缓冲轨,则把入轨第一个车厢移至一个空缓冲轨;否则车厢无法重排,算法结束;
二、程序分析
1. 存储结构
本程序采用单链表结构,具体为链队列结构,使用队列结构的先进先出原则可以较好地处理车厢重排问题。链队列结构示意图如下:
……..
front
a1
a2
.
.
.
an
rear
2. 关键算法分析
一、本程序的关键算法主要为处理车厢重排问题的函数TrainPermute(),其伪代码如下:
?
void TrainPermute():
1.?初始化条件:计数器i=0,与非门aa=1
2.?判断是否能入轨while(用i<n判断是否n节车厢都入缓冲轨)&&(用aa=1判断是否有合适的缓冲轨可入)
2.1将aa置空;
2.2用for循环,依次取入入轨中的每一个车厢的编号进入合适的缓冲轨;
? 2.2.1如果缓冲轨中尾指针比进入缓冲轨元素小,则
进入该缓冲轨;
计数器i+1;
有合适缓冲轨,将aa变为真;
跳出for循环并进入while循环;
2.2.2如果缓冲轨中第一个元素为空,则
? 进入缓冲轨成为第一个元素;
计数器i+1;
有合适缓冲轨,将aa变为真;
? 跳出for循环并进入while循环;
2.3 用aa判断是否有进入合适的缓冲轨
①? aa=0即没有合适的缓冲轨,则
输出无法排列;
② aa=1即有合适的缓冲轨,则
遍历缓冲轨,
输出每个缓冲轨按顺序存储的车厢;
按从小到大的顺序出轨
for(引入输出轨计数器newOut=1;newOut<n; newOut+1;)
?newOut与每个队列的头元素比较若相等,则
? 元素出队;
?输出显示;
?具体代码如下:
void TrainPermute(int arr[],LinkQueue<int> a[],int n,int k)
{
int i=0;
bool aa=1;
while((i<n)&&(aa)) //当入轨中有车厢时
{
aa=0; //亮点:与非门思想!
for(int m=0;m<k;m++)
{
if(a[m].GetRear()<arr[i])
{
a[m].EnQueue(arr[i]);
i++;
aa=1;
break;
}
if(a[m].front->next==NULL)
{
a[m].EnQueue(arr[i]);
aa=1;
i++;
break;
}
}
}
if(aa==0) //当无法将入轨中队头车厢移至合适缓冲轨中时,程序结束
{
cout<<"车厢无法重排,算法结束"<<endl;
}
else //当入轨中已经没有车厢时
{
for(int m=0;m<k;m++)
{
cout<<"第"<<(m+1)<<"个缓冲轨的列车编号";
a[m].Trans();
cout<<endl;
}
cout<<"火车车厢出轨顺序为:"<<endl;
for(int newOut=1;newOut<=n;newOut++)
{
for(int j=0;j<k;j++) //扫描缓冲轨,将其队头元素依次由小到大输出 {
if(a[j].GetFront()==newOut)
{
cout<<a[j].DeQueue()<<" ";
}
}
}
}
}
二、主函数伪代码如下:
1. 输入n与k值,若输入值错误,则程序结束;
2. 通过循环结构为数组array[]赋值,具体分析见代码;
3. 输出入轨中火车车厢号码排列;
4. 调用TrainPermute()函数;
三、为array[]随机赋值的基本思想为:设置计数器count=0,设置数组ifmark[]来标记array[]赋值情况,依次将1至n等n个数随机赋给array[],其中,若array[t]未被赋值,即ifmark[t]=0,则将值赋给array[t],计数器加一;若array[t]已被赋值,即ifmark[t]=1,则重新开始循环。
srand((unsigned)time(NULL));
int count=0;
int *array;
array=new int[n];
int *ifmark;
ifmark=new int[n];
while(count!=n)
{
t=rand()%n;
if(ifmark[t]!=1)
{
array[t]=count+1;
ifmark[t]=1;
count++;
}
}
三、实验过程
程序代码及运行结果
#include<iostream>
#include<ctime>
using namespace std;
const int QueueSize=1000;
template<class T>
struct Node
{
?T data;
?Node<T> *next;
};
template<class T>
class LinkQueue? //链队列模板类?
{
public:
?LinkQueue(); //构造函数
?~LinkQueue(); //析构函数
?void Trans(); //遍历缓冲轨
?void EnQueue(T x);//入队
?T DeQueue(); //出队
?T GetFront() //查找队头元素
?{if(front!=rear) return front->next->data;}
?T GetRear() //查找队尾元素
?{if(front!=rear) return rear->data;}
?bool Empty() {front==NULL?return 1:return 0;} //判断队空
?friend void TrainPermute(int arr[],LinkQueue<T> a[],int n,int k);
private:
?Node<T> *front,*rear;
};
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)
?{
Node<T> *q=p;
p=p->next;
delete q;
?}
}
template<class T>
void LinkQueue<T>::EnQueue(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>::Trans()
{ Node<T> *p=front->next;
while(p)
{
?cout<<p->data<<' ';
?p=p->next;
};
}
void main()
{
?try
?{
int n,k,t;
cout<<"请输入火车车厢数n(n请小于1000): \nn=";
cin>>n;
? cout<<"请输入缓冲轨数k:\nk=";
cin>>k;
cout<<"系统将对"<<n<<"个数字随机排列入轨,并重新出轨。\n";
if(n>1000) throw"输入错误!车厢数必须小于1000!";
if(n<=0) throw"输入错误!车厢数必须大于0!";
if(k<=0) throw"输入错误!缓冲轨数必须大于0!";
srand((unsigned)time(NULL));
int count=0;
int *array;
array=new int[n];
int *ifmark;
ifmark=new int[n];
while(count!=n)
{
t=rand()%n;
if(ifmark[t]!=1)
{
?array[t]=count+1;
?ifmark[t]=1;
?count++;
}
}
cout<<"火车车厢入轨顺序为:"<<endl;
for(int i=0;i<n;i++)
cout<<array[i]<<" ";
cout<<endl;
LinkQueue<int> *buffer;
buffer=new LinkQueue<int>[k];
TrainPermute(array,buffer,n,k);
cout<<endl;
?}
?catch(char*s)
?{
cout<<s<<endl;
?}?
}
void TrainPermute(int arr[],LinkQueue<int> a[],int n,int k)
{
?int i=0;
?
?bool aa=1;
?
?while((i<n)&&(aa)) //当入轨中有车厢时
?{
aa=0;? //亮点:与非门思想!
for(int m=0;m<k;m++)
{
if(a[m].GetRear()<arr[i])
{
?a[m].EnQueue(arr[i]);
?i++;
?aa=1;
?break;
}
if(a[m].front->next==NULL)
{
?a[m].EnQueue(arr[i]);
?aa=1;
?i++;
?break;
}
}
?}
?if(aa==0)//当无法将入轨中队头车厢移至合适缓冲轨中时,程序结束
?{
cout<<"车厢无法重排,算法结束"<<endl;
?}?
?else ?//当入轨中已经没有车厢时
?{
for(int m=0;m<k;m++)
{
cout<<"第"<<(m+1)<<"个缓冲轨的列车编号";
a[m].Trans();
cout<<endl;
}
cout<<"火车车厢出轨顺序为:"<<endl;
for(int newOut=1;newOut<=n;newOut++)
{
for(int j=0;j<k;j++)//扫描缓冲轨,将其队头元素依次由小到大输出
{
?if(a[j].GetFront()==newOut)
?{
cout<<a[j].DeQueue()<<" ";
?}
}
}
?}
}
?
四、总结
本次数据结构实验主要是练习使用队列的思想,我做的是火车重排问题的实验,此实验在课本上有一些讲解,也给出来主要函数TrainPermute()的主要编写思路,减轻了自己的工作量,不过由于此程序的代码比较复杂,在编译调试过程中也很耗费时间,通过设置断点,分步调试,才使得程序没有了bug。例如,由于程序用了较多的循环,包括多重循环,在刚刚写出代码的时候常常陷入死循环,而因为代码冗长,仅仅通过看代码很难找出逻辑上的错误。功夫不负有心人,最后终于用与非门的思想解决了这个死循环问题,并简单优化程序。
总的来说,本程序由于使用了模板类结构,扩展性还算比较好。但是代码部分有些冗长,可读性不算太好。如果要做下一步工作的话,应该是尽量精简代码,使得程序更加具有实用性和可读性。