营销的网站建设公司,wordpress英文企业模板下载,杭州网站设计上市公司,赣州小程序建设包括哪些服务目录
1.引言
2.C模拟实现
2.1模拟实现结点
2.2模拟实现list前序
1#xff09;构造函数
2#xff09;push_back函数
2.3模拟实现迭代器
1#xff09;iterator
构造函数和析构函数#xff1a;
*操作符重载函数#xff1a;
前置/后置/--#xff1a;
/!操作符重载…目录
1.引言
2.C模拟实现
2.1模拟实现结点
2.2模拟实现list前序
1构造函数
2push_back函数
2.3模拟实现迭代器
1iterator
构造函数和析构函数
*操作符重载函数
前置/后置/--
/!操作符重载函数
-操作符重载函数
2const_iterator
2.4模拟实现list后序
3insert函数
4erase函数
5头插头删尾插尾删函数
6size函数
7begin/end函数
8clear函数
9析构函数
3.完整list 1.引言
先来说说为什么要模拟实现库里的list
我认为模拟实现list有以下几个意义和好处:
1. 学习通过自己实现一个类似于STL中的list数据结构可以加深对数据结构和算法的理解。通过亲自编码实现能更好地理解list的内部工作原理以及C语言中与数据结构相关的特性和语法。
2. 练习编写一个类似于STL中的list可以作为练习和提升编码能力的手段。这有助于加强对C语言的掌握并提高面向对象编程的技能。
3. 定制化需求有时候STL中提供的list功能不能完全满足特定需求此时可以通过自己实现一个list类来扩展或定制list的功能以更好地适应特定的应用场景。
2.C模拟实现 提前声明由于list不同类型的函数重载太多太杂本篇仅仅模拟实现简单的构造析构操作符重载深浅拷贝增删查改等部分函数的介绍感谢读者的支持 建议先创建一个list.hpp头文件单独创建一个命名空间防止已经展开了std的命名空间实现的list与库中list发生冲突。 我们就定义命名空间为drw接下来完成三个部分的编写
2.1模拟实现结点
思路
我们先来定义一个结构体__list_node来代表list中存放数据的结点方便list中函数操作等等访问要求设置一个模板class T来接受各种类型的显式实例化这里不能将__list_node直接命名为Node是为了防止与其他同名结构体冲突设置三个成员变量分别为:prev next val用来储存前后结点以及此处结点的数值使用初始化列表完成构造和析构函数
实现
templateclass T
struct __list_node
{__list_nodeT* prev;__list_nodeT* next;T val;__list_node(const T tT()):prev(nullptr),next(nullptr),val(t){}~__list_node(){prev nullptr;next nullptr;val 0;}
};
2.2模拟实现list前序 由于list同样需要模板class T来显式实例化那么我们先设置一个class T模板参数为什么是先呢是因为后面还会有补充请耐心看完~ 因为list不希望结点被外界访问将结点进行了封装所以可以先将__list_node重命名为Node来方便表示并且只能在public之外重命名list类中只有一个私有成员变量就是Node* _head这代表头结点。接下来完成成员函数
1构造函数
思路
这里我们实现两个构造函数分别是直接构造和拷贝构造因为这两种构造都要先初始化一个头结点我们不妨设置一个Emptyinit函数来做这个事情方便复用在Emptyinit函数中先new一个Node对val不做处理让prev指向自己next也指向自己直接构造就是Emptyinit函数的过程直接复用拷贝构造参数是const listT l除了调用Emptyinit之外还要调用push_back对新的list进行尾插拷贝这里的push_back后续会讲解
实现
void Emptyinit()
{Node* guard new Node;guard-prev guard;guard-next guard;_head guard;
}list()
{Emptyinit();
}list(const listT l)
{Emptyinit();for (auto e : l)//加上防止自定义类型深拷贝{push_back(e);}
}
2push_back函数
思路
先new一个新结点node将t传进去初始化node再将新结点的prev设置为_head的prevnext为_head更新_head的prev以及原先_head之前结点的next
实现
void push_back(const T t)
{Node* newnode new Node(t);newnode-prev _head-prev;_head-prev-next newnode;newnode-next _head;_head-prev newnode;//双向带头循环链表需要复习
}
void push_back(const T t)
{insert(_head, t);
}
这里还可以直接调用insert函数后面介绍由于后续函数需要迭代器这里穿插介绍模拟实现迭代器
2.3模拟实现迭代器 在使用list的时候我们知道迭代器可以/--但是不能/-因为list迭代器属于双向迭代器但不属于随机迭代器但每个结点存储位置是分散开的啊这怎么实现/--呢于是可以定义一个迭代器结构体将其封装成类就可以进行这一操作了 设置模板templateclass T定义__list_iterator为了方便表示__list_node这里也提前重命名一下为Node设置成员变量为node
1iterator
构造函数和析构函数
思路直接使用初始化列表进行赋值nullptr即可同样赋值nullptr进行析构因为node已经有默认构造和析构就不需要更多的处理
实现
__list_iterator(Node* _node):node(_node)
{ }~__list_iterator()
{node nullptr;
}
*操作符重载函数
思路直接返回node代表的val即可
实现
T operator*()
{return node-val;
}
前置/后置/--
思路前置就让node指向next即可后置就拷贝tmp让node指向next返回tmp --前置node指向prev后置拷贝tmpnode指向prev返回tmp
实现
__list_iteratorT operator()//前置
{node node-next;return *this;
}__list_iteratorT operator(int)//后置
{__list_iteratorT tmp(*this);node node-prev;return tmp;
}__list_iteratorT operator--()//前置
{node node-next;return *this;
}__list_iteratorT operator--(int)//后置
{__list_iteratorT tmp(*this);node node-prev;return tmp;
}
/!操作符重载函数
思路判断一下是否相等即可
实现
bool operator!(const __list_iteratorT it){return node ! it.node;}bool operator(const __list_iteratorT it){return node it.node;}
-操作符重载函数
思路为什么要有这个函数是因为如果list存储的是含有多个成员变量的结构体那么想要访问成员变量不应该仅仅有*.还应该提供- 这里直接返回T*类型的(node-val)即可就不进行实现展示了。
2const_iterator
思考const迭代器与iterator相差在哪里呢无非就是*操作符重载函数多了一些const其他大致相同所以我们就不必再去大费周章重新写这里增加一个模板参数Ref在显式实例化的时候传T或者const T就可以解决这个问题 那么这仅仅解决了*函数的重载问题-函数呢这当然又需要一个模板参数Ptr传参方法是一样的。为了简化类型将 __list_iteratorT, Ref,Ptr 重命名为self
演示整个迭代器
templateclass T,class Ref,class Ptr//为什么要传Ref是因为两个结构体太累赘这样可以简化要传Ptr是为了给-函数的返回类型也进行模板化
struct __list_iterator
{typedef __list_nodeT Node;typedef __list_iteratorT, Ref,Ptr self;//这里再次重定义一下方便Node* node;__list_iterator(Node* _node):node(_node){ }Ref operator*(){return node-val;}Ptr operator-()//为什么要重载访问成员操作符呢是因为显式实例化传参也就是vector里面可能保存的是自定义类型而不是内置类型{return (node-val);}self operator()//前置{node node-next;return *this;}self operator(int)//后置{self tmp(*this);node node-next;return tmp;}self operator--()//前置{node node-prev;return *this;}self operator--(int)//后置{self tmp(*this);node node-prev;return tmp;}bool operator!(const self it){return node ! it.node;}bool operator(const self it){return node it.node;}~__list_iterator(){node nullptr;}
};
2.4模拟实现list后序
3insert函数
思路
insert函数就是在迭代器位置为pos的地方插入数据开辟一个新结点newnode将数据传入初始化记录一下pos的前一个结点地址prev让prev的next指向newnodenewnode的prev指向prevnewnode的next指向pospos的prev指向newnode返回newnode
实现
iterator insert(iterator pos, const T t)
{//无需断言Node* prev pos.node-prev;Node* newnode new Node(t);prev-next newnode;newnode-prev prev;newnode-next pos.node;pos.node-prev newnode;return newnode;
}
4erase函数
思路
判断一下pos是否合法不能删除头结点记录一下前一个和后一个结点地址分别为prev和next让prev的next指向nextnext的prev指向prev释放掉pos结点返回next的地址这是防止迭代器失效的措施
实现
iterator erase(iterator pos)
{assert(pos ! end());//不能删除头结点Node* prev pos.node-prev;Node* next pos.node-next;prev-next next;next-prev prev;delete pos.node;return next;
}
5头插头删尾插尾删函数
思路
由于实现了insert和erase这里直接复用就方便多了
实现
void push_back(const T t)
{insert(_head, t);
}void pop_back()
{erase(_head-prev);
}void push_front(const T t)
{insert(_head-next, t);
}void pop_front()
{erase(_head-next);
}
6size函数
思路
要计算链表中的结点个数但不能算入头结点定义size_t sz从头结点的下一个开始遍历到指针指向_head结束
实现
size_t size()
{size_t sz 0;iterator it begin();while (it ! end()){sz;it;}return sz;
}
7begin/end函数
思路
直接将_head的下一个结点或者_head返回因为end代表最后一个元素的下一个位置
实现
iterator begin()
{return _head-next;
}iterator end()
{return _head;
}const_iterator begin()const
{return _head-next;
}const_iterator end()const
{return _head;
}
8clear函数
思路
clear函数是将list中的每一个结点进行释放删除相当于清空链表用循环实现即可但是要注意迭代器的失效问题erase之后的迭代器要及时更新
实现
void clear()
{iterator it begin();while (it ! end()){iterase(it);//迭代器失效了要注意}
}
9析构函数
思路
调用clear函数之后释放掉头结点就完成了析构
实现
~list()
{clear();delete _head;_head nullptr;
}
3.完整list
这里给出完整的实现代码
#pragma once
#includeiostream
#includeassert.h
using namespace std;
namespace drw
{templateclass Tstruct __list_node{__list_nodeT* prev;__list_nodeT* next;T val;__list_node(const T tT()):prev(nullptr),next(nullptr),val(t){}~__list_node(){prev nullptr;next nullptr;val 0;}};templateclass T,class Ref,class Ptr//为什么要传Ref是因为两个结构体太累赘这样可以简化要传Ptr是为了给-函数的返回类型也进行模板化struct __list_iterator{typedef __list_nodeT Node;typedef __list_iteratorT, Ref,Ptr self;//这里再次重定义一下方便Node* node;__list_iterator(Node* _node):node(_node){ }Ref operator*(){return node-val;}Ptr operator-()//为什么要重载访问成员操作符呢是因为显式实例化传参也就是vector里面可能保存的是自定义类型而不是内置类型{return (node-val);}self operator()//前置{node node-next;return *this;}self operator(int)//后置{self tmp(*this);node node-next;return tmp;}self operator--()//前置{node node-prev;return *this;}self operator--(int)//后置{self tmp(*this);node node-prev;return tmp;}bool operator!(const self it){return node ! it.node;}bool operator(const self it){return node it.node;}~__list_iterator(){node nullptr;}};//这样实现太过于累赘最好再添加一个模版参数来实现//templateclass T//struct __const_list_iterator//{// typedef __list_nodeT Node;// Node* node;// __const_list_iterator(Node* _node)// :node(_node)// {// }// const T operator*()const// {// return node-val;// }//__const_list_iteratorT operator()//前置//{// node node-next;// return *this;//}//__const_list_iteratorT operator(int)//后置//{// __const_list_iteratorT tmp(*this);// node node-next;// return tmp;//}// bool operator!(const __const_list_iteratorT it)// {// return node ! it.node;// }// bool operator(const __const_list_iteratorT it)// {// return node it.node;// }// ~__const_list_iterator()// {// node nullptr;// }//};templateclass Tclass list{typedef __list_nodeT Node;public:/*typedef __list_iteratorT iterator;typedef __const_list_iteratorT const_iterator;*///typedef const __list_iteratorT const_iterator;//不能这样使用 const迭代器那么迭代器就不能改变了typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;void Emptyinit(){Node* guard new Node;guard-prev guard;guard-next guard;_head guard;}list(){Emptyinit();}list(const listT l){Emptyinit();for (auto e : l)//加上防止自定义类型深拷贝{push_back(e);}}listT operator(listT l){swap(_head, l._head);return *this;}//void push_back(const T t)//{// Node* newnode new Node(t);// newnode-prev _head-prev;// _head-prev-next newnode;// newnode-next _head;// _head-prev newnode;//双向带头循环链表需要复习//}void push_back(const T t){insert(_head, t);}void pop_back(){erase(_head-prev);}void push_front(const T t){insert(_head-next, t);}void pop_front(){erase(_head-next);}iterator begin(){return _head-next;}iterator end(){return _head;}const_iterator begin()const{return _head-next;}const_iterator end()const{return _head;}iterator insert(iterator pos, const T t){//无需断言Node* prev pos.node-prev;Node* newnode new Node(t);prev-next newnode;newnode-prev prev;newnode-next pos.node;pos.node-prev newnode;return newnode;}iterator erase(iterator pos){assert(pos ! end());//不能删除头结点Node* prev pos.node-prev;Node* next pos.node-next;prev-next next;next-prev prev;delete pos.node;return next;}size_t size(){size_t sz 0;iterator it begin();while (it ! end()){sz;it;}return sz;}void clear(){iterator it begin();while (it ! end()){iterase(it);//迭代器失效了要注意}}~list(){clear();delete _head;_head nullptr;}private:Node* _head;};
}
