当前位置: 首页 > news >正文

C++(17)——list的模拟实现

前面的文章中,介绍了stringvector的模拟实现,本篇文章将介绍对于list的模拟实现。

目录

1. list的基本结构:

2. list功能实现:尾部插入元素:

3. list迭代器的实现:

4. list功能实现:在任意位置前插入元素: 

4.1 函数实现方法:

4.2 函数运行逻辑:

5. list功能实现:删除任意位置的结点:

6. 拷贝构造与赋值重载:

7. list功能实现:clear与析构函数:


1. list的基本结构:

对于list,可以将其看作数据结构中的双向带头循环链表一起学数据结构(4)——带头结点的双向循环链表_带头结点的双循环链表-CSDN博客

针对于双向带头循环链表,其基本构成单元为如下图所示:

其中,prev用来保存上一个结点的地址,next用于保存下一个结点的地址,data用于保存数据。对于上述结构单元,可以由下方的代码表示:

namespace violent
{template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _next;T _data;};
}

对于双向带头循环链表,其结构可以由下图表示:

其中,链表的第一个结点称为哨兵位头结点,此结点的data不用于存储数据,只是利用prev,next建立其他结点的关系。因此,在编写针对于链表单元结构的构造函数时,需要考虑到哨兵位头结点。本文将采用隐式类型转换的方式,来完成对于构造函数的编写:

template<class T>struct ListNode{ListNode(const T& x = T()): _prev(nullptr), _next(nullptr), _data(x){}ListNode<T>* _prev;ListNode<T>* _next;T _data;};

对于一个带头双向循环链表结构的实现,可以看作是若干个结构单元的相互链接,因此在初始化链表结构时,只需要在构造函数中,完成对于哨兵位头结点的建立,以及其内部指针的指向即可,即:

具体的实现方法,就是再创建一个类,名为list的类,将上述表示单个结点结构的类作为一种类型引入到list,即:

template<class T>class list{typedef ListNode<T>  Node;Node* _node;};

通过上述给出的图片,可以得到下面的构造函数:

class list{typedef ListNode<T>  Node;public:list(){_phead = new Node;_phead->_next = _phead;_phead->_prev = _phead;}Node* _phead;};

2. list功能实现:尾部插入元素:

在插入一个元素之前,首先需要创建一个新的结构单元用于保存这个元素,例如需要插入的元素为x,需要提前创建一个名为newnode的结点用于存储该元素,即:

Node* newnode = new Node(x);

newnode进行插入时,即:

第一步,首先获取链表最后一个结点的地址,这里命名为tail,通过上图不难得出taii=phead->prev.

第二步,建立newnodetail的联系,即:tail->next=newnode,newnode->prev=tail,对于此关系的图片表示是如下:

 最后一步:建立pheadnewnode的联系,即phead->prev=newnode,newnode->next=phead

代码实现如下:

void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _phead->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _phead;_phead->_prev = newnode;}

3. list迭代器的实现:

       在vecotr,string中,由于这两种数据结构的空间是连续的,因此,在实现其迭代器功能时,通常先利用typedef对指针进行更名,使用时直接++即可。

      但是对于list,前面说到list的结构可以近似的看为链表,由于链表的空间不连续,因此,在使用迭代器进行访问时,对迭代器++不能达成访问空间中下一个结点的目的。对于list来说,正确访问下一个结点的访问为通过本结点的next获取下一个结点的地址。因此,可以考虑使用运算符重载,将++的运行逻辑从指向连续空间的下一个地址改为通过本结点的next访问下一个结点。

     但是,运算符重载只能针对于自定义类型,因为迭代器的实现是依托于指针来完成的。虽然在前面利用创建自定义类型的方式创建了链表中单个结点结构的对象,但是,需要注意,此处运算符重载进行重载的目标并不是ListNode这个自定义类型,而是这个类型的指针,而指针是一个内置类型,因此,不能直接完成对于指针的重载。而是再创建一个自定义类型用于封装指针,在内部进行运算符重载。

    对于封装方法:首先需要将表示单个结点结构的自定义类型引入到新的类中,此处将这个类命名为__list_iterator。为了方便使用,将表示单个结点结构的类重命名为Node,成员变量为类型为Node的指针。即:

