【数据结构】第2章线性表双向链表

左手的ㄟ右手 2022-11-26 01:54 204阅读 0赞

【双向链表的初始化、按位查找、按值查找、前驱、后继、插入、删除、遍历、前插法（头插法）、后插法（尾插法）】完整代码

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70]

#include<bits/stdc++.h>
    using namespace std;
    typedef int Status;
    typedef int ElemType;
    #define OVERFLOW -1
    #define ERROR 0
    #define OK 1
    
    //-----双向链表的储存结构-----
    typedef struct DuLNode
    {
        
        ElemType data;                  //数据域
        struct DuLNode *prior;          //直接前驱
        struct DuLNode *next;           //直接后继
    }DuLNode, *DuLinkList;
    
    DuLinkList L;
    
    //1、双向链表初始化
    Status InitList_DuL(DuLinkList &L)
    {
        //构造一个空的双向链表L
        L = new DuLNode;              
        L->prior = NULL;
        L->next = NULL;             
        return OK;
    }
    
    //6、双向链表按位查找
    DuLNode *GetElem_DuL(DuLinkList L, int i)
    {
        
        DuLNode *p = L->next;
        int j = 1;   
        while(p && j < i)
        {
        
            p = p->next;
            j++;
        }
        if(!p || j > i)
            return NULL;
        else
            return p;
    }
    
    //7、双向链表按值查找
    DuLNode *LocateElem_DuL(DuLinkList L, ElemType e)   //返回的是e结点的地址，所以LNode *
    {
        //在带头结点的双向链表中查找值为e的元素
        DuLNode *p = L->next;                     //p指向首元结点
        while(p && p->data != e)                //顺链域向后扫描，直到p为空或p所指结点的数据域等于e
            p = p->next;                        //p指向下一个结点
        return p;                               //查找成功返回值为e的结点地址p，查找失败p为NULL
    }
    
    //8、双向链表前驱
    Status PriorElem_DuL(DuLinkList L, ElemType cur_e, ElemType &pre_e)
    {
        
        DuLNode *p;
        if(!(p = LocateElem_DuL(L, cur_e)))                //在L中确定第i个元素的位置指针p
            return ERROR;
        pre_e = p->prior->data;
        return OK; 
    }
    
    //9、双向链表后继
    Status NextElem_DuL(DuLinkList L, ElemType cur_e, ElemType &next_e)
    {
        
        DuLNode *p;
        if(!(p = LocateElem_DuL(L, cur_e)))                //在L中确定第i个元素的位置指针p
            return ERROR;
        next_e = p->next->data;
        return OK; 
    }
    
    //10、双向链表插入
    Status ListInsert_DuL(DuLinkList &L, int i, ElemType e)
    {
        //在带头结点的双向链表L中第i个位置之前插入元素e
        DuLNode *p;
        if(!(p = GetElem_DuL(L, i)))                //在L中确定第i个元素的位置指针p
            return ERROR;                           //p为NULL时，第i个元素不存在
        DuLNode *s = new DuLNode;                   //生成新结点*s
        s->data = e;                                //将结点*s的数据域置为e
        s->prior = p->prior;                        //将结点*s插入L中，步骤1
        p->prior->next = s;                         //步骤2
        s->next = p;                                //步骤3
        p->prior = s;                               //步骤4
        return OK;
    }
    
    //11、双向链表删除
    Status ListDelete_DuL(DuLinkList &L, int i)
    {
        //删除带头结点的双向链表L中的第i个元素
        DuLNode *p;
        if(!(p = GetElem_DuL(L, i)))                //在L中确定第i个元素的位置指针p
            return ERROR;                           //p为NULL时，第i个元素不存在
        p->prior->next = p->next;                   //步骤1
        p->next->prior = p->prior;                  //步骤2
        delete p;                                   //释放被删除结点的空间
        return OK; 
    }
    
    //12、双向链表遍历
    Status TraverseList_DuL(DuLinkList L)
    {
        
        DuLNode *p = L->next;             //p指向首元结点
        while(p->next)
        {
        
            cout<<p->data<<' ';
            p = p->next;
        }
        cout<<p->data<<'\n';
        return OK;
    }
    
    //13、前插法创建双向链表
    void CreateList_H_DuL(DuLinkList &L, int n)
    {
        //逆位序输入n个元素的值，建立带头结点的双向链表L
        L = new DuLNode;
        DuLNode *p = new DuLNode;           //生成新结点*p
        cin>>p->data;
        L->prior = NULL;
        L->next = p;
        p->prior = L;
        p->next = NULL;
        for(int i = 1; i < n; i++)
        {
        
            DuLNode *s = new DuLNode;       //生成新结点*s 
            cin>>s->data;
            s->prior = p->prior;            //步骤1
            p->prior->next = s;             //步骤2
            s->next = p;                    //步骤3
            p->prior = s;                   //步骤4
            p = s;
        }
    }
    
    //14、后插法创建双向链表
    void CreateList_R_DuL(DuLinkList &L, int n)
    {
        //正位序输入n个元素的值，建立带头结点的双向链表L
        L = new DuLNode;
        L->next = NULL;                 //先建立一个带头结点的空链表
        DuLNode *r = L;                   //尾指针r指向头结点
        for(int i = 0; i < n; i++)
        {
        
            DuLNode *p = new DuLNode;       //生成新结点*p
            cin>>p->data;               //输入元素值赋给新结点*p的数据域
            r->next = p;                //将新结点*p插入尾结点*r之后
            p->next = NULL;             
            p->prior = r;
            r = p;                      //r指向新的尾结点*p
        }
    }
    
    //双向链表
    int main()
    {
        
        cout<<"------------------------双向链表菜单----------------------"<<'\n';
        cout<<"操作0：退出程序"<<'\n';
        cout<<"操作1：创建一个带头结点的双向链表，且遍历此链表"<<'\n';
        cout<<"操作2：查找双向链表中的第i个结点，并输出结点元素的值"<<'\n';
        cout<<"操作3：在双向链表中的第i个结点前插入一个结点值为e的正整数"<<'\n';
        cout<<"操作4：删除双向链表链表中的第j个结点"<<'\n';
        cout<<"--------------------------------------------------------"<<'\n';
        int a, n, flag = 1;
        while(flag)
        {
        
            cout<<'\n'<<"请选择要执行的操作：";
            while(cin>>a)
            {
        
                if(a < 0 || a > 5)
                    cout<<"请选择正确操作编号：";
                else
                    break;
            }
            switch(a)
            {
        
                case 0:
                {
        
                    cout<<"感谢使用本程序，祝您生活愉快！"<<'\n';
                    flag = 0;
                    break;
                }
                case 1:
                {
        
                    cout<<"----菜单-----"<<'\n';
                    cout<<"操作1：前插法"<<'\n';
                    cout<<"操作2：后插法"<<'\n';
                    cout<<"-------------"<<'\n';
                    cout<<"请选择单链表的创建方式：";
                    int b;
                    while(cin>>b)
                    {
        
                        if(b != 1 && b != 2)
                            cout<<"请选择正确操作编号：";
                        else
                            break;
                    }
                    cout<<"请输入要建立的单链表的元素个数：";
                    cin>>n;
                    if(b == 1)
                    {
        
                        cout<<"请按逆位序依次输入这"<<n<<"个元素：";
                        CreateList_H_DuL(L, n);
                    }
                    else if(b == 2)
                    {
        
                        cout<<"请按正位序依次输入这"<<n<<"个元素：";
                        CreateList_R_DuL(L, n);
                    }
                    cout<<"单链表创建完毕：";
                    TraverseList_DuL(L);
                    break;
                }
                case 2:
                {
        
                    int i;
                    cout<<"查找单链表中的第i个结点,请输入i的值：";
                    cin>>i;
                    if(GetElem_DuL(L, i))
                        cout<<"单链表中的第"<<i<<"个结点元素为："<<GetElem_DuL(L, i)->data<<'\n';
                    else
                        cout<<"i值不合法！"<<'\n';
                    break;
                }
                case 3:
                {
        
                    int i;
                    ElemType e;
                    cout<<"在单链表中的第i个结点前插入一个结点值为e的正整数，请依次输入i和e的值：";
                    cin>>i>>e;
                    if(ListInsert_DuL(L, i, e))
                    {
        
                        cout<<"单链表插入完毕：";
                        TraverseList_DuL(L);
                    }
                    else
                        cout<<"i值不合法！"<<'\n';
                    break;
                }
                case 4:
                {
        
                    int j;
                    cout<<"删除单链表中的第j个结点，请输入j的值：";
                    cin>>j;
                    if(ListDelete_DuL(L, j))
                    {
        
                        cout<<"单链表删除完毕：";
                        TraverseList_DuL(L);
                    }
                    else
                        cout<<"j值不合法！"<<'\n';
                    break;
                }
            }
        }
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70]: /images/20221124/b78b57ce3c8a458b9554c855fa98a6d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70 1]: /images/20221124/a673e66270c14808bc0c628315b49e47.png