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

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

2、列的常见算法和程序实现。2、实验容:火车车厢重排问题。转轨站示意图如下：Hi581963H11ii* 入轨；H3r742.；出轨IH2(a)将369、247依次入缓冲轨965H154321入轨H387r岀轨H2(c)将8入缓冲轨，5移至岀轨58”!96I-'H1i;i14321入轨:H311 1:7一i岀轨H2(b)将1移至出轨，234移至1111987654321H1'11入轨:11H3!11岀轨H2(d)将6789移至出轨581742963*H3987654321入轨1岀轨.H2_>火车车厢重排算法伪代码如下:1. 分别对k个队列初始化；2. 初始化下一个要输出的车厢

3、编号nowOut = 1;3. 依次取入轨中的每一个车厢的编号；3.1如果入轨中的车厢编号等于 nowOut，贝U输岀该车厢；3.1.2 nowOut+ ;3.2否则，考察每一个缓冲轨队列for (j=1; jv=k; j+ )取队列j的队头元素c；3.2.2 如果 c=nowOut，贝U将队列j的队头元素出队并输出；3.2.2.2 nowOut+ ；3.3如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢，则求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j；如果j存在，则把入轨中的第一个车厢移至缓冲轨j；如果j不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个 空缓冲轨；

4、否则车厢无法重排，算法结束；3、实验要求： 使用顺序存储队列的方式完成该实验。二、设计分析根据实验要求，采用队列来完成本次实验。实验中定义了三个队列，一个用来存储输入的车厢号，另两个用来存储缓 存出队顺序及序号。三、源程序代码#i nclude<stdio.h>#in clude<stdlib.h>#defi ne Max 20typedef struct int dataMax; int fron t,rear;squeue;void in itqueue(squeue *&q)q=(squeue *)malloc(sizeof(squeue);q->f

5、ro nt=q->rear=0;void enq ueue(squeue *&q,i nt e) q->rear=(q->rea 叶1)%Max; q->dataq->rear=e; void dequeue(squeue *&q)q->fro nt=(q->fro nt+1)%Max; int gettop(squeue *&q)retur n q->dataq->fr on t+1; int getrear(squeue *&q)retur n q->dataq->rear;void rese

6、t(squeue *&q ,squeue *&w1,squeue *&w2,i nt k)int no wout=1;int n1=0 ,n 2=0;for(int i=0;i<50;i+) if(q->dataq->fr on t+1=no wout)prin tf("%d号车厢出轨！ t",q->dataq->fro nt+1);no wout+;dequeue(q);else if(gettop(w1)=no wout)prin tf("%d号车厢出轨！ t",gettop(w1);no wou

7、t+;dequeue(wl);else if(gettop(w2)=no wout)prin tf("%d号车厢出轨！ t",gettop(w2);no wout+;dequeue(w2);elseint c=gettop(q);n 1=getrear(w1);n 2=getrear(w2);if(n 1> n2)if(c>n 1)enq ueue(w1,c); dequeue(q);elseenq ueue(w2,c); dequeue(q);elseif(c>n 2)enq ueue(w2,c); dequeue(q);elseenq ueue(w1,

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

9、; I *");prin tf("n");goto label;Iabel2:printf("输入重排前的序列n");for(i nt i=1;i<=k;i+)scan f("%d",&ai); enq ueue(q,ai);int r=exame nter(a,k); if(r=0)printf("您的输入车厢号有误！请输入连续自然数：n"); goto Iabel2;else if(r!=0)printf("重排前的序列为n");for(i=1;i<=k;i+)

10、prin tf("%dt",ai);prin tf("n");printf("排列后的车厢号为：n");reset(q,w1,w2,k);elseprin tf("我也不知道错哪了？'");四、测试用例(尽量覆盖所有分支)1.输入正确的序列后得到结果如图：要输人几个车厢?581742963童裤前的序列为581c ami: iriue5号车Jffi出轨!P>e*s anu kyo% *C： Du>匚ajid. Set tiigsAAdB ini. a Hr ator 桌fell。疋"卓火车dI X7出出 车车 Imlr4Id2.倒输这几个数如图:非前陀序列为号辜黑岀轨I2A寻车厢岀軌！?c ortl: £nue要输人几个车厢T弓号车厢岀軌I P>e*s eny ky tn7«Y ©ID3.顺序输这个序列iASShmj?列5?吗出出车车Imlr4如果输入的车厢数有误的时候（为负数或零）5.如果输入的序列不是连续自然数五、实验总结先后学习了 C/C+,对编程语言基本上有一些了解，但在数据结构试验程序 设计过程中还是学到了很多。经过两天的设计，在不断翻阅以前资料的情况下，有针对性的复习了 C/C+中指针、循环的相关理论知识和 VC6.