入栈与出栈的所有排列可能性

文章类别：C语言程序设计 | 发表日期:2008-9-24 14:45:38

#include <stdio.h>
#include <stdlib.h>
#include <bios.h>
#include <string.h>
#include <graphics.h>
/*定义全局变量*/
int pu=0,po=0,t=0;
char tp[130][12];

/*用栈排出入栈出栈的顺序*/
struct train{
  int numb;
  struct train *next;
  };

struct push{
  int a;
  int b;
  char data[24];
  struct push *next;
  };

struct push *creat(struct push *top)
{
  top=(struct push *)malloc(sizeof(struct push));
  top->next=NULL;
  return top;
}

struct push *pup(struct push *top,int a,int b,int n)
{
  struct push *p,*q;
  q=top->next;
  p=(struct push *)malloc(sizeof(struct push));
  p->a=a;
  p->b=b;
  if(q)
    strcpy(p->data,q->data);
  if(q->a<n||!q)
   {
    p->data[a+b-1]='r';
    p->data[a+b]='\0';
   }
  else
   {
     p->data[a+b-1]='c';
     p->data[a+b]='\0';
   }
  p->next=top->next;
  top->next=p;
return top;
}

struct push *pop(struct push *top)
{
  top=top->next;
  return top;
}

struct push *apaili(struct push *top,int numb)  /*向后移动一个出命令*/
{
  struct push *q;
  q=top->next;
  if(pu<numb)
   {
     pu++;
     top=pup(top,pu,po,numb);
     top=apaili(top,numb);
    }
   if(po<numb)
    {
      po++;
      top=pup(top,pu,po,numb);
      top=apaili(top,numb);
     }
     return top;
}

struct push *bpaili(struct push *top,int numb) /*移动第一个出命令到最后*/
{
  int a,b,cir;
  char x[22];
  struct push *p;
     do{
  p=top->next;
  p=p->next;
  a=p->a;
  b=p->b;
  if(p->data[a+b-1]=='r')
  break;
  else
  {
  do{
      top=pop(top);
      p=top->next;
      a=p->a;
      b=p->b;
    }while(p->data[a+b-1]=='c');
  if(a==1)
    {
      cir=1;
      break;
      }
  top=pop(top);
  a--;
  b++;
  top=pup(top,a,b,numb);
  top->next->data[a+b-1]='c';
  pu=a;
  po=b;
  top=apaili(top,numb);
  strcpy(x,top->next->data);
  if(jc(x))
  {
    strcpy(tp[t],x);
    t++;
  }
  }
     }while(a+b<2*numb);
     if(cir==1)
     return top;
     top=pop(top);
     top=bpaili(top,numb);

}

int jc(char c[22])
{
  int i=0,k=0;
  if(c[i]!=0)
  do{
     if(c[i]=='r')
     k++;
     if(c[i]=='c')
     k--;
     if(k<0)
     return 0;
     i++;
     }while(c[i]!='\0');
     return 1;
}

/*调用排好的顺序进行入栈与出栈操作*/
struct train *tcreat(struct train *ttop)
{
  ttop=(struct train *)malloc(sizeof(struct train));
  ttop->next=NULL;
  return ttop;
 }

struct train *tpup(struct train *ttop,int data)
{
  struct train *p;
  p=(struct train *)malloc(sizeof(struct train));
  p->numb=data;
  p->next=ttop->next;
  ttop->next=p;
  return ttop;
  }

struct train *tpop(struct train *ttop)
{
 int data;
 struct train *p;
 p=ttop->next;
 data=p->numb;
 ttop=ttop->next;
 printf("%d ",data);
 return ttop;
 }

inso(char c[22],int n)
{
  int i,k=0,begin[12];
  struct train *ttop;
  ttop=tcreat(ttop);
  for(i=0;i<n;i++)
  begin[i]=i+1;
  i=0;
  if(c[i]!='\0')
  while(c[i]!='\0')
  {
    switch(c[i])
    {
      case 'r': ttop=tpup(ttop,begin[k]);
  k++;
  break;
      case 'c': ttop=tpop(ttop);
  break;
      }
    i++;
    }
}

