课程设计 列车调度

#include<stdio.h>
#include<malloc.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW -1
#define OK 1
#define TRUE 1
#define ERROR 0
#define FALSE 0
#define NULL 0

typedef struct//栈
{int *base;
int *top;
int  stacksize;
}Stack;

int InitStack(Stack &s)             //构造一个空栈S
{s.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));
if(!s.base)return(OVERFLOW);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return OK;
}

int Push(Stack &s,int e)             //插入元素e为新的栈顶元素，并返回OK
{if(s.top-s.base>=s.stacksize)
{s.base=(int*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(int));
if(!s.base)return (OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;}
*s.top++=e;
return OK;}

int Pop(Stack &s,int &e)          //删除S的栈顶元素并用e返回其值，并返回OK，否则返回ERROR
{if(s.top==s.base)
return ERROR;
e=*--s.top;
return OK;}

int StackEmpty(Stack s)            //若栈S为空栈，则返回TRUE,否则FALSE
{if(s.top==s.base)
return TRUE;
else
return FALSE;}

 typedef struct BiTNode {//2叉树
    int data,inm,all;
    BiTNode  *lchild,*rchild,*parent;
} BiTNode, *BiTree;

 typedef struct QNode//队列
{BiTree data;
struct QNode *next;
}QNode,*QueuePtr;

 typedef struct{
QueuePtr front;
QueuePtr rear;
}Queue;
 
int InitQueue(Queue &q)              //构造一个空队列Q
{q.front=q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!q.front)return (OVERFLOW);
q.front->next=NULL;
return OK;}

int EnQueue(Queue &q,BiTree e)        //插入元素e为Q的新的队尾元素。并用e返回其值；并返回OK      
{QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)return  (OVERFLOW);
p->data=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
return OK;}

int DEQueue(Queue &q,BiTree &e)         //若Q为非空队列,删除Q的队首元素，并用e返回其值；并返回OK，否则返回ERROR
{QueuePtr p;
if(q.front==q.rear)
return ERROR;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)
q.rear=q.front;
free(p);
return OK;}

int QueueEmpty(Queue q)                  //若Q为空队列，则返回TRUE，否则FALSE
{if(q.front==q.rear)
return TRUE;
else
return  FALSE;}

void train_dispatch(int n)
{BiTNode *a[500];                         //存储叶子地址的数组
BiTree T;
BiTNode *p;
Queue s;
int m=0;
T=(BiTNode*)malloc(sizeof(BiTNode));        //以层次顺序构造一颗所有操作组的2叉树
p=T;
p->data=1;
p->inm=n-1;
p->all=1;
p->parent=NULL;
InitQueue(s);
EnQueue(s,p);
while(!QueueEmpty(s))
{DEQueue(s,p);
if(p->inm>0&&p->all>0)                    //表示下一步操作可以是进，也可以是出
{p->lchild=(BiTNode*)malloc(sizeof(BiTNode));
p->lchild->parent=p;
p->lchild->data=1;
p->lchild->inm=p->inm-1;
p->lchild->all=p->all+1;
EnQueue(s,p->lchild);
p->rchild=(BiTNode*)malloc(sizeof(BiTNode));
p->rchild->parent=p;
p->rchild->data=-1;
p->rchild->inm=p->inm;
p->rchild->all=p->all-1;
EnQueue(s,p->rchild);}
else
{if(p->inm>0&&p->all==0)                 //表示下一步操作只可以是进，不可以是出
{p->lchild=(BiTNode*)malloc(sizeof(BiTNode));
p->lchild->parent=p;
p->lchild->data=1;
p->lchild->inm=p->inm-1;
p->lchild->all=p->all+1;
EnQueue(s,p->lchild);}
else
{if(p->inm==0&&p->all>0)                   //表示下一步操作不可以进，只可以是出
{p->rchild=(BiTNode*)malloc(sizeof(BiTNode));
p->rchild->parent=p;
p->rchild->data=-1;
p->rchild->inm=p->inm;
p->rchild->all=p->all-1;
EnQueue(s,p->rchild);}
else
{if(p->inm==0&&p->all==0)                     //表示已没有下一步操作了
{a[m]=p;
m++;}}}}}
printf("%d节车厢有%d中序列可能\n",n,m);       //m为叶子数，也为操作组数目
printf("具体车厢序列如下:\n");
Stack one,two;                   //用栈把操作组翻译回可能输出序列
InitStack(one);
InitStack(two);
int i=0;
int j=1;
int k=0;
int c;
int e;
int b[10];
while(i<m)
{p=a[i];                       //根据叶子找回操作组，放进栈one，栈顶为第一个操作
while(p)
{j=1;
k=0;
Push(one,p->data);
p=p->parent;}
while(!StackEmpty(one))
{Pop(one,e);
if(e==1)
{Push(two,j);j++;}
else
{Pop(two,e);
b[k]=e;                       //把应输出序列按顺序存在数组b[ ]内
k++;}}
for(c=0;c<k;c++)
{printf("%d ",b[c]);}
if((i+1)%4!=0)
printf("     ");
else
printf("\n");                 //把数组b[ ]内数据输出
i++;}}

void main()
{printf("软件一班  学号：3107006754  姓名：吴林江\n\n");
loap:
int n;

printf("请输入列车车厢节数(1-7节以内) ");
scanf("%d",&n);
if(n<1||n>7)
printf("范围错误!!");
else
train_dispatch(n);            //列出n列车厢调度后所有可能出现的序列情况
char z;
printf("\n是否继续？回车继续，Q键退出");
while(getchar()!='\n');
z=getchar();
if(z=='q'||z=='Q')
;
else
goto loap;
}