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

// main3-1.cpp 检验bo3-1.cpp的主程序
//#include"c1.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的前面

// #include"c3-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.top>S.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.top>S.base) // S.base指向栈元素
visit(*S.base++); // 对该栈元素调用visit()，
cout<<"\n"; // 栈底指针上移1个存储单元
}

#define ElemType SElemType

Status equal(ElemType c1,ElemType c2) // 判断是否相等的函数

{
if(c1==c2)
return TRUE;
else
return FALSE;
}

int comp(ElemType a,ElemType b) // 根据a<、=或>b，分别返回-1、0或1
{
if(a==b)
return 0;
else
return (a-b)/abs(a-b);
}

void print(ElemType c) // 以十进制整型的格式输出元素的值
{
cout<<<"\t";
}

void print1(ElemType &c) // 以十进制整型的格式输出元素的值(设c为引用类型)
{
cout<栈元素入栈s中
cout<<"栈中元素依次为\n";
StackTraverse(s,print); // 从栈底到栈顶依次对栈s中每个元素调用print()函数
Pop(s,e); // 弹出栈顶元素，其值赋给e
cout<<"弹出的栈顶元素e=";
cout<

关于我们      便捷服务       自信AI       AI导航        抽奖活动©2010-2026 宁波自信网络信息技术有限公司  版权所有客服电话：[phone]  投诉电话：[phone]浙公网安备33021202000488号   浙ICP备2021020529号-1  |  浙B2-20240490  关注我们 ：