营销型网站建设极速建站,建设网站书籍pdf,做小程序商城,云服务器一年多少钱目录 一#xff0c;实现list所需要包含的三个类
二#xff0c;三个类的实现
1.list_node
2.list类 3.iterator_list类
三#xff0c;功能实现
1.list类里的push_back() 2.iterator类里的运算符重载
3#xff0c;list类里面的功能函数
1.insert#xff08;#xff… 目录 一实现list所需要包含的三个类
二三个类的实现
1.list_node
2.list类 3.iterator_list类
三功能实现
1.list类里的push_back() 2.iterator类里的运算符重载
3list类里面的功能函数
1.insert
2.erase()函数
3.clear()与析构函数
4.拷贝构造函数赋值运算符重载
5.打印函数 一实现list所需要包含的三个类 因为list是一个带头双向循环链表。所以list的实现会比较的复杂一些。总得来说实现一个双向带头循环链表需要构造三个类。1.list类2.list_node类3.list_iterator类。前两个类相信大家会比较的熟悉。第三个类大家会比较不熟悉因为它是一个迭代器的类。也就是说这个类是迭代器的封装。它的实现很有价值因为它能让我们在使用list时也可以像之前的数据结构一样方便。 二三个类的实现
1.list_node 这首先要实现的便是节点类。这个类是最容易实现的。这个类的作用便是给要产生的节点画一个图定义一下这个节点的结构和类型。代码如下 templateclass T//模板struct list_node{list_node(const T val T()//匿名对象 )//构造函数起初始化的作用:val(val), prev(nullptr), next(nullptr){}T val;list_nodeT* prev;list_nodeT* next;}; 现在你看到了这个节点的结构便是这样。其实这与之前实现的那个带头双向循环链表的结构差不多。不过在cpp中引入了模板的概念所以这个节点便可以调用模板参数来进行泛化。 2.list类 list类的定义可太简单了。list的成员变量只有一个参数便是_head。这是哨兵位的头节点。当然还有一个无参的构造函数和一个功能函数。代码如下 templateclass Tclass list{ public:typedef list_nodeT Node;void empty()//初始化功能函数。{_head new Node;_head-prev _head;_head-next _head;}list()//构造函数{empty();}private:Node* _head;}; 当然这里的list类也是要用模板来进行泛化的。 3.iterator_list类 这个类就算是比较复杂的一个类了。因为迭代器要实现两种重载版本1.普通版本。2.const版本。所以迭代器类的模板参数会有三个 template class T, class Ref, class ptr 这三个模板参数会重载两种版本的三个参数T对象TT指针类型。在这个类里面也只有一个成员_node。类型与list类里面的成员类型相同。该类代码如下 template class T, class Ref, class ptrstruct iterator_list{typedef list_nodeT Node;iterator_list(Node* node):_node(node){}Node* _node;}; 三功能实现
1.list类里的push_back() 首先来实现一个push_back()函数这个函数的作用便是实现尾插数据。逻辑十分简单代码如下 void push_back(const T val){Node* newnode new Node(val);Node* tail _head-prev;tail-next newnode;newnode-prev tail;newnode-next _head;_head-prev newnode;} 写完这个以后我便想要通过显示list里的数据来验证答案但是很显然我们做不到。因为list是一个自定义的类。但是我们有办法所以我们便可以通过iterator来达到这个目的。所以我们必须在iterator类里面实现几个运算符重载。 2.iterator类里的运算符重载 首先先实先这三个运算符重载1.*2.3. 代码如下 Ref operator *()//Ref代表T{return _node-val;}self operator(){_node _node-next;return *this;}bool operator!(self it){return _node ! it._node;} 然后再在list类里面实现begin()与end()函数之后便可以实现范围for的使用了end与begin代码如下 //实现两个版本的begin与enditerator begin(){return _head-next;}iterator end(){return _head;}const_iterator begin()const{return _head-next;}const_iterator end()const{return _head;} 在实现了上面的代码以后为了让迭代器的功能更加全面那我们再实现几个函数重载。再iterator_list里面的全部运算符重载如下 Ref operator *(){return _node-val;}self operator()//前置{_node _node-next;return *this;}self operator(int)//后置{Node* tmp(*this);_node _node-next;return tmp;}self operator --()//前置--{_node _node-prev;return *this;}self operator--(int)//后置--{Node* tmp(*this);_node _node-prev;return tmp;}bool operator!(const self it)//若用引用便要加上const{return _node ! it._node;}bool operator(self it){return _node it._node;}self operator(int n){while (n){_node _node-next;n--;}return *this;}ptr operator-()//箭头解引用{return _node-val;}在实现了这些运算符重载以后list类里面的功能函数便好写了许多。 3list类里面的功能函数
1.insert 这个函数实现的功能便是在pos位置之前插入一个新的节点。这个pos的类型是迭代器类型。在list类里边的迭代器重定义为 typedef iterator_listT, T ,T* iterator;
typedef iterator_listT, const T, const T* const_iterator;我们只需要关注第一个迭代器即可因为第二个迭代器修饰的对象是不可以修改的。所以insert的实现代码如下 iterator insert(iterator pos, const T x)//在pos位置之前插入新节点{Node* newnode new Node(x);Node* prev pos._node-prev;prev-next newnode;newnode-prev prev;newnode-next pos._node;pos._node-prev newnode;return pos._node-prev;//防止迭代器失效所以返回pos的前一个位置} 检验一下检验代码如下 void test_list2(){listint l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);for (auto e : l1){cout e ;}cout endl;l1.insert(l1.begin(), 9);l1.insert(l1.end(), 99);for (auto e : l1){cout e ;}cout endl;} 结果正确 在实现了insert函数以后便可以复用实现push_back()与push_front()。代码如下 void push_back(const T val){insert(begin(), val);}void push_front(const T val){insert(end(), val);} 2.erase()函数 erase()函数实现的功能便是传入一个位置然后将该位置上的节点删除掉。代码实现如下 iterator erase(iterator pos){Node* prev pos._node-prev;Node* next pos._node-next;Node* cur pos._node;delete cur;prev-next next;next-prev prev;return iterator(next);//返回新的迭代器} 复用erase实现尾删与头删代码如下 void pop_back(){erase(--end());//尾巴是--end()的位置}void pop_front(){erase(begin());} 实验代码 void test_list3(){listint l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);for (auto e : l1){cout e ;}cout endl;l1.insert(l1.begin(), 9);l1.insert(l1.end(), 99);for (auto e : l1){cout e ;}cout endl;l1.pop_back();l1.pop_front();for (auto e : l1){cout e ;}cout endl;} 结果正确 3.clear()与析构函数 实现了erase()函数以后再接再厉接着复用实现clear函数代码如下 void clear(){iterator it begin();while (it ! end()){it erase(it);//erase()每次都会返回下一个位置}} 从上面代码的逻辑便可以看出clear()函数是不会删除掉头节点的。但是析构函数需要。于是复用clear()函数后析构函数代码如下 ~list(){clear();delete _head;} 4.拷贝构造函数赋值运算符重载 拷贝构造函数实现过程大概分三步首先new出来一个空间。然后再复用push_back()函数将要赋值的数据拷贝到新节点内。实现代码如下 list(const listT l1){empty();for (auto e : l1){push_back(e);}} 实现了拷贝构造以后按照惯例赋值也要被安排上了。赋值运算符重载实现代码如下 listT operator ( listT l1){if (this! l1){clear();for (auto e : l1){push_back(e);}}return *this;} 这是一个传统写法的运算符重载。如果想要更加精简可以写成现代写法代码如下 void swap( listT l1)//别加const{std::swap(_head, l1._head);//记得这个swap是std里面的swap}listT operator(listT l1){if (this ! l1){swap(l1);}return *this;} 5.打印函数 在这里我们每次打印一个list对象时会很麻烦每次都要用范围for来实现打印的功能。为了偷懒我就想实现一个打印函数print来实现打印功能。实现代码如下 templateclass Tvoid print(listT l1){typename listT::iterator it l1.begin();//这里要用typename为前缀来告诉编译器等listT实例化以后再来执行这条语句for (auto e : l1){cout e ;}cout endl;} 但是上面的代码针对的类型时list类的泛型如果想要实现能加载更多容器的print()函数那就得改一下类型改为如下代码 template class Containsvoid print(Contains l1){typename Contains::iterator it l1.begin();for (auto e : l1){cout e ;}cout endl;}
