attemper.c

数据结构课程设计 车厢调度 一、需求分析 1、用编号依次为1

/*车厢调度-胡海洪*/
#include<stdio.h>
#include<conio.h>
#define MAXSIZE 45

int n;
int path[MAXSIZE];   /*定义全局变量*/

struct pathss{
 int paths[MAXSIZE][MAXSIZE];
 int number;
}AllPath;      /*定义一个二维数组来保存所有的输出序列*/

struct SNode{
 int data[MAXSIZE];
 int top;
}S;   /*栈的顺序存储结构的定义*/

void InitStack()   /*栈的初始化*/
{
 S.top=-1;
}

void Push(int q)  /*进栈*/
{
 S.data[++S.top]=q;
}

int Pop()     /*出栈*/
{
 int temp;
 temp=S.data[S.top--];
 return temp;
}

int StackEmpty()  /*判断栈是否为空*/
{
 if(S.top==-1)
   return 1;
 else
   return 0;
}

void Attemper(int pos,int path[],int cur)  /*调度过程*/
{
 int m,i;
 if(pos<n)
   {
    Push(pos+1);     /*一个数进栈后,要么立刻出栈,要么进行下一个数的进栈*/
    Attemper(pos+1,path,cur);
    Pop();
   }
 if(!StackEmpty())
   {
    m=Pop();       /*一个数出栈后,要么继续出栈(栈不空),要么继续下一个数的进栈*/
    path[cur++]=m;
    Attemper(pos,path,cur);
    Push(m);
   }
 if(pos==n && StackEmpty())   /*一种可能输出序列产生*/
   {
    printf("\t\t\t");
    printf("%2d:",AllPath.number+1);
    for(i=0;i<cur;i++)
      {
       printf("%3d",path[i]);
       AllPath.paths[AllPath.number][i]=path[i];  /*将每种序列保存在二维数组里*/
      }
    printf("\n");
    AllPath.number++;
   }
}

void Print()   /*一个栈打印操作*/
{
 int i;
 for(i=S.top;i>=0;i--)
   printf("\t\t\t  |%d|\n",S.data[i]);
}

void DisplayOnly(int k,int Output,int Input) /*显示操作序列的状态的变化过程*/
{ 
 int j;
 getchar();    /*每按一次回车,就有一次变化*/
 for(j=0;j<=Output;j++)
   printf("<----%d",AllPath.paths[k][j]);   /*负责显示输出序列的状态变化*/
 printf("\n");
 Print();  	       /*栈的状态变化*/
 printf("\t\t\t\t\t");
 for(j=Input;j<=n;j++)      /*负责显示输入序列的状态变化*/
    printf("<----%d",j);	  
 printf("\n");
}

void ChooseDisplay()    /*状态变化过程*/
{
 int k,Output,Input=1;
 printf("请输入你想要查看序列状态变化过程的序号:");
 scanf("%d",&k);
 k=k-1;
 InitStack();
 printf("\n    输出序列\t           栈\t\t  输入序列");
 DisplayOnly(k,-1,1);
 for(Output=0;Output<n;Output++)
   { 
    if(AllPath.paths[k][Output]>=Input)          /*当输出序列中当前的数据大于等于入口处*/
      {                                          /*的数据时, 入口处的数据要一直压栈,*/
       while(AllPath.paths[k][Output]>=Input)    /*直到当前的数据小于入口处的数据*/
         {
          Push(Input);
          Input++;
          DisplayOnly(k,Output-1,Input);  
         }
       Pop();
       DisplayOnly(k,Output,Input);  
      }   
    else                                  /*当序列中当前的数据小于入口处*/
      {                                   /*的数据时,弹出栈顶,重新显示结果*/
       Pop();
       DisplayOnly(k,Output,Input);  
      }
   }
}


void message()  /*菜单显示*/
{
 printf("\n\t\t\t* * * * * * * * * * * * * * * * *\n ");
 printf("\t\t\t*\t1:输入火车的长度N\t*\n");
 printf("\t\t\t*\t2:输出所有可能序列\t*\n");
 printf("\t\t\t*\t3:演示一个序列变化\t*\n");
 printf("\t\t\t*\t4:退出本程序\t\t*\n");
 printf("\t\t\t* * * * * * * * * * * * * * * * *\n");
}

void InputNumber()  /*输入序列的长度*/
{
 printf("请输入火车车厢的长度N:");
 scanf("%d",&n);
}

void DisplayAll()  /*显示所有输出序列*/
{
 AllPath.number=0;
 InitStack();
 Push(1);
 printf("所有可能的输出序列如下:\n");
 Attemper(1,path,0);
}

void main() /*主函数*/
{
 int flag;
 printf("\n");
 printf("\n");
 printf("\n");
 printf("\n");
 printf("\t\t* * * * * * * * * * * * * * * * * * * * * * * *\n");
 printf("\t\t*\t\t\t\t\t      *\n");
 printf("\t\t*\t    实习2.3  题目：车厢调度\t      *\n");
 printf("\t\t*\t\t\t\t\t      *\n");
 printf("\t\t* * * * * * * * * * * * * * * * * * * * * * * *\n");
 printf("\t\t*\t\t\t\t\t      *\n");
 printf("\t\t*\t04级计算机科学与技术1班\t胡海洪\t      *\n");
 printf("\t\t*\t\t\t\t\t      *\n");
 printf("\t\t*\t\t学号：3104006429\t      *\n");
 printf("\t\t*\t\t\t\t\t      *\n");
 printf("\t\t* * * * * * * * * * * * * * * * * * * * * * * *\n");
 printf("\n\n\n\t\t\t     请按任一键进入菜单……\n");
 getch();
 system("cls"); 
 message();
 scanf("%d",&flag);
 while(flag!=4)
   {
    switch(flag)
      {
       case 1: InputNumber();break;
  
       case 2: DisplayAll();break;
  
       case 3: ChooseDisplay();break;
      }
    message();
    scanf("%d",&flag);
   }
}