德清网站公司建设,做水产有什么网站,网站写文案,公司宣传网站建设前面的文章中#xff0c;介绍了#xff0c;的模拟实现#xff0c;本篇文章将介绍对于的模拟实现。
目录
1. list的基本结构#xff1a; 2. list功能实现#xff1a;尾部插入元素#xff1a;
3. list迭代器的实现#xff1a;
4. list功能实现#xff1a;在任意位置前…前面的文章中介绍了的模拟实现本篇文章将介绍对于的模拟实现。
目录
1. list的基本结构 2. list功能实现尾部插入元素
3. list迭代器的实现
4. list功能实现在任意位置前插入元素
4.1 函数实现方法
4.2 函数运行逻辑
5. list功能实现删除任意位置的结点
6. 拷贝构造与赋值重载
7. list功能实现clear与析构函数 1. list的基本结构
对于可以将其看作数据结构中的双向带头循环链表一起学数据结构4——带头结点的双向循环链表_带头结点的双循环链表-CSDN博客
针对于双向带头循环链表其基本构成单元为如下图所示 其中用来保存上一个结点的地址用于保存下一个结点的地址用于保存数据。对于上述结构单元可以由下方的代码表示
namespace violent
{templateclass Tstruct ListNode{ListNodeT* _prev;ListNodeT* _next;T _data;};
}
对于双向带头循环链表其结构可以由下图表示
其中链表的第一个结点称为哨兵位头结点此结点的不用于存储数据只是利用建立其他结点的关系。因此在编写针对于链表单元结构的构造函数时需要考虑到哨兵位头结点。本文将采用隐式类型转换的方式来完成对于构造函数的编写
templateclass Tstruct ListNode{ListNode(const T x T()): _prev(nullptr), _next(nullptr), _data(x){}ListNodeT* _prev;ListNodeT* _next;T _data;}; 对于一个带头双向循环链表结构的实现可以看作是若干个结构单元的相互链接因此在初始化链表结构时只需要在构造函数中完成对于哨兵位头结点的建立以及其内部指针的指向即可即 具体的实现方法就是再创建一个类名为的类将上述表示单个结点结构的类作为一种类型引入到即
templateclass Tclass list{typedef ListNodeT Node;Node* _node;};
通过上述给出的图片可以得到下面的构造函数
class list{typedef ListNodeT Node;public:list(){_phead new Node;_phead-_next _phead;_phead-_prev _phead;}Node* _phead;}; 2. list功能实现尾部插入元素
在插入一个元素之前首先需要创建一个新的结构单元用于保存这个元素例如需要插入的元素为需要提前创建一个名为的结点用于存储该元素即
Node* newnode new Node(x);
当进行插入时即 第一步首先获取链表最后一个结点的地址这里命名为通过上图不难得出.
第二步建立与的联系即,对于此关系的图片表示是如下 最后一步建立与的联系即, 代码实现如下
void push_back(const T x){Node* newnode new Node(x);Node* tail _phead-_prev;tail-_next newnode;newnode-_prev tail;newnode-_next _phead;_phead-_prev newnode;} 3. list迭代器的实现 在中由于这两种数据结构的空间是连续的因此在实现其迭代器功能时通常先利用对指针进行更名使用时直接即可。 但是对于前面说到的结构可以近似的看为链表由于链表的空间不连续因此在使用迭代器进行访问时对迭代器不能达成访问空间中下一个结点的目的。对于来说正确访问下一个结点的访问为通过本结点的获取下一个结点的地址。因此可以考虑使用运算符重载将的运行逻辑从指向连续空间的下一个地址改为通过本结点的访问下一个结点。 但是运算符重载只能针对于自定义类型因为迭代器的实现是依托于指针来完成的。虽然在前面利用创建自定义类型的方式创建了链表中单个结点结构的对象但是需要注意此处运算符重载进行重载的目标并不是这个自定义类型而是这个类型的指针而指针是一个内置类型因此不能直接完成对于指针的重载。而是再创建一个自定义类型用于封装指针在内部进行运算符重载。 对于封装方法首先需要将表示单个结点结构的自定义类型引入到新的类中此处将这个类命名为___。为了方便使用将表示单个结点结构的类重命名为成员变量为类型为的指针。即
templateclass Tstruct __list_iterator{typedef ListNodeT Node;Node* _node;};
对于上述类的初始化如下
templateclass Tstruct __list_iterator{typedef ListNodeT Node;__list_iterator(Node* node): _node(node){}Node* _node;};
为了正常的使用迭代器来完成对于的打印不但需要对于还需要对于和进行重载代码如下
templateclass Tstruct __list_iterator{typedef ListNodeT Node;typedef __list_iteratorT self;__list_iterator(Node* node): _node(node){}self operator(){_node _node-_next;return *this;}self operator(int){self tmp(_node);_node _node-next;return tmp;}T operator*(){return _node-_data;}bool operator!(const self s){return _node ! s._node;}Node* _node;}; 在完成上述步骤后向中引入___再添加两个函数用于表示链表的起始和结束。 需要注意的是在定义链表的起始时并不能定义成哨兵位头结点因为哨兵位头结点并没有保存数据在访问链表时需要从第一个保存数据的结点开始访问。而对于尾结点由于链表是双向循环的。因此可以将不存储任意数据的哨兵位头结点看作尾结点代码如下
typedef __list_iteratorT iterator;iterator begin(){return _phead-_next;}iterator end(){return _phead;} 在完成了上述步骤后就可以使用迭代器对于进行正常的访问例如
void test1(){listint It;It.push_back(1);It.push_back(2);It.push_back(3);It.push_back(4);listint::iterator it1 It.begin();while (it1 ! It.end()){cout *it1 ;it1;}}
代码运行结果如下 4. list功能实现在任意位置前插入元素
4.1 函数实现方法
与尾部插入元素的大致思路相同首先需要创建一个结点来存储这个元素
Node* newnode new Node(x);
例如需要在位置之前插入这个结点首先需要获取位置的前一个结点的地址。但是只是类型为的一个对象需要先创建一个变量来存储中成员变量也就是这个结点的地址通过来获取位置前一个结点的坐标即
Node* cur pos._node;
Node* prev cur-_prev;
在对 这三个位置所代表的结点进行连接即
void insert(iterator pos,const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;}
利用下方的代码对于函数功能进行测试即
It.insert(It.begin(), 5);It.insert(It.begin(), 6);It.insert(It.begin(), 7);It.insert(It.begin(), 8);for (auto e : It){cout e ;}
运行结果如下 4.2 函数运行逻辑
为了更清晰的了解的动作逻辑下面给出函数的整体运行步骤例如对于下方的代码
It.insert(It.begin(), 5);
函数运行的第一步为首先通过函数获取地址 在返回时由于函数的返回类型为自定义类型因此在返回前会去调用___中的构造函数来构造一个临时变量作为返回值即 再获取返回值后跳转到函数中即 最后根据中编写好的代码的顺序进行运行。 在完成了对于函数的编写后对于_函数可以复用从而简化_即
void push_back(const T x){insert(_phead, x);}
同理也可以实现头部插入任意元素_即
void push_front(const T x){insert(_phead-_next, x);} 5. list功能实现删除任意位置的结点
在删除任意位置的结点前首先需要找到这个结点的前结点和后结点的地址为了方便表达用表示前结点的地址用表示后结点的地址。代码如下
iterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;return next;}
在完成了对于的编写后可以通过复用来完成对于头部删除_和尾部删除_代码如下
void pop_back(){erase(_phead-_prev);}void pop_front(){erase(_phead-_next);} 利用下方代码对上述的函数进行测试
It.pop_back();It.pop_back();It.pop_front();It.pop_front();for (auto e : It){cout e ;}
运行结果如下 6. 拷贝构造与赋值重载
list(const listT s){empty();for (auto e : s){push_back(e);}}void swap(listT s){std::swap(_phead, s._phead);}listT operator(listT s){swap(s);return *this;} 7. list功能实现clear与析构函数
对于函数其功能是用于清理空间中的所有内容即所有开辟的结点但是不包括哨兵位头结点。
对于析构函数则是在函数的基础上将哨兵位头结点也进行处理。
二者对应代码如下
void clear(){iterator i2 begin();while (i2 ! end()){i2 erase(i2);}}~list(){clear();delete _phead;phead nullptr;}
