c++:数据结构链表list的模拟实现

devtools/2024/9/20 7:12:51/ 标签: 数据结构, c++, 链表, 后端

文章目录

  • 链表的知识回顾
  • 前期工作
  • 构造节点
  • 迭代器
    • 注意
    • 构造迭代器
    • 解引用*迭代器
    • 迭代器->
    • 迭代器++
    • 迭代器- -
    • 判断两个迭代器是否相等
  • 链表
    • empty_init
    • 构造
    • 拷贝构造
    • swap
    • operator=
    • begin和end
    • insert
    • push_back
    • push_front
    • erase
    • pop_back
    • pop_front
    • size
    • empty
    • clear
    • 析构


链表的知识回顾

链表是有一个个节点链接起来的.每一个节点里面存有数据val,下一个节点的地址next,双向循环链表还会有上一个节点的地址.
双向带头循环链表比双向循环链表多了一个头节点.又称哨兵位.在很多时候,多一个头节点能帮我们解决很多事.

在这里插入图片描述

下面模拟实现的就是双向带头循环链表,跟c++容器库list里面一样


前期工作

写一个自己的命名空间,防止跟库里面函数冲突.我们后面所写的函数都在中国命名空间里面.

namespace shh
{
}

构造节点

因为节点里面要存储很多值,所以我们写一个类把它封装起来.
同时,因为节点里面存储的数据val类型不清楚,写一个模板,让编译器自己根据类型去生成.

	//把节点封装成一个类template<class T>struct ListNode{ListNode<T>* prev = nullptr;ListNode<T>* next = nullptr;T val = T();ListNode(const T& tmp = T()):prev(nullptr), next(nullptr), val(tmp){}};

这里写一个构造,为我们后面可以直接用值tmp去生成节点,不用自己写.

迭代器

vector和string里面的迭代器都是原生指针,因为他们存储的物理空间连续.
例如: iterator(int
) ,iterator++ 会跳到下一个数字.iterator可以访问数据.

