数据结构之双链表

朴灿烈づ我的快乐病毒、 2022-05-24 22:08 150阅读 0赞

### 1.0 可以说算是背景吧 ###

因为你用循环链表的话你想找到指针值执向的后继节点很容易，那你要是想找指针所指结点的前一个，那实在是太操蛋了，你还得在找一圈，就想好你在操场上跑步，后面的人给你一脚，本来你可以回头就是一个飞脚，但是不行，你只能快点跑，然后绕一圈跑到他后面才能收拾他，这。。。难受

为了避免你难受，双链表就来了。

### 2.0 什么是双链表 ###

双链表就是在循环链表的基础上，给每个结点增加前驱（prior）指针

#include <iostream> 
    using namespace std;
    //双向链表的结构
    struct DulNode{
        int data;
        DulNode *prior;
        DulNode *next;
    }; 
    
    class LinkList{
        public:
            //空的双向链表 只有头结点 
            LinkList(){
                first = new DulNode;
                first->next = first;            
                rear = first; 
                first->prior = rear; 
            }
            //采用头插法建立双向链表 
            LinkList(int a[],int n){
                //初始化一个只有头结点的空结点 前驱后继均指向自己 
                first = new DulNode;
                first->next = first;
                rear = first; 
                first->prior = rear; 
    
    
                //插入其他结点 
                for(int i=0;i<n;i++){
                    DulNode *s = new DulNode;
                    s->data = a[i];         //注意插入的时候链的拆解顺序 
                    s->next = first->next;  //s->next = 原来第一个结点
                    first->next->prior = s; //原来第一个结点的前驱指向新的结点 
                    first->next = s;        //头结点的后结点指向新的结点 
                    s->prior = first;       //新的结点的前驱指向头结点 
                    if(i == 0)rear = s;
                }
            }
            void ShowDulList(){
                DulNode *p;//工作指针
                p = first->next; 
                while(p != first ){
    
                    cout<<"这个数是："; 
                    cout<<p->data<<endl<<"他的前驱是"<<p->prior->data<<endl
                    <<"他的后继节点是"<<p->next->data<<endl;
                    cout<<"---------------------------------------\n";
                    p = p->next;
                }
            } 
        private:
            DulNode *first; 
            DulNode *rear;
    };
    
    int main(){
        int a[6] = {
       1,2,3,4,5,6};
        LinkList dul(a,6);
        dul.ShowDulList();
    }

上述代码是双链表的初始化，但是有一个问题，就是第一个结点的前驱和最后结点的后继指向的是头结点，这显然不是我们所需要的，所以我们稍稍的修改下

#include <iostream> 
    using namespace std;
    //双向链表的结构
    struct DulNode{
        int data;
        DulNode *prior;
        DulNode *next;
    }; 
    
    class LinkList{
        public:
            //空的双向链表 只有头结点 
            LinkList(){
                first = new DulNode;
                first->next = first;            
                rear = first; 
                first->prior = rear; 
            }
            //采用头插法建立双向链表 
            LinkList(int a[],int n){
                length = n;
                //初始化一个只有头结点的空结点 前驱后继均指向自己 
                first = new DulNode;
                first->next = first;
                rear = first; 
                first->prior = rear; 
    
    
                //插入其他结点 
                for(int i=0;i<n;i++){
                    DulNode *s = new DulNode;
                    s->data = a[i];         //注意插入的时候链的拆解顺序 
                    s->next = first->next;  //s->next = 原来第一个结点
                    first->next->prior = s; //原来第一个结点的前驱指向新的结点 
                    first->next = s;        //头结点的后结点指向新的结点 
                    s->prior = first;       //新的结点的前驱指向头结点 
                    if(i == 0)rear = s;
                }
    
                //修改bug
    
                rear->next = first->next;
                first->next->prior = first->prior; 
            }
            void ShowDulList(){
                DulNode *p;//工作指针
                p = first->next; 
                int count = 0;
                while(count != length){             
                    cout<<"这个数是："; 
                    cout<<p->data<<endl<<"他的前驱是"<<p->prior->data<<endl
                    <<"他的后继节点是"<<p->next->data<<endl;
                    cout<<"---------------------------------------\n";
                    p = p->next;
                    count++;
                }
            } 
        private:
            DulNode *first; 
            DulNode *rear;
            int length;
    };
    
    int main(){
        int a[6] = {
       1,2,3,4,5,6};
        LinkList dul(a,6);
        dul.ShowDulList();
    }

> 这里注意插入的时候应该注意修改指针的顺序，  
> 例如如果先给first->next = s;  
> 那么就不能修改插入位置的后面那个结点的前驱指针，因为first->next已经不指向那个结点了

这是最开始的是初始化的方式，中间有bug 改了半天没成功，后来换了上面的那个算法，然后不知道怎么改的这个bug又修复了，所以贴出来，怎么用看你们心情了

#include <iostream> 
    using namespace std;
    //双向链表的结构
    struct DulNode{
        int data;
        DulNode *prior;
        DulNode *next;
    }; 
    
    class LinkList{
        public:
            //空的双向链表 只有头结点 
            LinkList(){
                first = new DulNode;
                first->next = first;            
                rear = first; 
                first->prior = rear; 
            }
            //采用头插法建立双向链表 
            LinkList(int a[],int n){
                //初始化一个只有头结点的空结点 前驱后继均指向自己 
                first = new DulNode;
                first->next = NULL;
                first->prior = NULL; 
    
                length = n;
                //插入其他结点 
                for(int i=0;i<n;i++){
    
                    DulNode *s = new DulNode;
                    s->data = a[i];         //注意插入的时候链的拆解顺序 
                     if(i == 0)
                     {                  
                        first->next = s;
                        first->prior = s;
                        s->next = first->next;
                        s->prior = first->prior;
                        s->data = a[0];
                    }else{
    
                        s->data = a[i]; 
                        s->next = first->next;          //s->next = 原来第一个结点
                        first->next->prior = s;
                        first->next = s;                //原来第一个结点的前驱指向新的结点 
                        first->prior->next = s;        //头结点的后结点指向新的结点 
                        s->prior = first->prior;       //新的结点的前驱指向头结点 
    
                    }          
                }
            }
            void ShowDulList(){
                DulNode *p;//工作指针
                p = first->next; 
                int count = 0;
                while(count != length ){
                    count++;
                    cout<<"这个数是："; 
                    cout<<p->data<<endl<<"他的前驱是"<<p->prior->data<<endl
                    <<"他的后继节点是"<<p->next->data<<endl;
                    cout<<"---------------------------------------\n";
                    p = p->next;
                }
            } 
        private:
            DulNode *first; 
            DulNode *rear;
            int length;
    };
    
    int main(){
        int a[6] = {
       1,2,3,4,5,6};
        LinkList dul(a,6);
        dul.ShowDulList();
    }