template<class T>struct __list_iterator{typedef ListNode<T> Node;Node* _node;};

对于上述类的初始化如下:

template<class T>struct __list_iterator{typedef ListNode<T> Node;__list_iterator(Node* node): _node(node){}Node* _node;};

为了正常的使用迭代器来完成对于list的打印,不但需要对于++,还需要对于*!=进行重载,代码如下:

template<class T>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T> self;__list_iterator(Node* node): _node(node){}self& operator++(){_node = _node->_next;return *this;}self& operator++(int){self tmp(_node);_node = _node->next;return tmp;}T& operator*(){return _node->_data;}bool operator!=(const self& s){return _node != s._node;}Node* _node;};

       在完成上述步骤后,向list中引入__list_iterator,再添加end,begin两个函数用于表示链表的起始和结束。

       需要注意的是,在定义链表的起始时,并不能定义成哨兵位头结点,因为哨兵位头结点并没有保存数据,在访问链表时,需要从第一个保存数据的结点开始访问。而对于尾结点,由于链表是双向循环的。因此,可以将不存储任意数据的哨兵位头结点看作尾结点,代码如下:

typedef __list_iterator<T> iterator;iterator begin(){return _phead->_next;}iterator end(){return _phead;}

在完成了上述步骤后,就可以使用迭代器对于list进行正常的访问,例如:

void test1(){list<int> It;It.push_back(1);It.push_back(2);It.push_back(3);It.push_back(4);list<int>::iterator it1 = It.begin();while (it1 != It.end()){cout << *it1 << ' ';++it1;}}

代码运行结果如下:

4. list功能实现:在任意位置前插入元素: 

4.1 函数实现方法:

与尾部插入元素的大致思路相同,首先需要创建一个结点来存储这个元素:

Node* newnode = new Node(x);

例如,需要在pos位置之前插入这个结点,首先需要获取pos位置的前一个结点的地址prev。但是,pos只是类型为iterator的一个对象,需要先创建一个变量cur,来存储pos中成员变量node,也就是这个结点的地址,通过cur来获取pos位置前一个结点的坐标,即:

Node* cur = pos._node;
Node* prev = cur->_prev;

在对 prev,newnode,cur这三个位置所代表的结点进行连接,即:

void insert(iterator pos,const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}

利用下方的代码对于insert函数功能进行测试,即:

It.insert(It.begin(), 5);It.insert(It.begin(), 6);It.insert(It.begin(), 7);It.insert(It.begin(), 8);for (auto e : It){cout << e << ' ';}

运行结果如下:

4.2 函数运行逻辑:

为了更清晰的了解insert的动作逻辑,下面给出函数的整体运行步骤,例如对于下方的代码:

It.insert(It.begin(), 5);

函数运行的第一步为首先通过begin()函数获取地址:

在返回时,由于函数的返回类型为自定义类型iterator,因此在返回前会去调用__list_insertiterator中的构造函数,来构造一个临时变量作为返回值,即:

再获取返回值后,跳转到insert函数中,即:

 最后根据insert中编写好的代码的顺序进行运行。

在完成了对于insert函数的编写后,对于push_back函数可以复用insert,从而简化push_back,即:

void push_back(const T& x){insert(_phead, x);}

同理也可以实现头部插入任意元素push_front,即:

void push_front(const T& x){insert(_phead->_next, x);}

5. list功能实现:删除任意位置的结点:

在删除任意位置的结点前,首先需要找到这个结点的前结点和后结点的地址,为了方便表达,用prev表示前结点的地址,用next表示后结点的地址。代码如下:

iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return next;}

在完成了对于erase的编写后,可以通过复用erase来完成对于头部删除pop_front和尾部删除pop_back,代码如下:

void pop_back(){erase(_phead->_prev);}void pop_front(){erase(_phead->_next);}

利用下方代码对上述的函数进行测试:
 

It.pop_back();It.pop_back();It.pop_front();It.pop_front();for (auto e : It){cout << e << ' ';}

运行结果如下:

6. 拷贝构造与赋值重载:

list(const list<T>& s){empty();for (auto e : s){push_back(e);}}void swap(list<T>& s){std::swap(_phead, s._phead);}list<T>& operator=(list<T> s){swap(s);return *this;}

7. list功能实现:clear与析构函数:

