资源描述：
《北理工数据结构作业2.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章作业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);}答：stack2、简述下列算法的功能（栈的元素类型SElemType为int）。（1）Ststusalgo1(StackS){intI,n,A[255];n=
2、0;while(!StackEmpty(S)){n++;Pop(S,A[n]);}for(i=1;i<=n;i++)Push(S,A[n]);}答：实现栈中元素的逆置（2）Statusalgo2(StackS,inte){StackT;intd;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的元素1、设有4个元素1、2、3、4依次进栈，而出栈操作可随时进行（进出栈可任
3、意交错进行，但要保证进栈次序不破坏1、2、3、4的相对次序），请写出所有可能的出栈次序。答：共14种情况，顺序如下：1234，1243，1324，1342，1432，2134，2143，2314，2341，2431，3421，3241，3214，4321。2、写出下列程序段的输出结果（队列中的元素类型QelemType为char）。viodmain(){QueueQ;InitQueue(Q);charx=’e’,y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQu
4、eue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);}}答：cha3、简述下列算法的功能（栈和队列的元素类型均为int）。voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpt(Q)){DeQueue(Q,d);Push(S,d);}while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}答：利用栈S将队列Q中的元素进行逆置。1、为了充分利用空间，将两个栈共同存储在长度为n的一维数组
5、中，共享数组空间。设计两个栈共享一维数组的存储表示方式，画出示意图。答：设计两个栈Stack1和Stack2共享数组空间，Stack1的栈底放在数组的首端，Stack2的栈底放在数组的尾端，分别向两个栈中存储相应的元素，两个栈的栈顶分别向数组中间扩展。当总的存储空间不大于数组长度时，数组空间将得到最大利用。当两个栈占满整个数组空间时，这时两个栈共享一个长度为n的数组空间，再向栈中放元素时会发生上溢。0（Stack1底）12……Stack1顶……Stack2顶……n-3n-2n-1（Stack2底）实验二1、简单计算器。请按照四则运算加、减、乘、除、幂（^）和括号的优先
6、关系和惯例，编写计算器程序。要求：①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。②输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。例如，输入：4+2*5=输出：14输入：(4+2)*(2-10)=输出：-48程序如下：#include#include#include#defineOK1#defineERROR0#defineOVERFLOW-2#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储
7、空间分配增量typedefstruct{//定义运算符栈数据类型char*base;char*top;intstacksize;}SqStack1;typedefstruct{//定义操作数栈数据类型int*base;int*top;intstacksize;}SqStack2;intInitStack1(SqStack1&S){//构造一个空的运算符栈S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksiz
