自定义实现list及其功能

这篇具有很好参考价值的文章主要介绍了自定义实现list及其功能。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

自定义实现list及其功能,list,windows,数据结构

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

namespace test
{
	//******************************设置结点******************************
	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& x = T())
			:_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};

	//***************************************定义list迭代器***************************
	// typedeflist iterator<T, T&, T*>           iterator;
	// typedeflist iterator<T, const T&, const T*> const iterator;

	//list_node为结点类
	//template<class T>
	template<class T,class Ref,class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T,Ref,Ptr> iterator;
		Node* _node;

		//构造函数,浅拷贝
		__list_iterator(Node* node)
			: _node(node)
		{}

		__list_iterator(const iterator& l)
			:_node(l._node)
		{}

		//重载!=
		bool operator!=(const iterator& it)const
		{
			return it._node != this->_node;
		}

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

		//重载 *it it.operator*()
		//T& operator*()
		//{
		//	return _node->_data;
		//}
		//T* operator->()
		//{
		//	return &(operator*());//&(_node->date);
		//}

		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &(operator*());//&(_node->date);
		}

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

		//重载前置--
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		//重置后置--
		iterator operator--(int)
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}



	};

	//**************************************模拟实现list******************************************
	//list_node为结点类
	 template<class T>
	 class list
	 {
		 typedef list_node<T> Node;
	 public:
		 typedef __list_iterator<T,T&,T*> iterator;
		 typedef __list_iterator<T,const T&,const T*> const_iterator;

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

		 iterator begin()
		 {
			 return iterator(_head->_next);
		 }
		 iterator end()
		 {
			 return iterator(_head);
		 }

		 iterator 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;
			 ++size;
			 return iterator(newnode);
		 }

		 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;
			 size--;
			 return iterator(next);
		 }

		 void push_back(const T& x)
		 {
			 //Node* tail = _head->_prev;
			 //Node* newnode = new Node(x);

			 _head  tail  newnode
			 //tail->_next = newnode;
			 //newnode->_prev = tail;
			 //newnode->_next = _head;
			 //_head->_prev = newnode;
			 insert(end(), x);

		 }

		 void push_front(const T& x)
		 {
			 insert(begin(), x);
		 }
			 
		 void pop_back()
		 {
			 erase(--end());
		 }

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

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

		 void empty_init()
		 {
			 //创建并初始化哨兵位头结点
			 _head = new Node;
			 _head->_next = _head;
			 _head->_prev = _head;
			 size = 0;
		 }

		 void swap(list<T>& x)
		 {
			 std::swap(_head, x._head);
			 std::swap(size, x.size);
		 }

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

		 //模板构造函数初始化
		 template <class InputIterator>
		 list(InputIterator first, InputIterator last)
		 {
			 empty_init();
			 while (first != last)
			 {
				 push_back(*first);
				 ++first;
			 }
		 }

		 list(const list<T>& lt)
		 {
			 empty_init();

			 list<T> tmp(lt.begin(), lt.end());
			 swap(tmp);
		 }

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

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

	 private:
		 Node* _head;
		 size_t size = 0;
	 };

值得我们注意一下的是
自定义实现list及其功能,list,windows,数据结构

struct Pos
	 {
		 int _a1;
		 int _a2;
		 Pos(int a1 = 0, int a2 = 0)
			 :_a1(a1)
			 ,_a2(a2)
		 {}
	 };
void test_list2()
	 {
		 int x = 10;
		 int* p1 = &x;
		 cout << *p1 << endl;


		 //多会用 . 多会用->
		 Pos aa;
		 Pos* p2 = &aa;
		 aa._a1;
		 p2->_a1;

		 list<Pos> lt;

		 lt.push_back(Pos(10, 20));
		 lt.push_back(Pos(10, 21));

		 list<Pos>::iterator it = lt.begin();
		 while (it != lt.end())
		 {
			 //cout << (*it)._a1 << " : " << (*it)._a2 << endl;
			 //it->是it.operator->()的类型(T*)
			 //语法为了可读性,编译器进行了特殊处理,省略了一个->

			 //return &(operator*());//&(_node->date);
			 cout << it->_a1 << " : " << it->_a2 << endl;
			 //原型cout << it->->_a1 << " : " << it->->_a2 << endl;
			 ++it;
		 }
		 cout << endl;
	 }

在这里我们注意到如果listpush的是一个结构体时,我们在使用->重载时,语法为了可读性,编译器进行了特殊处理,省略了一个->,正常情况为cout << it->->_a1 << " : " << it->->_a2 << endl;文章来源地址https://www.toymoban.com/news/detail-595144.html

