hemi网站怎么做热图,网站建设品牌有哪些,六年级做的网站的软件下载,域名更换网站文章目录 一、模拟list类的框架二、函数接口实现1、迭代器接口2、常用删除、插入接口3、常用其他的一些函数接口4、默认成员函数 一、模拟list类的框架
1、使用带哨兵的双向链表实现。 2、链表结点#xff1a;
// List的结点类
templateclass T
struct ListNode
{Li… 文章目录 一、模拟list类的框架二、函数接口实现1、迭代器接口2、常用删除、插入接口3、常用其他的一些函数接口4、默认成员函数 一、模拟list类的框架
1、使用带哨兵的双向链表实现。 2、链表结点
// List的结点类
templateclass T
struct ListNode
{ListNodeT* _pPre; //后继指针ListNodeT* _pNext; //前驱指针T _val; //数据//构造结点ListNode(const T val T()) :_val(val), _pPre(nullptr), _pNext(nullptr){}
};3、list类的成员变量和构造双向链表的哨兵位结点函数。 //让哨兵位结点指向自己
typedef ListNodeT Node;
typedef Node* PNode;void CreateHead(){_pHead new Node;_pHead-_pNext _pHead;_pHead-_pPre _pHead;}PNode _pHead; //哨兵位结点二、函数接口实现
1、迭代器接口
list的迭代器是双向迭代器支持、–但是它们在内存上储存是不连续的无法简单通过指针去进行、–操作所以我们要对list的迭代器进行封装。 (1)list正向迭代器类 成员变量两个结点指针。
typedef ListNodeT* PNode;
PNode _pNode; //结点指针
PNode _P;//保存哨兵位结点指针用于判断解引用是否访问哨兵位结点构造函数
//构造函数 获取一个结点指针ListIterator(const PNode pNode nullptr, const PNode const P nullptr) :_pNode(pNode),_P(P){}拷贝构造、赋值、析构函数 因为_pNode的指针指向的内存是有list类释放的所以该类无需进行资源清理使用浅拷贝即可所以拷贝、赋值、析构都使用编译器生成的即可。
重载操作符 //Ref为T Ptr为T*typedef ListIteratorT, Ref, Ptr Self;//解引用Ref operator*(){assert(_P ! _pNode);return _pNode-_val;}//该运算符重载的意义为T为自定义类型时使用迭代器可以通过该运算符直接访问自定义类型成员Ptr operator-(){return (_pNode-_val);}//前置Self operator(){_pNode _pNode-_pNext;return *this;}//后置Self operator(int){Self tmp(_pNode);_pNode _pNode-_pNext;return tmp;}//前置--Self operator--(){_pNode _pNode-_pPre;return *this;}//后置--Self operator--(int){Self tmp(_pNode);_pNode _pNode-_pPre;return tmp;}//比较bool operator!(const Self l){return l._pNode ! _pNode;}bool operator(const Self l){return l._pNode _pNode;}获取成员变量函数 //获取该迭代器成员变量PNode get(){return _pNode;}ListIterator类一览
//Ref为T Ptr为T*
templateclass T, class Ref, class Ptr
class ListIterator
{typedef ListNodeT* PNode;typedef ListIteratorT, Ref, Ptr Self;
public://构造函数 获取一个结点指针ListIterator(const PNode pNode nullptr, const PNode const P nullptr) :_pNode(pNode),_P(P){}Ref operator*(){assert(_P ! _pNode);return _pNode-_val;}Ptr operator-(){return (operator*());}Self operator(){_pNode _pNode-_pNext;return *this;}Self operator(int){Self tmp(_pNode);_pNode _pNode-_pNext;return tmp;}Self operator--(){_pNode _pNode-_pPre;return *this;}Self operator--(int){Self tmp(_pNode);_pNode _pNode-_pPre;return tmp;}bool operator!(const Self l){return l._pNode ! _pNode;}bool operator(const Self l){return l._pNode _pNode;}PNode get(){return _pNode;}
private:PNode _pNode;PNode _P;
};
};(2)反向迭代器类 与正向迭代器不一样的有 * 操作符_pNode保存的是有效元素的下一个位置如想要的是_pNode-_pPre指向的元素但是该迭代器保存的是_pNode的指针还有–与正向迭代器相反。 其他操作与正向迭代器一致。
templateclass T, class Ref, class Ptr
class Reverse_ListIterator
{typedef ListNodeT* PNode;typedef Reverse_ListIteratorT, Ref, Ptr Self;
public:Reverse_ListIterator(const PNode pNode nullptr, const PNode const P nullptr) :_pNode(pNode), _P(P){}Ref operator*(){assert(_P ! _pNode -_pPre);return _pNode-_pPre-_val;}Ptr operator-(){return (operator*());}Self operator(){_pNode _pNode-_pPre;return *this;}Self operator(int){Self tmp(_pNode);_pNode _pNode-_pPre;return tmp;}Self operator--(){_pNode _pNode-_pNext;}Self operator--(int){Self tmp(_pNode);_pNode _pNode-_pNext;return tmp;}bool operator!(const Self l){return l._pNode ! _pNode;}bool operator(const Self l){return l._pNode _pNode;}PNode get(){return _pNode;}
private:PNode _pNode;PNode _P;
};
(3)list迭代器接口
//一些类型的重命名typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T* const_iterator;typedef Reverse_ListIteratorT, T, T* reverse_iterator;typedef Reverse_ListIteratorT, const T, const T* reverse_const_iterator;// List Iterator//第一个有效元素位置的迭代器
iterator begin()
{return iterator(_pHead-_pNext,_pHead);
}
//最后一个有效元素位置的下一个位置的迭代器
iterator end()
{return iterator(_pHead,_pHead);
}
//加了const 修饰
const_iterator begin() const
{return const_iterator(_pHead-_pNext,_pHead);
}
const_iterator end()const
{return const_iterator(_pHead,_pHead);
}//反向迭代器
//哨兵位的位置reverse_iterator rbegin(){return reverse_iterator(_pHead,_pHead);}
//第一个有效元素位置reverse_iterator rend(){return reverse_iterator(_pHead -_pNext,_pHead);}
//加了const修饰reverse_const_iterator rbegin() const{return reverse_const_iterator(_pHead,_pHead);}reverse_const_iterator rend()const{return reverse_const_iterator(_pHead-_pNext,_pHead);}2、常用删除、插入接口
(1)insert 在迭代器位置前插入一个结点。
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T val)
{//创造一个结点PNode tmp new Node(val);//获取迭代器中的指针PNode _pos pos.get();//进行插入PNode prv _pos-_pPre;prv-_pNext tmp;tmp-_pPre prv;tmp-_pNext _pos;_pos-_pPre tmp;//返回新迭代器return iterator(tmp);
}迭代器是否失效 因为插入新的结点不会影响到原来的结点所以该迭代器不会失效。
(2)erase 删除迭代器位置结点。
// 删除pos位置的节点返回该节点的下一个位置
iterator erase(iterator pos)
{//判断是否为哨兵位结点iterator it end();assert(pos ! it);//获取迭代器结点指针PNode tmp pos.get();//进行删除PNode next tmp-_pNext;PNode prv tmp-_pPre;prv-_pNext next;next-_pPre prv;delete tmp;tmp nullptr;//返回被删除结点的下一个位置的结点迭代器return iterator(next);
}迭代器是否失效 因为将结点删除了所以原本的迭代器是不能使用的所以迭代器失效了。
(3)push_back、pop_back、push_front、pop_front 这里的头插、尾插、头删、尾删均复用上面两个函数接口。
void push_back(const T val) { insert(end(), val); }
void pop_back() { erase(--end()); }
void push_front(const T val) { insert(begin(), val); }
void pop_front() { erase(begin()); }3、常用其他的一些函数接口
(1)size 返回大小通过遍历链表即可找到。
size_t size()const
{//保存哨兵位的下一个位置PNode tmp _pHead-_pNext;//开始遍历size_t count 0;while (tmp ! _pHead){tmp tmp-_pNext;count;}return count;
}(2)empty 是否为空判断哨兵位结点是否指向自己即可。
bool empty()const
{return _pHead _pHead-_pNext;
}(3)clear 清空链表遍历链表逐个清空保留哨兵位结点再让哨兵位结点自己连接自己。 void clear(){//保存有效结点位置PNode tmp _pHead-_pNext;//遍历删除while (tmp ! _pHead){PNode p tmp-_pNext;delete tmp;tmp p;}//重新指向_pHead-_pNext _pHead;_pHead-_pPre _pHead;
(4)swap 交换只需要交换指向哨兵位结点的指针即可。
void swap(listT l)
{std::swap(_pHead, l._pHead);
}(4)front 获取第一个位置的元素。
T front()
{assert(!empty());return _pHead-_pNext-_val;
}
const T front()const
{assert(!empty());return _pHead-_pNext-_val;
}(5)back 获取最后一个位置元素。
T back()
{assert(!empty());return _pHead-_pPre-_val;
}
const T back()const
{assert(!empty());return _pHead-_pPre-_val;
}4、默认成员函数
(1)构造函数 构造函数都会先进行构造哨兵位结点再进行下面的操作除了无参构造其他都复用了尾插将元素尾插到链表结尾。
//无参构造
list()
{ //构造一个哨兵位结点CreateHead();
}//利用n个val值进行构造
list(int n, const T value T())
{//构造一个哨兵位结点CreateHead();//将元素尾插入while (n ! 0){push_back(value);--n;}
}//这里用迭代器区间构造重写一个模板使其可以使用其他容器的迭代器
template class Iterator
list(Iterator first, Iterator last)
{//构造一个哨兵位结点CreateHead();//将元素尾插入while (first ! last){push_back(*first);first;}
}//拷贝构造
list(const listT l)
{//构造一个哨兵位结点CreateHead();//遍历将元素尾插入PNode tmp l._pHead-_pNext;while (tmp ! l._pHead){push_back(tmp-_val);tmp tmp-_pNext;}
}(2)重载赋值运算符 通过传值传参构造一个临时容器 l ,再将其与原来的容器交换当出了函数作用域之后临时容器就会调用析构函数对临时容器的资源进行清理(就是原来容器的资源)。
listT operator(listT l)
{//与临时变量进行交换swap(l);return *this;
}(3)析构函数 对链表清理。
~list()
{//清空链表clear();//删除哨兵位结点delete _pHead;_pHead nullptr;
}三、总代码
#pragma once
#includeiostream
#includeassert.h
#includestring
using namespace std;namespace xu
{// List的结点类templateclass Tstruct ListNode{ListNodeT* _pPre; //后继指针ListNodeT* _pNext; //前驱指针T _val; //数据//构造结点ListNode(const T val T()) :_val(val), _pPre(nullptr), _pNext(nullptr){}};//List的正向迭代器类//Ref为T Ptr为T*templateclass T, class Ref, class Ptrclass ListIterator{typedef ListNodeT* PNode;typedef ListIteratorT, Ref, Ptr Self;public://构造函数 获取一个结点指针ListIterator(PNode pNode nullptr) :_pNode(pNode){}Ref operator*(){return _pNode-_val;}Ptr operator-(){return (operator*());}Self operator(){_pNode _pNode-_pNext;return *this;}Self operator(int){Self tmp(_pNode);_pNode _pNode-_pNext;return tmp;}Self operator--(){_pNode _pNode-_pPre;return *this;}Self operator--(int){Self tmp(_pNode);_pNode _pNode-_pPre;return tmp;}bool operator!(const Self l){return l._pNode ! _pNode;}bool operator(const Self l){return l._pNode _pNode;}PNode get(){return _pNode;}private:PNode _pNode;};//List的反向迭代器类templateclass T, class Ref, class Ptrclass Reverse_ListIterator{typedef ListNodeT* PNode;typedef Reverse_ListIteratorT, Ref, Ptr Self;public:Reverse_ListIterator(PNode pNode nullptr) :_pNode(pNode){}Ref operator*(){return _pNode-_pPre-_val;}Ptr operator-(){return (operator*());}Self operator(){_pNode _pNode-_pPre;return *this;}Self operator(int){Self tmp(_pNode);_pNode _pNode-_pPre;return tmp;}Self operator--(){_pNode _pNode-_pNext;}Self operator--(int){Self tmp(_pNode);_pNode _pNode-_pNext;return tmp;}bool operator!(const Self l){return l._pNode ! _pNode;}bool operator(const Self l){return l._pNode _pNode;}PNode get(){return _pNode;}private:PNode _pNode;};//list类templateclass Tclass list{typedef ListNodeT Node;typedef Node* PNode;public:typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T* const_iterator;typedef Reverse_ListIteratorT, T, T* reverse_iterator;typedef Reverse_ListIteratorT, const T, const T* reverse_const_iterator;public://默认构造list() { //构造一个哨兵位结点CreateHead(); }list(int n, const T value T()){//构造一个哨兵位结点CreateHead();//将元素尾插入while (n ! 0){push_back(value);--n;}}template class Iteratorlist(Iterator first, Iterator last){//构造一个哨兵位结点CreateHead();//将元素尾插入while (first ! last){push_back(*first);first;}}list(const listT l){//构造一个哨兵位结点CreateHead();//遍历将元素尾插入PNode tmp l._pHead-_pNext;while (tmp ! l._pHead){push_back(tmp-_val);tmp tmp-_pNext;}}listT operator(listT l){//与临时变量进行交换swap(l);return *this;}~list(){//清空链表clear();//删除哨兵位结点delete _pHead;_pHead nullptr;}///// List Iteratoriterator begin(){return iterator(_pHead-_pNext);}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(_pHead-_pNext);}const_iterator end()const{return const_iterator(_pHead);}reverse_iterator rbegin(){return reverse_iterator(_pHead);}reverse_iterator rend(){return reverse_iterator(_pHead -_pNext);}reverse_const_iterator rbegin() const{return reverse_const_iterator(_pHead);}reverse_const_iterator rend()const{return reverse_const_iterator(_pHead-_pNext);}///// List Capacitysize_t size()const{PNode tmp _pHead-_pNext;size_t count 0;while (tmp ! _pHead){tmp tmp-_pNext;count;}return count;}bool empty()const{return _pHead _pHead-_pNext;}// List AccessT front(){assert(!empty());return _pHead-_pNext-_val;}const T front()const{assert(!empty());return _pHead-_pNext-_val;}T back(){assert(!empty());return _pHead-_pPre-_val;}const T back()const{assert(!empty());return _pHead-_pPre-_val;}// List Modifyvoid push_back(const T val) { insert(end(), val); }void pop_back() { erase(--end()); }void push_front(const T val) { insert(begin(), val); }void pop_front() { erase(begin()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){//创造一个结点PNode tmp new Node(val);//获取迭代器中的指针PNode _pos pos.get();//进行插入PNode prv _pos-_pPre;prv-_pNext tmp;tmp-_pPre prv;tmp-_pNext _pos;_pos-_pPre tmp;//返回新迭代器return iterator(tmp);}// 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos){//判断是否为哨兵位结点iterator it end();assert(pos ! it);//获取迭代器结点指针PNode tmp pos.get();//进行删除PNode next tmp-_pNext;PNode prv tmp-_pPre;prv-_pNext next;next-_pPre prv;delete tmp;tmp nullptr;//返回被删除结点的下一个位置的结点迭代器return iterator(next);}void clear(){//保存有效结点位置PNode tmp _pHead-_pNext;//遍历删除while (tmp ! _pHead){PNode p tmp-_pNext;delete tmp;tmp p;}//重新指向_pHead-_pNext _pHead;_pHead-_pPre _pHead;}void swap(listT l){std::swap(_pHead, l._pHead);}private://让哨兵位结点指向自己void CreateHead(){_pHead new Node;_pHead-_pNext _pHead;_pHead-_pPre _pHead;}PNode _pHead; //哨兵位结点};};
文章转载自： http://www.morning.xqknl.cn.gov.cn.xqknl.cn http://www.morning.qxlhj.cn.gov.cn.qxlhj.cn http://www.morning.cfynn.cn.gov.cn.cfynn.cn http://www.morning.rbgqn.cn.gov.cn.rbgqn.cn http://www.morning.bzqnp.cn.gov.cn.bzqnp.cn http://www.morning.gsjfn.cn.gov.cn.gsjfn.cn http://www.morning.rwjtf.cn.gov.cn.rwjtf.cn http://www.morning.pigcamp.com.gov.cn.pigcamp.com http://www.morning.kmcby.cn.gov.cn.kmcby.cn http://www.morning.fgppj.cn.gov.cn.fgppj.cn http://www.morning.lpmlx.cn.gov.cn.lpmlx.cn http://www.morning.wpsfc.cn.gov.cn.wpsfc.cn http://www.morning.qphcq.cn.gov.cn.qphcq.cn http://www.morning.wlxfj.cn.gov.cn.wlxfj.cn http://www.morning.gryzk.cn.gov.cn.gryzk.cn http://www.morning.bmnm.cn.gov.cn.bmnm.cn http://www.morning.ztfzm.cn.gov.cn.ztfzm.cn http://www.morning.qdmdp.cn.gov.cn.qdmdp.cn http://www.morning.qkdcb.cn.gov.cn.qkdcb.cn http://www.morning.mwqbp.cn.gov.cn.mwqbp.cn http://www.morning.ggtkk.cn.gov.cn.ggtkk.cn http://www.morning.npmcf.cn.gov.cn.npmcf.cn http://www.morning.nbsbn.cn.gov.cn.nbsbn.cn http://www.morning.fqtzn.cn.gov.cn.fqtzn.cn http://www.morning.wgcng.cn.gov.cn.wgcng.cn http://www.morning.dtpqw.cn.gov.cn.dtpqw.cn http://www.morning.kdnbf.cn.gov.cn.kdnbf.cn http://www.morning.knzmb.cn.gov.cn.knzmb.cn http://www.morning.wctqc.cn.gov.cn.wctqc.cn http://www.morning.hsdhr.cn.gov.cn.hsdhr.cn http://www.morning.dnphd.cn.gov.cn.dnphd.cn http://www.morning.dwfxl.cn.gov.cn.dwfxl.cn http://www.morning.yrmpr.cn.gov.cn.yrmpr.cn http://www.morning.qbzdj.cn.gov.cn.qbzdj.cn http://www.morning.dxgt.cn.gov.cn.dxgt.cn http://www.morning.rqhbt.cn.gov.cn.rqhbt.cn http://www.morning.yzxlkj.com.gov.cn.yzxlkj.com http://www.morning.xznrk.cn.gov.cn.xznrk.cn http://www.morning.bqpgq.cn.gov.cn.bqpgq.cn http://www.morning.c7617.cn.gov.cn.c7617.cn http://www.morning.wsxxq.cn.gov.cn.wsxxq.cn http://www.morning.jrksk.cn.gov.cn.jrksk.cn http://www.morning.rzysq.cn.gov.cn.rzysq.cn http://www.morning.pzpj.cn.gov.cn.pzpj.cn http://www.morning.ntqlz.cn.gov.cn.ntqlz.cn http://www.morning.jmdpp.cn.gov.cn.jmdpp.cn http://www.morning.gbrps.cn.gov.cn.gbrps.cn http://www.morning.rhsr.cn.gov.cn.rhsr.cn http://www.morning.znrgq.cn.gov.cn.znrgq.cn http://www.morning.nsppc.cn.gov.cn.nsppc.cn http://www.morning.rsmtx.cn.gov.cn.rsmtx.cn http://www.morning.ljsxg.cn.gov.cn.ljsxg.cn http://www.morning.yfzld.cn.gov.cn.yfzld.cn http://www.morning.qcdtzk.cn.gov.cn.qcdtzk.cn http://www.morning.jljiangyan.com.gov.cn.jljiangyan.com http://www.morning.gcqkb.cn.gov.cn.gcqkb.cn http://www.morning.zlgbx.cn.gov.cn.zlgbx.cn http://www.morning.zkqjz.cn.gov.cn.zkqjz.cn http://www.morning.cxlys.cn.gov.cn.cxlys.cn http://www.morning.nnpwg.cn.gov.cn.nnpwg.cn http://www.morning.rgmls.cn.gov.cn.rgmls.cn http://www.morning.plzgt.cn.gov.cn.plzgt.cn http://www.morning.cwqrj.cn.gov.cn.cwqrj.cn http://www.morning.rhkq.cn.gov.cn.rhkq.cn http://www.morning.ndlww.cn.gov.cn.ndlww.cn http://www.morning.leeong.com.gov.cn.leeong.com http://www.morning.qcsbs.cn.gov.cn.qcsbs.cn http://www.morning.qlsyf.cn.gov.cn.qlsyf.cn http://www.morning.nhgfz.cn.gov.cn.nhgfz.cn http://www.morning.fllfc.cn.gov.cn.fllfc.cn http://www.morning.dqdss.cn.gov.cn.dqdss.cn http://www.morning.ndnhf.cn.gov.cn.ndnhf.cn http://www.morning.qxmpp.cn.gov.cn.qxmpp.cn http://www.morning.rkkpr.cn.gov.cn.rkkpr.cn http://www.morning.fxzw.cn.gov.cn.fxzw.cn http://www.morning.qwwcf.cn.gov.cn.qwwcf.cn http://www.morning.jcfg.cn.gov.cn.jcfg.cn http://www.morning.nrqtk.cn.gov.cn.nrqtk.cn http://www.morning.rqgq.cn.gov.cn.rqgq.cn http://www.morning.nthyjf.com.gov.cn.nthyjf.com
