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

、队列、数组非编程作业:,请写出全部可能的出栈序列和不可能的出栈序列。参考答案:可能的出栈序列:(14种)dcba cdba bacd cbda adcb cbad bdca acdb bcda acbd   bcad abdcbadc abcd不可能的出栈序列:(10种)dbca dbac dabc dacb dcabcabdcdab bdac cadb adbc ?参考答案:当牺牲一个存储结点,约定以“队列头指针在队列尾指针的下一位置(指环状的下一个位置)上”作为队列“满”状态的标志时,循环队列判断队满的条件为:(+1)%MaxQsize==;判断队空的条件为:==。,采用压缩存储存放于一维数组F[n(n+1)/2]中(从F[0]开始存放),请分别给出存放上三角阵时任一矩阵元素aij(1≤i,j≤n)的地址计算公式和存放下三角阵时任一矩阵元素aij(1≤i,j≤n)的地址计算公式。参考答案:存放上三角阵时,任一矩阵元素aij(1≤i,j≤n)的地址计算公式为:存放下三角阵时,任一矩阵元素aij(1≤i,j≤n)的地址计算公式为:。参考答案:编程作业栈采用顺序栈存储,试设计算法实现将表达式转换成后缀表达式输出。例如,输入表达式:  a+b/c-(d*e+f)*g输出其后缀表达式:abc/+de*f+g*-参考答案:#include<>#include<>#include<>#defineOVERFLOW-2#defineOK1#defineERROR0#define STACK_INIT_SIZE 100 #defineSTACKINCREMENT 10 typedef intStatus;typedefcharSElemType;typedefcharstring[80];typedef struct{ SElemType *base;SElemType *top; int stacksize;}SqStack;StatusInitStack(SqStack&S){  =(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!) exit(OVERFLOW);=;=STACK_INIT_SIZE;return(OK);}StatusClearStack(SqStack&S){  =(SElemType*)realloc(,STACK_INIT_SIZE*sizeof(SElemType));if(!)exit(OVERFLOW);=;=STACK_INIT_SIZE;return(OK);}voidDestroyStack(SqStack&S){  =0;if()  free();==NULL;}StatusStackEmpty(SqStackS){  if(==)returntrue;elsereturnfalse;}SElemTypeGetTop(SqStackS){  SElemTypee;if(>)e=*(-1);returne;}StatusPush(SqStack&S,SElemTypee){    if(->=) //栈满{ =(SElemType*)realloc(,(+STACKINCREMENT)*sizeof(SElemType));if(!) exit(OVERFLOW);=+;+=STACKINCREMENT;}*++=e;returnOK;}StatusPop(SqStack&S,SElemType&e){  if(==) //栈空returnERROR;e=*--;returnOK;}StatusStackTraverse(SqStackS,void(*visit)(SElemType)) //栈遍历{  inti=0;if(!)returnERROR;while(>)(*visit)(*