3.28.c

来自「数据结构习题及答案」· C语言 代码 · 共 47 行

◆3.28② 假设以带头结点的循环链表表示队列，并且
只设一个指针指向队尾元素结点(注意不设头指针)，
试编写相应的队列初始化、入队列和出队列的算法。

实现下列函数：
Status InitCLQueue(CLQueue &rear);
Status EnCLQueue(CLQueue &rear, ElemType x);
Status DeCLQueue(CLQueue &rear, ElemType &x);

带头结点循环链队列CLQueue的类型为以下LinkList类型：
typedef struct LNode{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;
typedef LinkList CLQueue;
Status InitCLQueue(CLQueue &rear)
{  
  rear=(CLQueue)malloc(sizeof(LNode));
  rear->next=rear;
  return OK;

}

Status EnCLQueue(CLQueue &rear, ElemType x)
{ LinkList p;
  if(!(p=(LNode*)malloc(sizeof(LNode)))) return ERROR;
  p->data=x;
  p->next=rear->next;                     //直接把p加在rear的后面
  rear->next=p;
  rear=p;                                  //修改尾指针
  return OK;
}

Status DeCLQueue(CLQueue &rear, ElemType &x)
{ 
  LinkList p;
  if(rear==rear->next) return ERROR;          //队列已空
  p=rear->next->next;                        //p指向队首元素
  x=p->data;
  rear->next->next=p->next;                  //删除首元素
  if(rear==p) rear=rear->next;               //保护队尾指针rear,防止rear丢失
  free(p);
  return OK;

}