但是链表没有办法做到这一点.所以,我们将链表节点的指针封装成一个类,然后用上运算符重载,自己控制运算符,就能实现vector中T*的功能.

	template<class T,class Ref,class Ptr>struct list_iterator{typedef ListNode<T> Node;typedef list_iterator<T,Ref,Ptr> iterator;//节点指针Node* _node;};

这个类里面封装的是节点的指针,所以它唯一的成员变量就是Node.*

注意

这里的模板有三个参数,为什么呢?
首先T是节点数据的类型,这个没问题.
但是其他两个呢?

Ref是引用,Ptr是指针.这样子写是为了能生成多种引用T&,和T.*
当我们需要修改这个数据是我们直接传T&.如果我们不允许别人修改数据时,传const T&,让别人只能读.不能修改.
其实还有另一种解决方法,copy这个类,把这个类改成const版本的.但是这样会造成代码冗余.

构造迭代器

		//list_iterator(Node* node):_node(node){}

写了这个,我们就可以传一个节点的指针来构造迭代器

解引用*迭代器

		Ref operator*(){return _node->val;}

Ref是T& / const T&
我们这里要模拟的是vector中T*的功能,解引用取得数据,所以返回节点中的数据

迭代器->

		Ptr operator->(){return &_node->val;}

Ptr是T / const T
我们这里要模拟的是指针中->的功能,所以要传数据T的地址.

在调用上,我们假设有一个类A,里面有两个值a1和a2,我们用这个类来充当节点中的数据val
it->是调用it.operator->(),返回的是一个T.
it.operator->() ->a1 才能取到a1

为了美观,编译器会帮我们减少一个箭头 变成 it->_a1

	struct A{int _a1, _a2;A(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}};void TestList2(){list<A> lt;A a = { 3,3 };lt.push_back(a);lt.push_back(A{2,2});lt.push_back({1,1});list<A>::iterator it = lt.begin();while (it != lt.end()){/*cout << *it << " ";*/cout << it->_a1 << " "<< it->_a2;cout << endl;//it.operator->() ->a1//val* --> T*it++;}cout << endl;}

迭代器++

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

迭代器- -

		//--iiterator& operator--(){_node = _node->prev;return *this;}//i--iterator operator--(int){iterator tmp(_node);_node = _node->prev;return tmp;}

判断两个迭代器是否相等

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

链表

template<class T>class list{public://调用可读可写的迭代器typedef list_iterator<T,T&,T*> iterator;//调用只能读,不能修改的迭代器typedef list_iterator<T, const T&,const T*> const_iterator;typedef ListNode<T> Node;private:Node* _head;size_t _size;};

链表里面有两个成员变量,一个作为头节点,一个计算节点的个数

empty_init

这个函数的功能和构造函数一样,写出来是为了后面进行复用.

		void empty_init(){_head = new Node;_head->next = _head;_head->prev = _head;_size = 0;}

构造

复用empty_init

		list(){empty_init();}

拷贝构造

list T2(T1)
初始化T2,然后把T1的值都塞到后面

		list(const list<T>& T1){empty_init();for (auto& e : T1){push_back(e);}}

swap

T2.swap(T1)
交换两个链表

		void swap(const list<T>& T1){std::swap(_head, T1._haed);std::swap(_size, T1._size);}

operator=

这里运用了一个很巧妙的写法,把传过来的值拷贝构造list T1,然后将T1和*this交换
直接白嫖编译器的成果(拷贝构造),纯纯资本家

		const list<T>& operator=(list<T> T1){swap(T1);return *this;}

begin和end

begin返回头节点的下一个,end返回头节点.因为容器底层实现,遍历等都是左闭右开[ )

		const_iterator begin() const{return _head->next;}const_iterator end() const{return _head;}iterator begin() {return _head->next;}iterator end() {return _head;}

insert

注意:在链表中,我们的节点都需要自己new出来,因为链表不是一个连续的空间,没有办法直接开好.要一个个自己搞
pos里面存储的节点指针才是我们需要的

		// prev  tmp  nextvoid insert(iterator pos, const T& val){//new一个用数据val开辟出来的节点Node* tmp = new Node(val);Node* prev = pos._node->prev;Node* next = pos._node;prev->next = tmp;tmp->prev = prev;tmp->next = next;next->prev = tmp;_size++;}

push_back

复用insert尾插

		void push_back(const T& val){insert(end(), val);}

push_front

复用insert头插

		void push_front(const T& val){insert(begin(), val);}

erase

注意:delete要删除自定义类型要调用析构函数,我们这里要删除的是节点(指针),而不是迭代器
不能delete pos,迭代器只有访问节点的功能,不能管理节点

		iterator erase(iterator pos){Node* cur = pos._node;Node* prev = pos._node->prev;Node* next = pos._node->next;prev->next = next;next->prev = prev;//delete cur;_size--;return next;}

pop_back

复用erase,注意要删除的不是头节点,而是头节点的前一个,也就是存储有效数据的最后一个
所以–end(),改好使用我们之前写的迭代器–.

		void pop_back(){erase(--end());}

pop_front

		void pop_front(){erase(begin());}

size

		size_t size(){return _size;}

empty

		bool empty(){return _size == 0;}

clear

删除掉除头节点之外的其他节点

		void clear(){iterator it = begin();while (it != end()){it = erase(it);}}

析构

在clear的前提下删除头节点

		~list(){clear();delete _head;_head = nullptr;}

http://www.ppmy.cn/devtools/14283.html

相关文章

探索人工智能的边界:GPT 4.0与文心一言 4.0免费使用体验全揭秘!

探索人工智能的边界&#xff1a;GPT与文心一言免费试用体验全揭秘&#xff01; 前言免费使用文心一言4.0的方法官方入口进入存在的问题免费使用文心一言4.0的方法 免费使用GPT4.0的方法官方入口进入存在的问题免费使用GPT4.0的方法 前言 未来已来&#xff0c;人工智能已经可以…

【 AIGC 研究最新方向(上)】面向平面、视觉、时尚设计的高可用 AIGC 研究方向总结

目前面向平面、视觉、时尚等设计领域的高可用 AIGC 方向有以下 4 种&#xff1a; 透明图层生成可控生成图像定制化SVG 生成 本篇&#xff08;上篇&#xff09;介绍 1、2&#xff0c;而下篇将介绍 3、4。 透明图层生成 LayerDiffuse 代表性论文&#xff1a;Transparent Imag…

第55篇:创建Nios II工程之Hello_World<一>

Q&#xff1a;本期我们开始介绍创建Platform Designer系统&#xff0c;并设计基于Nios II Professor的Hello_world工程。 A&#xff1a;设计流程和实验原理&#xff1a;需要用到的IP组件有Clock Source、Nios II Professor、On-Chip Memory、JTAG UART和System ID外设。Nios I…

Yolov5 v7.0目标检测——详细记录环境配置、自定义数据处理、模型训练与常用错误解决方法(数据集为河道漂浮物)

1. Yolov5 YOLOv5是是YOLO系列的一个延伸&#xff0c;其网络结构共分为&#xff1a;input、backbone、neck和head四个模块&#xff0c;yolov5对yolov4网络的四个部分都进行了修改&#xff0c;并取得了较大的提升&#xff0c;在input端使用了Mosaic数据增强、自适应锚框计算、自…

Vue实现多角色登录,Vue-Router路由守卫控制权限页面

实现页面侧边栏和头部不变&#xff0c;当点击某个功能时&#xff0c;只有主体部分发生变化&#xff0c;这要用到子路由技术 我的项目结构如上&#xff0c;其中包含侧边栏和头部的文件是Manage.vue&#xff0c;主页面是Home.vue&#xff0c;个人页面是Person.vue&#xff0c;用户…

redis分布式锁 -- 基于redisson实现

1. 总结 1.1 加锁机制 线程去获取锁&#xff0c;获取成功: 执行 lua脚本&#xff0c;保存数据到 redis数据库。 线程去获取锁&#xff0c;获取失败: 一直通过 while循环尝试获取锁&#xff0c;获取成功后&#xff0c;执行 lua脚本&#xff0c;保存数据到 redis数据库。 1.2…

《深入浅出.NET框架设计与实现》笔记6.1——ASP.NET Core应用程序多种运行模式之一——自宿主(Self-Hosting)

ASP.NET Core应用程序可以在多种运行模式下运行&#xff0c;包括自宿主&#xff08;Self-Hosting&#xff09;、IIS服务承载、桌面应用程序、服务承载。 因此选择和时的模式很重要。 自宿主&#xff08;Self-Hosting&#xff09; 自宿主是指 ASP.NET Core 应用程序独立运行&a…

ArcGIS无法开始编辑TIN!开始编辑TIN显示灰色

ArcGIS无法开始编辑TIN&#xff01;开始编辑TIN显示灰色&#xff1f; 解决方案&#xff01; 1、确认自定义——扩展模块中空间分析、3D分析模块勾选。 2、确认以上后&#xff0c;还是不能编辑的话&#xff0c;我们可以调出 3D分析分析工具条&#xff0c;你就会发现。TIN编辑工…

内核定时器

内核定时器 定时器是我们最常用到的功能,一般用来完成延时功能。下面我们来学习linux提供的几种内核延时方法。 在真正使用内核定时器之前我们先看几个重要的系统全局变量: HZ:顾名思义就是频率, 在头文件include/asm-generic/param.h中定义 # define HZ CONFIG_HZ。而CON…

iOS问题记录 - Xcode 15安装低版本iOS模拟器(持续更新)

文章目录 前言开发环境问题描述问题分析1. 定位问题2. 逆向分析2.1. IDA Free2.2. Hopper Disassembler Demo 3. 模拟器日志4. supportedArchs 解决方案最后 前言 最近新需求很多&#xff0c;项目改动很大&#xff0c;开发完成后想测一遍在低版本iOS系统上的兼容性&#xff0c…

ROS Node

ROS Node ROS&#xff08;Robot Operating System&#xff09;节点是指在ROS中运行的基本单元&#xff0c;它们是一个独立的进程&#xff0c;执行特定的任务&#xff0c;并与其他节点进行通信以完成更复杂的功能。ROS节点是ROS中实现模块化、分布式和可扩展性的关键组件之一。…

力扣287. 寻找重复数

Problem: 287. 寻找重复数 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路 利用二分查找搜索1 ~ n中重复的元素&#xff0c;我们每次取出当前二分查找的区间的中间元素mid并在元始的数组nums中统计小于mid的元素的个数count&#xff1a; 若count > mid则说明重复的…

解决Java Heap Space问题的排查与优化方法

引言&#xff1a; 在 Java 开发中&#xff0c;经常会遇到 “java heap space” 错误&#xff0c;这意味着程序需要更多的堆内存来执行所需的操作。本文将介绍如何排查和解决这个问题&#xff0c;并提供一些优化方法&#xff0c;以避免类似的错误发生。 1. 确认错误信息 当遇到…

【JavaScript】axios

基础使用 <script src"https://cdn.bootcdn.net/ajax/libs/axios/1.5.0/axios.min.js"></script> <script>axios.get(https://study.duyiedu.com/api/herolist).then(res> {console.log(res.data)}) </script>get - params <script s…

Node.js -- fs模块

文章目录 1. 写入文件1.1 写入文件1.2 同步和异步1.3 文件追加写入1.4 流式写入1.5 文件写入的场景 2. 读取文件2.1 异步和同步读取2.2 读取文件应用场景2.3 流式读取2.4 fs 练习 -- 文件复制 3. 文件重命名和移动4. 文件删除5. 文件夹操作5.1 创建文件夹5.2 读取文件夹5.3 删除…

更新至2022年上市公司数字化转型数据合集(四份数据合集)

更新至2022年上市公司数字化转型数据合集&#xff08;四份数据合集&#xff09; 一、2000-2022年上市公司数字化转型数据&#xff08;年报词频、文本统计&#xff09; 二、2007-2022年上市公司数字化转型数据&#xff08;年报和管理层讨论&#xff09;&#xff08;含原始数据…

vim之将文件的内容追加到当前文件的尾部

a. 使用 :r 命令&#xff08;read 的缩写&#xff09;来将一个文件的内容读取并插入到当前文件的结尾。 1. 打开你想要修改的文件。 vim filename.txt 2. 在 Vim 的命令模式下&#xff08;按 Esc 键确保你处于命令模式&#xff09;&#xff0c;输入 :r 命令&#xff0c;然后…

Three.js入门学习笔记

学习资料&#xff1a; 【Three.js】Three.js快速上手教程_three.module.js-CSDN博客 2024年了&#xff0c;是该学学Three.js了_three.js 2024-CSDN博客 一、three.js简介 three.js是JavaScript编写的WebGL第三方库。 three.js&#xff0c;webGL&#xff0c;openGL三者的关…

Django模型继承之多表继承

在Django模型继承中&#xff0c;支持的第二种模型继承方式是层次结构中的每个模型都是一个单独的模型。每个模型都指向分离的数据表&#xff0c;并且可以被独立查询和创建。在继承关系中&#xff0c;子类和父类之间通过一个自动创建的OneToOneField进行连接。示例代码如下&…

python 笔记ast.literal_eval

1 介绍 ast.literal_eval 是 Python 标准库 ast 模块中的一个函数&#xff0c;用于安全地评估表示 Python 字面量或容器&#xff08;如列表、字典、元组、集合&#xff09;的字符串 import ast # 解析并执行一个数字表达式 num ast.literal_eval("3.14") prin…