C/C++顺序与链式队列详解(附代码)(二)

简介: C/C++顺序与链式队列详解(附代码)

二、链式队列(队列子系统课设)

1:链队列入队

  链式队列的实现思想同顺序队列类似,只需创建两个指针(命名为 top 和 rear)分别指向链表中队列的队头元素和队尾元素

  上图所示为链式队列的初始状态,此时队列中没有存储任何数据元素,因此 top 和 rear 指针都同时指向头节点。

  链队队列中,当有新的数据元素入队,只需进行以下 3 步操作:
1:将该数据元素用节点包裹,例如新节点名称为 elem;
2:与 rear 指针指向的节点建立逻辑关系,即执行 rear->next=elem;
3:最后移动 rear 指针指向该新节点,即 rear=elem;

  由此,新节点就入队成功了。
  例如,在上图的基础上,我们依次将 {1,2,3} 依次入队,各个数据元素入队的过程如下图所示:

2:链队列出队

  当链式队列中,有数据元素需要出队时,按照 “先进先出” 的原则,只需将存储该数据的节点以及它之前入队的元素节点按照原则依次出队即可。这里,我们先学习如何将队头元素出队。

  链式队列中队头元素出队,需要做以下 3 步操作:
1:通过 top 指针直接找到队头节点,创建一个新指针 p 指向此即将出队的节点;
2:将 p 节点(即要出队的队头节点)从链表中摘除;
3:释放节点 p,回收其所占的内存空间;

  例如,在上图的基础上,我们将元素 1 和 2 出队,则操作过程如下图所示:

3:完整代码

  本人自己感觉c++的cout和cin比c语言的scanf和printf更加好用,因此代码中的printf和scanf都被我用cout和cin代替了,如果需要纯c语言的代码,可以自行将代码中的cout和cin改换成printf和scanf即可。代码部分并没有出现只有c++特有的函数,因此不需要担心修改问题

#pragma once
#include<iostream>//cout和cin需要这个头文件
#include <cstdio>//引入c语言库函数
#include<cstdlib>///引入c语言库函数
typedef int Status;
typedef int ElemType;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSIZE 5
#define make (struct student*)malloc(sizeof(struct student));
using namespace std;
int num = 0;
int status = 0;
typedef struct QueueList 
{
    ElemType data;
    struct QueueList* next;
}QueueList;    
void menu(void)
{
    cout << "********************" << endl;
    cout << "*1 ……入队        *" << endl;
    cout << "*2 ……出队        *" << endl;
    cout << "*3 ……读队首元素  *" << endl;
    cout << "*4 ……显示        *" << endl;
    cout << "*5 ……排队    *" << endl;
    cout << "*0 ……退出        *" << endl;
    cout << "********************" << endl;
}
QueueList* InitQueue()  //创建链式队列的函数
{
    if (status == 1)//进行过5操作后,数据全部被free了,强制退出程序
    {
        cout << "队列已被删除" << endl;
        exit(-1);
    }
    QueueList* head = (QueueList*)malloc(sizeof(QueueList));    //创建一个头节点
    head->next = NULL; //对头节点进行初始化
    return head; 
}
QueueList* EndQueue(QueueList* rear, ElemType e)
{
    if (status == 1)//进行过5操作后,数据全部被free了,强制退出程序
    {
        cout << "队列已被删除" << endl;
        exit(-1);
    }
    QueueList* p = (QueueList*)malloc(sizeof(QueueList));//构造新节点
    p->data = e; //数据赋值
    p->next = NULL;//封闭队列
    rear->next = p;//让队尾指向p
    rear = p;//新队尾为p
    num++;
    cout << "当前数量" << num << endl;
    return rear;//返回新队尾
}
QueueList* DeQueue(QueueList* front, QueueList* rear)
{
    if (status == 1)//进行过5操作后,数据全部被free了,强制退出程序
    {
        cout << "队列已被删除" << endl;
        exit(-1);
    }
    if ((front->next == NULL)||(front==rear))
    {
        cout << "队列为空" << endl;
        return rear;
    }
    QueueList* p = (QueueList*)malloc(sizeof(QueueList));
    p = front->next;//此时p为要删除的数据
    cout << "待删除的数据是" << p->data << endl;
    front->next = p->next;
    if (p == rear)//此时要删除的数据就已经是最后一个数据
        rear = front;//此时队列已空,返回原有头指针即可
    free(p);
    num--;
    cout << "当前数量" << num << endl;
    return rear; 
}
Status ShowQueue(QueueList* front)
{
    if (status == 1)//进行过5操作后,数据全部被free了,强制退出程序
    {
        cout << "队列已被删除" << endl;
        exit(-1);
    }
    int i = 0;
    if (front->next == NULL)
    {
        cout << "队列为空" << endl;
        return ERROR;
    }
    do
    {
        cout << "第" << i++ << "个数据是" << front->next->data << endl;
        front = front->next;//显示数据的代码
    } while (front->next != NULL);
    return OK;
}
Status GetHead(const QueueList* front)
{
    if (front->next == NULL)
    {
        cout << "队列为空" << endl;
        return ERROR;
    }
    cout << "队列头元素为" << front->next->data << endl;
    return OK;
}
//出列顺序为1 2 4 5 7 8 10 3 9 6。
Status LeaveQueue(QueueList* front, QueueList* rear)
{
    status = 1;
    QueueList* p, * p1;
    if (front == rear)
    {
        cout << "队列为空" << endl;
        return ERROR;
    }
    p = front->next;
    while (num != 0)
    {
        for (int i = 1; i <= 2; i++)
        {
            p1 = p;
            cout << p->data << endl;
            if (p->next != NULL)
            {
                p = p->next;
                free(p1);
                num = num - 1;
            }
            else
            {
                free(p1);
                num = num - 1;
                break;
            }
        }
        p1 = p;
        if (p->next == NULL)
        {
            cout << p->data << endl;
            free(p);
            num = num - 1;
        }
        else
        {
            rear->next = p;
            p1 = p1->next;
            p->next = NULL;
            rear = p;
            p = p1;
        }
    }
}
int main()
{
    int choose;
    ElemType e;
    menu();
    QueueList* front, * rear, * p;
    front = rear = p = InitQueue();
    while (1)
    {
        cout << "请选择" << endl;
        cin >> choose;
        switch (choose)
        {
        case 1:
        {
            cout << "输入要插入的数据" << endl;
            cin >> e;
            rear = EndQueue(rear, e);
            break;
        }
        case 2:
        {
            rear = DeQueue(front, rear);
            break; 
        }
        case 3:
        {
            GetHead(front);
            break;
        }
        case 4:
        {
            ShowQueue(front);
            break;
        }
        case 5:
        {
             LeaveQueue(front,rear);
             break;
        }
        case 0:
        {
            cout << "退出" << endl;
            exit(0);
        }
        default:
            break;
        }
    }
}

