火车车厢重排问题优选,队列,c语言.docx

火车车厢重排问题优选,队列,c语言.docx计算机科学与工程学院
《算法与数据结构》试验报告 [ 一 ]
专业班级
10 级计算机工程 02
试验地点
计算机大楼计工教研室
学生学号
22
指导教师
蔡琼
学生姓名
肖宇博
试验时间
2012-4-21
试验项目
算法与数据结构
试验类别
基础性（） 设计性（） 综合性（√）
其它（ ）
试
验
（1）掌握队列的特点及其存储方法；
目
（2）掌握队列的常见算法和程序实现。
的
及
要
求
成 绩 评 定 表
类
别
评 分 标 准
分值
得分
合
计
上机表现
积极出勤、遵守纪律
30 分
主动完成设计任务
程序与报告
程序代码规范、功能正确
70 分
报告详实完整、体现收获
备注：
评阅教师：
日 期： 年 月 日
试 验 内 容
一、实验目的和要求
1、实验目的：
（1）掌握队列的特点及其存储方法；
（2）掌握队列的常见算法和程序实现。
2、实验内容 :
火车车厢重排问题。
转轨站示意图如下：
H1
3
1
3
入 轨
出 轨
H2
963 96
581
H
58
H
4321
入 轨
H
出 轨
入 轨
H
出 轨
742
7
H
H
将 369、247 依次入缓冲轨
96

(b) 将 1 移至出轨， 234 移至
5
H
54321
H
1
入 轨
H
出 轨
入 轨
H
出 轨
87
H
H
(c) 将 8 入缓冲轨， 5 移至出轨 (d) 将 6789 移至出轨
火车车厢重排算法伪代码如下：
分别对 k 个队列初始化；
2. 初始化下一个要输出的车厢编号 nowOut = 1;
依次取入轨中的每一个车厢的编号；
如果入轨中的车厢编号等于 nowOut，则输出该车厢；
nowOut++ ；
否则，考察每一个缓冲轨队列 for (j=1; j<=k; j++)
取队列 j 的队头元素 c；
如果 c=nowOut，则
3、实验要求：
使用顺序存储队列的方式完成该实验。
二、设计分析
根据实验要求，采用队列来完成本次实验。
实验中定义了三个队列，一个用来存储输入的车厢号，另两个用来存储缓
存出队顺序及序号。
三、源程序代码
#include<>
#include<>
#define Max 20
typedef struct
{
int data[Max];
int front,rear;
}squeue;
void initqueue(squeue *&q)
{
q=(squeue *)malloc(sizeof(squeue));
q->front=q->rear=0;
}
void enqueue(squeue *&q,int e)
{
q->rear=(q->rear+1)%Max;
q->data[q->rear]=e;
}
void dequeue(squeue *&q)
{
q->front=(q->front+1)%Max;
}
int gettop(squeue *&q)
{
return q->data[q->front+1];
}