数据结构课程设计之车厢调度

/*车厢调度-胡海洪*/ #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); } }