2. 计算机
  3. 简单队列是符合先进先出规则的数据结构，下面用不含有头结点的单向循环链表表示简单队列。 函数EnQueue(Queue*Q，KeyType new_elem)的功能是将元素new—elem加入队尾。 函数DeQueue(Queue*Q，Key

简单队列是符合先进先出规则的数据结构，下面用不含有头结点的单向循环链表表示简单队列。 函数EnQueue(Queue*Q，KeyType new_elem)的功能是将元素new—elem加入队尾。 函数DeQueue(Queue*Q，Key

admin2018-04-19  77
问题  简单队列是符合先进先出规则的数据结构，下面用不含有头结点的单向循环链表表示简单队列。
    函数EnQueue(Queue*Q，KeyType new_elem)的功能是将元素new—elem加入队尾。
    函数DeQueue(Queue*Q，KeyType*elem)的功能使将非空队列的队头元素出队(从队列中删除)，并通过参数带回刚出队的元素。
用单向循环链表表示的队列如图4．1所示。

队列及链表结点等相关类型定义如下：
enum{ERROR，OK)；
typedef int KeyType；
typedef  struct QNode{
    KeyType data；
    struct QNode *next；
}QNode，  *LinkQueue；
typedef struct{
    int  Size；
    LinkQueue rear；
    }Queue；
【C函数】
    int EnQueue(Queue*Q，KeyType new_elem)
    {  ／／元素new elem入队列
    QNode*p；
    P=(QNode*)malloc(sizeof(QNode))；
    if(!P)
    return ERROR；
    P一>data=new_elem；
    if(Q一>rear)  {
    P一>next=Q=>rear一>next；
    (1)_________;  
    }
    e1Se
    P一>next=P；
    (2)_________；
    Q->siZe++；
    return OK；
    }
    int DeQueue(Queue *Q，KeyType*elem)
    {    ／／出队列
    QNode*p；
    if(0=Q一>size)                 ／／是空队列
    return ERROR；
    P=(3)_________；                 ／／令P指向队头元素结点
    *elem=P一>data；
    Q一>rear->next=(4)_________；    ／／将队头元素结点从链表中去除
    if((5)_________)                 ／／被删除的队头结点是队列中唯一结点
Q一>rear=NULL；              ／／变成空队列
    free(p)；
    Q一>size一一；
    return OK；
}
选项
答案(1)Q->rear->next=p (2)Q->rear=p (3)Q->rear->next (4)p->next或Q->rear->next->next (5)Q->rear=p或Q->size=1或其等价形式
解析  本题考查数据结构的实现、C程序运算逻辑与指针参数的应用。
    队列是先入先出的线性数据结构。元素入队列时需要将其加入队尾，元素出队列时需要将其从队头删除。根据说明，队列采用单向循环链表表示且不设头结点，只设置指向队尾结点的指针。
    显然，队列为空时，队尾指针也为空。因此，当队尾指针为空时需要将新结点的指针域设置为指向结点自己，否则，需要通过“Q->rear->next”获得队头元素结点的指针，并将新结点的指针域设置为该值，再将新结点链接在原队尾结点之后，因此空(1)处应填入“Q->rear->next=p”。新元素加入队列后队尾指针就要更新，因此空(2)处应填入“Q->rear=p”。
    根据注释，空(3)所在语句需要获得队头元素所在结点的指针并用p表示，即空(3)应填入“Q->rear->next”。空(4)需要完成队头元素的出队列处理，也就是将队头元素的前驱结点的指针域(Q->rear->next)设置为指向队头元素的后继元素结点，表示
为“Q->rear->next=p->next"或“Q->rear->next=Q->rear->next->next”。
    进行出队列操作时的特殊情况是队列中唯一的元素被删除，此时需要修正队尾指针，空(5)所在语句即完成此处理，该空应填入“Q->rear=p”或“Q->size=1”。
转载请注明原文地址:https://kaotiyun.com/show/z2jZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)