ecstack.c

是C++的基础

#include "ECStack.h"
#include "MyAssert.h"
#include "Ulti.h"
#include "MyMath.h"
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <string.h>
/*---Start of SeqStack---*/
PSeqStack createNullSeqStack(void)
{
	PSeqStack reStack;
	reStack=(PSeqStack)malloc(sizeof(struct SeqStack));
	assertF(reStack!=NULL,"in createNullSeqStack,mem apply failure\n");
	
	reStack->slot=-1;
	
	return reStack;
}

void seqPush(PSeqStack inStack,Type inData)
{
	
	assertF(inStack!=NULL,"in seqPush,inStack is null\n");
	assertF(inStack->slot<SEQ_STACK_LEN-1,"in seqPush ,up flow!\n");
	
	inStack->slot++;
	inStack->dataArea[inStack->slot]=inData;
}
	
Type seqPop(PSeqStack inStack)
{
	Type reData;
	assertF(inStack!=NULL,"in seqPop,inStack is null\n");
	assertF(inStack->slot>-1,"in seqPop,down flow out\n");
	reData=inStack->dataArea[inStack->slot];
	inStack->slot--;

	return reData;
}

Type seqTop(PSeqStack inStack)
{
	return inStack->dataArea[inStack->slot];
}


int isNullSeqStack(PSeqStack inStack)
{
	return inStack->slot==-1;
}


/*---End   of SeqStack---*/
/*---Start of ShareStack---*/
PShareStack createNullShareStack(void)
{
	PShareStack reStack;
	reStack=(PShareStack)malloc(sizeof(struct ShareStack));
	assertF(reStack!=NULL,"in createNullShareStack,mem apply failure\n");
	
	reStack->upIndex=SHARE_STACK_LEN;
	reStack->buttomIndex=-1;

	return reStack;
}

void upPush(PShareStack inStack,Type inData)
{
	
	assertF(inStack!=NULL,"in upPush,pass in inStack is null\n");
	assertF(inStack->upIndex>inStack->buttomIndex+1,"in upPush down flow\n");
	
	inStack->upIndex--;
	inStack->shareDataPool[inStack->upIndex]=inData;
}
Type upPop(PShareStack inStack)
{
	Type reData;
	assertF(inStack!=NULL,"in upPop,pass in inStack is null\n");
	assertF(inStack->upIndex<SHARE_STACK_LEN,"in upPush up flow\n");
	reData=inStack->shareDataPool[inStack->upIndex];
	inStack->upIndex++;
	
	return reData;
}

Type upTop(PShareStack inStack)
{
	assertF(inStack!=NULL,"in upTop,pass in inStack is null\n");
	return	inStack->shareDataPool[inStack->upIndex];
}
	
void buttomPush(PShareStack inStack,Type inData)
{
	assertF(inStack!=NULL,"in buttomPush,pass in inStack is null\n");
	assertF(inStack->upIndex>inStack->buttomIndex+1,"in buttomPush,up flow\n");
	
	inStack->buttomIndex++;
	inStack->shareDataPool[inStack->buttomIndex]=inData;	
}
Type buttomPop(PShareStack inStack)
{
	Type reData;
	assertF(inStack!=NULL,"in buttomPop,pass in inStack is null\n");
	assertF(inStack->buttomIndex>=0,"in buttmPop ,down flow\n");
	reData=inStack->shareDataPool[inStack->buttomIndex];
	inStack->buttomIndex--;
	
	return reData;
}

Type buttomTop(PShareStack inStack)
{
	assertF(inStack!=NULL,"in buttomTop,pass in inStack is null\n");
	return inStack->shareDataPool[inStack->buttomIndex];
}
/*---End of ShareStack---*/

/*Classic Stack Problem Series*/
/*Problem1:Train leave station problem*/
void trainLeaveProblemAll(int numOfJie)
{
	int* flagArr;
	int i;
	flagArr=(int*)malloc(sizeof(int)*numOfJie);
	/*flagArr:
	0:not in the stack.
	1:being in the stack.
	2:has been in the stack,and has been poped.
	*/
	for(i=0;i<numOfJie;i++)
		flagArr[i]=0;
}

void trainLeaveProblemSole(int* possibleCondition,int len)
{
	int* flagArr;
	int i,j,flag;
	PSeqStack myStack;
	
	flagArr=(int*)malloc(sizeof(int)*len);
	
	myStack=createNullSeqStack();
	/*flagArr:
	0:not in the stack.
	1:being in the stack.
	2:has been in the stack,and has been poped.
	*/
	for(i=0;i<len;i++)
		flagArr[i]=0;
	
	flag=1;
	for(i=0;i<len;i++)
		if(flagArr[possibleCondition[i]]==1&&!isNullSeqStack(myStack)&&seqTop(myStack)!=possibleCondition[i])
		{
			flag=0;
		//	printf("this leave condition is invalid,error happen\n");
			break;
		}
		else if(flagArr[possibleCondition[i]]==1&&seqTop(myStack)==possibleCondition[i])
		{
			seqPop(myStack);
			flagArr[possibleCondition[i]]=2;
		}
		else
		{
			flagArr[possibleCondition[i]]=2;
			for(j=0;j<possibleCondition[i];j++)
				if(flagArr[j]==0)
				{
					seqPush(myStack,j);
					flagArr[j]=1;
				}
		}
	for(i=0;i<len;i++)
		possibleCondition[i]++;
	if(flag)
	{
		printf("v:\n");
		showArrListInt(possibleCondition,0,len);
	}
		
		
	
}