火车厢重排问题

火车厢重排问题 目录 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个函数模板来实现火车厢重排问题，预设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 knext->假 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