到了这里,关于自定义实现list及其功能的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】栈及其实现

    目录 🤠前言 什么是栈? 栈的定义及初始化 栈的定义 栈的初始化 栈的判空 栈顶压栈 栈顶出栈 栈的数据个数 栈的销毁 完整代码 总结 学了相当长一段时间的链表,总算是跨过了一个阶段。从今天开始我们将进入栈和队列的学习,相比于链表可以说是有手就行的难度,所以

    2024年02月06日
    浏览(61)
  • 数据结构之单链表及其实现!

    目录 ​编辑 1.  顺序表的问题及思考 2.链表的概念结构和分类 2.1 概念及结构 2.2 分类 3. 单链表的实现 3.1 新节点的创建 3.2 打印单链表 3.3 头插 3.4 头删 3.5 尾插 3.6 尾删 3.7 查找元素X 3.8 在pos位置修改 3.9 在任意位置之前插入 3.10 在任意位置删除 3.11 单链表的销毁 4. 完整代码

    2024年03月12日
    浏览(55)
  • 【数据结构】| 并查集及其优化实现

    以一个直观的问题来引入并查集的概念。 亲戚问题:有一群人,他们属于不同家族,同一个家族里的人互为亲戚,不同家族的人不是亲戚。随机指定两个人,问他们是否有亲戚关系。 以下图3个不相交的集合表示 3 个家族,当询问两个人是否有亲戚关系时,也就是问两个元素

    2024年02月09日
    浏览(37)
  • 数据结构笔记1线性表及其实现

    终于开始学习数据结构了 c语言结束之后 我们通过题目来巩固了 接下来我们来学习数据结构 这里我们将去认识到数据结构的一些基础知识,我在第一次学习的时候会很迷糊现在重新学习发现之前的时候还是因为c语言学的不牢固导致学习数据结构困难 这里 我会尽量的多写代

    2024年02月22日
    浏览(40)
  • 【数据结构与算法】之顺序表及其实现!

    目录 ​编辑 1. 顺序表的概念及结构 2. 接口的实现 2.1 顺序表的初始化 2.2 检查顺序表容量是否已满 2.3 顺序表的尾插 ​编辑 2.4 顺序表的尾删 2.5 顺序表的头插 2.6  顺序表的头删 2.7 顺序表在pos位置插入 2.8  顺序表在pos位置删除 2.9 顺序表的查找 2.10 顺序表的销毁 2.1

    2024年04月28日
    浏览(33)
  • 【数据结构】带头双向循环链表及其实现

    目录 1.带头双向循环链表 2.带头双向循环链表实现 2.1初始化 2.2销毁 2.3头插 2.4链表打印 2.5头删数据 2.6尾插数据 2.7尾删数据 2.8链表判空  2.9查找一个数据 2.10在pos位置前插入数据 2.11删除pos位置 2.12求链表的长度 2.顺序表和链表的比较 我们已经实现了无头单向循环链表 带头双

    2024年02月10日
    浏览(45)
  • 数据结构之List(双向链表)的实现

    方法名 参数 功能 返回 find const T val, int n, listNode * p 区间查找 从p往前数n个节点 指针或NULL const T val, listNode * p 区间查找 从p往前到首节点 const T val 查找 Size void 链表规模 size empty void 判空 bool first void 返回首节点 首节点指针 clear void 清空链表 void insertAsFirst const T val 作为首节

    2024年02月16日
    浏览(44)
  • 深入理解数据结构:队列的实现及其应用场景

    队列(Queue)是一种具有先进先出(FIFO)特性的数据结构。在队列中,数据的插入和删除操作分别在队列的两端进行。插入操作在队列的尾部进行,而删除操作则在队列的头部进行。这种特性使得队列在很多实际应用中非常有用,比如任务调度、缓冲区管理等。 线性表是一种

    2024年04月28日
    浏览(51)
  • 【数据结构与算法】之双向链表及其实现!

    ​                                                                                 个人主页:秋风起,再归来~                                                                                             数据结构与

    2024年04月23日
    浏览(42)
  • 模拟实现链式二叉树及其结构学习——【数据结构】

    W...Y的主页 😊 代码仓库分享 💕 之前我们实现了用顺序表完成二叉树(也就是堆),顺序二叉树的实际作用就是解决堆排序以及Topk问题。 今天我们要学习的内容是链式二叉树,并且实现链式二叉树,这篇博客与递归息息相关! 目录 链式存储 二叉树链式结构的实现 链式二叉

    2024年02月07日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包