火车餐厅在几号车厢火车车厢重排问题.docx

本文格式为Word版，下载可任意编辑火车餐厅在几号车厢火车车厢重排问题 测验二：火车车厢重排问题 班级：2022级数学班 学号:202208101127 姓名：裴志威 一.问题描述： 一列货运列车共有n节车厢，每节车厢将停放在不同的车站假定n个车站的编号分别为1~n,货运列车按照第n站至第1站 的依次经过这些车站车厢编号与他们的目的地一样为了便于从列车上卸掉相应的车厢，务必重排车厢依次，使得各车厢 从前往后按编号1到n的次序排列当全体车厢按照这种次序排列时，在每个车站只需卸掉结果一个车厢即可我们在一个 转轨站里完成重拍的工作，在转轨站有一个入轨，一个出轨和k个缓冲轨（位于入轨和出轨之间） 二.根本要求： （1）：设计存储布局表示n个车厢，k个缓冲轨以及入轨和出轨， （2）设计并实现车厢重排算法， （3）分析算法的时间性能 三.算法描述： 为了重排车厢，需从前往后依次检查入轨上的全体车厢假设正在检查的车厢就是下一个得志要求的车厢，可以直接把它放 到出轨上否那么，那么把它移动到缓冲轨上，直到按输出依次要求轮到它的时候才可以将他放到出轨上。

缓冲轨是按照FILO 的方式使用的，由于车厢的进出都是在缓冲轨的顶端举行的 在重排车厢过程中，仅允许以下活动： 1、车厢可以从入轨的前部移动到一个缓冲轨的顶部或者是出轨的左端 2、车厢可以从一个缓冲轨的顶部移动到出轨的左端 在将车厢放入缓冲轨的过程中，理应留神：有空的可以优先放，没空的缓冲轨时，要将新的车厢放在得志以下条件的缓冲轨 中：在缓冲轨的顶部车厢编号比新车厢的编号大的全体缓冲轨中选择顶部车厢编号最小的那个 四.伪代码： 1. 分别对k个队列初始化； 2. 初始化下一个要输出的车厢编号nowOut = 1; 3. 依次取入轨中的每一个车厢的编号； 3.1 假设入轨中的车厢编号等于nowOut，那么 3.1.1 输出该车厢； 3.1.2 nowOut++； 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.2 nowOut++； 3.3 假设入轨和缓冲轨的队头元素没有编号为nowOut的车厢，那么 3.3.1 求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j; 3.3.2 假设 j 存在，那么把入轨中的第一个车厢移至缓冲轨 j； 3.3.2 假设 j 不存在，但有多于一个空缓冲轨，那么把入轨中的第一个车厢移至一个空缓冲轨；否那么车厢无法重排，算法终止； 五.源程序代码： #include #include #define Max 20 typedef struct int data[Max]; int front,rear; }squeue; void initqueue(squeue *q) { } void enqueue(squeue *q,int e) { } void dequeue(squeue *q) { } int gettop(squeue *q) { } int getrear(squeue *q) { } void reset(squeue *q,squeue *w1,squeue *w2,int k) { int nowout=1; int n1=0,n2=0; for(int i=0;i50;i++) { if(q-data[q-front+1]==nowout) { { } return q-data[q-rear]; return q-data[q-front+1]; q-front=(q-front+1)%Max; q-rear=(q-rear+1)%Max; q-data[q-rear]=e; q=(squeue *)malloc(sizeof(sq第一文库网ueue)); q-front=q-rear=0; } nowout++; dequeue(q); else if(gettop(w1)==nowout) { printf("%d号车厢出轨！\t",gettop(w1)); nowout++; dequeue(w1); } else if(gettop(w2)==nowout) { } else { int c=gettop(q); n1=getrear(w1); n2=getrear(w2); if(n1n2) { if(cn1) { } else { enqueue(w2,c); dequeue(q); enqueue(w1,c); dequeue(q); printf("%d号车厢出轨！\t",gettop(w2)); nowout++; dequeue(w2); } else { } if(cn2) { enqueue(w2,c); dequeue(q); } else { enqueue(w1,c); dequeue(q); } } } } int examenter(int a[],int k) { } void main() { squeue *q,*w1,*w2; initqueue(q); initqueue(w1); initqueue(w2); int a[10],k; label: printf("要输入几个车厢？\n"); for(int i=1;i=k;i++) { } if(a[i]!=i) { } return 0; break; scanf("%d",k); if(k=0) { } printf("请输入正确的车厢号!\n"); printf("****************************************************"); printf("\n"); goto label; } for(int i=1;i=k;i++) { } int r=examenter(a,k); if(r==0) { } else if(r!=0) { } else { } printf("我也不知道错哪了？""); printf("重排前的序列为\n"); for(i=1;i=k;i++) { } printf("\n"); printf("排列后的车厢号为：\n"); reset(q,w1,w2,k); printf("%d\t",a[i]); printf("您的输入车厢号有误! 请输入连续自然数:\n"); goto label2; scanf("%d",a[i]); enqueue(q,a[i]); 六.测试结果 1.输入正确的序列后得到结果如图： 2.假设输入的车厢数有误的时候（为负数或零） 六、总结 本次数据布局测验主要是练习使用队列的思想，我做的是火车重排问题的测验，此测验在课本上有一些讲解，也给出来主要函数TrainPermute()的主要编写思路，减轻了自己的工作量，不过由于此程序的代码对比繁杂，在编译调试过程中也很花费时间，通过设置断点，分步调试，才使得程序没有了bug。

例如，由于程序用了较多的循环，包括多重循环，在刚刚写出代码的时候往往陷入死循环，而由于代码冗长，仅仅通过看代码很难找出规律上的错误功夫不负有心人，结果终究用与非门的思想解决了这个死循环问题，并简朴优化程序 总的来说，本程序由于使用了模板类布局，扩展性还算对比好但是代码片面有些冗长，可读性不算太好假设要做下 一步工作的话，理应是尽量精简代码，使得程序更加具有实用性和可读性 — 7 —。