trai改进版2.cpp

解决车厢重排问题

#include<iostream.h>
#include<stack>
#include<iomanip.h>
using namespace std;
void input_innum(int n,int *input)
{   cout<<"输入顺序就是进入轨道顺序"<<endl;
	for(int i=0;i<n;i++){
		cout<<"Please input the "<<i+1<<" carriage's number:"<<endl;
	    cin>>input[i];
	 
	}
}
void order(int n,int *input,int *Nowout)
{int i,j,t,z;
	for( i=0;i<n;i++){
		Nowout[i]=input[i];
	}
	for(i=0;i<n;i++){
        z=0;  
		for(j=0;j<n-i-1;j++){
			if(Nowout[j]>Nowout[j+1]){
				t=Nowout[j]; Nowout[j]=Nowout[j+1];  Nowout[j+1]=t; z=1;
			}
		}
		if(z==0)  break;
	}
}

int find(int k,int &minS,int &minH,stack<int> **H){//找出此时缓冲轨道顶中最小的编号车厢及轨道编号
	int j=0;//j判断是不是缓冲轨道都为空，j=0缓冲轨道全为空，无需比较，否则，比较得到minH		
	minH=101; 
	for(int i=1;i<=k;i++){
				if(!(*H[i]).empty() && (*H[i]).top()<=minH){
					minH=(*H[i]).top();
					minS=i;  j=1;
				}
	}
	 if(j==0)  {minH=0;}

   return 0;
}
int pushin(int d,int &k,int n,stack<int> **H){//将即将送入缓冲轨道的车厢送入合适的缓冲轨道
		int BestTrack=0;//目前最优的缓冲铁轨
		int BestTop=100;//目前最优的铁轨的头辆车厢
		if(k==0){ 
			k++;
			H[k]=new stack<int>;  
			(*H[k]).push(d);
			cout<<"Move car "<<d<<" from input to holding track "<<k<<endl;
		
		}
		else{int j=0;//j用来判断是不是有合适的缓冲轨道，j=1表示有 j=0表示没有
           for(int i=1;i<=k;i++){
			   if((*H[i]).empty()){//铁轨为空
				          (*H[i]).push(d);
						  cout<<"Move car "<<d<<" from input to holding track "<<i<<endl;
						  return 0;
			   }
				   
			   else{//铁轨不为空
				  
				   int x=(*H[i]).top(); 
				   if(x>=d && x<BestTop){
					   BestTop=x;
					   BestTrack=i;
				       j=1;
				   
			   }
			  }
		   }
		   if(j==1){//存在可以压入的缓冲轨道
				(*H[BestTrack]).push(d);
				cout<<"Move car "<<d<<" from input to holding track "<<BestTrack<<endl;
			
		   }else if(j==0){//不存在满足条件的缓冲轨道，需要新创建一个缓冲轨道
			   k++;
			   H[k]=new stack<int> ;
			   (*H[k]).push(d);
			   cout<<"Move car "<<d<<" from input to holding track "<<k<<endl;
			 
		   }
		}
		return 0;
}
//--------------------------------------------------------------------------------------------
int main() 
{
  int n,i,j=0,k=0; //n 为 车厢数 ,i用来计数 ,k表示缓冲轨道数 Nowout为下一次出轨所需的数  j用来指向Nowout[j]
  int *input,*Nowout;
  stack<int> output;// input 为入轨队列  output 为出轨对列 
  stack<int>* H[100];  //创建于缓冲轨道对应的堆栈
  char ch;  //控制可以反复调用主函数
  int minH=101;  //minH为缓冲铁轨中编号最小的车厢
  int minS=0;   //minS为minH号车厢对应的缓冲铁轨

  //------------------------------------------------------------------------------------
 do{  
    cout<<"Please input the number of train!"<<endl;
    cin>>n; 
	input=new int[n];
	Nowout=new int[n];
	input_innum(n,input);
	order(n,input,Nowout);
	cout<<"*******************************************"<<endl;
	for(i=0;i<n;i++){
		if(input[i]==Nowout[j]){//直接输出
				cout<<"Move car "<<input[i]<<" from input to output"<<endl;
				output.push(Nowout[j]);
				j++;
				if(k==0)  continue;
			//从缓冲轨道输出
				else{
					find(k,minS,minH,H); 
					while(Nowout[j]==minH){
						cout<<"Move car "<<minH<<" from holding track "<<minS<<" to output"<<endl;
						output.push(Nowout[j]);
						(*H[minS]).pop();  
						j++; minH=n+1;
						find(k,minS,minH,H); 
					}
				}
		}
	    else{//将input.top()送入缓冲轨道
             
 			pushin(input[i],k,n,H);      
		}
	}
	cout<<"*******************************************"<<endl;
	cout<<"The out order is(右端为先出端口):";
	while(!output.empty()){
		cout<<output.top()<<" ";
		output.pop();
	}
	cout<<endl;
	cout<<"Used the tracks are: "<<k<<endl;
	cout<<"Continue?(yes-anykey||no-'N'or'n')"<<endl;
	cin>>ch;
	minH=101; j=0;
    k=0;
 }while((ch!='N') && (ch!='n'));
	return 0;
}