072.火车车厢重排

  

   

    

     

    
    

     

      #include "stdafx.h"
     
    
   

    

     

    
    

     

      #include "stdio.h"
     
    
   

    

     

    
    

     

      #include "iostream.h"
     
    
   

    

     

    
    

     

      #include "stdlib.h"
     
    
   

    

     

    
    

     

      #include "malloc.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("栈上溢"); //上溢,退出运行
     
    
   

    

     

    
    

     
		exit(1);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	S->data[++S->top]=x;//栈顶指针加1后将x入栈
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      //出栈
     
    
   

    

     

    
    

     

      DataType Pop(SeqStack *S)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if(IsEmpty(S))
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("栈为空"); //下溢,退出运行
     
    
   

    

     

    
    

     
		return -1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return S->data[S->top--];//栈顶元素返回后将栈顶指针减1
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      // 取栈顶元素
     
    
   

    

     

    
    

     

      DataType Top(SeqStack *S)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if(IsEmpty(S))
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("栈为空"); //下溢,退出运行
     
    
   

    

     

    
    

     
		exit(1);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return S->data[S->top];
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int Hold(int c,int *minH, int *minS,SeqStack H[],int k, int n)
     
    
   

    

     

    
    

     

      {// 在一个缓冲铁轨中放入车厢c
     
    
   

    

     

    
    

     
	// 如果没有可用的缓冲铁轨，则返回0
     
    
   

    

     

    
    

     
	// 如果空间不足，则引发异常N o M e m
     
    
   

    

     

    
    

     
	// 否则返回1
     
    
   

    

     

    
    

     
	// 为车厢c寻找最优的缓冲铁轨
     
    
   

    

     

    
    

     
	// 初始化
     
    
   

    

     

    
    

     
	int BestTrack = 0,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;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else // 铁轨i 为空
     
    
   

    

     

    
    

     
			if (!BestTrack) 
     
    
   

    

     

    
    

     

      				BestTrack = i;
     
    
   

    

     

    
    

     
			if (!BestTrack) 
     
    
   

    

     

    
    

     
				return 0; //没有可用的铁轨
     
    
   

    

     

    
    

     
			//把车厢c 送入缓冲铁轨
     
    
   

    

     

    
    

     
			Push(&H[BestTrack],c);
     
    
   

    

     

    
    

     
			printf("Move car %d from input to holding track %d\n" ,c, BestTrack);
     
    
   

    

     

    
    

     
			//必要时修改minH 和minS
     
    
   

    

     

    
    

     
			if (c<*minH) {
     
    
   

    

     

    
    

     

      				*minH = c; 
     
    
   

    

     

    
    

     

      				*minS = BestTrack; 
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			return 1;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void Output(int* minH, int* minS, SeqStack H[ ], int k, int n)
     
    
   

    

     

    
    

     

      { //把车厢从缓冲铁轨送至出轨处，同时修改m i n S和m i n H
     
    
   

    

     

    
    

     
	int c,i; // 车厢索引
     
    
   

    

     

    
    

     
	// 从堆栈m i n S中删除编号最小的车厢minH
     
    
   

    

     

    
    

     

      	c=Pop(&H[*minS]) ;
     
    
   

    

     

    
    

     
	printf("Move car %d from holding track %d to output\n",*minH,*minS);
     
    
   

    

     

    
    

     
	// 通过检查所有的栈顶，搜索新的m i n H和m i n S
     
    
   

    

     

    
    

     

      	*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)
     
    
   

    

     

    
    

     

      {// k个缓冲铁轨，车厢初始排序为p [1:n]
     
    
   

    

     

    
    

     
	// 如果重排成功，返回1，否则返回0
     
    
   

    

     

    
    

     
	// 如果内存不足，则引发异常NoMem 。
     
    
   

    

     

    
    

     
	//创建与缓冲铁轨对应的堆栈
     
    
   

    

     

    
    

     

      	SeqStack *H;
     
    
   

    

     

    
    

     
	int NowOut = 1; //下一次要输出的车厢
     
    
   

    

     

    
    

     
	int minH =n+1; //缓冲铁轨中编号最小的车厢
     
    
   

    

     

    
    

     
	int minS,i; //minH号车厢对应的缓冲铁轨
     
    
   

    

     

    
    

     

      	H=(SeqStack*)calloc((k+1),sizeof(SeqStack)*(k+1));
     
    
   

    

     

    
    

     
	//车厢重排
     
    
   

    

     

    
    

     
	for (i = 1; i<= n; i++)
     
    
   

    

     

    
    

     
		if (p[i] == NowOut) {// 直接输出t
     
    
   

    

     

    
    

     
			printf("移动车厢%d从出口到入口",p[i]);
     
    
   

    

     

    
    

     

      			NowOut++;
     
    
   

    

     

    
    

     
			//从缓冲铁轨中输出
     
    
   

    

     

    
    

     
			while (minH == NowOut) {
     
    
   

    

     

    
    

     
				Output(&minH, &minS, H, k, n);
     
    
   

    

     

    
    

     

      				NowOut++;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else {// 将p[i] 送入某个缓冲铁轨
     
    
   

    

     

    
    

     
			if (!Hold(p[i], &minH, &minS, H, k, n))
     
    
   

    

     

    
    

     
				return 0;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		return 1;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void main(void)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int p[8]={2,4,1,6,5,3,8,7};
     
    
   

    

     

    
    

     
	Railroad(p,8,4);
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：程序员编程指南，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_41055260/article/details/124518288