2013数据结构作业2-栈队列和数组-参考答案

作业2.栈、队列、数组非编程作业：1．若进栈序列为ABCD，请写出全部可能的出栈序列和不可能的出栈序列。参考答案：可能的出栈序列：(14种)dcbacdbabacdcbdaadcbcbadbdcaacdbbcdaacbdbcadabdcbadcabcd不可能的出栈序列：(10种)dbcadbacdabcdacbdcabcabdcdabbdaccadbadbc2．简要说明循环队列如何判断队满和队空？参考答案：当牺牲一个存储结点，约定以“队列头指针在队列尾指针的下一位置（指环状的下一个位置）上”作为队列“满”状态的标志时，循环队列判断队满的条件为：(Q.rear+1)%MaxQsize==Q.front；判断队空的条件为：Q.front==Q.rear。3．设A为n阶对称矩阵，采用压缩存储存放于一维数组F[n(n+1)/2]中（从F[0]开始存放），请分别给出存放上三角阵时任一矩阵元素aij（1≤i,j≤n）的地址计算公式和存放下三角阵时任一矩阵元素aij（1≤i,j≤n）的地址计算公式。参考答案：存放上三角阵时，任一矩阵元素aij（1≤i,j≤n）的地址计算公式为：ij11+1Loc(a)=Loc(a)+1*2iijl存放下三角阵时，任一矩阵元素aij（1≤i,j≤n）的地址计算公式为：ij11+1Loc(a)=Loc(a)+1*2jjil4．写出下面稀疏矩阵的三元组顺序表和十字链表表示。400000503008000000000700200000A参考答案：编程作业栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。例如，输入表达式：a+b/c-(d*e+f)*g输出其后缀表达式：abc/+de*f+g*-参考答案：#includestdio.h#includestdlib.h#includestring.h#defineOVERFLOW-2#defineOK1#defineERROR0#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefintStatus;typedefcharSElemType;typedefcharstring[80];typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return(OK);}StatusClearStack(SqStack&S){S.base=(SElemType*)realloc(S.base,STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return(OK);}voidDestroyStack(SqStack&S){S.stacksize=0;if(S.base)free(S.base);S.base=S.top=NULL;}StatusStackEmpty(SqStackS){if(S.top==S.base)returntrue;elsereturnfalse;}SElemTypeGetTop(SqStackS){SElemTypee;if(S.topS.base)e=*(S.top-1);returne;}StatusPush(SqStack&S,SElemTypee){if(S.top-S.base=S.stacksize)//栈满{S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)//栈空returnERROR;e=*--S.top;returnOK;}StatusStackTraverse(SqStackS,void(*visit)(SElemType))//栈遍历{inti=0;if(!S.base)returnERROR;while(S.topS.base)(*visit)(*S.base++);printf(\n);returnOK;}StatusInOP(SElemTypec){charOperators[]={'+','-','*','/','(',')','#','\0'};intlen=strlen(Operators);for(inti=0;ilen;i++)if(c==Operators[i])returntrue;returnfalse;}SElemTypePrecede(SElemTypecurtop,SElemTypeinput){SElemTypeorder;switch(input){case'+':case'-':switch(curtop){case'+':case'-':case'*':case'/':case')':order='';break;case'(':case'#':order='';break;}break;case'*':case'/':switch(curtop){case'+':case'-':case'(':case'#':order='';break;case'*':case'/':case')':order='';break;}break;case'(':switch(curtop){case'+':order='';break;case'-':order='';break;case'*':order='';break;case'/':order='';break;case'(':order='';break;case'#':order='';break;}break;case')':switch(curtop){case'+':order='';break;case'-':order='';break;case'*':order='';break;case'/':order='';break;case'(':order='=';break;case')':order='';break;}break;case'#':switch(curtop){case'+':order='';break;case'-':order='';break;case'*':order='';break;case'/':order='';break;case')':order='';break;case'#':order='=';break;}break;}returnorder;}voidPass(stringSuffix,SElemTypech){*Suffix=ch;}voidTransform(stringInfix,stringSuffix){SqStackS;SElemTypech,e;intflag=0,len;InitStack(S);Push(S,'#');len=strlen(Infix);*(Infix+len)='#';ch=*Infix;while(!StackEmpty(S)){if(!InOP(ch))Pass(Suffix++,ch);else{switch(Precede(GetTop(S),ch)){case'':Push(S,ch);flag=0;break;case'=':Pop(S,e);flag=0;break;case'':Pop(S,e);Pass(Suffix++,e);flag=1;break;}}if(!flag)if(ch!='#')ch=*++Infix;}Pass(Suffix,'\0');DestroyStack(S);}voidmain(){stringInfix,Suffix;gets(Infix);Transform(Infix,Suffix);puts(Suffix);}