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

// main3-1.cpp 检验bo3-1.cpp的主程序
//#include"c1.h"
#include<iostream.h>
#include<string.h>
#include<ctype.h>
#include<malloc.h>
#include<limits.h>
//#include<stdio.h>
#include<stdlib.h>
#include<io.h>
#include<math.h>
#include<sys/timeb.h>
#include<stdarg.h> // 提供宏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<<c;
cout<<"\t";
}

void print1(ElemType &c) // 以十进制整型的格式输出元素的值(设c为引用类型)
{
cout<<c;
}

void print2(ElemType c) // 以字符型的格式输出元素的值
{
cout<<c;
}

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=";
cout<<e;
cout<<endl;
cout<<"栈空否?";
cout<<StackEmpty(s);
cout<<"\t(1:空 0:否 )";
GetTop(s,e); // 将新的栈顶元素赋给e
cout<<"\n栈顶元素e=";
cout<<e;
cout<<endl;
cout<<"栈的长度为";
cout<<StackLength(s);
ClearStack(s); // 清空栈s
cout<<endl;
cout<<"清空栈后，栈空否？";
cout<<StackEmpty(s);
cout<<"\t(1:空 0:否 )\n";
DestroyStack(s); // 销毁栈s
cout<<"销毁栈后:\ns.top=";
cout<<ElemType(s.top);
cout<<endl;
cout<<"s.stacksize=";
cout<<ElemType(s.stacksize);
cout<<endl;
cout<<"s.base=";
cout<<ElemType(s.base);
cout<<endl;
}