精华内容
下载资源
问答
  • C++实现双向链表

    2020-08-19 04:00:00
    主要为大家详细介绍了C++实现双向链表,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • c++实现双向链表

    2021-05-02 20:49:51
    双向链表 ** #include<bits/stdc++.h>//双向链表 using namespace std; struct Node { int data; Node *pre,*next; }; typedef Node* NODE; NODE p,q,head,tail; //需要额外的一个q,在建立双链表时指向...

    **

    双向链表

    自己瞎写的,不是很规范

    **

    #include<bits/stdc++.h>//双向链表
    using namespace std;
    
    struct Node
    {
        int data;
        Node *pre,*next;
    };
    typedef Node* NODE;
    NODE p,q,head,tail;
    //需要额外的一个q,在建立双链表时指向前面的节点
    int n;
    
    void reout()//逆序输出链表
    {
        p=tail;
        while(p->pre!=NULL)
        {
            cout<<p->data<<endl;
            p=p->pre;
        }
        cout<<p->data<<endl;
    }
    void out()//正序输出链表
    {
        p=head->next;
        while(p->next!=NULL)
        {
            cout<<p->data<<endl;
            p=p->next;
        }
        cout<<p->data<<endl;
    }
    
    void deletedata()//删除第n个节点
    {
        cin>>n;
        int js=1;
        NODE s;
        p=head->next;
        for(;js<n-1&&p!=NULL;js++,p=p->next)
        {}
        if(p!=NULL&&js==n-1)
        {
            s=p->next;
            p->next=s->next;
            p->next->pre=p;
            free(s);
        }
        else
        {
            cout<<"不存在第n个节点";
        }
    }
    
    int main()
    {
        head=new Node;
        head->data=0;
        tail=head;
        q=NULL;//
        for(;;)
        {
            cin>>n;
            if(n==-1)
            {
                break;
            }
            p=new Node;
            p->data=n;
            p->next=NULL;
    
            p->pre=q;//和单链表的区别
            q=p;//就在于这两步
    
            tail->next=p;
            tail=p;
        }
        deletedata();
        reout();
        out();
        return 0;
    }
    

    有问题的话欢迎评论。

    展开全文
  • 主要介绍了C++ 实现双向链表的实例的相关资料,需要的朋友可以参考下
  • 主要为大家详细介绍了C++实现双向链表,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • C++ 实现双向链表

    2017-07-27 23:13:03
    为什么要使用双向链表? 1.单链表的结点都只有一个指向下一结点的指针。 2.单链表的数据元素无法直接访问其前驱元素。 逆序访问单链表是极其耗费时间的。 void Reverse(pList* pplist) { assert(pplist); if...

    一.为什么要使用双向链表?
    1.单链表的结点都只有一个指向下一结点的指针。
    2.单链表的数据元素无法直接访问其前驱元素。
    逆序访问单链表是极其耗费时间的。

    void Reverse(pList* pplist)
    {
        assert(pplist);
        if (*pplist==NULL)
        {
            return;
        } 
        else
        {
            pNode tail = *pplist;
            pNode cur = *pplist;
            pNode _next = cur->next;
            pNode tmp = NULL;
            while (_next!=NULL)
            {
                tmp = _next->next;
                _next->next=cur;
                cur = _next;
                _next = tmp;
            }
            tail->next = NULL;
            *pplist = cur;
        }   
    }

    二 .双向链表与单向链表相比,各个结点多了一个指向前一个结点的指针。结构如图所示:

    这里写图片描述

    下面是对双向链表的增删查改:

    先是对一个双向链表的构造

    #define _CRT_SECURE_NO_WARNINGS 1
    #include <iostream>
    #include <assert.h>
    using namespace std;
    
    typedef int DataType;
    
    struct ListNode 
    { 
        ListNode* _next; 
        ListNode* _prev; 
        DataType _data; 
    
        ListNode(DataType x)
            :_data(x)
            ,_next(NULL)
            ,_prev(NULL)
        {}
    }; 
    
    class List 
    { 
        typedef ListNode Node; 
    public: 
        List()
            :_head(NULL)
            ,_tail(NULL)
        {
        }
        List(const List &l)
            :_head(NULL)
            ,_tail(NULL)
        {
            Node* cur = l._head;
            while (cur)
            {
                PushBack(cur->_data);
                cur = cur->_next;
            }
        }
        List& operator=(const List& l)
        {
            if (this != &l)
            {
                List tmp(l);
                Swap(tmp);
            }
            return *this;
        }
        void Swap(List &l)
        {
            swap(_head,l._head);
            swap(_tail,l._tail);
        }
        ~List()
        {
            if (_head != NULL)
            {
                Node* del = _head;
                _head = _head->_next;
                delete del;
            }
        }

    对其进行增删查改

    首先是尾部插入一个元素

    这里写图片描述

    void PushBack(DataType x)
        {
            if (_head == NULL)
            {
                _head = _tail  = new Node(x);
            }
            else
            {
                Node* cur = new Node(x);
                _tail->_next = cur;
                cur->_prev = _tail;
                _tail = cur;
            }
        }
    void Print()
        {
            Node* cur = _head;
            while (cur != NULL)
            {
                cout<<cur->_data<<"->";
                cur = cur->_next;
            }
            cout<<"NULL"<<endl;
        }
        void PopBack()
        {
            if (_head == NULL)
            {
                return ;
            }
            else if (_head->_next == NULL)
            {
                Node* cur = _head;
                delete cur;
                _head = NULL;
                _tail = NULL;
            } 
            else
            {
                Node* cur = _tail;
                cur->_prev->_next = NULL;
                _tail = cur->_prev;
                delete cur;
    
            }
        }
        void PushFront(DataType x)
        {
            if (_head == NULL)
            {
                _head = _tail  = new Node(x);
            }
            else
            {
                Node* tmp = _head;
                _head = new Node(x);
                _head->_next = tmp;
                tmp->_prev = _head;
    
            }
        }
        void PopFront()
        {
            if (_head == NULL)
            {
                return ;
            }
            else if (_head->_next == NULL)
            {
                Node* cur = _head;
                delete cur;
                _head = NULL;
                _tail = NULL;
            } 
            else
            {
                Node* cur = _head;
                _head = _head->_next;
                delete cur;
                _head->_prev = NULL;
            }
        }
        void Insert(Node* pos, DataType x)
        {
            assert(pos);
            if (pos == _head)
            {
                PushFront(x);
            }
            else
            {
                Node* tmp = new Node(x);
                Node* prev = pos->_prev;
                Node* next = pos->_prev->_next;
                prev->_next = tmp;
                tmp->_next = next;
                next->_prev = tmp;
                tmp->_prev = prev;
            }
        }

    这里写图片描述

    void Erase(Node* pos)
        {
            assert(pos);
            if (pos == _head)
            {
                PopFront();
            }
            else if (pos == _tail)
            {
                PopBack();
            } 
            else
            {
                pos->_next->_prev = pos->_prev;
                pos->_prev->_next = pos->_next;
                delete pos;
            }
        }
        Node* Find(DataType x)
        {
            Node* cur = _head;
            while (cur)
            {
                if (cur->_data == x)
                {
                    return cur;
                }
                cur = cur->_next;
            }
            return NULL;
        }
        void Reverse()
        {
            Node* prev = _head;
            while (prev)
            {
                Node* next = prev->_next;
                Node* tmp = prev->_prev;
                prev->_prev = prev->_next;
                prev->_next = tmp;
                prev = next;
            }
            Node* tmp = _head;
            _head = _tail;
            _tail = tmp;
        }
    private: 
        Node* _head; 
        Node* _tail; 
    };
    
    展开全文
  • c++实现双向链表,类模板双向链表

    千次阅读 2016-09-06 20:10:23
    c++实现双向链表的思想和c很类似,不同的是c++是将实现的函数放在类中,这样就可以由类实例化出对象再调用类中的函数进行添加、删除、查找、插入元素等功能。类模板实现双向链表在最后进行说明和实现,方法依然类似...
    c++实现双向链表的思想和c很类似,不同的是c++是将实现的函数放在类中,这样就可以由类实例化出对象再调用类中的函数进行添加、删除、查找、插入元素等功能。类模板实现双向链表在最后进行说明和实现,方法依然类似。
    c++实现双向链表

    #include<iostream>
    #include<assert.h>
    using namespace std;
    
    typedef int Datatype;
    typedef struct Node//链表是由一个个节点组成所以这里单独定义这一类型方便在链表类中使用
    {
         Datatype _data;
         struct Node* next;
         struct Node* prev;
    }Node,*pNode;
    
    typedef class LinkList
    {
    private:
         pNode head;
    public:
         LinkList()
        {
          head=NULL;
        }
    
     void pushback(Datatype x)
     {
          pNode p=new Node[sizeof(Node)];
          p->_data=x;
          p->next=NULL;
          if(head==NULL)
         {
            head=p;
            head->prev=NULL;
         }
         else
        {
            pNode cur=head;
            while(cur->next)
           {
               cur=cur->next;
           }
           cur->next=p;
           p->prev=cur;
        }
     }
    
     void pushfront(Datatype x)
     {
          pNode tmp=new Node[sizeof(Node)];
          if(head==NULL)
         {
            tmp->_data=x;
            head=tmp;
            head->next= NULL;
            head->prev=NULL;
        }
          else
       {
         //我们要在头结点前再插入一个结点,需要先创建一个新的结点,将头结点的值保存在新节点,然后让新节点的下
         //个结点指向头结点的下一个结点,再让新节点的prev指向头结点,这样就将新节点与原来的链表融合了,然后我
         //们将头结点的数据换成x即可。
            tmp->_data=head->_data;
            tmp->next=head->next;
            tmp->prev=head;//
            head->next=tmp;
            head->_data=x;
      }
     }
     void popback()
     {
          if(head!=NULL)
         {
           pNode cur=head;
           pNode pre=NULL;
           while(cur->next)
         {
           pre=cur;
           cur=cur->next;
         }
         delete[] cur;
         cur=NULL;
         pre->next=NULL;//一定要将pre->next置为空,前面一句仅仅是将cur的值置为空,此时pre->next还指向原来的那块空间
      }
     }
    
     void popfront()
     {
          if(head!=NULL)
         {
            if(head->next==NULL)
           {
              delete[] head;
              head=NULL;
           }
         else
          {
             pNode del=head;
             head=head->next;
             delete[] del;
             del=NULL;//这里将del置为空可以防止它变为野指针
          }
        }
     }
    
     pNode find(Datatype x)
     {
          if(head==NULL)
        {
          return NULL;
        }
          else
        {
           pNode cur=head;
           while(cur)
          {
             if(x==cur->_data)
            {
              return cur;
            }
             cur=cur->next;
          }
        return NULL;
      }
     }
    
     void insert(pNode pos,Datatype x)
     {
          assert(pos);//防止pos为空指针
          if(head==NULL)
         {
           return ;
         }
          else
         {
            pNode cur=head;
            if(head==pos)
           {
            pushfront(x);
           }
           else
           {
                while(cur)
              {
                 if(cur==pos)
                {
                 pNode tmp=new Node[sizeof(Node)];
                 tmp->_data=cur->_data;
                 tmp->next=cur->next;
                 tmp->prev=cur;
                 cur->_data=x;
                 cur->next=tmp;
                 return ;//insert成功后不要忘了直接返回结束函数
                }
                cur=cur->next;
             }
             cout<<"没有找到这个数字"<<endl;
          }
       }
     }
    
     void erase(pNode pos)//删除指定位置的结点
     {
          assert(pos);
          if(head==NULL)
         {
           return;
         }
         else
        {
            if(pos==head)
           {
             popfront();
           }
           else
          {
             pNode del=head->next;
             pNode pre=head;
             while(del)
            {
               if(del==pos)
               {
                   if(del->next!=NULL)
                 {
                    pre->next=del->next;
                    del->next->prev=pre;
                    delete[] del;
                    del=NULL;
                 }
                 else
                {
                   delete[] del;
                   pre->next=NULL;
                }
                 return;
              }
             del=del->next;
             pre=pre->next;
          }
       }
      }
     }
    
     int use_count()//返回链表中结点的数量
     {
          int count=0;
          pNode cur=head;
          while(cur)
         {
           cur=cur->next;
           count++;
         }
         return count;
     }
    
     void display()//打印链表
     {
          pNode cur=head;
          while(cur!=NULL)
         {
           cout<<cur->_data<<endl;
           cur=cur->next;
         }
     }
    
     ~LinkList()
     {
          pNode cur=head;
          while(cur!=NULL)
         {
             pNode Next=cur->next;
             delete cur;
             cur=Next;
             if(cur!=NULL)
            {
              Next=Next->next;
            }
             else
               break;
         }
     }
    };
    
    void test()
    {
         LinkList ls1;
         ls1.pushback(1);
         ls1.pushback(2);
         ls1.pushback(3);
         ls1.pushfront(0);
         ls1.display();
         ls1.popback();
         ls1.display();
         ls1.popfront();
         ls1.display();
         pNode ret=ls1.find(2);
         if(ret==NULL)
        {
          cout<<"没有找到"<<endl;
        }
         else
        {
          cout<<ret->_data<<endl;
        }
        ls1.insert(ret,5);
        ls1.display();
        pNode ret2=ls1.find(2);
        ls1.erase(ret2);
        ls1.display();
        int ret3=ls1.use_count();
        cout<<ret3<<endl;
    }
    
    int main()
    {
         test();
         getchar();
         return 0;
    }



    c++实现类模板双向链表
    实现方式和双向链表基本一样,这里只是介绍一下template的用法和注意事项
    模板是泛型编程的基础,所谓泛型编程就是编写与类型无关的逻辑代码,是一种复用的方式,模板分为模板函数和模板类。
    函数模板格式:
     template <class 形参名1, class 形参名2, class 形参名n>
    返回类型 函数名(参数列表)
     {...}
    模板形参的定义既可以使用class,也可以使用typename,含义是相同的,这里实现时我们用的是typename。
    在这里我们先在类的内部定义好函数,具体实现在类外进行,实现方法不再详细解释。

    #include<iostream>
    #include<assert.h>
    using namespace std;
    
    template<typename T>
    struct Node
    {
         T _data;
         Node<T>* next;
         Node<T>* prev;
    };
    template<typename T>
    class LinkList
    {
    private:
         Node<T>* head;
    public:
         LinkList();
         void pushback(T x);
         void pushfront(T x);
         void popback();
         void popfront();
         Node<T>* find(T x);
         void insert(Node<T>* pos,T x);
         void erase(Node<T>* pos);
         int use_count();
         void display();
         ~LinkList();
    };
    
    template<typename T>
    LinkList<T>::LinkList()
    {
         head=NULL;
    }
    
    template<typename T>
    LinkList<T>::~LinkList()
    {
         Node<T>* cur=head;
         while(cur!=NULL)
        {
           Node<T>* Next=cur->next;
           delete cur;
           cur=Next;
           if(cur!=NULL)
          {
            Next=Next->next;
          }
          else
            break;
       }
    }
    
    template<typename T>
    void LinkList<T>::pushback(T x)
    {
         Node<T>* p=new Node<T>[sizeof(Node<T>)];
         p->_data=x;
         p->next=NULL;
         if(head==NULL)
        {
          head=p;
          head->prev=NULL;
        }
         else
        {
          Node<T>* cur=head;
          while(cur->next)
         {
            cur=cur->next;
         }
         cur->next=p;
         p->prev=cur;
       }
    }
    
    template<typename T>
    void LinkList<T>::display()
    {
         Node<T>* cur=head;
         while(cur!=NULL)
        {
          cout<<cur->_data<<endl;
          cur=cur->next;
        }
    }
    
    template<typename T>
    void LinkList<T>::pushfront(T x)
    {
         Node<T>* tmp=new Node<T>[sizeof(Node<T>)];
         if(head==NULL)
         {
          tmp->_data=x;
          head=tmp;
          head->next= NULL;
          head->prev=NULL;
         }
        else
        {
          tmp->_data=head->_data;
          tmp->next=head->next;
          tmp->prev=head;
          head->next=tmp;
          head->_data=x;
       }
    }
    
    template<typename T>
    void LinkList<T>::popback()
    {
         if(head!=NULL)
        {
          Node<T>* cur=head;
          Node<T>* pre=NULL;
          while(cur->next)
         {
            pre=cur;
            cur=cur->next;
         } 
         delete[] cur;
         cur=NULL;
         pre->next=NULL;//一定要将pre->next置为空,前面一句仅仅是将cur的值置为空,此时pre->next还指向原来的那块空间
      }
    }
    
    template<typename T>
    void LinkList<T>::popfront()
    {
         if(head!=NULL)
        {
           if(head->next==NULL)
          {
            delete[] head;
            head=NULL;
          } 
           else
          {
            Node<T>* del=head;
            head=head->next;
            delete[] del;
            del=NULL;
          }
       }
    }
    
    template<typename T>
    int LinkList<T>::use_count()
    {
         int count=0;
         Node<T>* cur=head;
         while(cur)
       {
          cur=cur->next;
          count++;
       }
       return count;
    }
    
    template<typename T>
    Node<T>* LinkList<T>::find(T x)
    {
         if(head==NULL)
        {
           return NULL;
        }
         else
       {
           Node<T>* cur=head;
           while(cur)
          {
             if(x==cur->_data)
            {
               return cur;
            }
            cur=cur->next;
          }
         return NULL;
      }
    }
    
    template<typename T>
    void LinkList<T>::insert(Node<T>* pos,T x)
    {
          assert(pos);
          if(head==NULL)
         {
            return ;
         }
          else
         {
            pNode cur=head;
            if(head==pos)
           {
              pushfront(x);
           }
            else
           {
              while(cur)
             {
                 if(cur==pos)
               {
                  Node<T>* tmp=new Node<T>[sizeof(Node<T>)];
                  tmp->_data=cur->_data;
                  tmp->next=cur->next;
                  tmp->prev=cur;
                  cur->_data=x;
                  cur->next=tmp;
                   return ;
                }
            cur=cur->next;
           }
           cout<<"没有找到这个数字"<<endl;
         }
       }
    }
    
    template<typename T>
    Node<T>* LinkList<T>::find(T x)
    {
           if(head==NULL)
         {
            return NULL;
         }
           else
         {
            Node<T>* cur=head;
            while(cur)
           {
              if(x==cur->_data)
             {
                return cur;
             }
            cur=cur->next;
            }
            return NULL;
        }
    }
    
    void test()
    {
          LinkList<int> ls;
          ls.pushback(1);
          ls.display();
          ls.pushfront(0);
          ls.display();
          ls.popback();
          ls.display();
          ls.popfront();
          ls.display();
          cout<<ls.use_count()<<endl;
          ls.pushback(1);
          ls.pushback(2);
          ls.pushback(3);
          ls.pushback(4);
          ls.display();
          Node<int>* ret=ls.find(2);
          cout<<ret->_data<<endl;
    }
    
    int main()
    {
          test();
          getchar();
          return 0;
    }
    
    



    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,697
精华内容 678
关键字:

c++实现双向链表

c++ 订阅