计算机科学与工程学院
《算法与数据结构》试验报告[ 一 ]
专业班级 学生学号
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
742
H
7
出 轨
H
96
H
(a) 将 369、247 依次入缓冲轨
(b) 将 1 移至出轨， 234 移至
H
H
5
入 轨
54321
H
87
1
H
出 轨
入 轨
出 轨
H H
(c) 将 8 入缓冲轨， 5 移至出轨 (d) 将 6789 移至出轨
火车车厢重排算法伪代码如下：
1. 分别对 k 个队列初始化； 2. 初始化下一个要输出的车厢编号
nowOut = 1;
3. 依次取入轨中的每一个车厢的编号；
如果入轨中的车厢编号等于 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];
}
int getrear(squeue *&q) {
{
return q->data[q->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->data[q->front+1]==nowout) {
printf(\号车厢出轨！ \\t\ nowout++; dequeue(q);
}
else if(gettop(w1)==nowout) {
printf(\号车厢出轨！ \\t\ nowout++; dequeue(w1);
}
火车车厢重排问题--优选,队列,c语言.docx
