火车厢重排问题.doc

1
目录
1．题目： 3
1-——火车厢重排问题 3
1- 4
=0
定义X
i=1
i<k
BestTrack=i,H[BestTrack].EnQueue
c>x&&x>Best
真
假
BestLast=x,BestTrack=i
真
真
假
BestTrack
真
假
i++
3-2-()函数的流程图
7
NowOut=1
minH=n+1
定义minS
i=0
i<n
假
真
i++
====+==++++
P[i]=NowOut
minH==NowOut
输入p[i],NowOut++
真
Output(),NowOut++
真
假
!Hold(p[i],minH,minS,H,K)
false
真
假
ture
8
4. 算法描述
该问题是利用C++语言来实现的，首先通过建立一个类模板，类模板下有6个函数模板（分别为LinkQueue::LinkQueue(),LinkQueue::~LinkQueue(),LinkQueue::EnQueue(T x),T LinkQueue::DeQueue(),T LinkQueue::GetQueue(),bool Empty()），使用函数模板是先声明一个函数模板，之后才转化成相应的模板函数来进行调用执行，具体流程为函数模板实例化为模板函数，然后被main和output函数调用
4-1. 模块一：LinkQueue() 构造函数
初始化一个空的链队列
template <class T>
LinkQueue<T>::LinkQueue( )
{
Node <T> *s; //队列存在
s=new Node<T>; //定义S为一个新的节点
s->next=NULL; //s为空
front=rear=s; //队列为空
}
4-2. 模块二：析构函数
释放链队列中的各结点的存储空间
template <class T>
LinkQueue<T>::~LinkQueue( )
{
while(front)
{
Node <T> *p; //假设队列存在
p=front->next; //输入的值不存在
delete front; //销毁队列
front=p; //释放队列所占用的存储空间
}
}
9
4-3. 模块三：EnQueue函数
将队头元素x入队
template <class T>
void LinkQueue<T>::EnQueue(T x)
{
Node<T> *s; //假设队列已存在
s=new Node<T>; //申请一个新的结点
s->data=x; //申请一个数据域为x的结点s
s->next=NULL;
rear->next=s; //将结点s插入到队尾
rear=s; //如果插入成功，队尾增加了一个元素
}
4-4. 模块四：DeQueue函数
将队头元素出队
template <class T>
T LinkQueue<T>::DeQueue()
{
Node <T> *p; int x; //假设队列存在，定义一个数值为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;
}
4-：GetQueue函数
取链队列的队头元素
template <class T>
T LinkQueue<T>::