cpp2.cpp

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

#include <stdio.H>
#include <stdlib.h>
#include <conio.h> 
typedef int SElemType;
typedef int Status; 
int end;/*最后一个车厢的号码*/
long total=0;/*总的组合方案数目*/ 

/***************************栈的数据结构*****************************/ 
typedef struct stacklist
{
     SElemType *base;
     SElemType *top;
     int stacksize;
}SqStack; 

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);
     }
}
/******************************核心算法结束*****************************/ 


/********************************主程序*********************************/
void main()
{
     SqStack input,temp,output;
     int i;
     printf("*****************************CARRIAGE ARRANGE***********************************\n");
     printf("                                     ---GuangDong University of Technology刘勇彬\n");
     printf("********************************************************************************");
     printf("Please input the last Number of the Carriage: ");
     scanf("%d",&end);
     printf("********************************************************************************");
     /*初始化三个栈*/
     Sinit(&input);
     Sinit(&temp);
     Sinit(&output);
     /*将车厢号码进栈*/
     for(i=end;i>=1;i--)
          SPush(&input,i);
     printf(" The total attemper mode list as follows:\n");                  
	 Set_out(&input,&temp,&output);
     printf("the total:%ld\\n",total);
     getch(); 
}