做最好最全的命理网站,wordpress 连接插件,网页设计实训总结模板,c 网站建设步骤大家都知道在C的学习中迭代器是必不可少的#xff0c;今天我们学习的是C中的链表的底层迭代器的实现#xff0c;首先我们应该先知道链表的底层迭代器和顺序表的底层迭代器在实现上有什么区别#xff0c;为什么顺序表的底层迭代器更加容易实现#xff0c;而链表的底层迭代器…大家都知道在C的学习中迭代器是必不可少的今天我们学习的是C中的链表的底层迭代器的实现首先我们应该先知道链表的底层迭代器和顺序表的底层迭代器在实现上有什么区别为什么顺序表的底层迭代器更加容易实现而链表的底层迭代器不容易实现接下来小编再来告诉大家如何来实现链表的底层迭代器学完今天这篇我相信大家对C中的迭代器一定会有一个更加深刻的认识大家先看今天学习的内容
一、顺序表和链表的底层迭代器的区别
为了知道它们两个的区别先得告诉大家顺序表的底层迭代器是如何实现的首先大家先得明白顺序表私有成员都有什么好方便大家来理解它们的底层迭代器是如何实现的请看下图顺序表的私有成员变量 private:iterator _start;iterator _finish;iterator _end_of_storage;
如图就是顺序表的私有成员变量 第一个 _start 是记录顺序表的起始位置的指针类型是 T*
_finish记录的是顺序表内末尾元素的下一个位置的指针类型是T*,_end_of_storage记录的是顺序表的目前的所有容量的下一个位置类型也是T*。
在明白了顺序表的私有成员变量的意义并且顺序表的储存是连续的空间有点类似于数组的数据储存所以大家也应该明白了顺序表的底层迭代器是如何实现的了吧如果不懂请看下图操作及注释如下图
但是由于链表的物理结构不是连续的所以想顺序表一样的底层迭代器实现方法是行不通的这也是为什么在底层实现链表的迭代器中不能通过给迭代器来做到迭代器指向下一个元素的地址因为链表的数据在空间中分布式随意的。那该如何去设计链表的底层迭代器呢请大家继续往下看。
二、链表的底层迭代器该如何实现
首先先请大家看一下链表中的数据是如何分布的如下图
如图可见链表中的数据是随意分布的但是我们仍然可以用前一个节点找到下一个节点但为什么这样子不行不算迭代器呢因为在C中迭代器的定义就是通过 来找到下一个元素接通过 * 号来拿到他这个位置的数据这才是迭代器的规定如下段代码的遍历效果 如上链表的分布图虽然我们可以拿到下一个节点的位置和这个节点的数据但我们不是通过 和 * 来实现的所以通过这样的方式做出的迭代器是不对的。那我们该如何实现呢小编新学了一个方法就是把迭代器底层封装成一个类让它内部进项运算符重载来达到 实现像迭代器一样遍历的过程* 实现像迭代器一样拿出数据的过程那么该如何实现呢请大家继续往下看。
三、链表底层迭代器的实现
上面说到把迭代器封装成一个类然后用运算符重载来达到 和 * 的过程把它彻底改变为一个正规的迭代器现在大家就和我一起实现这个迭代器的类
1、首先大家要明白链表(带头双向循环链表)的结构如下代码
templateclass T
// 这里用结构体是因为ListNode中的每个成员都应该可以访问 没有私有成员
// 也可以使用友元来解决这个问题
struct ListNode
{T _data;ListNode* _next;ListNode* _prev;ListNode(const T data T()):_next(nullptr),_prev(nullptr), _data(data){}
}; templateclass Tclass list{public:typedef ListNodeT Node;private:Node* _head;};
如上图代码在这里我们已经知道下一步需要把链表独特的遍历方式(用前一个指针找到后一个指针)用运算符重载的改为 和 * 来实现遍历和拿到数据保证它和迭代器的实现和用法一模一样。那该如何实现这个类呢。
2、实现迭代器的类
我们需要定义一个迭代器的类因为有普通迭代器和不可修改的迭代器它们两个的函数大多数相同为了减少代码量我们加入两个模板参数来帮我们减轻代码量 // 这里加入 Ref 和 Ptr 是为了区分普通迭代器和const迭代器的区别// 本来要写两份迭代器一份可修改一份不可修改 现在直接交给编译器去做templateclass T , class Ref, class Ptrstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;// 链表的迭代器应该是 Node* 类型的指针Node* _node;ListIterator(Node* node):_node(node){}// 前置Self operator(){_node _node-_next;return *this;}//前置--Self operator--(){_node _node-_prev;return *this;}Self operator(int){Self tem(*this);_node _node-_next;return tem;}Self operator--(int){Self tem(*this);_node _node-_prev;return tem;}Ptr operator-(){return (_node-_data);}Ref operator*(){return _node-_data;}bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}};
以上就是今天的所有内容希望大家会喜欢
