数据结构 栈操作 源程序

2010.09.24

数据结构中栈操作的代码,C语言实现的。

# define OK 1

# define TRUE 1

# define FALSE 0

# define ERROR 0

# define INFEASIBLE -1

# define OVERFLOW -2

# define STACK_INIT_SIZE 100 //存储空间初始分配量

# define STACKINCREMENT 10   //存储空间分配增量

typedef int Status;         //返回函数结果的状态

typedef struct {

 int *base;          //在栈构造之前和销毁之后,base的值为NULL
 
 int *top;           //栈顶指针
 
 int stacksize;      //当前已分配的储存空间,以元素为单位

}SqStack;

Status InitStack(SqStack &S);

Status InitStackElem(SqStack &S);

Status Push(SqStack &S, int e);

Status Pop(SqStack &S, int &e);

int StackElemNum(SqStack S);

Status Print_Stack(SqStack S);

Status StackIfFullAndIncrement(SqStack &S);

# include "stdio.h"

# include "stdlib.h"

# include "time.h"

# include "conio.h"    //getch()

int e = 0; //常用变量 e为数据

int counter = 0;

void main() {

    //初始化栈,并填充数据
    
    SqStack S;
    
    InitStack(S);
    
    InitStackElem(S);
    
    Print_Stack(S);
    
    //向栈中插入数据
    
    printf("请输入一个要插入栈顶的数据:");
    
    scanf("%d",&e);
    
    Push(S,e);
    
    Print_Stack(S);
    
    //弹出栈顶数据
    
    printf("是否要弹出栈顶数据?(y/n)\n");
    
    if(getch() == 'y' || getch() == 'Y') {
    
        Pop(S,e);
    
        printf("弹出的栈顶数据是%d\n",e);
    
    }
    
    else if(getch() == 'n' || getch() == 'N') printf("程序继续进行.\n");
    
    else printf("输入有误,程序继续执行.\n");
    
    //统计栈中数据个数
    
    Print_Stack(S);
    
    printf("栈中数据个数为%d.\n",StackElemNum(S));
    
    printf("程序执行完毕.\n");

}

Status InitStack(SqStack &S) {

    //构造一个空栈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 OK;

}//InitStack

Status InitStackElem(SqStack &S) {

    //向栈中填充数据
    
    int n,i;
    
    printf("请输入要向栈中填充的数据个数:");
    
    scanf("%d",&n);
    
    srand((unsigned) time (NULL));
    
    for(i=0;i<n;i++) {
    
        StackIfFullAndIncrement(S);
    
        *S.top++ = rand()%100+1;
    
    }
    
    return OK;

}//InitStackElme

Status Push(SqStack &S,int e) {

    //插入数据e为新的栈顶元素
    
    StackIfFullAndIncrement(S);
    
    *S.top = e;
    
    S.top++;
    
    return OK;

}//Push

Status Pop(SqStack &S,int &e) {

    //若栈不空,则删除S的栈顶数据,用e返回其值,并返回OK;否则返回ERROR
    
    if(S.base == S.top) return ERROR;
    
    e = * --S.top;
    
    return OK;

}//Pop

Status StackElemNum(SqStack S) {

    //栈中数据个数
    
    int *temp;
    
    temp = S.base;
    
    for(counter = 0; temp<S.top; counter++) temp++;
    
    printf("栈中的数据个数是%d\n",counter);
    
    return OK;

}//StackElemNum

Status Print_Stack(SqStack S) {

    //输出栈中的数据
    
    counter = 0;
    
    while(S.base<S.top) {        counter++;      --S.top;        printf("第%-3d个:%-4d    ",counter,*S.top);         if(counter%4 == 0) printf("\n");  }   printf("\n");     return OK; }//Print_Stack Status StackIfFullAndIncrement(SqStack &S) {  //判断栈满,并追加存储空间    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;
    
    }
    
    return OK;

}//StackIfFullAndIncrement
Comments
Write a Comment