栈的建立与基本操作的算法(C语言实现).doc

《栈的建立与基本操作的算法(C语言实现).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、栈的建立与基本操作的算法（C语言实现）/*c3-1.h栈的顺序存储表示*/#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT2/*存储空间分配增量*/typedefstructSqStack{SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间，以元素为单位*/}SqStack;/*顺序栈*//*bo3-1.c顺序栈（存储结构由c3-1.h定义）的基本操作（9个）*/Sta

2、tusInitStack(SqStack*S){/*构造一个空栈S*/(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}StatusDestroyStack(SqStack*S){/*销毁栈S，S不再存在*/free((*S).base);(*S).base=NULL;(*S).top=NU

3、LL;(*S).stacksize=0;returnOK;}StatusClearStack(SqStack*S){/*把S置为空栈*/(*S).top=(*S).base;returnOK;}StatusStackEmpty(SqStackS){/*若栈S为空栈，则返回TRUE，否则返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;}intStackLength(SqStackS){/*返回S的元素个数，即栈的长度*/returnS.top-S.base;}StatusGetTop(SqStackS,SE

4、lemType*e){/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR*/if(S.top>S.base){*e=*(S.top-1);returnOK;}elsereturnERROR;}StatusPush(SqStack*S,SElemTypee){/*插入元素e为新的栈顶元素*/if((*S).top-(*S).base>=(*S).stacksize)/*栈满，追加存储空间*/{(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof

5、(SElemType));if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;}*((*S).top)++=e;returnOK;}StatusPop(SqStack*S,SElemType*e){/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/if((*S).top==(*S).base)returnERROR;*e=*--(*S).top;returnOK;}Status

6、StackTraverse(SqStackS,Status(*visit)(SElemType)){/*从栈底到栈顶依次对栈中每个元素调用函数visit()。*//*一旦visit()失败，则操作失败*/while(S.top>S.base)visit(*S.base++);printf("");returnOK;}/*main3-1.c检验bo3-1.cpp的主程序*/#include"c1.h"typedefintSElemType;/*定义栈元素类型，此句要在c3-1.h的前面*/#include"c3-1.h"#include"bo3-1.c"St

7、atusvisit(SElemTypec){printf("%d",c);returnOK;}voidmain(){intj;SqStacks;SElemTypee;if(InitStack(&s)==OK)for(j=1;j<=12;j++)Push(&s,j);printf("栈中元素依次为：");StackTraverse(s,visit);Pop(&s,&e);printf("弹出的栈顶元素e=%d",e);printf("栈空否：%d(1:空0:否)",StackEmpty(s));GetTop(s,&e);printf("栈顶元素e=%d栈的

8、长度为%d",e,S