//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");
}
}
评论0