关于火车车厢排序问题
#include <stdio.h>#include <stdlib.h>
#include <iostream.h>
#include <string.h>
#define StackSize 100//假定预分配的栈空间最多元素为100个元素
#define MaxLength 100//最大的字符串长度
typedef int DataType;
typedef struct{
DataType data[StackSize];
int top;
}SeqStack;
void Initial(SeqStack *S)
{S->top=-1;}
int IsEmpty(SeqStack *S)
{ return S->top==-1;}
int IsFull(SeqStack *S)
{return S->top==StackSize-1;}
void Push(SeqStack *S,DataType x)
{if(IsFull(S)){printf("栈已满\n");exit(1);}
S->data[++S->top]=x;
}
DataType Pop(SeqStack *S)
{if(IsEmpty(S)){printf("栈已空\n");return (-1);}
return S->data[S->top--];
}
DataType Top(SeqStack *S)
{if(IsEmpty(S)){printf("栈已空\n");exit(1);}
return S->data[S->top];
}
int Hold(int c,int *minH,int *minS,SeqStack *H,int k,int n)
{
int BestTrack=0,i;//目前最优车道
int BestTop=n+1;//最优车道上的头辆车厢
DataType x;//车厢索引
for(i=1;i<=k;i++)//扫描缓冲轨道
{
if(!IsEmpty(&H[i]))
{x=Top(&H[i]);
if(c<x && x<BestTop)
{BestTop=x;BestTrack=i;}
}
else
if(!BestTrack) {BestTrack=i;}
}
Push(&H[BestTrack],c);
printf("移动车%d从出口到缓冲道%d\n",c,BestTrack);
if(c<*minH){*minH=c;*minS=BestTrack;}
if(!BestTrack){printf("没有可用的轨道\n"); return 0;}
return 1;
}
void Output(int *minH,int *minS,SeqStack H[],int k,int n)
{
int c,i;
c=Pop(&H[*minS]);
printf("移动车%d从缓冲车道%d到出口\n",*minH,*minS);
*minH=n+1;
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,a,j;
H=(SeqStack*)calloc(10,sizeof(SeqStack));
for(j=1;j<=k;j++)
{
Initial (&H[j]);
}
for(a=0;a<=n-1;a++)
{
if(p[a]==NowOut)
{printf("移动车厢%d从入口到出口\n",p[a]);NowOut++;
while(minH==NowOut){Output(&minH,&minS,H,k,n);NowOut++;}
}
else
{if(!Hold(p[a],&minH,&minS,H,k,n)) return 0;}
}
return 1;
}
void main(void)
{
int p[8]={3,2,1,8,6,7,4,5};
Railroad(p,8,4);
}