车厢调度4.cpp.txt

关于数据结构

#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("%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("请输入车厢的序列的长度:");   
    
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(); 
}