链表的实现(C++版)

对于链表的学习,之前在C语言部分的时候就已经有学习过,也学会了使用C语言来打造一个链表.如今学了C++ 则想通过C++来打造一个链表,以达到锻炼自己的目的.

1.链表的初步实现

1.节点模板的设置

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

这边使用一个模板来定义这个节点,因为我们传进来的数据可能是任意类型的,为了方便数据的传参,我们直接使用template <class T>来写一个万能的模板.除了next指针和prve指针和data以外,我们还得写一个构造函数,这边的构造函数的初始化就是把_next金额_prve初始化成一个空指针,然后_data来根据传入的参数来做决定. 传入的参数为 const T&x = T() 这里用的是传引用传参,然后如果有x的话,就用x来初始化,如果没有x的话,后面带着的这个T()就可以对其调用默认的构造函数了. 如果不给T()的话,就得自己在传递一个参数.

2.链表模板的设置

	template <class T>class list{typedef ListNode<T> Node;public:list(){_head = new Node;_head->_next = _head;_head->_prve = _head;_head->data = 0;}void push_back(const T& x){Node* newnode = new Node(x);Node* Tail = _head->_prve;Tail->_next = newnode;newnode->_prve = Tail;newnode->_next = _head; _head->_prve = newnode;}private:Node* _head;};

这里也没什么好说的,生成了一个带头链表,尾插就是一个链表的基本操作.

此时我们想打印出来看看,该怎么做?

想到用迭代器来进行打印,但是,由于我们是自己实现链表,因此又重新开了个命名空间,因此,iterator, !=, *, ++等符号我们都是用不了的,这些我们都得自己来进行运算符重载.因此,实现C++ 的链表,难的不是链表本身,而是实现链表的迭代器,这是一个麻烦的过程.

3.迭代器的模拟

对于迭代器,他有一个好处,就是不管你的数据底层是一个什么样子的数据,他都可以对你进行访问.这可能让我们会联想到指针,对于指针来说,数据的原生指针就是一个天然的迭代器,但是,这是建立在一个你的数据的物理空间是连续的情况下的基础的,链表都是随机生成的节点地址,他在物理空间上是不连续的.

因此我们想要模拟一个迭代器的行为,首先定义一个迭代器的类

我们 可以看到, ListIerator这个迭代器,就是一个单参数的构造函数.

1.重载运算符++

我们想要的是这个迭代器++之后会指向下一个节点,而由于在链表中,直接++是无法让当前的迭代器指向下一个节点的,因此我们需要对其进行重载一下.

		//前置++iterator& operator++(){_node = _node->_next;return *this;}//后置++iterator operator++(int){iterator tmp(*this);_node = _node->_next;return tmp;}

在这里,我们把ListIterator类重定义成了iterator,在重载运算符中,由于我们返回的数据是有类型的,而这个*this指针的类型则是当前的ListIterator也就是iterator,因此,在这里我们要把重载函数的类型写成iterator.

而在重载后置++的时候,由于我们需要的是返回++之前的值,因此,我们需要另一个迭代器来获取返回之前的数据,得完成一个拷贝构造,因此这边重载后置++的时候就需要浅拷贝,因而不用加&.

2.重载运算符--

		//前置--iterator& operator--(){_node = _node->_prve;return *this;}//后置--iterator operator--(int){iterator tmp(*this);_node = _node->_prve;return tmp;}

这个跟重载++是类似的.

3.begin()函数和end()函数

		iterator begin(){//iterator it(_head->next);//return it;//return _head->next; (这个便是隐式类型转换)return iterator(_head->_next);}iterator end(){//iterator it(_head);//return it;//return _head; (这个也是隐式类型转换)return iterator(_head);}

这边的begin函数和end函数都是为了获取当前位置的迭代器,因此就使用了迭代器类型来进行返回当前的节点.

最后,我们还需要重载一下!=号和==号

		bool operator!=(const iterator& it){return _node != it._node;}bool operator==(const iterator& it){return _node == it._node;}

目前,当前的这个链表,就可以进行使用啦~

接下来就是对这个链表进行完善了.

4.insert函数的实现

		void insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);//prve newnode cur nextNode* prve = cur->_prve;prve->_next = newnode;newnode->_prve = prve;newnode->_next = cur;cur->_prve = newnode;}

