数据结构考研分类复习真题 第三章 答案[11]

（）每个栈仅用一个顺序存储空间时操作简便但分配存储空间小了容易产生溢出分配空间大了容易造成浪费各栈不能共享空间

（）多个栈共享一个顺序存储空间充分利用了存储空间只有在整个存储空间都用完时才能产生溢出其缺点是当一个栈满时要向左右栈查询有无空闲单元如果有则要移动元素和修改相关的栈底和栈顶指针当接近栈满时查询空闲单元移动元素和修改栈底栈顶指针的操作频繁计算复杂并且耗费时间

（）多个链栈一般不考虑栈的溢出（仅受用户内存空间限制）缺点是栈中元素要以指针相链接比顺序存储多占用了存储空间

设top和top分别为栈和的栈顶指针

（）入栈主要语句

if(toptop==) {printf(栈满\n); exit();}

case:top++SPACE[top]=x; //设x为入栈元素

case:topSPACE[top]=x;

出栈主要语句

caseif（top==） {printf（栈空\n）exit（）}

topreturn（SPACE[top+]） //返回出栈元素

caseif（top==N）{printf（栈空\n）exit（）}

top++return（SPACE[top]） //返回出栈元素

（）栈满条件toptop=

栈空条件top=并且top=N //top=为左栈空top=N为右栈空

设顺序存储队列用一维数组q[m]表示其中m为队列中元素个数队列中元素在向量中的下标从到m设队头指针为front队尾指针是rear约定front指向队头元素的前一位置rear指向队尾元素当front等于时队空rear等于m时为队满由于队列的性质（删除在队头而插入在队尾）所以当队尾指针rear等于m时若front不等于则队列中仍有空闲单元所以队列并不是真满这时若再有入队操作会造成假溢出其解决办法有二一是将队列元素向前平移（占用至rearfront）二是将队列看成首尾相连即循环队列（m）在循环队列下仍定义front=rear时为队空而判断队满则用两种办法一是用牺牲一个单元即rear+=front（准确记是（rear+）%m=frontm是队列容量）时为队满另一种解法是设标记方法如设标记tagtag等于情况下若删除时导致front=rear为队空tag=情况下若因插入导致front=rear则为队满

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []