链表的实现(C++版)
对于链表的学习,之前在C语言部分的时候就已经有学习过,也学会了使用C语言来打造一个链表.如今学了C++ 则想通过C++来打造一个链表,以达到锻炼自己的目的.
1.链表的初步实现
1.节点模板的设置
template <class T> struct ListNode{ListNode <T>* _next;ListNode <T>* _prve;T data;ListNode(const T& x = T()):_next(nullptr),_prve(nullptr),_data(x){}};
这边使用一个模板来定义这个节点,因为我们传进来的数据可能是任意类型的,为了方便数据的传参,我们直接使用template <class T>来写一个万能的模板.除了next指针和prve指针和data以外,我们还得写一个构造函数,这边的构造函数的初始化就是把_next金额_prve初始化成一个空指针,然后_data来根据传入的参数来做决定. 传入的参数为 const T&x = T() 这里用的是传引用传参,然后如果有x的话,就用x来初始化,如果没有x的话,后面带着的这个T()就可以对其调用默认的构造函数了. 如果不给T()的话,就得自己在传递一个参数.
2.链表模板的设置
template <class T>class list{typedef ListNode<T> Node;public:list(){_head = new Node;_head->_next = _head;_head->_prve = _head;_head->data = 0;}void push_back(const T& x){Node* newnode = new Node(x);Node* Tail = _head->_prve;Tail->_next = newnode;newnode->_prve = Tail;newnode->_next = _head; _head->_prve = newnode;}private:Node* _head;};
这里也没什么好说的,生成了一个带头链表,尾插就是一个链表的基本操作.
此时我们想打印出来看看,该怎么做?
想到用迭代器来进行打印,但是,由于我们是自己实现链表,因此又重新开了个命名空间,因此,iterator, !=, *, ++等符号我们都是用不了的,这些我们都得自己来进行运算符重载.因此,实现C++ 的链表,难的不是链表本身,而是实现链表的迭代器,这是一个麻烦的过程.
3.迭代器的模拟
对于迭代器,他有一个好处,就是不管你的数据底层是一个什么样子的数据,他都可以对你进行访问.这可能让我们会联想到指针,对于指针来说,数据的原生指针就是一个天然的迭代器,但是,这是建立在一个你的数据的物理空间是连续的情况下的基础的,链表都是随机生成的节点地址,他在物理空间上是不连续的.
因此我们想要模拟一个迭代器的行为,首先定义一个迭代器的类
我们 可以看到, ListIerator这个迭代器,就是一个单参数的构造函数.
1.重载运算符++
我们想要的是这个迭代器++之后会指向下一个节点,而由于在链表中,直接++是无法让当前的迭代器指向下一个节点的,因此我们需要对其进行重载一下.
//前置++iterator& operator++(){_node = _node->_next;return *this;}//后置++iterator operator++(int){iterator tmp(*this);_node = _node->_next;return tmp;}在这里,我们把ListIterator类重定义成了iterator,在重载运算符中,由于我们返回的数据是有类型的,而这个*this指针的类型则是当前的ListIterator也就是iterator,因此,在这里我们要把重载函数的类型写成iterator.
而在重载后置++的时候,由于我们需要的是返回++之前的值,因此,我们需要另一个迭代器来获取返回之前的数据,得完成一个拷贝构造,因此这边重载后置++的时候就需要浅拷贝,因而不用加&.
2.重载运算符--
//前置--iterator& operator--(){_node = _node->_prve;return *this;}//后置--iterator operator--(int){iterator tmp(*this);_node = _node->_prve;return tmp;}这个跟重载++是类似的.
3.begin()函数和end()函数
iterator begin(){//iterator it(_head->next);//return it;//return _head->next; (这个便是隐式类型转换)return iterator(_head->_next);}iterator end(){//iterator it(_head);//return it;//return _head; (这个也是隐式类型转换)return iterator(_head);}这边的begin函数和end函数都是为了获取当前位置的迭代器,因此就使用了迭代器类型来进行返回当前的节点.
最后,我们还需要重载一下!=号和==号
bool operator!=(const iterator& it){return _node != it._node;}bool operator==(const iterator& it){return _node == it._node;}目前,当前的这个链表,就可以进行使用啦~
接下来就是对这个链表进行完善了.
4.insert函数的实现
void insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);//prve newnode cur nextNode* prve = cur->_prve;prve->_next = newnode;newnode->_prve = prve;newnode->_next = cur;cur->_prve = newnode;}这些已经没什么好说的了,跟之前用C语言实现的链表的基本逻辑是一样的.
而当我们实现了insert函数的时候,就可以让他在push_back和push_front来复用.
void push_back(const T& x){/*Node* newnode = new Node(x);Node* Tail = _head->_prve;Tail->_next = newnode;newnode->_prve = Tail;newnode->_next = _head;_head->_prve = newnode;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());//删除最后一个节点}void pop_fornt(){erase(begin());}5.erase函数的实现
void erase(iterator pos){Node* cur = pos._node;Node* prve = cur->_prve;Node* next = cur->_next;//prve cur nextprve->_next = next;next->_prve = prve;delete cur;}这里需要注意的一个地方就是当我们释放了cur节点的时候,cur所指向的pos就也会被释放掉了,然后当前的pos就造成一个迭代器失效的问题,因此,我们需要返回pos节点的下一个节点.
iterator erase(iterator pos){Node* cur = pos._node;Node* prve = cur->_prve;Node* next = cur->_next;//prve cur nextprve->_next = next;next->_prve = prve;delete cur;return iterator(next);}2.链表继续优化
1.重载->
以上的仅仅只是支持用来插入int,float,double等数据.
而当我们遇到一个结构体类型的数据,如果继续使用以上的方法是会报错的.
如果想直接来读取数据,只能是用这种方法.
这里就是it来调用operator*,然后返回的就是 A 由于 A里面不止是有一个数据,因此还需要进行一次解引用,来读取_a1 或者 _a2
但是这种方法相对来说是非常不方便的.
因此,我们则可以对->来进行重载.
T* operator->()
{return &_node->_data;
}这个写法乍一看是比较诡异的,但自己推敲之后,发现还是比较好理解的,
首先,我们上面的那种写法,是先把迭代器it解引用一遍,然后再通过 . 来进行解引用第二遍来获取里面的数据,而这里重载的->,则是直接返回的就是 A*(T*) , 然后 A*就会自己来解引用,进而就会得到里面的数据.
修改之后的遍历是这样的,
而其中的又是编译器简化了,我们可以拆开看看
这两种写法是一样的,上面的那种就是it先调用->重载,然后再解引用,而下面这种是直接省略了,编译器帮我们做了,是为更加简便的方法.
2.模板的传引用和传指针
目前我们的模板仅仅是能返回不是const的数据,当我们有需求来返回const的数据时,我们能想到的是把这个类再复制一边,然后加个const来修饰,但是这样是过于麻烦的.
当除了类型,其它的内容都一样的时候,我们就可以考虑使用模板来更好的传递数据.
template <class T , class Ref , class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T> iterator;Node* _node;ListIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//前置++iterator& operator++(){_node = _node->_next;return *this;}//后置++iterator operator++(int){iterator tmp(*this);_node = _node->_next;return tmp;}//前置--iterator& operator--(){_node = _node->_prve;return *this;}//后置--iterator operator--(int){iterator tmp(*this);_node = _node->_prve;return tmp;}bool operator!=(const iterator& it){return _node != it._node;}bool operator==(const iterator& it){return _node == it._node;}};可以看到,我在声明模板的时候,新加入了两个类名,一个是Ref , 一个是Ptr,代表着传引用和传指针,然后写道对应的函数上.
而在list里面, 我们可以这样做
一个是传T , 然后是T& , 然后是 T* ,这样就可以使得可以根据所需来返回我们需要的数据了.