顺序栈的表示与c语言实现之动态分配型

1
2
3
4
5
6
7
8
9
#define STACK_INIT_SIZE 100  //存储空间初始分配量
#define STACKINCREMENT 10  //存储空间的分配增量<相对初始分配量较小，视具体情况而定>
typedef struct{
	SElemType *base; //定义类型为SElemType类型的指针指向栈底，即栈底指针
	                 //在栈构造之前和销毁之后，base的值为NULL
	SElemType *top;  //定义栈顶指针，指向栈顶元素的下一个位置　①
	int stacksize;  //定义当前存储空间总量stacksize，以元素SElemtype为单位
}SqStack;   

1
2
3
4
5
6
7
8
9
10
11
12
int InitStack(SqStack *S)
{
	//1.动态申请存储空间
	S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    //判断是否申请成功
	if(!S->base) return 0;    //S->base==NULL;
	//2.初始化SqStack结构各个成员 
	S->top=S->base;
	S->stacksize=STACK_INIT_SIZE;
	return 1;
} 

1
2
3
4
5
6
7
int StackEmpty(SqStack S)
{
	//若栈顶指针指向栈底则栈为空
	if(S.top==S.base)return 1;
	else return 0;   //return S.top==S.base?1:0;
} 

1
2
3
4
5
6
int StackFull(SqStack S)
{
	if(S.top-S.base==S.stacksize) return 1;
	else return 0;  //return S.top-S.base==S.stacksize?1:0;
} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Push(SqStack *S,SElemType e)
{
	//栈满，申请分配更多空间 
	if(S->top-S->base==S->stacksize)
	{
		SElemType *newbase=(SElemType *)realloc(S->base,(S->stacksize+
		STACKINCREMENT)*sizeof(SElemType));
		if(newbase==NULL)return 0;
		//一旦空间申请成功，SqStack结构中各结构成员需更新
		S->base=newbase; 
		S->top=S->base+S->stacksize;
		S->stacksize+=STACKINCREMENT;
	}
	//入栈
	*(S->top)=e;
	S->top++; 
	return 1;
} 

1
2
3
4
5
6
7
8
int Pop(SqStack *S,SElemType *e)
{
	if(S->base==S->top)return 0;//判空
	S->top--;
	*e=*(S->top);
	return 1;
} 

1
2
3
4
5
6
7
8
int GetTop(SqStack S,SElemType *e)
{
	if(S.base==S.top)return 0;//判空 
	S.top--;
	*e=*(S.top);　//取出栈顶指针所指元素的值并赋值给e
	return 1;
}

1
2
3
4
5
6
7
8
9
10
11
12
int StackTraverse(SqStack S,void(*visit)(SElemType))
{                            //函数指针做函数参数②
    //1.首先用一指针指向栈顶元素<定位>
	SElemType *p=S.top-1;
	//2.循环遍历各个元素
	while(p>=S.base)
	{
		visit(*p);  //调用visit()方法实现具体操作 
		p--;
	}
} 

1
2
3
4
5
6
7
8
int ClearStack(SqStack *S)
{
	//1.判空，若栈本为空，返回0
	if(S->top==S->base)return 0;
	S->top==S->base;
	return 1;
} 

1
2
3
4
5
6
7
8
9
10
int DestroyStack(SqStack *S)
{
	//判空，若栈本为空，返回0
	if(S->top==S->base)return 0;
	free(S->base);  //释放空间 
	S->base=S->top=NULL;  //指针为空 
	S->stacksize=0; //栈中无元素 
	return 1; 
}