火车车厢重排列问题 堆栈解决

#include "Manage.h" #include"malloc.h" #include<iostream> using namespace std; Manage::Manage(void) { count_stack=0; count=0; stacks = new List_stack[max_stacks]; } //重排列车厢，使其按从小到大顺序输出 bool Manage::arrange(Queue_entry a[],int n) { Queue_entry *b; int m=0;//标记车厢号大小顺序 rail_queue=(Queue_entry*)calloc(n,4);//创建火车队列 b=(Queue_entry*)calloc(n,4);//创建用于给原队列标号的队列 count=n;//需重排的车厢数 //重排列数组a[] for(int j=0;j<n;j++) rail_queue[j]=b[j]=a[j]; bubble_sort(b,n); max=b[count-1]+1; stack_min=max;//初始化缓冲轨中最小的车厢标号 for (int i=0; i<count; i++) { carriage_num=a[i]; if(carriage_num==b[m])//直接输出 { cout << " Move No."<<carriage_num<<" from input to output"<<endl; m++; while(stack_min==b[m])//从缓冲轨中输出 { output(); m++; } }//end if else if(!hold())//将不能输出的压入缓冲栈中 return false; }//end for cout<<"车厢重排列后输出排列如下："<<endl; for(int k=0;k<count;k++) cout << b[k] <<" "; cout<<endl<<endl; return true; }//end //将暂时不能输出的车厢放入缓冲栈中，并判断是否需要创建新的栈 bool Manage::hold() { int best_track=-1;//拥有对于要压入车厢的最优铁轨 int best_carriage=max;//最优铁轨的最小车厢标号 int temp;//用于检索车厢的临时变量 for(int i=0;i<count_stack;i++)//查看该车厢是否可压入已有栈 { stacks[i].top(temp); if(carriage_num<=temp && temp<=best_carriage) { best_carriage=temp; best_track=i; } } if(best_track==-1 && count_stack<=max_stacks)//若不能压入已有栈，压入一空栈 { best_track=count_stack; count_stack++; } if(best_track!=-1 && count_stack>max_stacks)//若无空轨道，返回重排失败。 return false; //输出移动过程 stacks[best_track].push(carriage_num); cout << " Move No." << carriage_num << " from input to holding track "<< best_track << endl; if (carriage_num<=stack_min) { stack_min=carriage_num; stack_best=best_track; } return true; } //从所有缓冲栈输出车厢号最小的车厢 void Manage::output() { stacks[stack_best].pop(); cout << " Move No."<< stack_min << " from holding track "<< stack_best << " to output"<<endl; //重新检索拥有最小车厢号的栈 int temp;//用于检索车厢的临时变量 stack_min=max; for(int i=0; i<count_stack; i++) { if(stacks[i].empty()) continue; stacks[i].top(temp); if(temp<=stack_min) { stack_min=temp; stack_best=i; }//end if }//end for }//end // void Manage::bubble_sort(Queue_entry a[],int n) //冒泡排序 { int temp; for(int i=0;i<n-1;i++) { for(int j=0;j<n-1-i;j++) if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } }//end outer for }