栈与队列习题与答案(6)

指针top[1]=m+1，当top[0]=0为左栈空，top[1]=m+1为右栈空；当top[0]=0并且top[1]=m+1时为全栈空。当top[1]-top[0]=1时为栈满。 27、（1）每个栈仅用一个顺序存储空间时，操作简便，但分配存储空间小了，容易产生溢出，分配空间大了，容易造成浪费，各栈不能共享空间。

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

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

28、设top1和top2分别为栈1和2的栈顶指针 （1）入栈主要语句

if(top2-top1==1) {printf(“栈满\\n”); exit(0);} case1:top1++；SPACE[top1]=x; //设x为入栈元素。 case2:top2--；SPACE[top2]=x; 出栈主要语句

case1：if（top1==-1） {printf（“栈空\\n”）；exit（0）；} top1--；return（SPACE[top1+1]）； //返回出栈元素。 case2：if（top2==N）{printf（“栈空\\n”）；exit（0）；} top2++；return（SPACE[top2-1]）； //返回出栈元素。 （2）栈满条件：top2-top1=1

栈空条件：top1=-1并且top2=N //top1=-1为左栈空，top2=N为右栈空 29、设顺序存储队列用一维数组q[m]表示，其中m为

队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。 30、见上题29的解答。 31、参见上面29题。 32、typedef struct node

{elemtype elemcq[m]; //m为队列最大可能的容量。

int front ,rear; //front和rear分别为队头和队尾指针。 }cqnode; cqnode cq;

初始状态

cq.front=cq.rear=0;

队列空

cq.front==cq.rear;

队列满

(cq.rear+1)%m==cq.front;

33、栈的特点是后进先出，队列的特点是先进先出。初始时设栈s1和栈s2均为空。 （1）用栈s1和s2模拟一个队列的输入：设s1和s2容量相等。分以下三种情况讨论：若s1未满，则元素入s1栈；若s1满，s2空，则将s1全部元素退栈，再压栈入s2，之后元素入s1栈；若s1满，s2不空（已有出队列元素），则不能入队。 （2）用栈s1和s2模拟队列出队（删除）：若栈s2不空，退栈，即是队列的出队；若s2为空且s1不空，则将s1栈中全部元素退栈，并依次压入s2中，s2栈顶元素退栈，这就是相当于队列的出队。若栈s1为空并且s2也为空，队列空，不能出队。 （3）判队空 若栈s1为空并且s2也为空，才是队列空。 讨论：s1和s2容量之和是队列的最大容量。其操作是，s1栈满后，全部退栈并压栈入s2（设s1和s2容量相等）。再入栈s1直至s1满。这相当队列元素“入队”完毕。出队时，s2退栈完毕后，s1栈中元素依次退栈到s2，s2退栈完毕，相当于队列中全部元素出队。

在栈s2不空情况下，若要求入队操作，只要s1不满，就可压入s1中。若s1满和s2不空状态下要求队列的入队时，按出错处理。 34、（1）队空s.front=s.rear； //设s是sequeuetp类型变量 （2）队满：（s.rear+1）MOD MAXSIZE=s.front //数组下标为0.. MAXSIZE-1 具体参见本章应用题第29题 35、typedef struct {elemtp q[m];

int front,count; //front是队首指针，count是队列中元素个数。 }cqnode;

//定义类型标识符。

(1)判空：int Empty(cqnode cq) //cq是cqnode类型的变量 {if(cq.count==0) return(1)；else return(0); //空队列} 入队: int EnQueue(cqnode cq，elemtp x)

{if(count==m){printf(“队满\\n”)；exit(0); } cq.q[(cq.front+count)%m]=x; //x入队

count++; return(1); //队列中元素个数增加1,入队成功。 }

出队: int DelQueue(cqnode cq)

{if (count==0){printf(“队空\\n”)；return(0);} printf(“出队元素”，cq.q[cq.front]); x=cq.q[cq.front];

cq.front=(cq.front+1)%m; //计算新的队头指针。 return(x)

}

(2) 队列中能容纳的元素的个数为m。队头指针front指向队头元素。

36、循环队列中元素个数为（REAR-FRONT+N）%N。其中FRONT是队首指针，指向队首元素的前一位置；REAR是队尾指针，指向队尾元素；N是队列最大长度。

37、循环队列解决了用向量表示队列所出现的“假溢出”问题，但同时又出现了如何判断队列的满与空问题。例如：在队列长10的循环队列中，若假定队头指针front指向队头元素的前一位置，而队尾指针指向队尾元素，则front=3，rear=7的情况下，连续出队4个元素，则front==rear为队空；如果连续入队6个元素，则front==rear为队满。如何判断这种情况下的队满与队空，一般采取牺牲一个单元的做法或设标记法。即假设front==rear为队空，而（rear+1）%表长==front为队满，或通过设标记tag。若tag=0，front==rear则为队空；若tag=1，因入队而使得front==rear，则为队满。 本题中队列尾指针rear，指向队尾元素的下一位置,listarray[rear]表示下一个入队的元素。在这种情况下，我们可规定，队头指针front指向队首元素。当front==rear时为队空，当（rear+1）%n=front时为队满。出队操作（在队列不空情况下）队头指针是front=（front+1）%n， 38、既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是dbca。 39、（1）4132 （2）4213 （3）4231 40、（1）队空的初始条件：f=r=0；

（2）执行操作A3后，r=3；// A3表示三次入队操作 执行操作D1后，f=1；//D1表示一次出队操作 执行操作A5后，r=0； 执行操作D2后，f=3； 执行操作A1后，r=1； 执行操作D2后，f=5；

执行操作A4后，按溢出处理。因为执行A3后，r=4，这时队满，若再执行A操作，则出错。 41．一般说，高级语言的变量名是以字母开头的字母数字序列。故本题答案是: AP321,PA321,P3A21,P32A1,P321A。

五、算法设计题

1、[题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。

#define maxsize 两栈共享顺序存储空间所能达到的最多元素数 #define elem …… 此处隐藏：4739字，全部文档内容请下载后查看。喜欢就下载吧 ……