这些已经没什么好说的了,跟之前用C语言实现的链表的基本逻辑是一样的.

而当我们实现了insert函数的时候,就可以让他在push_back和push_front来复用.

		void push_back(const T& x){/*Node* newnode = new Node(x);Node* Tail = _head->_prve;Tail->_next = newnode;newnode->_prve = Tail;newnode->_next = _head;_head->_prve = newnode;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());//删除最后一个节点}void pop_fornt(){erase(begin());}

5.erase函数的实现

		void erase(iterator pos){Node* cur = pos._node;Node* prve = cur->_prve;Node* next = cur->_next;//prve cur nextprve->_next = next;next->_prve = prve;delete cur;}

这里需要注意的一个地方就是当我们释放了cur节点的时候,cur所指向的pos就也会被释放掉了,然后当前的pos就造成一个迭代器失效的问题,因此,我们需要返回pos节点的下一个节点.

		iterator erase(iterator pos){Node* cur = pos._node;Node* prve = cur->_prve;Node* next = cur->_next;//prve cur nextprve->_next = next;next->_prve = prve;delete cur;return iterator(next);}

2.链表继续优化

1.重载->

以上的仅仅只是支持用来插入int,float,double等数据.

而当我们遇到一个结构体类型的数据,如果继续使用以上的方法是会报错的.


 

如果想直接来读取数据,只能是用这种方法.

这里就是it来调用operator*,然后返回的就是 A 由于 A里面不止是有一个数据,因此还需要进行一次解引用,来读取_a1 或者 _a2

但是这种方法相对来说是非常不方便的.

因此,我们则可以对->来进行重载.

T* operator->()
{return &_node->_data;
}

这个写法乍一看是比较诡异的,但自己推敲之后,发现还是比较好理解的,

首先,我们上面的那种写法,是先把迭代器it解引用一遍,然后再通过 . 来进行解引用第二遍来获取里面的数据,而这里重载的->,则是直接返回的就是 A*(T*) , 然后 A*就会自己来解引用,进而就会得到里面的数据.

修改之后的遍历是这样的,

而其中的又是编译器简化了,我们可以拆开看看

这两种写法是一样的,上面的那种就是it先调用->重载,然后再解引用,而下面这种是直接省略了,编译器帮我们做了,是为更加简便的方法.

2.模板的传引用和传指针

目前我们的模板仅仅是能返回不是const的数据,当我们有需求来返回const的数据时,我们能想到的是把这个类再复制一边,然后加个const来修饰,但是这样是过于麻烦的.

当除了类型,其它的内容都一样的时候,我们就可以考虑使用模板来更好的传递数据.

	template <class T , class Ref , class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T> iterator;Node* _node;ListIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//前置++iterator& operator++(){_node = _node->_next;return *this;}//后置++iterator operator++(int){iterator tmp(*this);_node = _node->_next;return tmp;}//前置--iterator& operator--(){_node = _node->_prve;return *this;}//后置--iterator operator--(int){iterator tmp(*this);_node = _node->_prve;return tmp;}bool operator!=(const iterator& it){return _node != it._node;}bool operator==(const iterator& it){return _node == it._node;}};

可以看到,我在声明模板的时候,新加入了两个类名,一个是Ref , 一个是Ptr,代表着传引用和传指针,然后写道对应的函数上.

而在list里面, 我们可以这样做

一个是传T , 然后是T& , 然后是 T* ,这样就可以使得可以根据所需来返回我们需要的数据了.

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/388286.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

k8s学习--使用kubepshere部署devops项目时遇到的报错(无法找到gitee仓库)

今天在kubesphere部署devops项目&#xff0c;编辑流水线的时候&#xff0c;发现怎么也访问不到gitee仓库 报错的流水线位置 报错日志 报错原因 变量问题 因为看见了csy/sangomall&#xff0c;所以理所当然的把路径变量GITEE_ACCOUNT写成了用户名 解决方法 结果发现仓库…

可靠的图纸加密软件,七款图纸加密软件推荐

大家好啊,我是小固,今天跟大家聊聊图纸加密软件。 作为一名设计师,我深知保护自己的知识产权有多重要。曾经就因为图纸泄露,差点血本无归,那个教训可真是惨痛啊!所以我今天就给大家推荐几款靠谱的图纸加密软件,希望能帮到你们。 固信软件https://www.gooxion.com/ 首先要隆重…

Java语言程序设计——篇十一(1)

&#x1f33f;&#x1f33f;&#x1f33f;跟随博主脚步&#xff0c;从这里开始→博主主页&#x1f33f;&#x1f33f;&#x1f33f; 欢迎大家&#xff1a;这里是CSDN&#xff0c;我的学习笔记、总结知识的地方&#xff0c;喜欢的话请三连&#xff0c;有问题可以私信&#x1f33…

Vue 的安装与配置

今天是八月一日&#xff0c;我也开启了Vue的学习&#xff0c;希望和大家一起学编程&#xff0c;相互督促&#xff0c;相互进步&#xff01; 安装vscode 安装Node.js 官网&#xff1a;https://nodejs.org/zh-cn 下载完正常安装就行 可以winr输入cmd&#xff0c;也可以vscod…

springboot智能健康管理平台-计算机毕业设计源码57256

摘要 在当今社会&#xff0c;人们越来越重视健康饮食和健康管理。借助SpringBoot框架和MySQL数据库的支持&#xff0c;开发智能健康管理平台成为可能。该平台结合了小程序技术的便利性和SpringBoot框架的快速开发能力&#xff0c;为用户提供了便捷的健康管理解决方案。 通过智能…

【多线程】单例模式

&#x1f3c0;&#x1f3c0;&#x1f3c0;来都来了&#xff0c;不妨点个关注&#xff01; &#x1f3a7;&#x1f3a7;&#x1f3a7;博客主页&#xff1a;欢迎各位大佬! 文章目录 1. 什么是单例模式1.1 理解单例模式1.2 单例模式的特点 2. 饿汉模式3. 懒汉模式3.1 单线程下的懒…

中国人民解放军建军97周年

缅怀先烈&#xff0c;砥砺前行 付吾辈之韶华&#xff0c;耀吾辈之中华! 万里河山&#xff0c;有您心安!

Django REST Framework(十五)路由Routes

如何在Django REST framework中利用SimpleRouter和DefaultRouter来高效生成视图集的路由信息,并详细解释如何使用action装饰器为视图集中的自定义方法生成路由 1.路由的定义规则 路由称为URL(Uniform Resource Locator,统一资源定位符),也可以称为URLconf,是对可以从互联…

【Java题解】杨辉三角—力扣

&#x1f389;欢迎大家收看&#xff0c;请多多支持&#x1f339; &#x1f970;关注小哇&#xff0c;和我一起成长&#x1f680;个人主页&#x1f680; ⭐目前主更 专栏Java ⭐数据结构 ⭐已更专栏有C语言、计算机网络⭐ 题目链接&#xff1a;杨辉三角 目录&#x1f451; ⭐题…

the request was rejected because no multipart boundary was found

文章目录 1. 需求描述2. 报错信息3. 探索过程1. 使用postman 排除后端错误2. 搜索网上的解决方法3. 解决方法 1. 需求描述 想要在前端上传一个PDF 发票&#xff0c;经过后端解析PDF之后&#xff0c;将想要的值自动回填到对应的输入框中 2. 报错信息 org.apache.tomcat.util.…

2024年有哪些开放式耳机值得入手?值得关注的开放式耳机评测大赏

如今&#xff0c;开放式耳机越来越受到人们的关注。2024 年更是涌现出了众多优秀的开放式耳机产品。但在众多选择面前&#xff0c;哪一款耳机的音质更出色&#xff1f;哪一款佩戴起来更舒适&#xff1f;又有哪一款在通话质量和连接性能上表现更优异呢&#xff1f;接下来我将详细…

【Devops】CertD 完全免费、自动申请、自动部署SSL证书一站式管理工具 | 自动化HTTPS | 3个月SSL自动轮换

CertD CertD 是一个免费全自动申请和自动部署更新SSL证书的工具。 后缀D取自linux守护进程的命名风格&#xff0c;意为证书守护进程。 关键字&#xff1a;证书自动申请、证书自动更新、证书自动续期、证书自动续签 一、特性 本项目不仅支持证书申请过程自动化&#xff0c;还…

SpringMVC源码解析(二):请求执行流程

SpringMVC源码系列文章 SpringMVC源码解析(一)&#xff1a;web容器启动流程 SpringMVC源码解析(二)&#xff1a;请求执行流程 目录 前言DispatcherServlet入口一、获取HandlerExcutionChain(包括Handler)1、获取Handler1.1、通过request获取查找路径1.2、通过查找路径获取Han…

找工作很迷茫?程序员的岗位宝典来了!

随着数字化转型进展深入&#xff0c;大量数字化、智能化的岗位相继涌现。 但即使这样&#xff0c;大家依然认为&#xff0c;找到一份合适的工作实在是太&#xff01;难&#xff01;了&#xff01; 调查显示&#xff0c;技术创新和商业模式正在成为助推企业发展的两大动力。同时…

【iOS】——锁

五类锁 锁作为一种非强制的机制&#xff0c;被用来保证线程安全。每一个线程在访问数据或者资源前&#xff0c;要先获取&#xff08;Acquire&#xff09;锁&#xff0c;并在访问结束之后释放&#xff08;Release&#xff09;锁。如果锁已经被占用&#xff0c;其它试图获取锁的…

计算机网络必会面经

1.键入网址到网页显示&#xff0c;期间发生了什么 2.在TCP/IP网络模型中。TCP将数据进行分段后&#xff0c;为什么还需要IP层继续分片 3.详细说明tcp三次握手&#xff0c;为什么是三次&#xff0c;若每次握手丢了&#xff0c;解决办法是什么 4.详细说明tcp四次挥手&#xff…

【Python】python基础

本篇文章将讲解以下知识点&#xff1a; &#xff08;1&#xff09;循环语句 &#xff08;2&#xff09;字符串格式化 &#xff08;3&#xff09;运算符 一&#xff1a;循环语句 循环语句有两种&#xff1a;while for 本篇文章只讲解while循环 格式&#xff1a; whil…

Unity材质球自动遍历所需贴图

Unity材质球自动遍历所需贴图 文章目录 Unity材质球自动遍历所需贴图一、原理二、用法1.代码&#xff1a;2.使用方法 一、原理 例如一个材质球名为&#xff1a;Decal_Text_Cranes_01_Mat &#xff0c; 然后从全局遍历出&#xff1a;Decal_Text_Cranes_01_Albedo赋值给材质球的…

【网络基础】初识网络 {计算机网络背景;网络协议初识;网络传输基本流程;网络中的地址管理;网络设备简单介绍}

一、计算机网络背景 1.1 网络发展 计算机网络的发展可以追溯到20世纪60年代&#xff0c;那时候最初的计算机网络只是为了让科学家们能够共享计算机资源和数据。但是在20世纪80年代&#xff0c;互联网的出现彻底改变了计算机网络的面貌&#xff0c;使得人们可以随时随地通过互…

AI剪辑短视频以及账号管理矩阵工具系统搭建开发

目录 前言 一、系统有哪些功能&#xff1f; 二、怎么开发 前言 通过AI剪辑短视频以及生成短视频&#xff0c;以及对自媒体账号的管理功能的功能进行开发。这款系统能够批量混合剪辑视频然后一键发布到绑定好的自媒体账号里面。 一、系统有哪些功能&#xff1f; 1.AI智能文…