/*输出所有情况*/
print(int k)
{
 int i,j=0,m;
 for(i=0;i<t;i++)
 {
  if(i%2==0)
  {
   m=8+j;
   gotoxy(5,m);
  }
  j++;
  printf("第%3d种排列:",i+1);
  inso(tp[i],k);
  gotoxy(32,m);
  if((i+1)%16==0)
  {
   getch();
   j=0;
   }
 }
}

/*产生随机数功能函数*/
int ram()
{
  int a,b;
  b=random(100);
  if(b<=100)
  a=4;
  if(b<=60)
  a=3;
  if(b<=30)
  a=2;
  if(b<=10)
  a=1;
  return a;
  }

int aram()
{
 int a,b;
 b=random(120);
 if(b<=120)
 a=3;
 if(b<=60)
 a=2;
 if(b<=20)
 a=1;
 if(b<=5)
 a=0;
 return a;
}

/*清屏功能函数*/
void clears(int x,int y,int n,int m)
{
   setfillstyle(1,8);
   bar(x,y,n,m);

}

/*提示栏信息库*/
tel(int n)
{
 switch(n)
 {
 case 1:clears(459,300,625,465);
  gotoxy(59,21);
  printf("这是输入平台一");
  gotoxy(59,23);
  printf("输入要调用货车厢个数");
         gotoxy(59,25);
         printf("它必须不大于现有个数");
  break;
  case 2:clears(459,300,625,465);
  gotoxy(59,21);
  printf("这是输入平台二");
  gotoxy(59,23);
  printf("你想要调用客车厢个数");
          gotoxy(59,25);
         printf("它必须不大于现有个数");
  break;
  case 3:clears(459,300,625,465);
  gotoxy(59,21);
  printf("这是输入平台三");
  gotoxy(59,23);
  printf("邮件车厢要用到多少个");
         gotoxy(59,25);
         printf("它必须不大于现有个数");
  break;
  case 4:clears(459,300,625,465);
  gotoxy(59,21);
  printf("这里是操作提示框");
  gotoxy(59,23);
         printf("它可以给你操作提示");
         gotoxy(59,25);
  printf("看清信息后任意键继续");
  break;
  case 5:clears(459,300,625,465);
  gotoxy(59,21);
  printf("正在输出资料");
  gotoxy(59,23);
  printf("任意键查看下一页");
  break;
  case 6:clears(459,300,625,465);
  moveto(460,310);
  setcolor(12);
  outtext("WARING !");
  gotoxy(59,23);
  printf("输入的数字是非法的");
  gotoxy(59,25);
  printf("看清信息，任意键重输");
  break;
  case 7:clears(459,300,625,465);
  moveto(460,310);
  setcolor(12);
  outtext("WARING !");
  gotoxy(59,23);
  printf("输入的数字错误的");
  gotoxy(59,25);
  printf("看清信息，按键重输");
  break;
  case 8:clears(459,300,625,465);
  moveto(460,310);
  setcolor(12);
  outtext("ok!");
  gotoxy(59,23);
  printf("车厢已经排列好");
  gotoxy(59,25);
  printf("按键查看所有排列顺序");
  break;
  case 9:clears(459,300,625,465);
  gotoxy(59,21);
  printf("这是输入平台四");
  gotoxy(59,23);
  printf("输入你要的排列的序号");
  gotoxy(59,25);
  printf("选择后");
  gotoxy(59,27);
  printf("系统将排列演示");
  break;
 case 10:clears(459,300,625,465);
  gotoxy(59,21);
  printf("正在根据你的选择");
  gotoxy(59,23);
  printf("进行调度演示");
  break;
 case 11:clears(459,300,625,465);
  gotoxy(59,21);
  printf("车厢调度成功");
  gotoxy(59,23);
  printf("顺序如右图所示");
  break;
 case 12:clears(459,300,625,465);
  gotoxy(59,21);
  printf("又有车头进站");
  gotoxy(59,23);
  printf("要为它安排车厢吗");
  gotoxy(59,25);
  printf("(Y/N)");
  break;
  }
}