对于clear函数,其功能是用于清理空间中的所有内容,即所有开辟的结点,但是不包括哨兵位头结点。

对于析构函数,则是在clear函数的基础上,将哨兵位头结点也进行处理。

二者对应代码如下:

void clear(){iterator i2 = begin();while (i2 != end()){i2 = erase(i2);}}~list(){clear();delete _phead;phead = nullptr;}


 

相关文章:

C++(17)——list的模拟实现

前面的文章中&#xff0c;介绍了&#xff0c;的模拟实现&#xff0c;本篇文章将介绍对于的模拟实现。 目录 1. list的基本结构&#xff1a; 2. list功能实现&#xff1a;尾部插入元素&#xff1a; 3. list迭代器的实现&#xff1a; 4. list功能实现&#xff1a;在任意位置前…...

花瓣网美女图片爬取

爬虫基础案例01 花瓣网美女图片 网站url&#xff1a;https://huaban.com 图片爬取 import requests import json import os res requests.get(url "https://api.huaban.com/search/file?text%E7%BE%8E%E5%A5%B3&sortall&limit40&page1&positionsear…...

Android native层c++调用java层API

在Android开发中&#xff0c;从本地&#xff08;native&#xff09;代码调用Java层的接口是一个常见的需求&#xff0c;尤其是在使用JNI&#xff08;Java Native Interface&#xff09;进行混合编程时。以下是一个基本的步骤指南&#xff0c;展示如何从C代码调用Java方法&#…...

Docker 集群配置

1、配置 MySQL MySQL 简单安装 docker安装完MySQL并run出容器后&#xff0c;建议请先修改完字符集编码后再新建mysql库-表-插数据 docker run -d -p 2222:3306 --privilegedtrue -e MYSQL_ROOT_PASSWORD123456 \ -v /opt/mysql/log:/var/log/mysql \ -v /opt/mysql/data:/va…...

VUE3+elementPlus 之 Form表单校验器 之 字符长度校验

需求&#xff1a;校验字符长度&#xff0c;超过后仍可输入&#xff0c;error提示录入字符数与限制字符数 校验字符长度&#xff1a; /*** 检验文字输入区的长度* param {*} rule 输入框的rule 对象&#xff0c;field&#xff1a;字段名称* param {*} value …...

【Mysql】数据库架构学习合集

目录 1. Mysql整体架构1-1. 连接层1-2. 服务层1-3. 存储引擎层1-4. 文件系统层 2. 一条sql语句的执行过程2-1. 数据库连接池的作用2-2. 查询sql的执行过程2-1. 写sql的执行过程 1. Mysql整体架构 客户端&#xff1a; 由各种语言编写的程序&#xff0c;负责与Mysql服务端进行网…...

轻型民用无人机驾驶航空器安全操控——理论考试多旋翼部分笔记

今天已经可以在线考取轻型民用无人机驾驶航空器执照了&#xff0c;所以我也在在线观看完视频之后整理了如下的知识点&#xff0c;所有知识点全部来自UOM平台。 目录 航空器知识 &#xff08;1&#xff09;多旋翼民用无人驾驶航空器螺旋桨的作用 &#xff08;2&#x…...

UE4学习笔记 FPS游戏制作3 添加武器

文章目录 章节目标为骨骼添加武器挂载点添加武器 章节目标 本章节为手部添加一个武器挂载点&#xff0c;并挂载一个武器 为骨骼添加武器挂载点 添加挂载点需要以一个动画片段为基础&#xff0c;为骨骼添加挂载点。 首先找到我们需要的动画片段&#xff0c;通常是idle 双击打…...

详解 Prim 算法的实现

一、算法思路 Prim 算法是用来求最小生成树的&#xff0c;它的思想也有点类似于贪心——逐个将离当前集合最近的点加入到集合中&#xff0c;直至发现图不连通或所有点都被加到集合中&#xff0c;算法即宣告终止。它的具体做法是&#xff1a; step 1&#xff1a;初始时&#xf…...

Android 使用高德地图

一、获取高德平台key 【1】基于application包名&sha1值在高德控制台获取key值&#xff0c;详情参考&#xff1a; 获取Key-创建工程-开发指南-Android 地图SDK | 高德地图API 【2】在manifest中声明权限 【3】将拿到的key值在manifest中进行声明 <!--允许程序打开网络…...

