北理工数据结构作业2

本文格式为Word版，下载可任意编辑——北理工数据结构作业2第三章作业

1、写出以下程序段的输出结果。viodmain(){StackS;

charx,y;InitStack(S);x=’c’;y=’k’;

Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);}printf(x);

}答：stack

2、简述以下算法的功能（栈的元素类型SElemType为int）。（1）Ststusalgo1(StackS){intI,n,A[255];n=0;

while(!StackEmpty(S)){n++;Pop(S,A[n]);}

for(i=1;i#include#include#defineOK1#defineERROR0#defineOVERFLOW-2

#defineSTACK_INIT_SIZE100//存储空间初始分派量#defineSTACKINCREMENT10//存储空间分派增量

typedefstruct{//定义运算符栈数据类型char*base;

输出：14输出：-48

输入：(4+2)*(2-10)=

char*top;intstacksize;}SqStack1;

typedefstruct{//定义操作数栈数据类型int*base;int*top;intstacksize;}SqStack2;

intInitStack1(SqStack1if(!S.base)exit(OVERFLOW);S.top=S.base;

S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack1

intInitStack2(SqStack2if(!S.base)exit(OVERFLOW);S.top=S.base;

S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack2

charGetTop1(SqStack1S){//若栈不空，则用char型元素e返回S的栈顶元素，并返回OK；否则返回ERRORchare;

if(S.top==S.base)returnERROR;e=*(S.top-1);returne;}//GetTop1

intGetTop2(SqStack2S){//若栈不空，则用int型元素e返回S的栈顶元素，并返回OK；否则返回ERRORinte;

if(S.top==S.base)returnERROR;e=*(S.top-1);returne;}//GetTop2

intPush1(SqStack1if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}

*S.top++=e;returnOK;}//Push1

intPush2(SqStack2if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}

*S.top++=e;returnOK;}//Push2

intPop1(SqStack1e=*-