/*车头信息库*/
int atri(void)
{
  gotoxy(60, 5);
  printf("这是一辆AT型车头");
  gotoxy(60,6);
  printf("最多可以带2个车厢");
  return 2;
}

int btri(void)
{
  gotoxy(60,5);
  printf("这是一辆BT型车头");
  gotoxy(60,6);
  printf("最多可以带3个车厢");
  return 3;
 }

int ctri(void)
{
  gotoxy(60,5);
  printf("这是一辆CT型车头");
  gotoxy(60,6);
  printf("最多可以带4个车厢");
  return 4;
 }

int dtri(void)
{
  gotoxy(60,5);
  printf("这是一辆DT型车头");
  gotoxy(60,6);
  printf("最多可以带5个车厢");
  return 5;
}

/*车厢信息库*/
truk(int a,int b)
{
  setcolor(BROWN);
  rectangle(a,b,a+70,b+20);
  setfillstyle(6,6);
  bar(a+1,b+1,a+69,b+19);
}

passage(int a,int b)
{
  setcolor(BROWN);
  rectangle(a,b,a+70,b+20);
  setfillstyle(2,1);
  bar(a+1,b+1,a+69,b+19);
}

mail(int a,int b)
{
  setcolor(BROWN);
  rectangle(a,b,a+70,b+20);
  setfillstyle(2,WHITE);
  bar(a+1,b+1,a+69,b+19);
}

carbox()
{
  truk(460,160);
  passage(460,200);
  mail(460,240);
}

/*车厢个数显示信息*/
ttel(a,b,c)
{
  gotoxy(69,11);
  printf("货厢%d个",a);
  gotoxy(69,14);
  printf("客厢%d个",b);
  gotoxy(69,16);
  printf("邮厢%d个",c);
}

/*图象*/
door(int a,int b,int c)
{
 setcolor(YELLOW);
 rectangle(1,1,637,478);
 rectangle(10,27,628,468);
 line(1,20,637,20);
 setfillstyle(1,3);
 bar(2,2,636,19);
 setfillstyle(1,8);
 bar(11,28,627,467);
 moveto(7,7);
 settextstyle(5,0,4);
 setcolor(5);
 outtext("J01126 WANGBIN");
 setcolor(YELLOW);
 rectangle(450,27,457,468);
 rectangle(11,400,450,407);
 rectangle(457,120,628,138);
 rectangle(457,280,628,298);
 setfillstyle(1,9);
 bar(451,28,456,467);
 bar(12,401,449,406);
 bar(2,21,636,26);
 bar(2,21,9,477);
 bar(2,469,636,477);
 bar(629,21,636,477);
 line(458,45,627,45);
 setfillstyle(1,4);
 bar(458,28,627,44);
 bar(458,121,627,137);
 bar(458,281,627,297);
 setcolor(GREEN);
 moveto(460,35);
 outtext("STATION'S INFORMATION");
 moveto(460,128);
 outtext("COMPATE'S INFORMATION");
 moveto(465,287);
 outtext("MESSAGE");
 carbox();
 ttel(a,b,c);
 }

int nform(void)
{
  int numb;
  setcolor(YELLOW);
  rectangle(150,150,350,230);
  rectangle(153,153,347,227);
  line(150,150,155,155);
  line(150,230,155,225);
  line(350,230,345,225);
  line(350,150,345,155);
  setfillstyle(1,9);
  bar(154,154,346,226);
  moveto(170,170);
  outtext("INPUT THE NUMBER ");
  setfillstyle(1,8);
  bar(170,190,290,210);
  gotoxy(30,13);
  scanf("%d",&numb);
  return numb;
 }

void initt()
{
  int graphdrive=IBM8514LO;
  int graphmode=IBM8514HI;
  initgraph(&graphdrive,&graphmode," ");
  setbkcolor(8);
  }

