试题四（共 15 分）阅读以下说明和 C 函数，填补函数中空缺，将解答填入答题纸对应栏内。【说明】简单队列是符合先进先出规则数据结构，下面用不含有头结点单向循环链表表示简单队列。函数 enqueue（queue *q，KeyType new_elem） 功能是将元素new_elem 加入队尾。函数 Dnqueue（queue *q，KeyType *elem）功能使将非空队列队头元素出队（从队列中删除），并通过参数带回刚出队元素。用单向循环链表表示队列如图 4-1 所示。
图 4-1 单向循环链表表示队列示意图队列及链表结点等相关类型定义如下:enum {errOr， OK};typedef int KeyType;typedef struct qNode﹛KeyType data;Struct qNode*next;﹜qNode，*Linkqueue; Typedef struct﹛int size;Link:queue 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;（）;﹜elseP->next=p;﹙﹚;q->size++;return OK;﹜ int Dequeue（queue*q,KeyType*elem）﹛ ／／出队列qNode*p;if（0＝＝q->size） ／／是空队列return errOr；P=（）; ／／令 p 指向队头元素结点*elem =p->data;q->rear->next=（）; ／／将队列元素结点从链表中去除if（（）） ／／被删除队头结点是队列中唯一结点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（5）Q→rear==p 或 Q→rear→next==p→next 或 Q→size==1
【解析】
本题考察C语言指针与链表知识，为入队列和删除队列问题。对于入队列，那么当队列Q不为空时，P队尾t要指向原Q队尾指向元素，即：P->next=Q->rear->next，Q队尾要指向p，即：Q→rear→next=p。当队列Q为空时，插入p元素，则p队尾指向p自身，即：p→next=p，且整个队列Q队尾也是p，即：Q→rear=p。对于队列删除元素p，先判断Q是否为空，为空队列则返回 ERROR;If(0＝＝q->size) //是空队列Return ERROR；另p指向队头元素结点，队头元素结点可用Q→rear→next表示。此时，p转化为头结点，p出列，则需要Q队尾指向p下一个元素，因此第4空填：p→next。最后，判断被删除队头结点是否是队列中唯一结点，可采用：Q→rear==p 或 Q→rear→next==p→next 或 Q→size==1 等表示方法。
