C++——list的实现

2024-09-07 11:44
文章标签 c++ 实现 list

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

目录

0.前言

1.节点类 

2.迭代器类 

①普通迭代器

②const迭代器 

③模板迭代器

3.list类 

3.1 clear、析构函数、swap

①clear

② 析构函数 

③ swap

3.2构造函数 

①无参构造

 ②赋值构造

3.3 迭代器

3.4插入函数

①insert插入

②头插

③尾插

3.5 删除函数

①erase删除

②头删 

③尾删

4.测试

源代码(list.h) 


 

0.前言

我们知道,list是一个双向循环链表,所以list的每个节点中需要存在一个指向前一个节点的指针prev、一个指向下一个节点的指针next和一个数据域data

35f348f4278543a9a4d796c80ea00ba8.png

1.节点类 

因为list的底层是节点,而节点的底层又是prev、next指针和数据域data,所以我们先将节点封装为一个类,然后再用list类调用节点类。节点类的代码如下:

//定义链表节点template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;//链表节点构造函数ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}

2.迭代器类 

在string和vector中我们使用迭代器访问数据时需要有这样的操作:

vector<int>::iterator it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;

 需要知悉的是,在C++中,为了方便和统一,无论什么类我们大多都采用此方法进行访问,string与vector都是连续的,如此访问必然不会有差错,可是list并不是连续的

我们希望++it就能找到下一个节点,而it解引用(*it)就得到节点里存的data,所以,为了使迭代器能够正常访问,我们在自定义的类中必须实现以下方法:

1. 指针可以解引用,迭代器的类中必须重载operator*()

2. 指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()

3. 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)

4. 迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()

代码如下:

①普通迭代器

//①普通迭代器 可读可写template<class T>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator D;Node* _node;//迭代器构造函数__list_iterator(Node* x):_node(x){}//重载++//前置++D& operator++()//返回迭代器的引用{_node = _node->_next;//指向下一个节点return *this;}//后置++D operator++(int){D tmp(*this);_node = _node->_next;return tmp;//返回拷贝之前的值}//重载--//前置--D& operator--(){_node = _node->_prev;return *this;}//后置--D operator--(int){D tmp(*this);_node = _node->_prev;return tmp;}//重载解引用T& operator*()//返回数据的引用{return _node->_data;//返回节点里的数据}//重载->T* operator->(){return &_node->_data;}//重载!=bool operator !=(const D& s){return _node != s._node;}//重载==bool operator==(const D& s){return _node == s._node;}};

②const迭代器 

const迭代器的作用是只可读不可写,防止数据被修改,因此我们只需在普通迭代器的基础上对operator*()和operator->()添加const操作即可:

//②const迭代器 可读不可写template<class T>struct __list_const_iterator{typedef ListNode<T> Node;typedef __list_const_iterator D;Node* _node;//迭代器构造函数__list_const_iterator(Node* x):_node(x){}//重载++//前置++D& operator++()//返回迭代器的引用{_node = _node->_next;//指向下一个节点return *this;}//后置++D operator++(int){D tmp(*this);_node = _node->_next;return tmp;//返回拷贝之前的值}//重载--//前置--D& operator--(){_node = _node->_prev;return *this;}//后置--D operator--(int){D tmp(*this);_node = _node->_prev;return tmp;}//重载解引用const T& operator*()//返回数据的引用{return _node->_data;//返回节点里的数据}//重载->const T* operator->(){return &_node->_data; }//重载!=bool operator !=(const D& s){return _node != s._node;}//重载==bool operator==(const D& s){return _node == s._node;}};

③模板迭代器

观察以上两个迭代器,不同之处也就在于对operator*()和operator->()的操作不同,代码相似度可以说达到了90%,那么有没有办法减少冗余,提高代码的可读性呢?

答案当然是有的,我们可以为两个迭代器提供一个共同的模板,再提供两个参数,当调用普通迭代器和const迭代器时,只需根据所传递的参数而选择不同的迭代器。

template<class T, class Ref, class Ptr>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T, Ref, Ptr> D;Node* _node;//迭代器构造函数__list_iterator(Node* x):_node(x){}//重载++//前置++D& operator++()//返回迭代器的引用{_node = _node->_next;//指向下一个节点return *this;}//后置++D operator++(int){D tmp(*this);_node = _node->_next;return tmp;//返回拷贝之前的值}//重载--//前置--D& operator--(){_node = _node->_prev;return *this;}//后置--D operator--(int){D tmp(*this);_node = _node->_prev;return tmp;}//重载解引用Ref operator*()//返回数据的引用{return _node->_data;//返回节点里的数据}//重载->Ptr operator->(){return &_node->_data;}//重载!=bool operator !=(const D& s){return _node != s._node;}//重载==bool operator==(const D& s){return _node == s._node;}};

