seo企业建站系统h5技术的网站

当前位置： 首页 > news >正文

seo企业建站系统,h5技术的网站,官方百度下载安装,优化网站工具一.本次所需实现的三个类及其成员函数接口 链表首先要有结点#xff0c;因此我们需要实现一个结点类。 链表要有管理结点的结构#xff0c;因此我们要有list类来管理结点。 链表中还要有迭代器#xff0c;而迭代器的底层其实是指针。但是我们现有的结点类无法完成迭代器的…一.本次所需实现的三个类及其成员函数接口 链表首先要有结点因此我们需要实现一个结点类。 链表要有管理结点的结构因此我们要有list类来管理结点。 链表中还要有迭代器而迭代器的底层其实是指针。但是我们现有的结点类无法完成迭代器的行为因此我们还需要实现一个迭代器类。 因此我们要实现的三个类分别是结点类、迭代器类、链表类。 namespace trousers {templateclass Tstruct _list_node{//初始化_list_node();//变量T data;//数值域_list_nodeT* prev;//前驱指针_list_nodeT* next;//后继指针};//迭代器 //由于list_node无法遍历和支持迭代器因此我们需要手动实现一个迭代器版本//Ref和Ptr分别代表引用和指针类型我们可以用一个类模板重载出两个迭代器版本。迭代器里面需要用到指针和引用一个模板的话不够用templateclass T, class Ref, class Ptrstruct _list_iterator{typedef _list_nodeT node;typedef _list_iteratorT,Ref,Ptr self;self operator();self operator(int);self operator–();self operator–(int);Ref operator*();Ptr operator-();//_pnode-_val operator-(this)-_valself operator(const self t)constself operator!(const self t)const//变量node _pnode;};//链表template class Tclass list{public:typedef _list_nodeT node;typedef _list_iteratorT,T,T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;//默认成员函数list();list(const listT lt);listT operator(const listT lt);~list();//迭代器相关函数iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;//访问容器相关函数T front();T back();const T front() const;const T back() const;//插入、删除函数void insert(iterator pos, const T x);iterator erase(iterator pos);void push_back(const T x);void pop_back();void push_front(const T x);void pop_front();//其他函数size_t size() const;void resize(size_t n, const T val T());void clear();bool empty() const;void swap(listT lt);//私有变量private:node* _head;//指向哨兵位}; }二.结点类的模拟实现 list的底层其实是一个带头双向循环链表。 因此我们需要实现的结点类中需要的成员为数据、前一个结点的指针、后一个结点的指针。 对于该类而言我们不需要在类中完成任何行为因此我们仅仅只需要实现一个构造函数即可。而该类由于都是内置成员因此我们的析构函数可以由编译器生成。 2.1结点类的构造函数 结点类的构造函数实现起来是比较简单的我们仅仅需要将val置想要的值并将两个指针置空即可。 _list_node(const T dataT()):_data(),_prev(nullptr),_next(nullptr){} 三.迭代器类的模拟实现 3.1迭代器的设计思路 在实现了结点类之后我们就要开始实现迭代器类了。 由于我们无法通过只有一个参数的类模板实现const和非const的两个迭代器 因此我们这里的类模板有三个参数。 templateclass T, class Ref, class Ptr其中的Ref表示引用Ptr表示解引用。  3.2迭代器类存在的意义 在之前实现string和vector的时候我们都不需要实现一个迭代器类为什么实现list的时候就需要实现一个迭代器类了呢 这是因为string和vector对象都将数据存储在了一块连续的内存空间我们通过指针操纵空间从而完成自增、自减、解引用等操作然后就可以对数据进行一系列的操作因此string和vector当中的迭代器就是原生的指针。 但是对于list而言各个结点在内存中的分布并不连续因此我们不能通过对结点的自增自减等操作来完成迭代器的行为。 而迭代存在的意义就是让使用者不必关心底层的实现可以用简单统一的方式对容器内的数据进行访问。 既然list的结点指针的行为不满足迭代器的定义那么我们就需要对结点指针进行封装对结点指针的各个运算符进行重载使得其支持像vector、string中的迭代器一样的操作。 举个例子我们在用list的自增行为时实际上是执行了pp-next语句。 总结list的迭代器类实际上只是对结点的指针进行了封装并对其各个操作符进行了重载使得结点指针的各种行为看起来和普通指针一样。 3.3构造函数 迭代器类的构造函数实际上是对结点指针进行了封装而已其成员变量只有一个结点的指针因此我们的构造函数直接根据所给的结点指针构造出一个迭代器对象即可。 _list_iterator(node* pnode):_pnode(pnode){} 3.4运算符的重载 3.4.1前置操作符 对于前置操作符我们的实现思路非常简单直接将结点指针指向next然后返回自增后的结果即可。 self operator(){_pnode _pnode-_next;return *this;} 3.4.2后置操作符 对于后置操作符我们采取使用一个临时变量记录该结点的方式对结点指针完成自增并返回临时变量即可。 self operator(int){self tmp(*this);_pnode _pnode-_next;return tmp;} 3.5–运算符的重载 –操作符的逻辑和操作符的逻辑基本上是一样的只不过是将自身修改为prev而不是next。 self operator–(){_pnode _pnode-_prev;return *this;}self operator–(int){self tmp(*this);_pnode _pnode-_prev;return tmp;} 3.6运算符的重载 在使用迭代器遍历时难免会比较两个迭代器是否相同因此我们还需要实现操作符。 而两个迭代器是否相同实际上就是判断这两个迭代器是不是同一个位置上的迭代器因此我们只需要比较这两个迭代器的地址即可。 bool operator(const self t)const{return _pnode t._pnode;} 3.7!运算符的重载 操作符和操作符的作用相反我们要判断的是这两个迭代器的地址是不是不同。 bool operator!(const self t)const{return _pnode ! t._pnode;} 3.8*运算符的重载 当我们使用操作符时其实就是想要得到这个地址的数据因此我们直接返回当前指针数据所指向的数据即可但由于我们可能会通过解引用修改数据因此我们这里可以返回引用。 Ref operator(){return _pnode-_data;} 3.9-运算符的重载 在一些场景下我们可能还会使用到-操作符。 譬如如下场景 当list容器内的每个结点存储的是自定义类型时那么当我们拿到一个位置的迭代器我们可能还会通过-操作符来访问该类型内部的成员。 如下例 listvector d; vectorint v1 { 1,2,3 }; vectorint v2 { 4,5,6 }; vectorint v3 (3,5); d.push_back(v1); d.push_back(v2); d.push_back(v3); list vector::iterator pos it.begin(); cout pos-size() endl; 因此有些情况下我们会使用到-操作符。 对于-操作符的重载我们直接返回结点当中所存储数据的地址即可。 Ptr operator-()//_pnode-_val operator-(this)-_val{//(*this)-_data;return (_node-_data);} 说到这里你可能会觉得有些不对按照这种重载方式的话我们似乎需要两个-才能调到我们想要的数据也就是这样 因为内部的this是被省略的因此我们实际上写应该是这样的 但是一个地方出现两个箭头的可读性有些过于差劲了因此编译器在这里做了一些特殊的处理省略了一个箭头也就是我们所写的版本。 四.list的模拟实现 4.1默认成员函数 4.1.1构造函数 list是一个带头双向循环链表因此在构造一个list对象时直接申请一个头节点并让前驱指针和后继指针都指向自己即可。 list(){_head new node;_head-_next _head;_head-_prev _head;} 4.2.2拷贝构造函数 拷贝构造函数我们需要先申请一个结点然后申请一个头结点之后我们再将原list链表一个一个通过尾插拷贝过去即可。 list(const listT lt){_head new node;_head-_next _head;_head-_prev _head;for (const auto e : lt){push_back(e);}} 4.2.3赋值运算符重载函数 赋值运算符重载和拷贝构造的实现方式是类似的我们可以先将被赋值的链表清空然后一个一个通过尾插拷贝过去。 listT operator(const listT lt){if (this ! lt)//防止自己给自己赋值以避免性能浪费{clear();for (const auto e : lt){push_back(e);}}return *this;} 但是这种写法过于繁琐我们也可以换一种思路我们不采取引用传参那么我们将会传入一个形参之后我们和形参进行交换即可完成任务而当我们的函数运行结束后还会自动销毁掉形参。 listT operator(const listT lt)//编译器接受右值时自动调用其拷贝构造函数构造出形参。{swap(lt);return *this;} 4.2.4析构函数 对于析构函数我们首先使用clear清理一下容器内的数据然后将头结点释放之后再将指针置空即可。 ~list(){clear();delete _head;_head nullptr;} 五.迭代器相关函数 begin和end begin是返回第一个有效数据的迭代器因此我们要返回头节点的下一个结点 iterator begin(){return iterator(_head-_next);} 这里需要大家注意的是我们要返回迭代器而不是结点指针因此我们需要用迭代器的构造函数构造出指向同一块空间的迭代器类型的匿名变量用于返回。  end是返回最后一个有效数据的后一个数据的迭代器在双向循环链表中要返回的是头结点 iterator end(){return iterator(_head);} 当然除了这两个之外我们还需要实现两个const版本的函数 const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);} 六.访问容器相关函数 6.1front和back front返回第一个有效数据back返回最后一个有效数据因此我们在实现front和back函数时直接返回第一个有效数据的引用和最后一个有效数据的引用即可。 T front(){return *begin();}T back(){return *(–end());} 除此之外我们还需要重载一对用于const对象的front和back函数。 const T front() const{return *begin();//我们已经重载了解引用}const T back() const{return (–end());} 6.2插入、删除函数 6.2.1insert 对于insert函数我们是这样写的 首先检查一下插入位置的合法性。然后用要插入的数据新建一个结点。然后记录下要插入位置处结点的指针之后建立节点之间的双向关系 void insert(iterator pos, const T x){assert(pos._pnode);node newnode new node(x);node* cur pos._pnode;node* prev cur-_prev;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;prev-_next newnode;} 6.2.2erase erase可以删除所给的迭代器位置的结点。 实现思路为 先根据迭代器得到该位置处的结点cur然后通过cur找到prev和next指针之后删掉cur并建立prev和next之间的双向关系。返回next位置 iterator erase(iterator pos){assert(pos._pnode);assert(pos ! end());node* cur pos._pnode;node* prev cur-_prev;node* next cur-_next;delete cur;prev-_next next;next-_prev prev;return iterator(next);} 6.2.3对头尾的插入和删除函数 我们直接复用insert和erase即可。 void push_back(const T x){insert(end(), x);}void pop_back(){erase(–end());}void push_front(const T x){insert(begin(), x);}void pop_front(){erase(begin());} 七.其他函数 7.1size 对于size函数我们可以通过迭代器的遍历获取个数。 size_t size() const{size_t sz 0;const_iterator it begin();while (it ! end()){it;sz;}return sz;} 除了这个方法外还有一个方法可以获取到个数。 我们可以多设置一个私有成员size在插入逻辑中每插入一个则size1在删除逻辑中每删除一个则size-1。这样也可以获取到size 的个数。 7.2resize resize函数规则 若当前容器的size小于所给n则尾插结点直到size等于n若当前容器的size大于所给n则只保留前n个有效数据。 那么如何实现resize函数呢 首先我们定义一个len表示链表的长度遍历到结尾后比较len和n的大小若len较大则删除掉多余的结点若len较小则尾插数值为x的结点。 void resize(size_t n, const T val T()){iterator it begin();size_t len 0;while (it ! end()){it;len;}while (len n){push_back(val);len;}while (len n){pop_back();len–;}} 7.3clear 对于clear函数我们需要做的是清空链表的有效数据。 因此我们逐个删除掉链表的结点只保留头节点即可。 void clear(){iterator itbegin();while (it ! begin()){it erase(it);//防止迭代器失效}} 7.4empty empty函数是判空的我们有很多种方法判断链表是否为空。 这里我们通过判断该容器的begin函数和end函数所返回的迭代器是否相同来进行判断。如果相同则代表只有一个头结点 bool empty() const{return begin() end();} 7.5swap swap函数用于交换两个容器在list容器当中存储的实际上只有头结点的指针因此我们只要交换一下头节点的指针即可。 void swap(listT lt){::swap(_head, lt._head);} 注意点在此处调用的swap是库中的swap我们在swap前面加上域作用限定符即可告诉编译器优先在全局范围内寻找swap函数。