火车厢重排问题
目录
1(题目:............................................................................................................. 2 1-1.队列的应用——火车厢重排问题 .............................................................. 2 1-2.简单指导..................................................................................................... 2 2.设计目的及内容 ................................................................................................ 3 2-1.目的 ............................................................................................................ 3 2-2.内容 ............................................................................................................ 3
设计内容 ................................................................................................... 3
3.概要设计 ............................................................................................................ 4
3-1.函数调用的关系图 ..................................................................................... 4 3-2.
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
图 ........................................................................................................ 4
3-2-1. 总体程序设计流程图 .................................................................... 4
3-2-2 Output函数的流程图. ..................................................................... 5
3-2-3. Hold函数的流程图 ........................................................................ 6
4. 算法描述 .......................................................................................................... 8 4-1. 模块一:LinkQueue() 构造函数 ............................................................. 8
初始化一个空的链队列 ............................................................................ 8 4-2. 模块二:析构函数 ................................................................................... 8
释放链队列中的各结点的存储空间 ......................................................... 8 4-3. 模块三:EnQueue函数 ............................................................................ 9
将队头元素x入队.................................................................................... 9 4-4. 模块四:DeQueue函数 ........................................................................... 9
将队头元素出队 ....................................................................................... 9 4-5.模块五:GetQueue函数 ............................................................................ 9
取链队列的队头元素 ................................................................................ 9 4-6. 模块六:Empty函数 .............................................................................. 10
判断链队列是否为空 .............................................................................. 10 4-7. 模块七:Outputput 函数 ....................................................................... 10
该函数调用6个函数
模板
个人简介word模板免费下载关于员工迟到处罚通告模板康奈尔office模板下载康奈尔 笔记本 模板 下载软件方案模板免费下载
来实现火车厢重排问题,预设K个缓冲轨
道,通过运用函数模板来比较各个缓冲轨道的队头元素,确定队列的
出队、入队元素,最后通过输入和输出函数来实现火车厢由小到大的
顺序出轨 ................................................................................................. 10 5.源程序 .............................................................................................................. 11 6. 运行结果及性能分析 .................................................................................... 15 6-1. 运行结果及性能分析 ............................................................................. 15
6-1-1.开始后的界面 ................................................................................ 15
6-1-2. 输入火车总数i=5和缓冲轨数j=3后的界面 ............................. 16
6-1-3.随机输入1.2.3.4.5的进入顺序后开始进入重排界面 .................. 16 6-2. 性能分析 ................................................................................................. 16 7.心得体会 .......................................................................................................... 17
1
1(题目:
1-1.队列的应用——火车厢重排问题
假设一列货运列车共有n节编号分别为1~n的车厢,在进站前这n节车厢并不是按其编号有序排列;现要求重新排列各车厢,使该列车在进入车站时,所有车厢从前到后按编号1~n的次序排列,以便各车厢能够停靠在与其编号一致的站点。
1-2.简单指导
为了达到这样的效果,可以在一个转轨站里完成车厢的重排工作。在转轨站中有一个入轨,一个出轨和K个位于入轨与出轨间的缓冲铁轨。如下图所示。开始时,具有n节车厢的货车从入轨处进入转轨站;转轨结束时,各车厢从右到左按照编号1~n的次序通过出轨处离开转轨站
2
2.设计目的及内容
2-1.目的
1、利用C言和C++等编程语言对实际问题进行编程,同时使用数据结构中的算法,实现各个函数的功能。
2、通过课程设计理解并掌握队列的基本概念及其操作,并在此基础上编写队列的基本算法(比如说初始化一个队列,测试队列是否为空,取当前对头元素,队列的插入及删除等)。
3、学会分析排序中的时间复杂度问题,提高分析算法的能力。
4、培养我们的算法分析能力,程序设计调试能力,纠错能力,以及遇到困难时沉着稳重、坚持不懈的能力。
2-2.内容
设计假设一列货运列车共有n节编号分别为1~n的车厢,在进站前这n节车厢并不是按其编号有序排列;现要求重新排列各车厢,使该列车在进入车站时,所有车厢从前到后按编号1~n的次序排列,以便各车厢能够停靠在与其编号一致的站点。
设计内容
(1)设计一个出轨和K个位于入轨与出轨间的缓冲铁轨来完成各个车厢按其编号排序。
(2)构造一个类来存储队列的各个函数,判定各个队列是否为空,并确定元素的入队、出队,完成车厢能够按其编号大小排序。
3
3.概要设计
3-1.函数调用的关系图
main
outp
ut
Hold() DeQuEmptyRailro
eue() () ad()
EmpEnQouLinkQ
ty() ueue tpueue
ut
3-2.流程图
3-2-1. 总体程序设计流程图
开始
输入i,j
输入火车进轨
的顺序
k=0
k
next->假
data)x&&x>真 ack=i Best
假
BestTrack=i,H[BestTrack].EBestTrack 真
nQueue
假
3-2-4.Railroad()函数的流程图
6
NowOut=1
minH=n+1
定义minS
i=0
i++
===i LinkQueue::LinkQueue( ) {
Node *s; //队列存在
s=new Node; //定义S为一个新的节点 s->next=NULL; //s为空
front=rear=s; //队列为空
}
4-2. 模块二:析构函数
释放链队列中的各结点的存储空间
template
LinkQueue::~LinkQueue( ) {
while(front)
{
Node *p; //假设队列存在
p=front->next; //输入的值不存在
delete front; //销毁队列
front=p; //释放队列所占用的存储空间
}
}
8
4-3. 模块三:EnQueue函数
将队头元素x入队
template
void LinkQueue::EnQueue(T x) {
Node *s; //假设队列已存在
s=new Node; //申请一个新的结点
s->data=x; //申请一个数据域为x的结点s s->next=NULL;
rear->next=s; //将结点s插入到队尾
rear=s; //如果插入成功,队尾增加了一个元素 }
4-4. 模块四:DeQueue函数
将队头元素出队
template
T LinkQueue::DeQueue() {
Node *p; int x; //假设队列存在,定义一个数值为x
if (rear==front) throw "下溢";
p=front->next;
->data; //暂存队头元素 x=p
front->next=p->next; //将队头元素所在结点摘链 if (p->next==NULL) rear=front; //判断出队前队列长度是否为1,如果删
除成功,返回被删元素值,否则,抛出异常删除 delete p; //如果删除成功,队头元素减少了一个
return x;
}
4-5.模块五:GetQueue函数
取链队列的队头元素
template
T LinkQueue::GetQueue() {
if (front!=rear) //判断队列是否为空 return front->next->data; //若不空,则返回队头元素 }
9
4-6. 模块六:Empty函数
判断链队列是否为空
template
bool LinkQueue::Empty( ) {
if(front==rear); //判断队列是否为空
return 1; //若为空,返回1
else
return 0; //若不为空,返回0
}
4-7. 模块七:Outputput 函数
该函数调用6个函数模板来实现火车厢重排问题,预设K个缓冲轨道,通过运用函数模板来比较各个缓冲轨道的队头元素,确定队列的出队、入队元素,最后通过输入和输出函数来实现火车厢由小到大的顺序出轨 void Output(int& minH, int& minQ, LinkQueue H[], int k, int n)
{
int c;
H[minQ].DeQueue( ) ;
cout << "Move car " << minH << " from holding track " << minQ << " to
output" << endl;
minH= n+2;
for (int i = 1; i <= k; i++) if (!H[i].Empty() &&(c = H[i].front->next->data) < minH)
{
minH = c;
minQ = i;}
}
bool Hold(int c, int& minH, int &minQ, LinkQueue H[], int k)
{
int BestTrack = 0,
BestLast = 0,
x;
for (int i = 1; i <= k; i++) if (!H[i].Empty()) {
x = H[i].rear->data;
if (c > x && x > BestLast) { BestLast = x;
BestTrack = i;}
}
10
else
if (!BestTrack) BestTrack = i; if (!BestTrack) return false; H [BestTrack ] . EnQueue ( c ) ; cout << "Move car " << c << " from input " << "to holding track " << BestTrack
<< endl;
if (c < minH) {minH = c; minQ = BestTrack ; }
return true;
}
bool Railroad(int p[], int n, int k) {
LinkQueue *H;
H = new LinkQueue [k + 1]; int NowOut = 1;
int minH = n+1;
int minS;
for (int i = 0; i < n; i++) if (p[i] == NowOut)
{
cout << "Move car " << p[i] << " from input to output" << endl;
NowOut++ ;
while (minH == NowOut)
{
Output(minH, minS, H, k, n); NowOut++ ;
}
}
else {
if (!Hold(p[i], minH, minS, H, k)) return false;
}
return true;
5.源程序
#include
const N=100;
template
struct Node
{
T data;
Node *next;
};
11
template class LinkQueue {
public:
LinkQueue( );
~LinkQueue( ); void EnQueue(T x); T DeQueue( );
T GetQueue( ); bool Empty( );
Node *front, *rear;
};
template LinkQueue::LinkQueue( )
{
Node *s;
s=new Node;
s->next=NULL;
front=rear=s;
}
template LinkQueue::~LinkQueue( )
{
while(front)
{
Node *p;
p=front->next;
delete front;
front=p;
}
}
template void LinkQueue::EnQueue(T x)
{
Node *s;
s=new Node; s->data=x;
s->next=NULL;
rear->next=s;
rear=s;
}
template T LinkQueue::DeQueue()
12
{
Node *p; int x;
if (rear==front) throw "下溢";
p=front->next;
->data; x=p
front->next=p->next;
if (p->next==NULL) rear=front; delete p;
return x;
}
template
T LinkQueue::GetQueue() {
if (front!=rear)
return front->next->data; }
template
bool LinkQueue::Empty( )
{
if(front==rear)
return 1;
else
return 0;
}
void Output(int& minH, int& minQ, LinkQueue H[], int k, int n)
{
int c;
H[minQ].DeQueue( ) ;
cout << "Move car " << minH << " from holding track " << minQ << " to
output" << endl;
minH= n+2;
for (int i = 1; i <= k; i++) if (!H[i].Empty() &&(c = H[i].front->next->data) < minH)
{
minH = c;
minQ = i;}
}
bool Hold(int c, int& minH, int &minQ, LinkQueue H[], int k)
{
int BestTrack = 0,
BestLast = 0,
x;
13
for (int i = 1; i <= k; i++) if (!H[i].Empty()) {
x = H[i].rear->data;
if (c > x && x > BestLast) { BestLast = x;
BestTrack = i;}
}
else
if (!BestTrack) BestTrack = i; if (!BestTrack) return false; H [BestTrack ] . EnQueue ( c ) ; cout << "Move car " << c << " from input " << "to holding track " << BestTrack
<< endl;
if (c < minH) {minH = c; minQ = BestTrack ; }
return true;
}
bool Railroad(int p[], int n, int k)
{
LinkQueue *H;
H = new LinkQueue [k + 1]; int NowOut = 1;
int minH = n+1;
int minS;
for (int i = 0; i < n; i++) if (p[i] == NowOut)
{
cout << "Move car " << p[i] << " from input to output" << endl;
NowOut++ ;
while (minH == NowOut)
{
Output(minH, minS, H, k, n); NowOut++ ;
}
}
else {
if (!Hold(p[i], minH, minS, H, k)) return false;
}
return true;
}
void main()
{
//int p[9]={3,6,9,2,4,7,1,8,5},i=9,j=3;
int p[N],i,j;
14
cout<<"火车总数i和缓冲轨数j"<>i>>j;
cout<<"输入火车进轨的顺序"<>p[k];
Railroad(p,i,j);
}
6. 运行结果及性能分析
6-1. 运行结果及性能分析
6-1-1.开始后的界面
15
6-1-2. 输入火车总数i=5和缓冲轨数j=3后的界面
6-1-3.随机输入1.2.3.4.5的进入顺序后开始进入重排界面
6-2. 性能分析
经过运算可得,Hold()函数的时间复杂度为O(k^k),Railroad()函数
16
的时间复杂度为O(n),其他函数的时间复杂度不能确定。
通过设计可得,我们在火车冲排问题上,尽量多建立几个缓冲轨道,有利于迅速找到火车重排的最优轨道,减少重排的时间复杂度~ 7.心得体会
在这实验途中,感觉最多的是压抑,觉得自己所学的东西是如此的肤浅,更让我觉得窝囊的是,一个课程设计程序居然照抄别人的程序,心里好郁闷。。。。感觉自己好无能。不管怎样,我希望以后的大学生活能活的心安理得点,最起码不需要在抄袭中度过,谢谢老师在满足教学评分的基础上,让我们缓交课程设计,让我们独立的把课程设计做好
虽然在此次设计成果不是很尽人意,但是在这过程又一次的惊醒了我,我学的东西很肤浅,真正要用到实际上,还差之甚远,所以在以后的过程中,还必须得不断的提高自己的分析和解决问题的能力,改变以前的学而不攻的学习态度,努力的将理论与实践结合起来,希望以后能够参加这方面的培
,把不足之处弥补过来,能够在学习中享受快乐~ 训
17