数据结构课程作业——车厢调度问题求解

//Vehicle_scheduling.cpp ///202066323011 曹聚鹏 #include <stdio.h> #include<stdlib.h> #include<string> #include <iostream> using namespace std; #define MaxStackSize 100//目前先使n和max保持一致 int n = 5; int num = MaxStackSize;//调度站容量 typedef int DataType; DataType in_orders[MaxStackSize]; typedef struct { DataType data[MaxStackSize]; //栈的申明定义 int top1; int top2; }DStack; void Initial(DStack*& s) //栈的初始化操作 { s = (DStack*)malloc(sizeof(DStack)); s->top1 = -1; s->top2 = MaxStackSize; } bool Push(DStack*& S, DataType x, DataType i) //入栈 { if (S->top1 + 1 == S->top2) //判满 { printf("堆栈已满无法插入！\n"); return 0; } else //未满则进行插入操作 { if (i == 1) { S->top1++; S->data[S->top1] = x; } else //选择插入的栈号进行插入操作 { S->top2--; S->data[S->top2] = x; } } return 1; } bool Pop(DStack*& S, DataType& x, DataType i) //出栈 { if (i == 1) { if (S->top1 <= -1) { printf("1号栈是空的，无数据元素出栈！\n"); return 0; } x = S->data[S->top1]; S->top1--; } else { if (S->top2 >= MaxStackSize) { printf("2号栈是空的，无数据元素出栈！\n"); return 0; } x = S->data[S->top2]; S->top2++; } return 1; } void Destroy(DStack* s) { free(s); } DataType GetTop(DStack* S, DataType& x, DataType i) //返回栈顶元素 { if (i == 1) { if (S->top1 == -1) { return 0; } x = S->data[S->top1]; } else { if (S->top2 >= MaxStackSize - 1) { printf("2号栈是空的，无数据元素出栈！\n"); return 0; } x = S->data[S->top2]; } return 1; } //使用时忘记保存头文件代码会造成什么错误 void disp(DStack* s, DataType i) //打印函数 { if (i == 1) { for (int j = 0; j <= s->top1; j++) { printf("%d ", s->data[j]); } } else { for (int j = MaxStackSize - 1; j >= s->top2; j--) { printf("%d ", s->data[j]); }printf("\n"); } } DStack* s; void process(int m, int i = 1); void process2(int m, string str_order, int i = 1); void menu(); void Interface(); void StrStorage(string& str_order); int main() { for (int i = 1; i <= n; i++) { in_orders[i] = i; } menu(); return 0; } void Interface()//界面显示 { printf("\n"); printf("----------------------------------欢迎来到本程序------------------------------\n"); printf("\t\t1.输出所有序列\t"); printf("\t\t2.展示操作序列\n"); printf("\t\t3.修改入栈序列长度"); printf("\t\t4.修改调度站容量\n"); printf("\t\t5.修改入栈序列\t"); printf("\t\t0.退出\n"); printf("\t\t当前序列长度:%d", n); printf("\t\t\t当前调度站容量：%d\n", num); printf("\t\t当前入栈序列:"); for (int i = 1; i <= n; i++) { printf("%d ", in_orders[i]); }printf("\n"); printf("------------------------------------------------------------------------------\n"); printf("请选择对应选项序号："); } void menu()//菜单页面显示 { int i; while (1) { Initial(s); process(0, 0);//设函数静态count值为0 process2(0, "", 0);//设函数静态count值为0 Interface();//展示界面 scanf("%d", &i); switch (i) { case 1: Push(s, in_orders[1], 1); process(1); break; case 2:Push(s, in_orders[1], 1); process2(1, ""); break; case 3: printf("重设入栈序列长度(n<=20)："); scanf("%d", &n);break; case 4:printf("重设调度站容量(num<=%d)：", MaxStackSize); scanf("%d", &num); printf("已修改"); break; case 5: printf("输入新序列："); for (int i = 1; i <= n; i++) { scanf("%d", &in_orders[i]); }printf("已修改"); break; case 0:Destroy(s); exit(0); break; default:break; }//swtich Destroy(s); system("pause"); system("cls"); }//while } void StrStorage(string& str_order) { str_order += "A:"; for (int j = 0; j <= s->top1; j++) { str_order += to_string(s->data[j]) + " "; } str_order += "\t\t\tB:"; for (int j = MaxStackSize - 1; j >= s->top2; j--) { str_order += to_string(s->data[j]) + " "; } str_order += "\n"; } void process(int m, int i)//m指的是已经处理过的最大的数字 { static int count = 0; int j = 0; int k; if (i == 0) { count = 0; return; } if (m < n && s->top1 < num - 1) { Push(s, in_orders[m + 1], 1); process(m + 1); Pop(s, k, 1);//回溯 } if (s->top1 != -1) { Pop(s, j, 1); Push(s, j, 2); process(m); Pop(s, j, 2); Push(s, j, 1); } if (s->top1 == -1 && m == n) { count++; printf("[%d]", count); disp(s, 2); } } void process2(int m, string str_order, int i)//m指的是已经处理过的最大的数字 { StrStorage(str_order); static int count = 0; int j = 0; int k;//k for test! if (i == 0) { count = 0; return; } if (m < n && s->top1 < num - 1) { Push(s, in_orders[m + 1], 1); process2(m + 1, str_order); Pop(s, k, 1);//仅仅是为了恢复原样 } if (s->top1 != -1) { Pop(s, j, 1); Push(s, j, 2); process2(m, str_order); Pop(s, j, 2);//注意改动 Push(s, j, 1); } if (s->top1 == -1 && m == n) { count++; printf("\n[%d]", count); disp(s, 2); printf("-----------------------------------------------------\n"); cout << "操作序列:进栈（A）出栈（B）\n" << str_order << endl; printf("-----------------------------------------------------\n"); } }