C++ 简单版STL list 链表（迭代器版）

客官°小女子只卖身不卖艺 2021-12-15 05:01 193阅读 0赞

最近课程开始上设计模式了。

苦于天天满课的状态，不过题目可以放到晚上去刷。

周末师大校赛挺有趣的，题目质量好高。

花了几天写LIST,一开始就想写出 跟STL用法一样的LIST，

加个迭代器然后循环着自己用。

结果发现！！！！好多坑，有C++ 模板 C++ 符号重载等等。

不过也提高了点C++ 代码能力。感觉迭代器就是对node的封装.....

#include <iostream>
    #include <cstdio>
    #include <list>
    #include <stdlib.h>
    #include <time.h>
    
    template<typename T>
    class Node {
        //双向链表节点
        public:
            T val;//存储节点值
            Node *next;
            Node *pre;
    };
    
    template<typename T>
    struct List_iterator { //简单版迭代器
        typedef Node<T>* Node;
        Node data;
    
        List_iterator() {
            data = 0;
        }
        List_iterator(Node other) {
            data = other;
        }
        List_iterator(const List_iterator &rhs) {
            data = rhs.data;
        }
        List_iterator& operator ++ () { //重载前置自增符号
            data = data->next;
            return *this;
        }
        T& operator * () {
            return data->val;
        }
        bool operator != (const List_iterator& rhs) {
            return (rhs.data != data);
        }
        bool operator == (const List_iterator& rhs) {
            return (rhs.data == data);
        }
    };
    
    /*
        head<->Node1<->Node2(tail)->NULL
    */
    
    template<typename T>
    class List { //双向链表
        public:
            typedef Node<T> Node;
            typedef Node* pNode;
            typedef List_iterator<T> iteratorL;
        private:
            pNode head;                    //指向头节节(头节点不放元素)
            pNode tail;                    //指向尾节点
            int _size;                     //当前链表长度
        private:
            void init();                //构造初始化函数
        public:
            List();                        //默认构造函数
            List(const List &);            //拷贝函数
            ~List();                    //析构函数
            iteratorL begin();            //获取第一个节点
            iteratorL end();            //获取最后一个节点的下一位置
            T front();                    //返回第一个节点的值
            T back();                    //返回最后一个节点的值
            int size() const;            //返回链表长度
            bool empty();                //判断链表是否为空,空则返回true
            void push_back(T val);        //插入值为val的节点到链表末尾
            void pop_back();            //删除链表末尾节点
            void push_front(T val);        //插入值为val的节点到链表头部
            void pop_front();            //删除链表头节点
            iteratorL insert(iteratorL pos,T val);//在指定位置插入值为val的节点
            void erase(iteratorL pos);    //删除指定位置的值
            //[first,last)区间中查找值为val的节点,并且返回该位置迭代器，找不到则返回 end()
            iteratorL find(const iteratorL first,const iteratorL last,const T val);
            void remove(T val);            //删除具有值为val的节点
            void sort();                //按照从小到大进行排序
            void swap(iteratorL first,iteratorL second);//交换两节点内容 
            void clear();                                //清空链表内容
    };
    
    template<typename T>
    void List<T>::init() {
        tail = head = new Node;
        head->next = 0;
        head->pre = 0;
        head->val = 0;
        _size = 0;
    }
    
    template<typename T>
    List<T>::List() {
        init();
    }
    
    template<typename T>
    List<T>::List(const List &other) {
        init();
        Node *p = other.head->next;
        while(p != 0) {
            push_back(p->val);
            p = p->next;
        }
    }
    
    template<typename T>
    List<T>::~List() {
        clear();
        delete head;
    }
    
    template<typename T>
    typename List<T>::iteratorL List<T>::begin() {
        return iteratorL(head->next);
    }
    
    template<typename T>
    typename List<T>::iteratorL List<T>::end() {
        return iteratorL(tail->next);
    }
    
    template<typename T>
    T List<T>::front() {
        if(!empty())
            return head->next->val;
    }
    
    template<typename T>
    T List<T>::back() {
        return tail->val;
    }
    
    template<typename T>
    int List<T>::size() const {
        return _size;
    }
    
    template<typename T>
    bool List<T>::empty() {
        return (_size == 0);
    }
    
    template<typename T>
    void List<T>::push_back(T val) {
        insert(end(),val);
    }
    
    template<typename T>
    void List<T>::pop_back() {
        erase(iteratorL(tail));
    }
    
    template<typename T>
    void List<T>::push_front(T val) {
        insert(begin(),val);
    }
    
    template<typename T>
    void List<T>::pop_front() {
        erase(begin());
    }
    
    template<typename T>
    typename List<T>::iteratorL
    List<T>::insert(iteratorL pos,T val) {
        //在Pos位置插入值为Val的节点 
        pNode addN = new Node;
        ++_size;
        addN->val = val;
        if(pos != end()) {
            pNode p = pos.data;
            pNode preN = p->pre;
            addN->pre = p->pre;
            addN->next = p;
            if(preN)
                preN->next = addN;
            p->pre = addN;
        } else { //插入末尾
            tail->next = addN;
            addN->pre = tail;
            addN->next = 0;
            tail = addN;
        }
        return iteratorL(addN);
    }
    
    template<typename T>
    void List<T>::erase(iteratorL pos) {
        if(pos != end()) {
            pNode p = pos.data;
    
            pNode preN = p->pre;
            pNode nextN = p->next;
            preN->next = nextN;
            if(p == tail)//删除尾节点特判
                tail = preN;
            if(nextN != 0)
                nextN->pre = preN;
            delete p;
            --_size;
        }
    }
    
    template<typename T>
    typename List<T>::iteratorL
    List<T>::find(const iteratorL first,const iteratorL last,const T val) {
        iteratorL it = first;
        while(it != last) {
            if(*it == val)
                return it;
            ++it;
        }
        return end();//找不到返回 end()
    }
    
    template<typename T>
    void List<T>::remove(T val) {
        iteratorL it = find(begin(),end(),val);
        if(it!=end()) {
            erase(it);
        }
    }
    
    template<typename T>
    void List<T>::clear() {
        while(empty() == false) {
            pop_back();
        }
    }
    
    template<typename T>
    void List<T>:: swap(iteratorL first,iteratorL second)//使用选择排序 
    {
        if(first == end() || second == end())//避免空指针 
            return;
        T tmp = first.data->val;
        first.data->val = second.data->val;
        second.data->val = tmp;
    }
    
    template<typename T>
    void List<T>:: sort()//使用选择排序 
    {
        if(empty() == false){
            iteratorL minI;
            for(iteratorL it = begin();it!=end();++it)
            {
                minI = it;//最小值初始化 
                for(iteratorL it2 = it;it2!=end();++it2)
                {
                    if(minI.data->val > it2.data->val){
                        minI = it2;
                    }
                }
                swap(minI,it);//交换两迭代器所指位置的内容 
            }        
        }
    }
    
    //打印输出List
    template<typename T>
    void print(List<T> q) {
        for(List<int>::iteratorL it = q.begin(); it!=q.end(); ++it) {
            std::cout << *it << " ";
        }
        std::cout << std::endl;
    }
    
    int main() {
        //测试 添加 删除 
        List<int> q;
        q.push_back(1);
        q.push_back(2);
        q.push_back(3);
        print(q);
    
        q.pop_back();
        q.push_front(3);
        q.push_front(4);
        q.pop_front();
        print(q);
    
        q.clear();
        print(q);
    
        q.push_back(1);
        List<int>::iteratorL it = q.begin();
        *it = 2;
        print(q);
    
        q.insert(q.begin(),3);
        print(q);
        
        //查找元素3 
        if(q.find(q.begin(),q.end(),3) != q.end()){
            printf("find 3\n");
        }
        
        //移除remove测试 
        q.remove(3);
        if(q.find(q.begin(),q.end(),3) != q.end()){
            printf("find 3\n");
        }
        
        
        //测试从小到大排序 
        q.clear();
        srand(static_cast<int>( time(0) ) );
        for(int i=0;i<20;++i){
            q.push_back(rand()%20);
        }
        print(q);
        q.sort();
        print(q);
        return 0;
    }

转载于:https://www.cnblogs.com/--zz/p/10712502.html