stack.cpp

车厢调度算法 具体的算法的演示和实现,数据结构的课程设计

#include "stdio.h"
#include "Stack.h"
#include "stdlib.h"

//双栈结构的基本操作函数

bool InitStack(TwStack &S)    
{
//构造一个空双栈
	S.base1=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
	if(!S.base1)exit(1);                      //存储分配失败
	S.base2=S.base1+STACK_INIT_SIZE-1;
	S.top=S.base1;
	S.low=S.base2;
	S.stacksize=STACK_INIT_SIZE;
	return true;
}//InitStack

bool Push(TwStack &S,int i,int x)
{
//当i＝0时，插入元素x为下栈的栈顶元素；
//当i＝1时，插入元素x为上栈的栈顶元素；
	if(S.top>S.low)
	{
		printf("栈满，不能继续进行，请减少车厢数目。\n");
		exit(0);
	}
	if(i==0)
	{
		*S.top=x;
		S.top++;
	}
	else
	{
		*S.low=x;
		S.low--;
	}
	return true;
}


bool Pop(TwStack &S,int i,int &x)
{
//当i＝0时，删除下栈的栈顶元素，并用x返回其值；
//当i＝1时，删除上栈的栈顶元素，并用x返回其值；
	if(i==0)
	{
		S.top--;
		x=*S.top;
	}
	else
	{
		S.low++;
		x=*S.low;
	}
	return true;
}


bool StackEmpty(TwStack S,int i)
{
//	当i=0时,若S.top=S.base1,也就是下栈为空栈，则返回TRUE，否则FALSE；
//  当i＝1时，若S.low=S.base2,也就是上栈为空栈，则返回TRUE，否则FALSE；
	if(i==0&&S.base1==S.top)
		return true;
	else if(i==1&&S.base2==S.low)
		return true;
	return false;
}


void PrintStack1(TwStack &S,int tou,int wei)
{
//简单显示数据，只输出栈S所有元素的值，栈S所有元素都还存在；
	int i;
	int *p;
	i=wei-tou+1;
	printf("序列: ");
	p=S.base2;
	printf("%d",*p);
	p--;
	i--;
	while(i>=1)
	{
		printf("-%d",*p);
		p--;
		i--;
	}
	printf("\n");

}

void PrintStack2(TwStack &S,int tou,int wei)
{
//详细显示数据，只输出栈S所有元素的值，栈S所有元素都还存在
	int i,j,k,h,x;
	int caozuo,flag,kong;
	int *p;
	TwStack T;
	InitStack(T);
	i=tou;
	printf("\n********************************************************************************");
	printf("序列: ");
	p=S.base2;
	printf("%d",*p);
	p--;
	i++;
	while(i<=wei)
	{
		printf("-%d",*p);
		p--;
		i++;
	}
	printf("\n");
	printf("步骤\t输入\t\t    栈(调度站)\t\t输出序列\t\t操作\n");
	i=tou;
	j=1;
	p=S.base2;
	caozuo=0;
	h=0;
	flag=1;		
	while(flag)       //循环一次就输出一个步骤
	{
		kong=0;
		if(i>wei&&StackEmpty(T,0)==true)
			flag=0;
		printf("%d",j++);
		if(j>10)
			kong+=2;
		else
			kong++;
		while(kong++!=8)
			printf(" ");
		for(k=i;k<=wei;k++,kong+=2)
			printf("%d ",k);
		while(kong++!=29)
			printf(" ");
		for(k=1;k<=T.top-T.base1;k++,kong+=2)
			printf("%d ",*(T.base1+k-1));
		while(kong++!=50)
			printf(" ");
		for(k=1;k<=h;k++,kong+=2)
			printf("%d ",*(S.base2-k+1));
		while(kong++!=73)
			printf(" ");
		if(caozuo==1)
			printf("Push(S,%d)",i-1);
		else if(caozuo==-1)
			printf("Pop(S,x)");
		if(i<=*p)
		{
			caozuo=1;
			Push(T,0,i);
			i++;
		}
		else
		{
			caozuo=-1;
			Pop(T,0,x);
			h++;
			p--;
		}
		printf("\n");
	} 
}