任务描述
本关任务：实现 step2/CLnkQueue.cpp 中的CLQ_IsEmpty、CLQ_Length、CLQ_In和CLQ_Out四个操作函数，以实现判断队列是否为空、求队列长度、队列元素入队和出队等功能。
相关知识
链式队列的定义
队列的存储除了顺序存储之外也可以采用链接存储方式来实现。图 1 描述了队列的一种链接存储实现方案。
该队列存储了 3 个元素 {56,77,15} ，其中 56 为队列头， 15 为队列尾。
这种实现方案中涉及到的两个属性元素如下：
rear: 指向队列尾结点的指针；next: 指向队列头结点的指针。
当队列是空队列时，rear指向附加头结点，附加头结点的数据项等于 0 ，如图 2 所示。
基于这些属性要素组织成的链表结点的结构定义为：
struct LNode {T data;LNode* next;};
为了讨论简单，我们假设队列元素的数据类型为整数：
typedef int T; // 队列元素的数据类型
据此，只要给定rear指针，我们就可以对队列进行入队和出队的操作。
- 在给定图 1 的状态下，进队一个元素 25 以后的状态如图 3 所示：
- 若出队一个元素是指将当前队列头结点去掉。则在给定图 3 的状态下，进行一次出队后的状态如图 4 所示：
链式队列的主要操作
对数据元素进行操作处理是一个数据结构的重要组成部分。队列涉及的主要操作如下：
创建队列：创建一个队列。具体操作函数定义如下： LNode* CLQ_Create()；
释放队列空间：释放队列所占用的空间，其中rear指向尾结点。具体操作函数定义如下： void CLQ_Free(LNode* rear)；
置空队列：将队列变为空队列，其中rear指向尾结点。具体操作函数定义如下： void CLQ_MakeEmpty(LNode* & rear)；
判断队列是否为空：若队列为空，则返回 true，否则返回false。具体操作函数定义如下： bool CLQ_IsEmpty(LNode* rear)；
求队列长度：获取队列的长度，其中rear指向尾结点。具体操作函数定义如下： int CLQ_Length(LNode* rear)；
新结点入队列：新结点加入链表尾部，其中rear指向尾结点。具体操作函数定义如下： void CLQ_In(LNode* & rear, T x)；
队列元素出队列：item为出队的元素的值。若出队成功(队列不为空)，则返回true；否则(队列空)，返回false。具体操作函数定义如下： bool CLQ_Out(LNode* & rear, T& item)；
获取队列头结点元素：若获取失败(队列空)，则返回值为false，否则返回值为true。具体操作函数定义如下： bool CLQ_Head(LNode* rear, T& item)；
打印队列：依次打印出队列中的每个元素。具体操作函数定义如下： void CLQ_Print(LNode* rear)。
编程要求
本关任务是实现 step2/CLnkQueue.cpp 中的CLQ_IsEmpty、CLQ_Length、CLQ_In和CLQ_Out四个操作函数，以实现判断队列是否为空、求队列长度、队列元素入队和出队等功能。具体要求如下：
CLQ_IsEmpty：判断队列是否为空，若队列为空，则返回true，否则返回false；
CLQ_Length：获取队列的长度；
CLQ_In：新结点加入链表尾部；
CLQ_Out：队列元素出队列，若出队成功(队列不为空)，则返回true；否则(队列空)返回false；
输入输出格式请参见后续说明及测试样例。
注意：本关必读中提及的其他操作已经由平台实现，你在实现本关任务的四个操作函数时，在函数体内可调用其他操作。
本关涉及的代码文件 CLnkQueue.cpp 中的 4 个操作函数的代码框架如下：
bool CLQ_IsEmpty(LNode* rear)
// 判断队列是否为空
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
/********** End **********/
}
int CLQ_Length(LNode* rear)
// 返回队列长度，rear指向尾结点
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
/********** End **********/
}
void CLQ_In(LNode* & rear, T x)
// 入队列, 新结点加入链表尾部。rear指向尾结点
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
/********** End **********/
}
bool CLQ_Out(LNode* & rear, T& item)
// 出队列。空队列时，返回值为false。rear指向尾结点
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
/********** End **********/
}
测试说明
本关的测试文件是 step2/Main.cpp ，负责对你实现的代码进行测试。具体代码如下：
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "CLnkQueue.h" #pragma warning(disable:4996) int main() { LNode* rear=CLQ_Create(); char dowhat[100]; while(true) { scanf("%s", dowhat); if (!strcmp(dowhat,"in")) { T x; scanf("%d", &x); CLQ_In(rear,x); }else if (!strcmp(dowhat,"out")) { T item; CLQ_Out(rear, item); } else { break; } } int length=CLQ_Length(rear); printf("Queue length: %d\n", length); printf("Queue data: "); CLQ_Print(rear); CLQ_Free(rear); }
注意：step2/Main.cpp 的代码不能被修改。
输入输出说明： 输入格式： 输入多个操作：如果输入 “in” ，则后面跟一个数 x ，表示 x 入队列；如果输入 “out” ，表示出队列操作；如果输入 “end” ，表示输入结束。
输出格式： 输出队列长度，然后从队头到队尾依次输出队列的各元素。
以下是平台对 step2/Main.cpp 的测试样例： 样例输入: in 1 in 3 in 5 in 9 in 12 out end 样例输出 Queue length: 4 Queue data: 3 5 9 12
开始你的任务吧，祝你成功！
人生，对于我们谁都有许多想法，但由于迟迟没有付诸行动，结果多少光阴过去，却只能停留在计划中，要想拥有成功，就需要赋予人生足够的速度，这是成功者的姿态，也是胜利者的姿态。
AC_Code
/ // 队列的链接存储实现文件。 // 采用循环链表，具有附加头节点，使用尾结点指针。 // CLQ_ Circularly Linked Queue #include <stdio.h> #include <stdlib.h> #include "CLnkQueue.h" LNode* CLQ_Create() // 创建一个队列。 { LNode* rear=(LNode*)malloc(sizeof(LNode)); rear->data = 0; rear->next = rear; return rear; } void CLQ_Free(LNode* rear) // rear指向尾结点。 { CLQ_MakeEmpty(rear); free(rear); } void CLQ_MakeEmpty(LNode* & rear) // rear指向尾结点。 // 将队列变为空队列。 { T item; while(!CLQ_IsEmpty(rear)) CLQ_Out(rear,item); } bool CLQ_IsEmpty(LNode* rear) // 判断队列是否为空。 { // 请在Begin-End之间补充代码，完成队列是否为空的判断。 /********** Begin *********/ return rear==rear->next; /********** End **********/ } int CLQ_Length(LNode* rear) // 返回队列长度，rear指向尾结点。 { // 请在Begin-End之间补充代码，获取队列长度。 /********** Begin *********/ return rear->next->data; /********** End **********/ } void CLQ_In(LNode* & rear, T x) // 入队列, 新结点加入链表尾部。rear指向尾结点。 { // 请在Begin-End之间补充代码，完成新结点入队操作。 /********** Begin *********/ LNode*newNode=new LNode; newNode->data=x; newNode->next=rear->next; rear->next=newNode; rear=newNode; rear->next->data++; /********** End **********/ } bool CLQ_Out(LNode* & rear, T& item) // 出队列。空队列时，返回值为false。rear指向尾结点。 { // 请在Begin-End之间补充代码，完成结点出队操作。 /********** Begin *********/ if(CLQ_IsEmpty(rear)) return false; else if(rear->next->data==1) { rear=rear->next; rear->next=rear; rear->data--; } else { LNode* addNode=rear->next; addNode->next=addNode->next->next; addNode->data--; return true; } /********** End **********/ } bool CLQ_Head(LNode* rear, T& item) // rear指向尾结点。 // 获取队列头。空队列时返回值为false。 { if (CLQ_IsEmpty(rear)) return false; item = rear->next->next->data; return true; } void CLQ_Print(LNode* rear) // 打印队列。 { if (CLQ_IsEmpty(rear)) { printf("The queue is: empty. \n"); return; } LNode* node=rear->next->next; do { printf("%d ", node->data); node = node->next; } while (node != rear->next); //printf("\n"); }
