火车车厢重排问题队列c语言

1、计算机科学与工程学院算法与数据结构试验报告一专业班级10级计算机工程02试验地点计算机大楼计工教研室学生学号1005080222指导教师蔡琼学生姓名肖宇博试验时间2012-4-21试验项目算法与数据结构试验类别基础性（） 设计性（） 综合性（） 其它（ ）试验目的及要求（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。成 绩 评 定 表类 别评 分 标 准分值得分合 计上机表现积极出勤、遵守纪律主动完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分备注： 评阅教师： 日 期： 年 月 日试 验 内 容 一、实验目的和要求1、实验目的：（1）掌握队

2、列的特点及其存储方法； （2）掌握队列的常见算法和程序实现。2、 实验内容: 火车车厢重排问题。转轨站示意图如下：出 轨入 轨581742963987654321H1H3H2 出 轨入 轨 581H1H3H2963742出 轨入 轨 58H1H3H29674321出 轨入 轨5H1H3H2968754321出 轨入 轨H1H3H2987654321(a) 将369、247依次入缓冲轨(b) 将1移至出轨，234移至出轨(c) 将8入缓冲轨，5移至出轨(d) 将6789移至出轨火车车厢重排算法伪代码如下：1. 分别对k个队列初始化；2. 初始化下一个要输出的车厢编号nowOut = 1; 3.

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 如果

4、 j 不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束；3、实验要求： 使用顺序存储队列的方式完成该实验。 2、 设计分析根据实验要求，采用队列来完成本次实验。实验中定义了三个队列，一个用来存储输入的车厢号，另两个用来存储缓存出队顺序及序号。3、 源程序代码#include<stdio.h>#include<stdlib.h>#define Max 20typedef structint dataMax;int front,rear;squeue;void initqueue(squeue *&q)q=(squeu

5、e *)malloc(sizeof(squeue);q->front=q->rear=0;void enqueue(squeue *&q,int e)q->rear=(q->rear+1)%Max;q->dataq->rear=e;void dequeue(squeue *&q)q->front=(q->front+1)%Max;int gettop(squeue *&q)return q->dataq->front+1;int getrear(squeue *&q)return q->dataq

6、->rear;void reset(squeue *&q,squeue *&w1,squeue *&w2,int k)int nowout=1;int n1=0,n2=0;for(int i=0;i<50;i+)if(q->dataq->front+1=nowout)printf("%d号车厢出轨！t",q->dataq->front+1);nowout+;dequeue(q);else if(gettop(w1)=nowout)printf("%d号车厢出轨！t",gettop(w1);now

7、out+;dequeue(w1);else if(gettop(w2)=nowout)printf("%d号车厢出轨！t",gettop(w2);nowout+;dequeue(w2);elseint c=gettop(q);n1=getrear(w1);n2=getrear(w2);if(n1>n2)if(c>n1)enqueue(w1,c);dequeue(q);elseenqueue(w2,c);dequeue(q);elseif(c>n2)enqueue(w2,c);dequeue(q);elseenqueue(w1,c);dequeue(q);i

8、nt examenter(int a,int k)for(int i=1;i<=k;i+)if(ai!=i)return 0;break;void main()squeue *q,*w1,*w2;initqueue(q);initqueue(w1);initqueue(w2);int a10,k;label:printf("要输入几个车厢？n");scanf("%d",&k);if(k<=0)printf("请输入正确的车厢号!n");printf("*");printf("n&quo

9、t;);goto label;label2:printf("输入重排前的序列n");for(int i=1;i<=k;i+)scanf("%d",&ai);enqueue(q,ai);int r=examenter(a,k);if(r=0)printf("您的输入车厢号有误! 请输入连续自然数:n");goto label2;else if(r!=0)printf("重排前的序列为n");for(i=1;i<=k;i+)printf("%dt",ai);printf(&quo

10、t;n");printf("排列后的车厢号为：n");reset(q,w1,w2,k);elseprintf("我也不知道错哪了？'");四、测试用例（尽量覆盖所有分支）1.输入正确的序列后得到结果如图：2.倒输这几个数如图：3.顺序输这个序列4.如果输入的车厢数有误的时候（为负数或零）5.如果输入的序列不是连续自然数五、实验总结 先后学习了C/C+,对编程语言基本上有一些了解，但在数据结构试验程序设计过程中还是学到了很多。经过两天的设计，在不断翻阅以前资料的情况下，有针对性的复习了C/C+中指针、循环的相关理论知识和vc6.0的基础知识和应用技