网站开发的主要技术难点和重点,战鼓网h5在线制作,互联网营销的优点,网站做跳转怎么做拖更了半个月#xff0c;我终于来填c的坑啦。上次我们说的vetcor不知道小伙伴还记得多少呢#xff1f;今天我们要讲list的模拟实现。 目录 架构结点list表的结构 构造函数尾插push_back()尾删pop_back()计算个数#xff1a;size()判断空empty()※迭代器问题普通迭代器迭代器…拖更了半个月我终于来填c的坑啦。上次我们说的vetcor不知道小伙伴还记得多少呢今天我们要讲list的模拟实现。 目录 架构结点list表的结构 构造函数尾插push_back()尾删pop_back()计算个数size()判断空empty()※迭代器问题普通迭代器迭代器主体begin()和end()operator*()前置 operator()后置 operator(int)前置-- operator--()后置-- operator--(int)重载不等于 operator!(const Self rhs)重载箭头 operator-() const迭代器问题解决方法一创建新的类。解决方法二模板 在某个位置前插入 insert()删除某位置的值 erase()清空链表 clear()拷贝构造析构函数问题实现整体代码 架构
我们之前也写过c语言版本的链表当时很麻烦还要传二级指针。但是现在不用了引用就能解决。我们先把大体的架构搭出来。
结点 list是一个个的结点指针链接而且我们看手册的时候会发现ist是一个双向带头的链表。所以我们先写节点的代码加粗样式。
templateclass T
struct ListNode
{
//为什么要用struct其实用class也ok但是要整个public因为节点我希望你可以随时申请所以不能弄成私有。ListNode(const T valT()):_prev(nullptr),_next(nullptr),data(val){}ListNodeT* _prev;//为什么是ListNodeT*的指针呢因为我们将来要指向//ListNodeT类型的节点。ListNodeT* _next;T data;
};list表的结构
我们也说了是双向带头链表所以list一定要有头结点。
templateclass Tclass list{public:typedef ListNodeT Node;private:Node* _head;//头结点是一个节点指针类型。size_t _size;//因为库中有size这个接口这里存一个会方便一点。};构造函数
在我们之前实现过得带头双向链表在刚开始的时候就是对头结点进行处理让头结点的前后指针指向自己。 list(){_head new Node;//给头一个空间_head-_prev _head;_head-_next _head;_size 0;}尾插push_back()
尾插我们很熟悉了。就是先new出一个节点的大小然后把这个节点连接到链表的尾部。如图
void push_back(const T val)
{Node* node new Node(val);//申请节点Node* tail _head-_prev;//如何找到4是_head-prev保存起来方便我们使用。node-_prev tail;//链接node-_next _head;tail-_next node;_head-_prev node;_size;//修改size
}尾删pop_back()
尾删也是老朋友了。话不多说如图 简单叙述过程就是先找到尾巴然后保存一起来(方便我们删除)。然后将指针链接到尾删的前一个值。
void pop_back()
{Node* tail _head-_prev;//保存_head-_prev tail-_prev;//更改指向tail-_prev-_next _head;delete tail;//删除节点_size--;//别忘了修改个数
}计算个数size()
这个就很简单了因为我们内置了个数所以直接返回就好了。
size_t size()
{return _size;
}判断空empty()
bool empty()
{return _size 0;
}※迭代器问题
链表的迭代器很麻烦不像vector那样用下标访问就可以的我们先把迭代器的主体写出来分析一下我们都需要什么吧。
bit::listint::const it lt2.begin();
while (it ! lt2.end())
{std::cout *it ;it;
}我们平时访问数据的时候就这些例如迭代器本身、*星号、begin()、end()、自增。那怎么写呢
普通迭代器 问题迭代器本身怎么写还用T* 吗写在list中码(一定要思考这个问题) 答案不不不我问你的自增你在增谁增加的list还是迭代器我们要写operator()你一定要明白是谁在。如果你把迭代器写到list中你operator()自增的是谁一定要把这个问题想清楚。 自增的迭代器本身。那么我们的自增就不能写到list中也就表示迭代器不能写在list中。那么我们就需要另外写一个类封装了。OK开写
迭代器主体
我们要遍历这个list链表的时候我们一定要有这个地方的节点指针我们才能访问这里的数据对吧所以里面的成员变量是Node* _node;
templateclass T
class List_Iterator
{
public:typedef ListNodeT Node;Node* _node;List_Iterator(Node* node):_node(node){}
};begin()和end()
begin()和end()多好写begin()是返回数据的开始和end()返回头结点(有效数据的下一个)。 问题你写在哪list类还是iterator类 答思考一下你的数据在哪你的数据在list 里面对吧我要访问遍历数据我去哪里拿数据list中那么你的begin()和end()一定不能写在iterator。begin()和end()应该写在list中。 templateclass Tclass list{public:typedef ListNodeT Node;iterator begin(){//这里存在单参数构造函数的隐式类型转换//按道理 return iterator(_head-next);//应该是这样的匿名对象但是单参数的构造函数可以进行隐式类型转换。return _head-_next;}iterator end(){return _head;}private:Node* _head;//头结点是一个节点指针类型。size_t _size;//因为库中有size这个接口这里存一个会方便一点。};operator*()
因为我们遍历一般都是要打印出它的值所星号也是必不可少的。星号表示解压用。那么我们只需要返回当前节点的值就可以了。
T operator* ()
{return _node-data;
}前置 operator()
自增很简单我们只需要下一个节点的指针就好那么我们怎么找到下一个节点呢是不是当前节点的_next?那就更简单了。
List_IteratorT operator()
{//this-_node this-_node-_next;_node _node-_next;return *this;
}后置 operator(int)
后置就是我们创建一个临时变量然后返回临时变量但是让实际已经指向下一个节点了。注不能返回引用因为是临时变量。
List_IteratorT operator(int)
{List_IteratorT tmp(*this);_node _node-_next;return tmp;
}前置-- operator–()
为什么要重载自减呢是因为有些地方我们还是有需要的所以就直写了。
List_IteratorT operator--()
{_node _node-_prev;return *this;
}后置-- operator–(int)
List_IteratorT operator--(int)
{Self tmp(*this);_node _node-_prev;return tmp;
}重载不等于 operator!(const Self rhs) 问题在比较的时候我们比的是节点指针还是数值呢 答节点指针数值可能重复。 bool operator!(const Self rhs )
{return rhs._node ! _node;
}重载箭头 operator-()
为什么要重载operator-我们一直用int内置类型来作为样例这没有问题但是我想问你你的list只存int吗没有自定义类型吗如果我希望能存一个student类呢可能你说(*it).成员变量也可以啊但是你觉得方便吗所以我们要重载-。
箭头的运算符重载 从图上我们能发现他隐藏了一个箭头他应该是it.operator-()-_a1;但是事实上只有意见箭头就表明了他隐藏了一个箭头。
T* operator-()
{return _node-data;
}const迭代器问题
以上我们用的都是普通的迭代器那么const迭代器怎么写呢你会说我知道了只要让他不改变不就好了OK说干就干。显示就是依然改了并没有用。
解决方法一创建新的类。
问题就出在了你迭代器本身你的返回值依然是普通的我依然可以改。那你突然灵光一现我在写一个const_ListIterator类就好了好说干就干。你用了一下真好用。但是你有没有发现代码很冗余唯独只有operator*()和operator-()的返回值改变了因为在拿取值的时候我们要返回const类型的。
templateclass T
class List_ConstIterator
{
public:typedef ListNodeT Node;typedef List_ConstIteratorT Self;Node* _node;List_ConstIterator(Node* node):_node(node){}//前置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 rhs) {return rhs._node ! _node;}bool operator(const Self rhs){return _node rhs._node;}const T operator* (){return _node-data;}const T* operator-(){return _node-data;}
};解决方法二模板
我们上面也说只是两个成员函数的返回类型不同那么我们在处理返回类型不同的时候怎么做的呢对就是模板模板是不是可以传不同类型呀那么我们就只需要改一下。 list类中
templateclass T ,class Ref ,class Ptr
class List_Iterator
{
public:typedef ListNodeT Node;typedef List_Iterator T, Ref, Ptr Self;Node* _node;List_Iterator(Node* node):_node(node){}//前置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 rhs ){return rhs._node ! _node;}bool operator(const Self rhs){return _node rhs._node;}Ptr operator-(){return _node-data;}Ref operator* (){return _node-data;}
};在某个位置前插入 insert()
库中给我们了三种我们只实现第一种。需要迭代器类型的pos和 T val。刚好迭代器问题我们刚刚解决。 连接方式如图
iterator insert(iterator pos, const T val)
{//我写的不美观Node* node new Node(val);Node* tmppos._node-_prev;tmp-_next node;node-_prev tmp;node-_next pos._node;pos._node-_prev node;_size;return _head;// Node* node new Node(val);// Node* prevpos-prev;// node-prevprev;// node-nextpos;// pos-prevnode;// prev-nextnode;// _size;// return _head
}删除某位置的值 erase()
这里我们要注意库中要求返回被删除值的下一个的迭代器。 iterator erase(iterator pos){//不美观版本assert(pos ! end());//这里我担心有人有人恶意传迭代器所以就判断了一下。Node* tmp pos._node-_prev;tmp-_next pos._node-_next;pos._node-_next-_prev tmp;delete pos._node;_size--;return tmp-_next;/*美观版本Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;return next;*/}清空链表 clear()
注意我们清空的链表不需要清头指针所以直接用迭代器pop_back()就可以了。
void clear()
{iterator it begin();while (it ! end()){it erase(it);}_size 0;
}拷贝构造
拷贝构造这里有几个问题。 问题1直接push_back()可以吗 答不可以。你的头指针没有初始化都是空插入直接空指针访问。所以你需要初始化。 问题2用我注释部分的迭代器可以吗 答不行如果你传进来是一个const类型的迭代器呢普通迭代器类型不匹配除非你用auto。 //lt1(lt2)
list(const listT lt)
{empty_init();//初始化头结点。for (auto e : lt){push_back(e);}iterator it lt.begin();类型不明确用范围for更好//auto it lt.begin();//这样也可以//while (it ! lt.end())//{// push_back(*it);// it;//}
}析构函数
释放空间并且还有头结点有些小伙伴以为只用释放各个数据的节点就可以了但是头结点也是你开出来的空间啊所以也要记得释放。
~list()
{clear();//复用delete _head;
}问题
如果我什么都写了只有拷贝构造没有写下面图代码对吗
答不对因为传值传参回去调用拷贝构造没有写拷贝构造就是浅拷贝当函数结束 临时对象会被析构。但是浅拷贝导致本对象被析构当整体结束的时候会导致二次析构。
实现整体代码
#pragma once
#includeiostream
#includeassert.hnamespace bit {templateclass Tstruct ListNode{ListNode(const T valT()):_prev(nullptr),_next(nullptr),data(val){}ListNodeT* _prev;//为什么是ListNodeT*的指针呢因为我们将来要指向//ListNodeT类型的节点。ListNodeT* _next;T data;};templateclass T ,class Ref ,class Ptrclass List_Iterator{public:typedef ListNodeT Node;typedef List_Iterator T, Ref, Ptr Self;Node* _node;List_Iterator(Node* node):_node(node){}//前置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 rhs ){return rhs._node ! _node;}Ref operator* (){return _node-data;}bool operator(const Self rhs){return _node rhs._node;}Ptr operator-(){return _node-data;}};//templateclass T//class List_ConstIterator//{//public:// typedef ListNodeT Node;// typedef List_ConstIteratorT Self;// Node* _node;// List_ConstIterator(Node* node)// :_node(node)// {}// //前置// 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 rhs) // {// return rhs._node ! _node;// }// const T operator* ()// {// return _node-data;// }// bool operator(const Self rhs)// {// return _node rhs._node;// }// const T* operator-()// {// return _node-data;// }//};templateclass Tclass list{public:typedef ListNodeT Node;typedef List_IteratorT, T, T* iterator;typedef List_IteratorT, const T, const T* const_iterator;//typedef List_IteratorT iterator;//typedef List_ConstIteratorT const_iterator;void empty_init(){_head new Node;//给头一个空间_head-_prev _head;_head-_next _head;_size 0;}list(){empty_init();//刚创建一个链表的时候没有插入任何数据我们需要让他指向自己}~list(){clear();delete _head;}//lt1(lt2)list(const listT lt){empty_init();for (auto e : lt){push_back(e);}iterator it lt.begin();类型不明确用范围for更好//auto it lt.begin();//这样也可以//while (it ! lt.end())//{// push_back(*it);// it;//}}void push_back(const T val){/*Node* node new Node(val);Node* tail _head-_prev;node-_prev tail;node-_next _head;tail-_next node;_head-_prev node;*/insert(end(), val);}void pop_back(){/*Node* tail _head-_prev;_head-_prev tail-_prev;tail-_prev-_next _head;delete tail;*/erase(--end());}//当我们想使用insert的时候发现需要迭代器那么我们先实现迭代器怎么做呢iterator begin(){//这里存在单参数构造函数的隐式类型转换//return _head-_next;}iterator end(){return _head;}const_iterator begin()const{//这里存在单参数构造函数的隐式类型转换return _head-_next;}const_iterator end()const{return _head;}//目前测试的迭代器没有大碍那么就写insertiterator insert(iterator pos, const T val){//我写的不美观Node* node new Node(val);Node* tmppos._node-_prev;tmp-_next node;node-_prev tmp;node-_next pos._node;pos._node-_prev node;_size;return _head;// Node* node new Node(val);// Node* prevpos-prev;// node-prevprev;// node-nextpos;// pos-prevnode;// prev-nextnode;// _size;// return _head}iterator erase(iterator pos){//我写的不美观assert(pos ! end());Node* tmp pos._node-_prev;tmp-_next pos._node-_next;pos._node-_next-_prev tmp;delete pos._node;_size--;return tmp-_next;//老师写的/*Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;return next;*/}size_t size(){return _size;}bool empty(){return _size 0;}void clear(){iterator it begin();while (it ! end()){it erase(it);}_size 0;}private:Node* _head;size_t _size;};
}
