#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 Stack_init(SqStack *s) 
{ 
 s->base=(SElemType *)malloc(end*sizeof(int)); 
 if(!s->base) exit(0); 
 s->top=s->base; 
 s->stacksize=end; 
} 

void Stack_Push(SqStack *s,SElemType e) 
{ 
*(s->top)++=e; 
} 

SElemType Stack_Pop(SqStack *s) 
{ 
if(s->top==s->base) 
return 0; 
return *(--(s->top)); 
} 

Status Stack_Empty(SqStack *s) 
{ 
if(s->top==s->base) 
return 1; 
return 0; 
} 

Status Stack_Full(SqStack *s) 
{ 
if(s->top-s->base==end) 
return 1; 
return 0; 
} 
void Stack_printreverse(SqStack s) 
{ 
 int *po; 
 po=s.base; 
printf("\\t[%ld]: ",total); 
for(;po!=s.top;)  
printf("%d ",*po++); 
 printf("\\n"); 
} 

/*-------------------------棧的定義結束------------------------*/ 


/*------------------------核心算法-----------------------------*/ 
void search(SqStack *inputPoint,SqStack *tempPoint,SqStack *outputPoint) 
{ 
if(!Stack_Empty(inputPoint)) 
{ 
Stack_Push(tempPoint,Stack_Pop(inputPoint)); 
search(inputPoint,tempPoint,outputPoint); 
Stack_Push(inputPoint,Stack_Pop(tempPoint)); 
} 
if(!Stack_Empty(tempPoint)) 
{ 
Stack_Push(outputPoint,Stack_Pop(tempPoint)); 
search(inputPoint,tempPoint,outputPoint); 
Stack_Push(tempPoint,Stack_Pop(outputPoint)); 
} 
if(Stack_Full(outputPoint)) 
{ 
total++; 
Stack_printreverse(*outputPoint); 
} 
} 
/*---------------------核心算法結束--------------------------*/ 


/*-----------------------主程序-------------------------------------*/ 
void main() 
{ 
SqStack input,temp,output; 
int i; 
printf("\\n\\n\\t\\t\\t\\tArrange Carriage\\n"); 
printf("\\n\\t\\t2001 Computer Science & Technology 數字熊\\n"); 
printf("\\n\\tPlease input the last Number of the Carriage: "); 
scanf("%d",&end); 
/*初始化三個棧*/ 
Stack_init(&input); 
Stack_init(&temp); 
Stack_init(&output); 
/*將車廂號碼進棧*/ 
for(i=end;i>=1;i--) 
Stack_Push(&input,i); 
search(&input,&temp,&output); 
printf("\\n\\t\\tthe total:%ld\\n",total); 
getch(); 

}