4:运行结果

  可以发现,我输入了10个数据之后,选择5功能后,队列内的数据按照1,2出列,3插到最后的要求实现了。这也就是队列的排队。

总结

  只能说早期的鸟儿有虫吃,昨天写了一个晚上没把5功能实现,结果今天写了半小时写出来了T-T

相关文章
|
存储 C++
C/C++顺序与链式队列详解(附代码)(一)
C/C++顺序与链式队列详解(附代码)
710 0
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
编译器 C++ 容器
【c++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
738 12
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
410 16
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
435 0
|
存储 编译器 程序员
c++的类(附含explicit关键字,友元,内部类)
本文介绍了C++中类的核心概念与用法,涵盖封装、继承、多态三大特性。重点讲解了类的定义(`class`与`struct`)、访问限定符(`private`、`public`、`protected`)、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数(构造函数、析构函数、拷贝构造、赋值重载)以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员(变量与函数)、友元(友元函数与友元类)的概念及其使用场景,并简要介绍了内部类的特性。
642 0
|
安全 C++
【c++】继承(继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员)
本文深入探讨了C++中的继承机制,作为面向对象编程(OOP)的核心特性之一。继承通过允许派生类扩展基类的属性和方法,极大促进了代码复用,增强了代码的可维护性和可扩展性。文章详细介绍了继承的基本概念、定义格式、继承方式(public、protected、private)、赋值兼容转换、作用域问题、默认成员函数规则、继承与友元、静态成员、多继承及菱形继承问题,并对比了继承与组合的优缺点。最后总结指出,虽然继承提高了代码灵活性和复用率,但也带来了耦合度高的问题,建议在“has-a”和“is-a”关系同时存在时优先使用组合。
1191 6
|
编译器 C++
类和对象(中 )C++
本文详细讲解了C++中的默认成员函数,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载和取地址运算符重载等内容。重点分析了各函数的特点、使用场景及相互关系,如构造函数的主要任务是初始化对象,而非创建空间;析构函数用于清理资源;拷贝构造与赋值运算符的区别在于前者用于创建新对象,后者用于已存在的对象赋值。同时,文章还探讨了运算符重载的规则及其应用场景,并通过实例加深理解。最后强调,若类中存在资源管理,需显式定义拷贝构造和赋值运算符以避免浅拷贝问题。
|
存储 编译器 C++
类和对象(上)(C++)
本篇内容主要讲解了C++中类的相关知识,包括类的定义、实例化及this指针的作用。详细说明了类的定义格式、成员函数默认为inline、访问限定符(public、protected、private)的使用规则,以及class与struct的区别。同时分析了类实例化的概念,对象大小的计算规则和内存对齐原则。最后介绍了this指针的工作机制,解释了成员函数如何通过隐含的this指针区分不同对象的数据。这些知识点帮助我们更好地理解C++中类的封装性和对象的实现原理。