用顺序栈进行栈的基本操作-C++源程序.doc

/ main3-1.cpp 检验bo3-1.cpp的主程序 /#includec1.h#include #include #include #include #include /#include #include #include #include #include #include / 提供宏va_start，va_arg和va_end，用于存取变长参数表 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 / #define INFEASIBLE -1 没使用 / #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3，故去掉此行 typedef int Status; / Status是函数的类型，其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型，其值是TRUE或FALSE typedef int SElemType; / 定义栈元素类型，此句要在c3-1.h的前面/ #includec3-1.h #define STACK_INIT_SIZE 10 / 存储空间初始分配量 #define STACK_INCREMENT 2 / 存储空间分配增量 struct SqStack / 顺序栈 SElemType *base; / 在栈构造之前和销毁之后，base的值为NULL SElemType *top; / 栈顶指针 int stacksize; / 当前已分配的存储空间，以元素为单位 ;void InitStack(SqStack &S) / 构造一个空栈S。 if(!(S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType) exit(OVERFLOW); / 动态分配存储空间失败，则退出 S.top=S.base; / 栈顶指向栈底(空栈) S.stacksize=STACK_INIT_SIZE; / 存储空间为初始分配量 void DestroyStack(SqStack &S) / 销毁栈S，S不再存在 free(S.base); / 释放栈空间 S.top=S.base=NULL; / 栈顶、栈底指针均为空 S.stacksize=0; / 当前已分配的存储空间为0 void ClearStack(SqStack &S) / 把栈S置为空栈 S.top=S.base; / 栈顶指针指向栈底 Status StackEmpty(SqStack S) / 若栈S为空栈，则返回TRUE；否则返回FALSE if(S.top=S.base) / 空栈条件 return TRUE; else return FALSE; int StackLength(SqStack S) / 返回栈S的元素个数，即栈的长度 return S.top-S.base; Status GetTop(SqStack S,SElemType &e) / 若栈S不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(S.topS.base) / 栈不空 e=*(S.top-1); / 将栈顶元素赋给e return OK; else return ERROR; void Push(SqStack &S,SElemType e) / 插入元素e为栈S新的栈顶元素 if(S.top-S.base=S.stacksize) / 栈满 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)* sizeof(SElemType); / 追加存储空间 if(!S.base) / 追加存储空间失败，则退出 exit(OVERFLOW); S.top=S.base+S.stacksize; / 修改栈顶指针，指向新的栈顶 S.stacksize+=STACK_INCREMENT; / 更新当前已分配的存储空间 *(S.top)+=e; / 将e入栈，成为新的栈顶元素，栈顶指针上移1个存储单元 Status Pop(SqStack &S,SElemType &e) if(S.top=S.base) / 栈空 return ERROR; e=*-S.top; / 将栈顶元素赋给e，栈顶指针下移1个存储单元 return OK; void StackTraverse(SqStack S,void(*visit)(SElemType) / 从栈底到栈顶依次对栈S中每个元素调用函数visit() while(S.topS.base) / S.base指向栈元素 visit(*S.base+); / 对该栈元素调用visit()， coutn; / 栈底指针上移1个存储单元 #define ElemType SElemType Status equal(ElemType c1,ElemType c2) / 判断是否相等的函数 if(c1=c2) return TRUE; else return FALSE; int comp(ElemType a,ElemType b) / 根据ab，分别返回-1、0或1 if(a=b) return 0; else return (a-b)/abs(a-b); void print(ElemType c) / 以十进制整型的格式输出元素的值 coutc; coutt; void print1(ElemType &c) / 以十进制整型的格式输出元素的值(设c为引用类型) coutc; void print2(ElemType c) / 以字符型的格式输出元素的值 coutc; void main() int j; SqStack s; SElemType e; InitStack(s); / 初始化栈s for(j=1;j=12;j+) Push(s,j); / 将值为j的栈元素入栈s中 cout栈中元素依次为n; StackTraverse(s,print); / 从栈底到栈顶依次对栈s中每个元素调用print()函数 Pop(s,e); / 弹出栈顶元素，其值赋给e cout弹出的栈顶元素e=; coute; coutendl; cout栈空否?; coutStackEmpty(s); coutt(1:空 0:否 ); GetTop(s,e); / 将新的栈顶元素赋给e coutn栈顶元素e=; coute; coutendl; cout栈的长度为; coutStackLength(s); ClearStack(s); / 清空栈s coutendl; cout清空栈后，栈空否？; coutStackEmpty(s); coutt(1:空 0:否 )n; DestroyStack(s); / 销毁