educoder数据结构与算法 队列 第2关 实现一个链接存储的队列

educoder数据结构与算法 队列 第2关 实现一个链接存储的队列,第1张

educoder数据结构与算法 队列 第2关 实现一个链接存储的队列

任务描述

本关任务:实现 step2/CLnkQueue.cpp 中的CLQ_IsEmpty、CLQ_Length、CLQ_In和CLQ_Out四个 *** 作函数,以实现判断队列是否为空、求队列长度、队列元素入队和出队等功能。

相关知识

链式队列的定义

队列的存储除了顺序存储之外也可以采用链接存储方式来实现。图 1 描述了队列的一种链接存储实现方案。

该队列存储了 3 个元素 {56,77,15} ,其中 56 为队列头, 15 为队列尾。

这种实现方案中涉及到的两个属性元素如下:

  • rear: 指向队列尾结点的指针;
  • next: 指向队列头结点的指针。

当队列是空队列时,rear指向附加头结点,附加头结点的数据项等于 0 ,如图 2 所示。

基于这些属性要素组织成的链表结点的结构定义为:

 
  1. struct LNode {
  2. T data;
  3. LNode* next;
  4. };

为了讨论简单,我们假设队列元素的数据类型为整数:

 
  1. 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 个 *** 作函数的代码框架如下:

 
  1. bool CLQ_IsEmpty(LNode* rear)
  2. // 判断队列是否为空
  3. {
  4. // 请在这里补充代码,完成本关任务
  5. }
 
  1. int CLQ_Length(LNode* rear)
  2. // 返回队列长度,rear指向尾结点
  3. {
  4. // 请在这里补充代码,完成本关任务
  5. }
 
  1. void CLQ_In(LNode* & rear, T x)
  2. // 入队列, 新结点加入链表尾部。rear指向尾结点
  3. {
  4. // 请在这里补充代码,完成本关任务
  5. }
 
  1. bool CLQ_Out(LNode* & rear, T& item)
  2. // 出队列。空队列时,返回值为false。rear指向尾结点
  3. {
  4. // 请在这里补充代码,完成本关任务
  5. }

测试说明

本关的测试文件是 step2/Main.cpp ,负责对你实现的代码进行测试。具体代码如下:

 
  1. #include
  2. #include
  3. #include
  4. #include "CLnkQueue.h"
  5. #pragma warning(disable:4996)
  6. int main()
  7. {
  8. LNode* rear=CLQ_Create();
  9. char dowhat[100];
  10. while(true) {
  11. scanf("%s", dowhat);
  12. if (!strcmp(dowhat,"in")) {
  13. T x;
  14. scanf("%d", &x);
  15. CLQ_In(rear,x);
  16. }else if (!strcmp(dowhat,"out")) {
  17. T item;
  18. CLQ_Out(rear, item);
  19. }
  20. else {
  21. break;
  22. }
  23. }
  24. int length=CLQ_Length(rear);
  25. printf("Queue length: %dn", length);
  26. printf("Queue data: ");
  27. CLQ_Print(rear);
  28. CLQ_Free(rear);
  29. }

注意: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


开始你的任务吧,祝你成功!

人生,对于我们谁都有许多想法,但由于迟迟没有付诸行动,结果多少光阴过去,却只能停留在计划中,要想拥有成功,就需要赋予人生足够的速度,这是成功者的姿态,也是胜利者的姿态。

// 队列的链接存储实现文件。
// 采用循环链表,具有附加头节点,使用尾结点指针。
// CLQ_   Circularly linked Queue

#include 
#include 
#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之间补充代码,完成队列是否为空的判断。
    
    return rear==rear->next;


    
}

int CLQ_Length(LNode* rear)
// 返回队列长度,rear指向尾结点。
{
    // 请在Begin-End之间补充代码,获取队列长度。
    
    return rear->next->data;


    
}

void CLQ_In(LNode* & rear, T x)
// 入队列, 新结点加入链表尾部。rear指向尾结点。
{
    // 请在Begin-End之间补充代码,完成新结点入队 *** 作。
    
    LNode*newNode=new LNode;
    newNode->data=x;
    newNode->next=rear->next;
    rear->next=newNode;
    rear=newNode;
    rear->next->data++;//为输出做准备




    
}

bool CLQ_Out(LNode* & rear, T& item)
// 出队列。空队列时,返回值为false。rear指向尾结点。
{
    // 请在Begin-End之间补充代码,完成结点出队 *** 作。
    
    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;
    } 


    
}

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");
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5660005.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表(0条)

保存