d0.c

输出入口处车厢编号依次为1,2,3,...n的所有可能输出的长度.堆栈的数据类型实现 数据结构题集c语言版(严蔚敏版)中2.3的可行程序

void Sinit(SqStack *s)										/*初始化栈*/
{
     s->base=(SElemType *)malloc(end*sizeof(int));
     if(!s->base) exit(0);
     s->top=s->base;
     s->stacksize=end;
} 

void SPush(SqStack *s,SElemType e)							/*进栈*/
{
     *(s->top)++=e;
} 

SElemType SPop(SqStack *s)									/*出栈*/				
{
     if(s->top==s->base)
          return 0;
     return *(--(s->top));
} 

Status SEmpty(SqStack *s)									/*判断栈是否为空*/
{
     if(s->top==s->base)
          return 1;
     return 0;
} 

Status SFull(SqStack *s)									/*判断栈是否为满*/																			
	
{
     if(s->top-s->base==end)
          return 1;
     return 0;
}

void SPReverse(SqStack s)									/*反序输出栈的元素*/
{
     int *po;
     po=s.base;
     printf("[%ld]:   ",total);
     for(;po!=s.top;) 
          printf("%d ",*po++);
     printf("\n");
} 
/*****************************栈的定义结束*****************************/ 


/*******************************核心算法*******************************
无论如何调度无非是“出”“进”两种情况，本算法用回溯的递归原理利用
调度栈temp和出栈output，反复调用函数Set_out实现各个车厢所有可能出栈
的情况
***********************************************************************/
void Set_out(SqStack *inputPoint,SqStack *tempPoint,SqStack *outputPoint)
{
     if(!SEmpty(inputPoint))
     {
          SPush(tempPoint,SPop(inputPoint));
          Set_out(inputPoint,tempPoint,outputPoint);
          SPush(inputPoint,SPop(tempPoint));
     }
    
     if(!SEmpty(tempPoint))
     {
          SPush(outputPoint,SPop(tempPoint));
          Set_out(inputPoint,tempPoint,outputPoint);
          SPush(tempPoint,SPop(outputPoint));
     }
     
     if(SFull(outputPoint))
     {
          total++;
          SPReverse(*outputPoint);
     }
}
/******************************核心算法结束*****************************/