/*动态信息*/
int headtrain()
{
  int i,z;
  i=ram();
  switch(i)
  {
    case 1:clears(459,47,625,110);
    z=atri();
    break;
    case 2:clears(459,47,625,110);
    z=btri();
    break;
    case 3:clears(459,47,625,110);
    z=ctri();
    break;
    case 4:clears(459,47,625,110);
    z=dtri();
    break;
    }
    return z;
}

ptrain(int a,int b,int c)
{
 int i;
 if(a==0)
 for(i=0;i<c;i++)
 truk(15+(b-c+i)*75,425);
 if(a==1)
 for(i=0;i<c;i++)
 passage(15+(b-c+i)*75,425);
 if(a==2)
 for(i=0;i<c;i++)
 mail(15+(b-c+i)*75,425);
}

/*主键面*/
first()
{
 int k,i,m,tr,pa,ma,ci;
 char c[22];
 struct push *top,*p;
 clrscr();
 tr=aram();
 do{
 pa=aram();
 }while(pa==tr);
 do{
 ma=aram();
 }while(ma==pa||ma==tr);
 door(tr,pa,ma);
 m=headtrain();
 tel(4);
 do{
    getch();
    k=0;
    for(i=0;i<3;i++)
    {
     tel(i+1);
     ci=nform();
     if((i==0&&ci>tr)||(i==1&&ci>pa)||(i==2&&ci>ma))
     {
      i--;
      tel(7);
      getch();
      continue;
      }
    k+=ci;
    if(k<=m)
    {
    ptrain(i,k,ci);
    savetrain(i,k,ci);
    }
    else
    {
    tel(6);
    clears(12,420,380,450);
    break;
    }
    }
 }while(k>m);
 clears(140,140,360,240);
 tel(8);
 getch();
 top=creat(top);
 top=apaili(top,k);
 strcpy(tp[t],top->next->data);
 t++;
 if(k!=1)
 top=bpaili(top,k);
 tel(5);
 print(k);
 getch();
}

/*动画*/
struct run{
int data;
char kind;
}ttrai[5];

savetrain(int i,int j,int c)
{
 int a;
 if(i==0&&c!=0)
 for(a=j-c;a<j;a++)
 {
 ttrai[a].data=a+1;
 ttrai[a].kind='t';
 }
 if(i==1&&c!=0)
 for(a=j-c;a<j;a++)
 {
  ttrai[a].data=a+1;
  ttrai[a].kind='p';
  }
 if(i==2&&c!=0)
 for(a=j-c;a<j;a++)
 {
  ttrai[a].data=a+1;
  ttrai[a].kind='m';
  }
}

runtrain(int k)
{
 int i=0,a;
 char c;
 c=ttrai[k].kind;
 switch(c)
 {
  case 't':for(a=0;a<210;a+=3)
    {
      clears(12,190,440,275);
      if(a<=160)
      truk(365-a,200);
      else
      truk(205,39+a);
      delay(1900);
     }
    break;
  case 'p':for(a=0;a<210;a+=3)
    {
      clears(12,190,440,275);
      if(a<=160)
      passage(365-a,200);
      else
      passage(215,39+a);
      delay(1900);
     }
    break;
  case 'm':for(a=0;a<210;a+=3)
    {
     clears(12,190,440,275);
     if(a<=160)
     mail(365-a,200);
     else
     mail(205,39+a);
     delay(1900);
    }
    break;
    }
}

 

bruntrain(char c)
{
 int a;
 switch(c)
 {
  case 't':for(a=0;a<220;a+=3)
    {
      clears(12,190,440,275);
      if(a<50)
      truk(205,249-a);
      else
      truk(258-a,200);
      delay(1900);
     }
     break;
  case 'p':for(a=0;a<220;a+=3)
    {
      clears(12,190,440,275);
      if(a<50)
      passage(205,249-a);
      else
      passage(258-a,200);
      delay(1900);
     }
    break;
  case 'm':for(a=0;a<220;a+=3)
    {
     clears(12,190,440,275);
     if(a<50)
     mail(205,249-a);
     else
     mail(258-a,200);
     delay(1900);
    }
    break;
    }
}

