火车二

 新葡亰操作系统     |      2020-01-22

非栈和队列
#include<iostream.h>
void Output(int NowOut, int Track, int& Last)
{ //将车厢NowOut 从缓冲铁轨移动到出轨,并修改Last
cout<< "Move car " << NowOut << " from holding track " << Track << " to output" << endl;
if (NowOut == Last) Last = 0;
}
bool Hold(int c, int last[], int track[], int k)
{ //把车厢c 移动到缓冲铁轨中
// 如果没有可用的缓冲铁轨,则返回f a l s e,否则返回t r u e
// 为车厢c 寻找最优的缓冲铁轨
// 初始化
int BestTrack = 0, // 目前最优的铁轨
BestLast = 0; // BestTr a c k中最后一节车厢
// 扫描缓冲铁轨
for(int i=1;i<=k;i++) // find best track
if (last[i]) {// 铁轨i 不为空
if (c>last[i]&&last[i]>BestLast) { // 铁轨i 尾部的车厢编号较大
BestLast=last[i];
BestTrack=i;}
}
else // 铁轨i 为空
if (!BestTrack) BestTrack = i;
if (!BestTrack) return false; // 没有可用的铁轨
// 把c 移动到最优铁轨
track[c] = BestTrack ;
last[BestTrack]=c;
cout<<"Move car "<<c<<"from input "<<"to holding track "<<BestTrack<<endl;
return true;
}
bool Railroad(int p[], int n, int k)
{// 用k 个缓冲铁轨进行车厢重排,车厢的初始次序为p [ 1 : n ]
// 如果重排成功,则返回t r u e,否则返回f a l s e
// 如果空间不足,则引发异常NoMem
// 对数组l a s t和t r a c k进行初始化
int *last=new int[k+1];
int *track=new int[n+1];
for (int i=1;i<=k;i++)
last[i]=0; // 铁轨i为空
for(i=1;i<=n;i++)
track[i]=0;
k--;
// 铁轨k 作为直接移动的通道
// 对欲输出的下一节车厢的编号置初值
int NowOut=1;
//按序输出车厢
for (i=0; i<n; i++)
if (p[i]==NowOut) {// 直接输出
cout<< "Move car "<<p[i]<<" from input to output"<<endl;
NowOut++;
// 从缓冲铁轨中输出
while (NowOut<=n&&track[NowOut])
{
Output(NowOut, track[NowOut], last[NowOut]);
NowOut++ ;
}
}
else {// 把车厢p[i] 移动到缓冲铁轨
if (!Hold(p[i], last, track, k))
return false;}
return true;
}
void main()
{
int p[9]={3,6,9,2,4,7,1,8,5},i=9,j=0;
cin>>j;
Railroad(p,i,j);

用栈写的啊
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#define stacksize 100
#define MaxLength 100
const N=100;
struct seqstack
{ int data[stacksize];
int top;
};
void Initial(seqstack *s)
{
s->top=-1;
}
int Isempty(seqstack *s)
{
return s->top==-1;
}
int Isfull(seqstack *s)
{
return int(s->top==stacksize-1);
}
void push(seqstack *s,int x)
{
if (Isfull(s))
{
cout<<"栈上益";
exit(1);
}
else s->data[++s->top]=x;
}
int Pop(seqstack *s)
{
if(Isempty(s))
{
cout<<"栈为空";
return -1;
}
return s->data[s->top--];
}
int Top(seqstack *s)
{
if(Isempty(s))
{
cout<<"栈为空";
exit(1);
}
return s->data[s->top];
}
int Hold(int c,int *minH,int *mins,seqstack H[],int k,int n)
{
int BestTrack=1,i;//目前最优车轨
int BestTop=n+1;//最优车轨上的头辆车厢
int x;//车厢索引
//扫描缓冲铁轨
for(i=1;i<k;i++)
if(!Isempty(&H[i]))//铁轨i不空
{
x=Top(&H[i]);
if(c<x&&x<BestTop)
{//铁轨i顶部的车辆编号最小
BestTop=x;
BestTrack=i+1;
}
}
else//铁轨i为空
if(!BestTrack)
BestTrack=i;
if(!BestTrack)return 0;//没有可用的车轨
push(&H[BestTrack],c);
cout<<"Move car"<<c<<"from input to holding track"<<BestTrack<<"n";
if(c<*minH)
{
*minH=c;
*mins=BestTrack;
}
return 1;
}
void Output(int *minH,int *mins,seqstack H[],int k,int n)
{
int c,i;
c=Pop(&H[*mins]);
cout<<"Move car"<<*minH<<"from holding track"<<*mins<<"to outputn";
*minH=n+2;
for(i=1;i<k;i++)
if(Isempty(&H[i])&&(c=Top(&H[i]))<*minH)
{
*minH=c;
*mins=i;
}
}
int Railroad(int p[],int n,int k)
{
seqstack *H;
int NowOut=1;
int minH=n+1;
int mins,i;
H=(seqstack *)calloc(sizeof(seqstack),(k));
for(i=0;i<n;i++)
if(p[i]==NowOut)
{
cout<<"移动车厢"<<p[i]<<"从出口到入口n";
++NowOut;
while(minH==NowOut)
{
Output(&minH,&mins,H,k,n);
NowOut++;
}
}
else{
if(!Hold(p[i],&minH,&mins,H,k,n))
return 0;
}
return 1;
}
void main()
{
int A[N];
int a,d;
cout<<"输入a表示车厢总数和d表示缓冲轨的数 "<<endl;
cin>>a>>d;
cout<<"进入车站车子的号码"<<endl;
for(int b=0;b<a;b++)
cin>>A[b];
Railroad(A,a,d);
}