北理工数据结构作业2

1、第三章作业1、 写出下列程序段的输出结果。viod main ( ) Stack S;char x, 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); 答：stack2、 简述下列算法的功能（栈的元素类型SElemType为int）。（1）Ststus algo1(Stack S) int I, n

2、, A255; n=0; while ( ! StackEmpty(S) ) n+; Pop(S, An); for ( i=1; i=n; i+ ) Push(S, An); 答：实现栈中元素的逆置（2）Status algo2(Stack S, int e) Stack T; int d; InitStack (T); while ( ! StackEmpty(S) ) Pop(S, d); if ( d!=e ) Push(T, d); while ( ! StackEmpty(T) ) Pop (T, d); Push (S, d); 答：通过栈T的辅助删除栈S中所有值为e的元素3、

3、设有4个元素1、2、3、4依次进栈，而出栈操作可随时进行（进出栈可任意交错进行，但要保证进栈次序不破坏1、2、3、4的相对次序），请写出所有可能的出栈次序。答：共14种情况，顺序如下：1234，1243，1324，1342，1432，2134，2143，2314，2341，2431，3421，3241，3214，4321。4、 写出下列程序段的输出结果（队列中的元素类型QelemType为char）。viod main ( ) Queue Q; InitQueue(Q);char x=e, y=c;EnQueue(Q, h); EnQueue(Q, r); EnQueue(Q, y);DeQu

4、eue(Q, x); EnQueue(Q, x);DeQueue(Q, x); EnQueue(Q,a);while ( ! QueueEmpty(Q) ) DeQueue(Q, y); printf(y);答：cha5、 简述下列算法的功能（栈和队列的元素类型均为int）。void algo3(Queue &Q) Stack S; int d; InitStack (S); while ( ! QueueEmpt(Q) ) DeQueue(Q, d); Push(S, d);while ( ! StackEmpty(S) ) Pop(S, d); EnQueue(Q, d); 答：利用栈S将

5、队列Q中的元素进行逆置。6、 为了充分利用空间，将两个栈共同存储在长度为n的一维数组中，共享数组空间。设计两个栈共享一维数组的存储表示方式，画出示意图。答：设计两个栈Stack1和Stack2共享数组空间，Stack1的栈底放在数组的首端，Stack2的栈底放在数组的尾端，分别向两个栈中存储相应的元素，两个栈的栈顶分别向数组中间扩展。当总的存储空间不大于数组长度时，数组空间将得到最大利用。当两个栈占满整个数组空间时，这时两个栈共享一个长度为n的数组空间，再向栈中放元素时会发生上溢。0（Stack1底）12Stack1顶Stack2顶n-3n-2n-1（Stack2底）实验二1、简单计算器。请按

6、照四则运算加、减、乘、除、幂（）和括号的优先关系和惯例，编写计算器程序。要求： 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。例如，输入：4+2*5=输出：14 输入：(4+2)*(2-10)=输出：-48程序如下：#include#include#include#define OK 1#define ERROR 0#define OVERFLOW -2#define STACK_INIT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量typ

7、edef struct/定义运算符栈数据类型 char *base; char *top; int stacksize;SqStack1;typedef struct/定义操作数栈数据类型 int *base; int *top; int stacksize;SqStack2;int InitStack1(SqStack1 &S)/构造一个空的运算符栈 S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE;

8、 return OK;/InitStack1int InitStack2(SqStack2 &S)/构造一个空的操作数栈 S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;/InitStack2char GetTop1(SqStack1 S)/若栈不空，则用char型元素e返回S的栈顶元素，并返回OK；否则返回ERROR char e; if(S.top=S.base) return

9、ERROR; e=*(S.top-1); return e;/GetTop1int GetTop2(SqStack2 S)/若栈不空，则用int型元素e返回S的栈顶元素，并返回OK；否则返回ERROR int e; if(S.top=S.base) return ERROR; e=*(S.top-1); return e;/GetTop2int Push1(SqStack1 &S,char e)/插入char型元素e为新的栈顶元素 if(S.top-S.base=S.stacksize) S.base=(char *)realloc(S.base,(S.stacksize+STACKINCRE

10、MENT)*sizeof(char); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;/Push1int Push2(SqStack2 &S,int e)/插入int型元素e为新的栈顶元素 if(S.top-S.base=S.stacksize) S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int); if(!S.base) exit(OVERFLO

11、W); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;/Push2int Pop1(SqStack1 &S,char &e)/若栈不空，则删除S的栈顶元素，用char型元素e返回其值，并返回OK；否则返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK;/Pop1int Pop2(SqStack2 &S,int &e)/若栈不空，则删除S的栈顶元素，用int型元素e返回其值，并返回OK；否则返回ERROR if(S.top=

12、S.base) return ERROR; e=*-S.top; return OK;/Pop2char Precede(char a,char b)/比较两个相继出现的运算符a和b间的优先级关系switch(a)case +:switch(b)case+:return;break;case-:return;break;case*:return;break;case/:return;break;case(:return;break;case=:return;break;case:return;break;case-:return;break;case*:return;break;case/:r

13、eturn;break;case(:return;break;case=:return;break;case:return;break;case-:return;break;case*:return;break;case/:return;break;case(:return;break;case=:return;break;case:return;break;case-:return;break;case*:return;break;case/:return;break;case(:return;break;case=:return;break;case:return;break;case-:

14、return;break;case*:return;break;case/:return;break;case(:return;break;case=:return;break;case:return;break;case(:switch(b)case+:return;break;case-:return;break;case*:return;break;case/:return;break;case(:return;break;case):return=;break;case:return;break;case-:return;break;case*:return;break;case/:r

15、eturn;break;case):return;break;case=:return;break;case:return;break;case#:switch(b)case+:return;break;case-:return;break;case*:return;break;case/:return;break;case(:return;break;case=:return=;break;case:return0;b-) x=x*a; return x;/powint Operate(int a,char theta,int b)/操作数a和b进行运算 switch(theta)case+

16、:return(a+b);case-:return(a-b);case*:return(a*b);case/:return(a/b);case:return(pow(a,b);/Operateint In(char c)/判断字符c是否为运算符if(c!=+&c!=-&c!=*&c!=/&c!=&c!=&c!=(&c!=) return ERROR;else return OK;/Inint EvaluateExpression()int x,a,b;char c,theta; SqStack1 OPTR;SqStack2 OPND;InitStack1(OPTR);InitStack2(OPND);Push1(OPTR,#);c=getchar();while(c!=n) x=0;if(!In(c)/c是操作数while(!In(c)x=x*10+c-48;c=getchar();P