/*演示时的键面*/
face()
{
  setcolor(10);
  rectangle(400,170,449,189);
  rectangle(11,170,60,189);
  setcolor(YELLOW);
  rectangle(200,276,290,400);
  setfillstyle(1,11);
  bar(401,172,448,187);
  bar(12,172,59,187);
  setfillstyle(1,7);
  bar(201,277,289,399);
  setcolor(RED);
  moveto(411,178);
  outtext("ENTER");
  moveto(18,178);
  outtext("OUT");
  moveto(220,340);
  outtext("STATION");
}

ztrain(int k)
{
  int i=0,j=0,a=0,e=0,b,d;
  char c[12];
  struct run tpu[5];
  strcpy(c,tp[k]);
  face();
  if(c[i]!='\0')
  do
  {
   switch(c[i])
   {
     case 'r':clears(15+j*73,424,88+j*75,445);
       for(b=0;b<10;b++ )
       delay(10000);
       runtrain(j);
       clears(12,190,440,275);
       for(b=0;b<10;b++)
       delay(10000);
       tpu[e].data=ttrai[j].data;
       tpu[e].kind=ttrai[j].kind;
       j++;
       e++;
       break;
     case 'c':ttrai[a].data=a+1;
       ttrai[a].kind=tpu[e-1].kind;
       bruntrain(tpu[e-1].kind);
       clears(12,190,440,275);
       for(b=0;b<5;b++)
       delay(10000);
       if(ttrai[a].kind=='t')
       d=0;
       if(ttrai[a].kind=='p')
       d=1;
       if(ttrai[a].kind=='m')
       d=2;
       ptrain(d,a+1,1);
       for(b=0;b<5;b++)
       delay(10000);
       a++;
       e--;
       break;
     }
   i++;
 }while(c[i]!='\0');
}

/*开始动画*/
begi()
{
 int i;
 void *trp;
 setcolor(7);
 rectangle(50,330,130,350);
 rectangle(50,310,80,330);
 rectangle(115,320,120,330);
 rectangle(0,359,637,362);
 for(i=0;i<4;i++)
 {
  if(i>1)
  circle(63+i*18,352,6);
  else
  circle(63+i*18,350,8);
 }
 trp=malloc(sizeof(imagesize(49,299,131,357)));
 getimage(49,299,131,357,trp);
 for(i=0;i<500;i++)
 putimage(50+i,300,trp,COPY_PUT);
 clrscr();
 setcolor(YELLOW);
 rectangle(100,125,500,300);
 rectangle(120,150,480,280);
 setfillstyle(1,9);
 bar(101,126,499,299);
 setfillstyle(1,8);
 bar(122,152,478,278);
 gotoxy(20,12);
 printf("有一辆车头进站，请立即安排车厢");
 gotoxy(20,14);
 printf("G键进入系统，E键退出");
}

atta()
{
 int i;
 setcolor(13);
 for(i=0;i<10;i++)
 {
 moveto(100,200);
 clears(11,35,449,400);
 delay(90000);
 outtext("HAVE A NEW MESSAGE");
 delay(90000);
 }
}

main()
{
 int x,i;
 char c;
 initt();
 begi();
 c=getch();
 if(c=='g'||c=='G')
 {
  while(1)
  {
  first();
  clears(12,35,430,380);
  do{
  tel(9);
  x=nform();
  if(x<=0||x>t)
   {
    tel(7);
    getch();
   }
  }while(x<=0||x>t);
  clears(12,35,430,380);
  tel(10);
  ztrain(x-1);
  tel(11);
  for(i=0;i<30;i++)
  delay(10000);
  tel(12);
  atta();
  c=getch();
  if(c=='n'||c=='N')
  exit(0);
  pu=0;
  po=0;
  t=0;
  }
 }
 else
 exit(0);
}



上一篇：{应用}图遍历应用 人气:6578
下一篇：{应用}程序设计：哈希表的一个应用 人气:7012

C语言程序设计视频教程