tostack.cpp

用C++语言实现的数据结构中的顺序栈的算法 具有很好的移植性能。

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define TRUE       1
#define FALSE      0
#define OK         1
#define   ERROR    0
#define INFEASIBLE -1
#define OVERFLOW   -2
#define STACK_INIT_SIZE    5
#define STACKINCREMENT     1
#define status int

typedef struct {
	int *base;
	int *top;
	int stacksize;
}SqStack;



//构造一个空栈S
SqStack InitStack(){
	SqStack S;
	S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));
	if(!S.base)  exit(OVERFLOW);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return S;
}//InitStack


//
SqStack CreateStack(){
	SqStack S;
	S=InitStack();
	int i=1,m;
	printf("请输入栈的首长度:");
	scanf("%d",&m);
	printf("请输入%d个元素:",m);
	while(i<=m){
		scanf("%d",S.top++);
		i++;
	}
	return S;
}


//销毁一个栈，S不再存在
int DestroyStack(SqStack S){
	if(!S.base)  exit(ERROR);
	free(S.base);
    return OK;
}//DestroyStack


//把S栈置空
int ClearStack(SqStack S){
	if(S.base==NULL) return OK;
	else {S.base=NULL;return OK;}
}//ClearStack


//检验是否为空。
int StackEmpty(SqStack S){
	if(S.base==NULL)  return  TRUE;
	else  return  FALSE;
}//StackEmpty


//栈的长度
int StackLength(SqStack S){
	return S.top-S.base;
}//StackLength

//取栈顶元素，出错则返回ERROR
int GetTop(SqStack S){
	int e;
	if(S.top==S.base)return ERROR;
	e=*(S.top-1);
	return e;
}//GetTop

//在栈顶插入新的元素
SqStack Push(SqStack S,int e){
	if(S.top-S.base>=S.stacksize){
		S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
		if(!S.base)  exit(OVERFLOW);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
	return S;
}//Push


//删除栈顶元素并返回其值，空栈返回ERROR
int Pop(SqStack S){
	int e;
    if(S.top==S.base) return ERROR;
	e=*--S.top;
	return  e;
}//Pop


int visit(int i){
	return  i+1;
}

//从栈底到栈顶依次取值调用visit()，失败则操作失败。
int StackTraverse(SqStack S){
	int *p;
	if(S.top==S.base) return ERROR;
	p=S.base;
	printf("Visit函数为Visit(i)=i+1\n");
	printf("计算结果为:");
	for( ;p!=S.top;p++)
		printf("%4d",visit(*p));
	return OK;
}


//打印栈
void PRINT(SqStack S){
	int *p;
    printf("此栈为:");
	for(p=S.base;p!=S.top;p++)
	    printf("%4d",*p);
}


//主函数
void main()
{ 
	int e,*p;
	char c;
	SqStack S;
	S=InitStack();
	if(StackEmpty(S)==FALSE)  ClearStack(S);
	S=CreateStack();
	while(1){
		c=getchar();
		switch(toupper(c)){                    //选择操作。
	case 'A':printf("栈的长度为:%d",StackLength(S));break;
	case 'B':printf("栈顶元素为:%d",GetTop(S));break;	      
	case 'C':printf("原栈为:");
	         for(p=S.base;p!=S.top;p++)
	         	printf("%4d",*p);
			 printf("\n请输入插入的e的值:");
			 scanf("%d",&e);
			 {Push(S,e);S.top++;}                //为什么Push里的S.top++不起作用，要这里另加?
			 PRINT(S);
			 printf("\n");
			 break;
	case 'D':printf("被删除的元素是:%3d",Pop(S));S.top--;       //为什么Pop里的S.top--也不起作用?
		     printf("\n");
		     PRINT(S);break;
	case 'E':StackTraverse(S);break;
	case 'F':exit(0);
	default:break;
		}
	printf("\nA:Stacklength  B:GetTop  C:Push  D:Pop  E:StackTraverse F:exit\n");  //选项。
	}
}