使用C++实现单链表的操作与实践

2025-02-10 16:50

本文主要是介绍使用C++实现单链表的操作与实践,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

《使用C++实现单链表的操作与实践》在程序设计中,链表是一种常见的数据结构,特别是在动态数据管理、频繁插入和删除元素的场景中,链表相比于数组,具有更高的灵活性和高效性,尤其是在需要频繁修改数据结构的应...

一、单链表的基本概念

单链表是一种由节点组成的线性数据结构,其中每个节点包含数据部分和指向下一个节点的指针。与数组不同,链表的节点在内存中不要求连续存储,而是通过指针连接。因此,链表的插入和删除操作较为灵活,不需要大量的数据移动。

在C++中,我们通过类的封装特性来实现面向对象的链表,这不仅能有效管理链表的内存,还能通过封装实现更易用、更安全的操作。

二、单链表类的设计

我们将通过一个简单的C++类来实现单链表,该类包含基本的链表操作,如插入、删除、打印链表等。

1. 节点的定义

首先,我们定义了一个 Node 结构体来表示链表中的每个节点。每个节点包含一个数据部分 data 和一个指向下一个节点的指针&n编程bsp;next

struct Node {
    int data;      // 数据域
    Node* next;    // 指针域,指向下一个节点
};

2. 链表的类定义

接下来,我们定义 List 类,它包含一个指向链表头部的指针 phead,以及若干成员函数来实现链表的常见操作。

class List {
private:
    Node* phead; // 链表头指针

public:
    // 构造函数
    List() : phead(nullptr) {}

    // 析构函数
    ~List() {
        while (phead != nullptr) {
            PopFront();
        }
    }

    // 创建节点
    Node* CreateNode(int x) {
        Node* node = new Nodandroide;
        node->data = x;
        node->next = nullptr;
        return node;
    }

    // 打印链表
    void PrintList() {
        Node* cur = phead;
        while (cur) {
            cout << cur->data << "-->";
            cur = cur->next;
        }
        cout << "NULL" << endl;
    }

    //eSeNtxKJV 头插法
    void PushFront(int x) {
        Node* newNode = CreateNode(x);
        newNode->next = phead;
        phead = newNode;
    }

    // 尾插法
    void PushBack(int x) {
        Node* newNode = CreateNode(x);
        if (phead == nullptr)
            phead = newNode;
        else {
            Node* tail = phead;
            while (tail->next != nullptr) {
                tail = tail->next;
            }
            tail->next = newNode;
        }
    }

    // 头删
    void PopFront() {
        if (phead == nullptr)
            cout << "链表为空,无法进行删除操作!" << endl;
        else {
            Node* del = phead;
            phead = del->next;
            delete del;
            del = nullptr;
        }
    }

    // 尾删
    void PopBack() {
        if (phead == nullptr)
            cout << "链表为空,无法进行删除操作!" << endl;
        else {
            if (phead->next == nullptr) {
                delete phead;
                phead = nullptr;
            } else {
                Node* tail = phead;
                while (tail->next->next != nullptr) {
                    tail = tail->next;
                }
                delhttp://www.chinasem.cnete tail->next;
                tail->next = nullptr;
            }
        }
    }
};

三、单链表的操作实现

  • PushFront: 在链表的头部插入新节点。
  • PushBack: 在链表的尾部插入新节点。
  • PopFront: 删除链表的头节点。
  • PopBack: 删除链表的尾节点。
  • PrintList: 打印链表中的所有节点。

四、测试与演示

下面的 main 函数展示了如何使用上述链表类实现基本操作:

int main() {
    List ls1;  // 创建一个链表对象

    // 进行一些操作
    ls1.PushBack(1);
    ls1.PushBack(2);
    ls1.PushBack(3);
    ls1.PushBack(4);
    ls1.PushBack(5);

    // 打印链表
    ls1.PrintList();

    // 头删除和尾删除
    ls1.PopFront();
    ls1.PopBack();

    // 头插操作
    ls1.PushFront(9);

    // 打印链表
    ls1.PrintList();

    return 0;
}

五、链表操作的复杂度

  1. PushFront 和 PopFront:这两个操作的时间复杂度为 O(1),因为它们仅仅操作链表的头节点。
  2. PushBack 和 PopBack:这两个操作的时间复杂度为 O(n),需要遍历整个链表,直到找到尾节点。
  3. PrintList:打印链表的时间复杂度为 O(n),需要遍历所有节点。

六、完整代码

