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++) {
计算机科学与工程学院
《算法与数据结构》试验报告[一]
专业班级 学生学号
学生
10 级计算机工程 02 1005080222 肖宇博
试验地点 指导教师 试验时间
计算机大楼计工教研室 蔡琼
2012-4-21
试验项目
试验类别
试 验 目 的 及 要 求
算法与数据结构 基础性（） 设计性（） 综合性（√） 其它（ ）
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 不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个 空缓冲轨；否则车厢无法重排，算法结束；
if(q->data[q->front+1]==nowout) {
printf("%d 号车厢出轨！\t",q->data[q->front+1]); nowout++; dequeue(q); } else if(gettop(w1)==nowout) {
printf("%d 号车厢出轨！\t",gettop(w1)); nowout++;
（1）掌握队列的特点及其存储方法； （2）掌握队列的常见算法和程序实现。
类别 上机表现 程序与报告
成绩评定表
评分标准
分值
积极出勤、遵守纪律 主动完成设计任务
30 分
程序代码规、功能正确 报告详实完整、体现收获
70 分
得分
合计
备注：
评阅教师： 日 期：
年月日
试验 容
一、实验目的和要求
1、实验目的： （1）掌握队列的特点及其存储方法； （2）掌握队列的常见算法和程序实现。
printf("请输入正确的车厢号!\n"); printf("****************************************************"); printf("\n"); goto label; } label2: printf("输入重排前的序列\n"); for(int i=1;i<=k;i++) { scanf("%d",&a[i]); enqueue(q,a[i]); } int r=examenter(a,k); if(r==0) { printf("您的输入车厢号有误! 请输入连续自然数:\n");
58
4321
入轨
H3
7
出轨
H2
(b) 将 1 移至出轨，234 移至 出轨
H1
987654321
入轨
H3
出轨
H2 (d) 将 6789 移至出轨
1. 分别对k个队列初始化； 2. 初始化下一个要输出的车厢编号nowOut = 1; 3. 依次取入轨中的每一个车厢的编号；
3.1 如果入轨中的车厢编号等于nowOut，则 3.1.1 输出该车厢； 3.1.2 nowOut++；
3、实验要求： 使用顺序存储队列的方式完成该实验。
二、设计分析
根据实验要求，采用队列来完成本次实验。 实验中定义了三个队列，一个用来存储输入的车厢号，另两个用来存储缓 存出队顺序及序号。
三、源程序代码
#include<stdio.h> #include<stdlib.h>
#define Max 20 typedef struct {
}
} }
} }
int examenter(int a[],int k) {
for(int i=1;i<=k;i++) {
if(a[i]!=i) {
return 0; break; } } }
void main() {
squeue *q,*w1,*w2; initqueue(q); initqueue(w1); initqueue(w2); int a[10],k; label: printf("要输入几个车厢？\n"); scanf("%d",&k); if(k<=0) {
2、实验容: 火车车厢重排问题。
转轨站示意图如下：
H1
581742963
H3
入轨
H2
987654321
出轨
963
H1
581
入轨
H3
742
出轨
H2 (a) 将 369、247 依次入缓冲轨
96
H1
5
54321
入轨
H3
87
Hale Waihona Puke 出轨H2 (c) 将 8 入缓冲轨，5 移至出轨
火车车厢重排算法伪代码如下：
96
H1
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]; }
if(c>n1) {
enqueue(w1,c); dequeue(q); } else { enqueue(w2,c); dequeue(q);
} } else {
if(c>n2) {
enqueue(w2,c); dequeue(q); } else { enqueue(w1,c); dequeue(q);
dequeue(w1);
} else if(gettop(w2)==nowout) {
printf("%d 号车厢出轨！\t",gettop(w2)); nowout++; dequeue(w2);
} else {
int c=gettop(q); n1=getrear(w1); n2=getrear(w2); if(n1>n2) {
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) {