数据结构算法 习题 答案 带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针).pdf

带头结点的循环链表表示队列算法设计 带头结点的循环链表表示队列是一种特殊的队列结构，它只设一个指针指向队尾元素结点，不设头指针。这种结构可以提高队列的效率和灵活性。本文将详细介绍带头结点的循环链表表示队列的算法设计，包括队列初始化、入队列和出队列的算法实现。 队列初始化算法 ---------------- 队列初始化算法的主要任务是将队列置空，使头结点成为队尾元素。下面是队列初始化算法的实现： ```c void InitQueue(LinkQueue &Q) { // 置空队：就是使头结点成为队尾元素 Q.rear = (QueueNode*)malloc(sizeof(QueueNode)); QueueNode* s; Q.rear->next = Q.rear->next;// 将队尾指针指向头结点 while(Q.rear != Q.rear->next) {// 当队列非空，将队中元素逐个出队 s = Q.rear->next; Q.rear->next = s->next; free(s); }// 回收结点空间 } ``` 入队列算法 ------------- 入队列算法的主要任务是将元素插入队尾结点处。下面是入队列算法的实现： ```c void EnQueue(LinkQueue &Q, Datatype x) { // 入队，也就是在尾结点处插入元素 QueueNode *p = (QueueNode*)malloc(sizeof(QueueNode));// 申请新结点 p->data = x; p->next = Q.rear->next;// 初始化新结点并链入 Q.rear->next = p; Q.rear = p;// 将尾指针移至新结点 } ``` 出队列算法 ------------- 出队列算法的主要任务是将头结点之后的元素摘下。下面是出队列算法的实现： ```c Datatype DeQueue(LinkQueue &Q, Datatype &x) { // 出队，把头结点之后的元素摘下 Datatype t; QueueNode *p; if(EmptyQueue(Q)) { p = Q.rear->next->next; // p 指向将要摘下的结点 x = p->data; // 保存结点中数据 if (p == Q.rear) { // 当队列中只有一个结点时，p 结点出队后，要将队尾指针指向头结点 Q.rear = Q.rear->next; Q.rear->next = p->next; } else { Q.rear->next->next = p->next;//摘下结点p } free(p);// 释放被删结点 return x; } } ``` 另外一种实现方式 ------------------ 下面是另一种实现带头结点的循环链表表示队列的算法实现： ```c typedef struct Node { int data; struct Node *next; }Node, *CiLNode; typedef struct { CiLNode CiLrear; }CiQueue; void InitCiQueue(CiQueue &Q) {// 初始化循环链表表示的队列Q Q = (CiLNode*)malloc(sizeof(CiLNode)); Q->next = Q; // 初始化队尾指针 } void EnCiQueue(CiQueue &Q, int x) {// 把元素x 插入循环链表表示的队列Q CiLNode *p = (CiLNode*)malloc(sizeof(CiLNode)); p->data = x; p->next = Q->next; // 直接把p 加在Q 的后面 Q->next = p; Q = p; // 修改尾指针 } Status DeCiQueue(CiQueue &Q, int x) {// 从循环链表表示的队列Q 头部删除元素x if(Q == Q->next) return INFEASIBLE; // 队列已空 CiLNode *p = Q->next->next; x = p->data; Q->next->next = p->next; free(p); return OK; } ``` 带头结点的循环链表表示队列是一种高效的队列结构，它可以提高队列的效率和灵活性。本文详细介绍了带头结点的循环链表表示队列的算法设计，包括队列初始化、入队列和出队列的算法实现。