3.list类 

做好了节点类和迭代器类的准备工作,终于来到了主角list类

//定义链表template<class T>class list{typedef ListNode<T> Node;public:/*typedef __list_iterator<T> iterator;typedef __list_const_iterator<T> const_iterator;*/typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;private:Node* _head;};

3.1 clear、析构函数、swap

①clear

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

② 析构函数 

//析构函数~list(){clear();delete _head;_head = nullptr;}

③ swap

//swapvoid swap(list<T>& tmp){std::swap(_head, tmp._head);}

3.2构造函数 

①无参构造

//链表构造函数list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}

 ②赋值构造

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

3.3 迭代器

//普通迭代器iterator begin(){//return iterator(_head->_next);return _head->_next;//单参数的构造函数支持隐式类型转换}iterator end(){return _head;}//const迭代器const_iterator begin() const{//return iterator(_head->_next);return _head->_next;//单参数的构造函数支持隐式类型转换}const_iterator end() const{return _head;}

3.4插入函数

①insert插入

//insert插入
iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;//取当前节点Node* prev = cur->_prev;//当前节点的前一个节点Node* newnode = new Node(x);//创建并初始化新节点prev->_next = newnode;//前一个节点的_next指针指向新节点newnode->_prev = prev;//新节点的_prev指针指向前一个节点newnode->_next = cur;//新节点的_next指针指向当前节点(此时相对于新节点就变成了后一个节点)cur->_prev = newnode;//当前节点的_prev指针指向新节点(此时相对于新节点就变成了后一个节点)//return iterator(newnode);return newnode;
}

②头插

//push_front头插void push_front(const T& x){insert(begin(), x);}

③尾插

原始写法

void push_back(const T& x){Node* newnode = new Node(x);//开辟并初始化新节点newnode Node* tail = _head->_prev;//定义上一个节点为tailtail->_next = newnode;//上一个节点tail的next指针指向新节点newnodenewnode->_prev = tail;//新节点newnode的prev指针指向上一个节点tailnewnode->_next = _head;//新节点newnode的next指针指向头节点_head_head->_prev = newnode;//头节点_head的prve指针指向新节点newnode}

复用insert

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

复用尾插,写拷贝构造:

//拷贝构造list(list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;//拷贝之前先创建一个头节点,自己指向自己for (const auto& e : lt){push_back(e);}}

3.5 删除函数

①erase删除

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;}

②头删 

//pop_front头删void pop_front(){erase(begin());}

③尾删

//pop_back尾删void pop_back(){erase(--end());}

4.测试

