爱华网
栈的抽象数据类型定义
ADT SqStack{
数据对象：D={ai| ai ∈ElemSet,i=1,2,3??，n,n≥0}
数据关系：R1={<ai-1,ai>| ai-1,ai ∈D,i=1,2,3,??，n}
约定其中ai端为栈底，an端为栈顶。
操作集合：
(1)void InitStack1(SqStack1 &S1);//声明栈建立函数
(2)void InitStack2(SqStack2 &S2);//声明栈建立函数
(3)void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数
(4)void Push1(SqStack1 &S1,char e);//声明入栈函数
(5)void Push2(SqStack2 &S2,float e);//声明入压栈函数
(6)char GetTop1(SqStack1 &S1);//声明取栈顶元素函数
(7)float GetTop2(SqStack2 &S2);//声明取栈顶元素函数
(8)char Pop1(SqStack1 &S1);//声明出栈函数
(9)float Pop2(SqStack2 &S2);//声明出栈函数
(10)char Compare(char m,char n);//声明比较函数
(11)float Operate(float a,char rheta,float b);//声明运算函数
(12)void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素
(13)void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素 }ADT SqStack
第四章 详细设计
源程序
#include<iostream>
using namespace std;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct //运算符栈
{
char *base;
char *top;
int stacksize;
}SqStack1;
typedef struct //运算数栈
{
float *base;
float *top;
int stacksize;
}SqStack2;
void InitStack1(SqStack1 &S1);//声明栈建立函数
void InitStack2(SqStack2 &S2);//声明栈建立函数
void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数 void Push1(SqStack1 &S1,char e);//声明入栈函数
void Push2(SqStack2 &S2,float e);//声明入压栈函数
char GetTop1(SqStack1 &S1);//声明取栈顶元素函数
float GetTop2(SqStack2 &S2);//声明取栈顶元素函数
char Pop1(SqStack1 &S1);//声明出栈函数
float Pop2(SqStack2 &S2);//声明出栈函数
char Compare(char m,char n);//声明比较函数
float Operate(float a,char rheta,float b);//声明运算函数 void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素 void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素
/*主函数*/
void main()
SqStack1 S1;//定义运算符栈
SqStack2 S2;//定义运算数栈
//freopen("data1.in","r",stdin);
//freopen("data1.out","w",stdout);
InitStack1(S1);//调用栈建立函数
InitStack2(S2);//调用栈建立函数
evaluate(S1,S2);//调用确定如何入栈函数
cout<<"按任意键结束!"<<endl;
}
/*运算符栈函数*/
void InitStack1(SqStack1 &S1)//构造一个空栈S1
{
S1.base=(char *)malloc(STACK_INIT_SIZE *sizeof(char)); if(!S1.base)cout<<"存储分配失败！";//存储分配失败 S1.top=S1.base;
S1.stacksize=STACK_INIT_SIZE;
}
void Push1(SqStack1 &S1,char e)//入栈
{
if(S1.top-S1.base>=S1.stacksize)//如果栈满，追加存储空间 {
S1.base=(char
*)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char)); if(!S1.base) cout<<"存储分配失败！";
else
{
S1.top=S1.base+S1.stacksize;
S1.stacksize=S1.stacksize+STACKINCREMENT;
}
}
*S1.top=e;S1.top=S1.top+1;//将元素压入栈中，指针上移 }
char GetTop1(SqStack1 &S1)//取栈顶元素
char e;
if(S1.top==S1.base)cout<<"nttt运算符栈已空!n"; else e=*(S1.top-1);
return e;
}
void DispStack1(SqStack1 &S1)//从栈底到栈顶依次输出各元素 {
char e,*p;
if(S1.top==S1.base)cout<<" ";
else
{
p=S1.base;
while(p<S1.top)
{
e=*p;
p++;
cout<<e;
}
}
}
char Pop1(SqStack1 &S1)//出栈
{
char e;
if(S1.top==S1.base)cout<<"nttt运算符栈已空!n"; e=*(--S1.top);
return e;
}
/*运算数栈函数*/
void InitStack2(SqStack2 &S2)//构造一个空栈S2
{
S2.base=(float *)malloc(STACK_INIT_SIZE *sizeof(float)); if(!S2.base)cout<<"存储分配失败！";//存储分配失败 S2.top=S2.base;
S2.stacksize=STACK_INIT_SIZE;
}
void Push2(SqStack2 &S2,float e)//入栈
{
爱华网www.aIhUaU.com网友整理上传,为您提供最全的知识大全,期待您的分享，转载请注明出处。