从redis setnx 来看看分布式锁

什么是分布式锁 分布式锁&#xff08;多服务共享锁&#xff09;在分布式的部署环境下&#xff0c;通过锁机制来让多客户端互斥的对共享资源进行访问/操作。 为什么需要分布式锁 在单体应用服务里&#xff0c;不同的客户端操作同一个资源&#xff0c;我们可以通过操作系统提供…...

校园网网络规划与设计——计算机网络实践报告

W...Y的主页 &#x1f60a; 代码仓库分享&#x1f495; 目录 一、设计目的 二、软硬件环境 三、理论基础 四、设计方案 五、网络配置步骤 六、设计过程中出现的问题及相应解决办法 八、参考资料 一、设计目的 深入理解网络工程的三层层次设计模型&#xff1b; 掌握网络…...

Qt QScrollArea 不显示滚动条 不滚动

使用QScrollArea时&#xff0c;发现添加的控件超出QScrollArea 并没有显示&#xff0c;且没有滚动条效果 原因是 scrollArea指的是scrollArea控件本身的大小&#xff0c;肉眼能看到的外形尺寸。 scrollAreaWidgetContents指的是scrollArea控件内部的显示区域&#xff0c;里面可…...

【SVN在Linux下的常用指令】

windows下的TortoiseSVN是资源管理器的一个插件&#xff0c;以覆盖图标表示文件状态&#xff0c;几乎所以命令都有图形界面支持&#xff0c;比较好用&#xff0c;这里就不多说。主要说说linux下svn的使用&#xff0c;因为linux下大部分的操作都是通过命令行来进行&#xff0c;所…...

2024 高级前端面试题之 Node 「精选篇」

该内容主要整理关于 Node 模块的相关面试题&#xff0c;其他内容面试题请移步至 「最新最全的前端面试题集锦」 查看。 Node模块精选篇 1. package.json版本号规则2. package.json 与 package-lock.json 的关3. npm 模块安装机制4. 模块化的差异 AMD CMD COMMONJS ESMODUL5. No…...

linux麒麟系统安装mongodb7.0

1.mogedb下载 下载的是他tar包 https://fastdl.mongodb.org/linux/mongodb-linux-x86_64-rhel80-7.0.5.tgz wget -o https://fastdl.mongodb.org/linux/mongodb-linux-x86_64-rhel80-7.0.5.tgz 也可以下载rpm包 2.将包上传至服务器并解压 #进入目录 并解压 cd /opt/ tar…...

Spring声明式事务

1.概念 事务就是用户定义的一系列执行SQL语句的操作, 这些操作要么完全地执行&#xff0c;要么完全地都不执行&#xff0c; 它是一个不可分割的工作执行单元 一个使用Mybatis-Spring的主要原因是它允许Mybatis参与到Spring的事务管理中&#xff0c;而不是给Mybatis创建一个新的…...

PyTorch深度学习实战(34)——Pix2Pix详解与实现

PyTorch深度学习实战&#xff08;34&#xff09;——Pix2Pix详解与实现 0. 前言1. 模型与数据集1.1 Pix2Pix 基本原理1.2 数据集分析1.3 模型构建策略 2. 实现 Pix2Pix 生成图像小结系列链接 0. 前言 Pix2Pix 是基于生成对抗网络 (Convolutional Generative Adversarial Netwo…...

第96讲:MySQL高可用集群MHA的核心概念以及集群搭建

文章目录 1.MHA高可用数据库集群的核心概念1.1.主从复制架构的演变1.2.MHA简介以及架构1.3.MHA的软件结构1.4.MHA Manager组件的启动过程1.5.MHA高可用集群的原理 2.搭建MHA高可用数据库集群2.1.环境架构简介2.2.搭建基于GTID的主从复制集群2.2.1.在三台服务器中分别搭建MySQL实…...

外星人入侵(python)

前言 代码来源《python编程从入门到实践》Eric Matthes 署 袁国忠 译 使用软件&#xff1a;PyCharm Community Editor 2022 目的&#xff1a;记录一下按照书上敲的代码 alien_invasion.py 游戏的一些初始化设置&#xff0c;调用已经封装好的函数方法&#xff0c;一个函数的…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...