void test_list(){//无参构造list<int> l1;for (auto e : l1){cout << e << " ";}cout << endl;//插入//insert插入l1.insert(l1.begin(), 1);for (auto e : l1){cout << e << " ";}cout << endl;//头插l1.push_front(0);for (auto e : l1){cout << e << " ";}cout << endl;//尾插l1.push_back(2);l1.push_back(3);l1.push_back(4);for (auto e : l1){cout << e << " ";}cout << endl;//删除//erase删除l1.erase(l1.begin());for (auto e : l1){cout << e << " ";}cout << endl;//头删l1.pop_front();for (auto e : l1){cout << e << " ";}cout << endl;//尾删l1.pop_back();for (auto e : l1){cout << e << " ";}cout << endl;//赋值构造list<int> l2 = l1;for (auto e : l1){cout << e << " ";}cout << endl;}

86afb71c747f45f981e321057edb713d.png

源代码(list.h) 

#pragma once#include <iostream>
#include <assert.h>
using namespace std;
#include <assert.h>namespace xxk
{//定义链表节点template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;//链表节点构造函数ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};//定义迭代器//在vector使用迭代器时:/*vector<int>::iterator it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;*///在这段代码中我们希望++it就能找到下一个节点,而it解引用(*it)我们需要得到节点里存的data//可是链表并不是连续的,因迭代器使用形式与指针完全相同,想要实现以上功能,我们必须要在自定义类中实现以下方法://1. 指针可以解引用,迭代器的类中必须重载operator*()//2. 指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()//3. 指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)//   至于operator--() / operator--(int)释放需要重载,根据具体的结构来抉择,双向链表可以向前移动,//   所以需要重载,如果是forward_list就不需要重载--//4. 迭代器需要进行是否相等的比较,因此还需要重载operator == ()与operator != ()//③为减少冗余,提高代码的可读性,使用模板将两个类写到一起template<class T, class Ref, class Ptr>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T, Ref, Ptr> D;Node* _node;//迭代器构造函数__list_iterator(Node* x):_node(x){}//重载++//前置++D& operator++()//返回迭代器的引用{_node = _node->_next;//指向下一个节点return *this;}//后置++D operator++(int){D tmp(*this);_node = _node->_next;return tmp;//返回拷贝之前的值}//重载--//前置--D& operator--(){_node = _node->_prev;return *this;}//后置--D operator--(int){D tmp(*this);_node = _node->_prev;return tmp;}//重载解引用Ref operator*()//返回数据的引用{return _node->_data;//返回节点里的数据}//重载->Ptr operator->(){return &_node->_data;}//重载!=bool operator !=(const D& s){return _node != s._node;}//重载==bool operator==(const D& s){return _node == s._node;}};//定义链表template<class T>class list{typedef ListNode<T> Node;public:/*typedef __list_iterator<T> iterator;typedef __list_const_iterator<T> const_iterator;*/typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;//普通迭代器iterator begin(){//return iterator(_head->_next);return _head->_next;//单参数的构造函数支持隐式类型转换}iterator end(){return _head;}//const迭代器const_iterator begin() const{//return iterator(_head->_next);return _head->_next;//单参数的构造函数支持隐式类型转换}const_iterator end() const{return _head;}//链表构造函数list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}//clearvoid clear(){iterator it = begin();while (it != end()){it = erase(it);}}//析构函数~list(){clear();delete _head;_head = nullptr;}//拷贝构造list(list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;//拷贝之前先创建一个头节点,自己指向自己for (const auto& e : lt){push_back(e);}}//swapvoid swap(list<T>& tmp){std::swap(_head, tmp._head);}//operator=list<T>& operator=(list<T> lt){swap(lt);return *this;}//尾插①//void push_back(const T& x)//{//	Node* newnode = new Node(x);//开辟并初始化新节点newnode //	Node* tail = _head->_prev;//定义上一个节点为tail//	tail->_next = newnode;//上一个节点tail的next指针指向新节点newnode//	newnode->_prev = tail;//新节点newnode的prev指针指向上一个节点tail//	newnode->_next = _head;//新节点newnode的next指针指向头节点_head//	_head->_prev = newnode;//头节点_head的prve指针指向新节点newnode//}//②复用insertvoid push_back(const T& x){insert(end(), x);}//insert插入iterator insert(iterator pos, const T& x){Node* cur = pos._node;//取当前节点Node* prev = cur->_prev;//当前节点的前一个节点Node* newnode = new Node(x);//创建并初始化新节点prev->_next = newnode;//前一个节点的_next指针指向新节点newnode->_prev = prev;//新节点的_prev指针指向前一个节点newnode->_next = cur;//新节点的_next指针指向当前节点(此时相对于新节点就变成了后一个节点)cur->_prev = newnode;//当前节点的_prev指针指向新节点(此时相对于新节点就变成了后一个节点)//return iterator(newnode);return newnode;}//push_front头插void push_front(const T& x){insert(begin(), x);}//erase删除函数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;}//pop_back尾删void pop_back(){erase(--end());}//pop_front头删void pop_front(){erase(begin());}private:Node* _head;};void test_list(){//无参构造list<int> l1;for (auto e : l1){cout << e << " ";}cout << endl;//插入//insert插入l1.insert(l1.begin(), 1);for (auto e : l1){cout << e << " ";}cout << endl;//头插l1.push_front(0);for (auto e : l1){cout << e << " ";}cout << endl;//尾插l1.push_back(2);l1.push_back(3);l1.push_back(4);for (auto e : l1){cout << e << " ";}cout << endl;//删除//erase删除l1.erase(l1.begin());for (auto e : l1){cout << e << " ";}cout << endl;//头删l1.pop_front();for (auto e : l1){cout << e << " ";}cout << endl;//尾删l1.pop_back();for (auto e : l1){cout << e << " ";}cout << endl;//赋值构造list<int> l2 = l1;for (auto e : l1){cout << e << " ";}cout << endl;}
}

 

 

这篇关于C++——list的实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

Spring Security+JWT如何实现前后端分离权限控制

《SpringSecurity+JWT如何实现前后端分离权限控制》本篇将手把手教你用SpringSecurity+JWT搭建一套完整的登录认证与权限控制体系,具有很好的参考价值,希望对大家... 目录Spring Security+JWT实现前后端分离权限控制实战一、为什么要用 JWT?二、JWT 基本结构

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Android实现两台手机屏幕共享和远程控制功能

《Android实现两台手机屏幕共享和远程控制功能》在远程协助、在线教学、技术支持等多种场景下,实时获得另一部移动设备的屏幕画面,并对其进行操作,具有极高的应用价值,本项目旨在实现两台Android手... 目录一、项目概述二、相关知识2.1 MediaProjection API2.2 Socket 网络

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

C# Where 泛型约束的实现

《C#Where泛型约束的实现》本文主要介绍了C#Where泛型约束的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录使用的对象约束分类where T : structwhere T : classwhere T : ne

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4