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

作业2. 栈、队列、数组 非编程作业： 若进栈序列为ABCD，请写出全部可能的出栈序列和不可能的出栈序列。 参考答案： 可能的出栈序列：(14种) dcba cdba bacd cbda adcb cbad bdca acdb bcda acbd bcad abdc badc abcd 不可能的出栈序列：(10种) dbca dbac dabc dacb dcab cabd cdab bdac cadb adbc 简要说明循环队列如何判断队满和队空？ 参考答案： 当牺牲一个存储结点，约定以“队列头指针在队列尾指针的下一位置（指环状的下一个位置）上” 作为队列“满”状态的标志时，循环队列判断队满的条件为：(Q.rear+1) % MaxQsize==Q.front；判断队空的条件为：Q.front == Q.rear。 设A为n阶对称矩阵，采用压缩存储存放于一维数组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 stdio.h #include stdlib.h #include string.h #define OVERFLOW -2 #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status; typedef char SElemType; typedef char string[80]; typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; Status InitStack(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); } Status ClearStack(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); } void DestroyStack(SqStack S) { S.stacksize=0; if(S.base) free(S.base); S.base=S.top=NULL; } Status StackEmpty(SqStack S) { if(S.top==S.base) return true; else return false; } SElemType GetTop(SqStack S) { SElemType e; if(S.topS.base) e=*(S.top-1); return e; } Status Push(SqStack S, SElemType e) { if(S.top-S.base=S.stacksize) //栈满 { S.base=(SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) *sizeof(SElemType)); if(!S