#include<IOStream>
using namespace std;
//节点类型声明
structpython Node
{
    int date;
    Node* next;
};
class List
{
private:
    //成员变量
    Node* phead;
public:
    //成员函数
    List() : phead(nullptr) {}//构造函数
    ~List()//析构函数
    {
        while(phead!=NULL)
        {
            PopFront();
        }
    }
    Node* CreateNode(int x)//创建节点
    {
        Node* node=new Node;
        node->date=x;
        node->next=NULL;
        return node;
    }
    void PrintList()//打印链表
    {
        Node *cur=phead;
        while(cur)
        {
            cout<<cur->date<<"-->";
            cur=cur->next;
        }
        cout<<"NULL"<<endl;
    }
    void PushFront(int x)//头插
    {
        Node*newnode=CreateNode(x);
        newnode->next=phead;
        phead=newnode;
    }
    void PushBack(int x)//尾插
    {
        Node*newnode=CreateNode(x);
        if(phead==NULL)
            phead=newnode;
        else
        {
            Node* tail = phead;
            while (tail->next != NULL)
            {
                tail = tail->next;
            }
            tail->next = newnode;
        }

    }
    void PopFront() //头删
    {
        if (phead==NULL)
            cout<<"链表为空,无法进行删除操作!"<<endl;
        else
        {
            Node* del=phead;
            phead=del->next;
            delete del;
            del=NULL;
        }
    }

    void PopBack()  //尾删
    {
        if (phead== NULL)
            cout<<"链表为空,无法进行删除操作!"<<endl;
       else
        {
           if(phead->next==NULL)
           {
               delete phead;
               phead=NULL;
           }
           else
           {
               Node* tail = phead;
               while (tail->next->next != NULL)
               {
                   tail = tail->next;
               }
               delete tail->next;
               tail->next=NULL;
           }
        }
    }

};
int main()
{
    List ls1;
    ls1.PushBack(1);
    ls1.PushBack(2);
    ls1.PushBack(3);
    ls1.PushBack(4);
    ls1.PushBack(5);
    ls1.PrintList();
    ls1.PopFront();
    ls1.PopBack();
    ls1.PushFront(9);
    ls1.PrintList();
    return 0;
}

七、总结

通过面向对象的方式实现单链表,我们可以更加方便和安全地进行链表操作。封装了节点管理、内存管理以及链表操作函数的类,让链表操作更加直观并且容易维护。在实际开发中,链表结构广泛应用于各种算法和数据管理系统,掌握链表的使用可以帮助我们高效地解决许多动态数据管理的问题。

以上就是使用C++实现单链表的操作与实践的详细内容,更多关于C++实现单链表的资料请关注China编程(www.chinasem.cn)其它相关文章!

这篇关于使用C++实现单链表的操作与实践的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1153377

相关文章

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri

Python常用命令提示符使用方法详解

《Python常用命令提示符使用方法详解》在学习python的过程中,我们需要用到命令提示符(CMD)进行环境的配置,:本文主要介绍Python常用命令提示符使用方法的相关资料,文中通过代码介绍的... 目录一、python环境基础命令【Windows】1、检查Python是否安装2、 查看Python的安

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现:TCMalloc与Jemalloc1. TCM

OpenCV实现实时颜色检测的示例

《OpenCV实现实时颜色检测的示例》本文主要介绍了OpenCV实现实时颜色检测的示例,通过HSV色彩空间转换和色调范围判断实现红黄绿蓝颜色检测,包含视频捕捉、区域标记、颜色分析等功能,具有一定的参考... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间

Python并行处理实战之如何使用ProcessPoolExecutor加速计算

《Python并行处理实战之如何使用ProcessPoolExecutor加速计算》Python提供了多种并行处理的方式,其中concurrent.futures模块的ProcessPoolExecu... 目录简介完整代码示例代码解释1. 导入必要的模块2. 定义处理函数3. 主函数4. 生成数字列表5.

Python中help()和dir()函数的使用

《Python中help()和dir()函数的使用》我们经常需要查看某个对象(如模块、类、函数等)的属性和方法,Python提供了两个内置函数help()和dir(),它们可以帮助我们快速了解代... 目录1. 引言2. help() 函数2.1 作用2.2 使用方法2.3 示例(1) 查看内置函数的帮助(

Linux脚本(shell)的使用方式

《Linux脚本(shell)的使用方式》:本文主要介绍Linux脚本(shell)的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录概述语法详解数学运算表达式Shell变量变量分类环境变量Shell内部变量自定义变量:定义、赋值自定义变量:引用、修改、删

Python实现精准提取 PDF中的文本,表格与图片

《Python实现精准提取PDF中的文本,表格与图片》在实际的系统开发中,处理PDF文件不仅限于读取整页文本,还有提取文档中的表格数据,图片或特定区域的内容,下面我们来看看如何使用Python实... 目录安装 python 库提取 PDF 文本内容:获取整页文本与指定区域内容获取页面上的所有文本内容获取

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一:创建批处理文件并添加到PATH1