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

typedef struct

{elemtp q[m];

int frontcount; //front是队首指针count是队列中元素个数

}cqnode; //定义类型标识符

()判空int Empty(cqnode cq) //cq是cqnode类型的变量

{if(cqcount==) return()else return(); //空队列}

入队: int EnQueue(cqnode cqelemtp x)

{if(count==m){printf(队满\n)exit(); }

cqq[(cqfront+count)%m]=x; //x入队

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

}

出队: int DelQueue(cqnode cq)

{if (count==){printf(队空\n)return();}

printf(出队元素cqq[cqfront]);

x=cqq[cqfront];

cqfront=(cqfront+)%m; //计算新的队头指针

return(x)

}

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

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

循环队列解决了用向量表示队列所出现的假溢出问题但同时又出现了如何判断队列的满与空问题例如在队列长的循环队列中若假定队头指针front指向队头元素的前一位置而队尾指针指向队尾元素则front=rear=的情况下连续出队个元素则front==rear为队空如果连续入队个元素则front==rear为队满如何判断这种情况下的队满与队空一般采取牺牲一个单元的做法或设标记法即假设front==rear为队空而（rear+）%表长==front为队满或通过设标记tag若tag=front==rear则为队空若tag=因入队而使得front==rear则为队满

本题中队列尾指针rear指向队尾元素的下一位置listarray[rear]表示下一个入队的元素在这种情况下我们可规定队头指针front指向队首元素当front==rear时为队空当（rear+）%n=front时为队满出队操作（在队列不空情况下）队头指针是front=（front+）%n

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