数据结构之顺序栈

//头文件SqStack.h    开始

#define STACK_INIT_SIZE 10
#define STACK_INC_SIZE 2
#define SElemType int
#define OK 0
#define ERROR 1
#define OVERFLOW 2
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef struct{
SElemType *base;
SElemType *top;
int stackSize;
}SqStack;


Status InitStack(SqStack *S);
Status DestroyStack(SqStack *S);
Status ClearStack(SqStack *S);
Status StackEmpty(SqStack *S);
int StackLength(SqStack *S);
Status GetTop(SqStack *S,SElemType *e);
Status Push(SqStack *S,SElemType *e);
Status Pop(SqStack *S,SElemType *e);
Status StackTraverse(SqStack *S,Status (*visit)());


Status InitStack(SqStack *S)
{
Status r= OK;
S->base = (SElemType *)malloc( STACK_INIT_SIZE * sizeof(SElemType) );
if ( S == NULL )r = OVERFLOW;
S->top = S->base;
S->stackSize = STACK_INIT_SIZE;
return r ;
}//end of InitStack(SqStack *S)
Status DestroyStack(SqStack *S)
{
free(S->base);
return OK;
}
Status StackEmpty(SqStack *S)
{
//printf("S->top - S->base=%d",S->top - S->base);
if(S->top - S->base)return FALSE;
else return TRUE;
}
int StackLength(SqStack *S)
{
return S->top - S->base;
}


Status GetTop(SqStack *S,SElemType *e)
{
if ( S->top == S->base )return ERROR;
*e = *(S->top-1);
return OK;
}


Status Push(SqStack *S,SElemType *e)
{
if ( S->top - S->base >= S->stackSize)
{
printf("\nIncrease and realloc stack size\n");
S->base = (SElemType *) realloc( S->base, (S->stackSize + STACK_INC_SIZE) * sizeof(SElemType));
S->top = S->base + S->stackSize;
S->stackSize += STACK_INC_SIZE;
}
if( !S->base)
{
return OVERFLOW;
}
*S->top++ = *e;
return OK;
}


Status Pop(SqStack *S,SElemType *e)
{
if ( S->top == S->base )return ERROR;
*e = *--S->top;
return OK;
}
Status ClearStack(SqStack *S)
{
S->top = S->base;
return OK;
}

//头文件SqStack.h    结束

－－－－－－－分割线－－－－－－－
//main.cpp 开始


#include "stdafx.h"
#include "stdlib.h"
#include "SqStack.h"
//对任意一个非负的十进制数，打印输出其numBase 进制,numBase可为2 8 16
void conversion(SElemType decValue,int numBase)
{

Status r = OK;
SqStack sqStack;
SElemType ex = 0;
int mod = 0;
SElemType tmpDecValue = decValue;
r = InitStack(&sqStack);
if ( r != OK )
{
printf("Init SqStack failed!\n");
}
else
{
printf("Init SqStack ok!\n");
printf("sqStack->stackSize=%d\n",sqStack.stackSize);
}
while(tmpDecValue)
{
mod = tmpDecValue % numBase;
Push(&sqStack, &mod);
tmpDecValue = tmpDecValue / numBase;
}
printf("------------\n");
printf("%d --> ",decValue);




while( !StackEmpty(&sqStack) )
{
if ( !Pop(&sqStack,&ex) )
printf("%x",ex);
}
printf("\n------------\n");


}


//行编辑器
void LineEdit()
{
printf("\nwelcome to use lineEdit\n");
printf("# :backspace\n");
printf("@ :backline\n");
printf("for example:\n");
printf("whli##ile is  while\n");
printf("1234@abc is  abc\n");
printf("press Enter key to end lineEdit\n");
SqStack sqStack,trueLine;
SElemType ch = 0;
InitStack(&sqStack);
InitStack(&trueLine);
ch = getchar();
while( ch !=EOF )
{
while( ch !=EOF && ch != '\n' )
{
switch( ch )
{
case '#':
Pop( &sqStack, &ch);break;//删除一个字符
case '@':
ClearStack( &sqStack);break;//删除所有字符
default:
Push( &sqStack, &ch);
}
ch = getchar();


}

while( !StackEmpty(&sqStack) )
{
Pop(&sqStack,&ch);//弹出来的是反序的，重新存入trueLine，以便输出
Push(&trueLine,&ch);
}


printf("\nline is :\n");
while( !StackEmpty(&trueLine) )
{
//输出
Pop(&trueLine,&ch);
printf("%c",ch);
}
printf("\n");


ClearStack( &sqStack);break;//删除所有字符
if(ch !=EOF)
{
ch = getchar();
}
}
DestroyStack(&sqStack);


}
int main(int argc, char* argv[])
{
Status r = OK;
SqStack sqStack;
SElemType e1 = 1;
SElemType e2 = 5;
SElemType e3 = 9;
SElemType ex = 0;
int i = 0;


r = InitStack(&sqStack);


Push(&sqStack,&e1);
Push(&sqStack,&e2);
Push(&sqStack,&e3);


printf("sqStack->length=%d\n",StackLength(&sqStack));
GetTop(&sqStack,&ex);
if ( !Pop(&sqStack,&ex) )
printf("Pop=%d\n",ex);
if ( !Pop(&sqStack,&ex) )
printf("Pop=%d\n",ex);
if ( !Pop(&sqStack,&ex) )
printf("Pop=%d\n",ex);
if ( !Pop(&sqStack,&ex) )
printf("Pop=%d\n",ex);


Push(&sqStack,&e1);
Push(&sqStack,&e2);
Push(&sqStack,&e3);


conversion(128,2);
LineEdit();


return 0;
}

//main.cpp 结束