【数据结构】第2章线性表线性表的合并

迷南。 2022-11-26 07:47 220阅读 0赞

【顺序表的初始化、表长、取值、查找、插入、遍历、合并；单链表的表长、取值、查找、插入、遍历、后插法（尾插法）创建、合并】算法步骤+完整代码

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

【问题描述】  
已知两个集合A和B, 现要求一个新的集合A = AUB。例如， 设 A =(7, 5, 3, 11) B=(2, 6, 3) 合并后 A = (7 , 5 , 3 , 11 , 2 , 6)  
【问题分析】  
可以利用两个线性表 LA和 LB 分别表示集合A和B (即线性表中的数据元素为集合中的成员， 这样只需扩大线性表LA, 将存在于LB中而不存在于LA 中的数据元素插入到 LA 中去。 只要从LB 中依次取得每个数据元素， 并依值在LA中进行查访， 若不存在， 则插入之。  
【算法步骤】（顺序表和链式表通用）

//线性表并集 O(n)
    void MergeList(List &LA, List LB)
    {
        //将所有在线性表LB中但不在LA中的数据元素插入到LA中，无重复
        int m = ListLength(LA), n = ListLength(LB);     //求线性表长度
        for(int i = 1; i <= n; i++) 
        {
        
            ElemType e;
            GetElem(LB, i, e);                          //取LB中的第i个元素赋给e
            if(!LocateElem(LA, e))                      //LA中不存在与e相同的数据元素
                ListInsert(LA, ++m, e);                 //将e插在LA的最后
        }
    }

在一个[沙雕问题][Link 1]上纠结了好久QAQ

## 1、顺序表的合并 ##

【完整代码】

#include<bits/stdc++.h>
    using namespace std;
    typedef int Status;
    typedef int ElemType;
    #define OVERFLOW -1
    #define ERROR 0
    #define OK 1
    
    //-----顺序表的储存结构-----
    #define MAXSIZE 100
    typedef struct 
    {
        
        ElemType *elem;     //沙雕问题的根源：这里终究只是一个指针，并不是有确定长度的数组，不能L.elem[3] = {1, 2, 3}这样赋值！！！
        int length;         //确定长度
    }SqList;
    
    SqList LA, LB;
    
    //1、顺序表初始化
    Status InitList(SqList &L)
    {
        //构造一个空的顺序表L
        L.elem = new ElemType[MAXSIZE];     //为顺序表分配一个大小为MAXSIZE的数组空间
        if(!L.elem)                         //如果分配失败，则L.elem会指向NULL，即此判断为真
            exit(OVERFLOW);                 //储存分配失败退出
        L.length = 0;                       //空表长度为0
        return OK;
    }
    
    //5、顺序表表长
    Status ListLength(SqList L)
    {
        
        return L.length;
    }
    
    //6、顺序表取值 O(1)
    Status GetElem(SqList L, int i, ElemType &e)
    {
        
        if(i < 1 || i > L.length)   //判断i值是否合理，若不合理，返回ERROR
            return ERROR;
        e = L.elem[i - 1];          //elem[i - 1]储存第i个数据元素
        return OK;
    }
    
    //7、顺序表查找 O(n)
    Status LocateElem(SqList L, ElemType e)
    {
        //再顺序表中查找值为e的元素，返回其序号
        for(int i = 0; i < L.length; i++)
            if(L.elem[i] == e)
                return i + 1;               //查找成功，返回序号i + 1
        return ERROR;                       //查找失败，返回0
    }
    
    //10、顺序表插入 O(n)
    Status ListInsert(SqList &L, int i, ElemType e)
    {
        //在顺序表L中第i个位置之前插入新的元素e, i值的合法范围是1 <= i <= L.length+1
        if(i < 1 || i > L.length + 1)               //i值不合法
            return ERROR;
        if(L.length == MAXSIZE)                 //当前存储空间已满
            return ERROR;
        for(int j = L.length - 1; j >= i - 1; j--)
            L.elem[j + 1] = L.elem[j];          //插入位置之后的元素后移
        L.elem[i - 1] = e;                      //将新元素e放在第i个位置
        L.length++;                             //表长+1
        return OK; 
    }
    
    //12、顺序表遍历
    Status TraverseList(SqList L)
    {
        
        for(int i = 0; i < L.length; i++)
        {
        
            if(i == L.length - 1)
                cout<<L.elem[i]<<'\n';
            else
                cout<<L.elem[i]<<' ';
        }
        return OK;
    }
    
    //13、顺序表并集 O(m * n)
    void MergeList(SqList &LA, SqList LB)
    {
        //将所有在线性表LB中但不在LA中的数据元素插入到LA中，无重复
        int m = ListLength(LA), n = ListLength(LB);     //求线性表长度
        for(int i = 1; i <= n; i++) 
        {
        
            ElemType e;
            GetElem(LB, i, e);                          //取LB中的第i个元素赋给e
            if(!LocateElem(LA, e))                      //LA中不存在与e相同的数据元素
                ListInsert(LA, ++m, e);                 //将e插在LA的最后
        }
    }
    
    //顺序表的合并
    int main()
    {
        
        int n;
        ElemType e;
        cout<<"请输入LA的元素个数：";
        cin>>n;
        cout<<"请按顺序输入这"<<n<<"个元素：";
        InitList(LA);
        for(int i = 1; i <= n; i++)
        {
        
            cin>>e;
            ListInsert(LA, i, e);
        }
        cout<<"请输入LB的元素个数：";
        cin>>n;
        cout<<"请按顺序输入这"<<n<<"个元素：";
        InitList(LB);
        for(int i = 1; i <= n; i++)
        {
        
            cin>>e;
            ListInsert(LB, i, e);
        }
        cout<<'\n';
        cout<<"集合A为：";
        TraverseList(LA);
        cout<<"集合B为：";
        TraverseList(LB);
        MergeList(LA, LB);
        cout<<"A与B合并后为：";
        TraverseList(LA);
        return 0;
    }

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

## 2、单链表的合并 ##

【完整代码】

#include<bits/stdc++.h>
    using namespace std;
    typedef int Status;
    typedef int ElemType;
    #define OVERFLOW -1
    #define ERROR 0
    #define OK 1
    
    //-----单链表的储存结构-----
    typedef struct LNode
    {
        
        ElemType data;              //结点的数据域
        struct LNode *next;         //结点的指针域
    }LNode, *LinkList;              //LinkList为指向结构体LNode的指针类型
    
    LinkList LA, LB;
    
    //5、单链表表长 O(n)
    Status ListLength(LinkList L)
    {
        //返回带头结点的单链表的长度
        LNode *p = L;                   //p指向头结点
        int j = 0;                      //计数器j初值赋为0
        while(p->next)                  //直到p的后继为空时停止
        {
        
            p = p->next;                //p指向下一个结点
            j++;                        //计数器j相应加1
        }
        return j;
    }
    
    //6、单链表取值 O(n)
    Status GetElem(LinkList L, int i, ElemType &e)
    {
        //在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个元素的值
        LNode *p = L->next;             //p指向首元结点
        int j = 1;                      //计数器j初值赋为1
        while(p && j < i)               //直到p为空或p指向第i个元素时停止
        {
        
            p = p->next;                //p指向下一个结点               
            j++;                        //计数器j相应加1                       
        }
        if(!p || j > i)                 //i值不合法，即i > n或i < 1
            return ERROR;
        e = p->data;                    //取第i个结点的数据域
        return OK;
    }
    
    //7、单链表查找 O(n)
    LNode *LocateElem(LinkList L, ElemType e)
    {
        //在带头结点的单链表中查找值为e的元素，返回e的地址（所以LNode *LocateElem）
        LNode *p = L->next;             //p指向首元结点
        while(p && p->data != e)        //直到p为空或p所指结点的数据域等于e时停止
            p = p->next;                //p指向下一个结点
        return p;                       //查找成功返回值为e的结点地址p，查找失败p为NULL
    }
    
    //10、单链表插入 O(n)
    Status ListInsert(LinkList &L, int i, ElemType e)
    {
        //在带头结点的单链表L中第i个位置插入值为e的新结点
        LNode *p = L;                   //p指向头结点
        int j = 0;                      //计数器j初值赋为0
        while(p && j < i - 1)           //直到p为空或p指向第i-1个结点时停止
        {
        
            p = p->next;                //p指向下一个结点
            j++;                        //计数器j相应加1
        }                               
        if(!p || j > i - 1)             //i值不合法，即i > n + 1或i < 1
            return ERROR;
        LNode *s = new LNode;           //生成新结点*s
        s->data = e;                    //将结点*s的数据域置为e
        s->next = p->next;              //先接后链
        p->next = s;                    //再接前链
        return OK; 
    }
    
    //12、单链表遍历 O(n)
    Status TraverseList(LinkList L)
    {
        
        LNode *p = L->next;             
        while(p->next)
        {
        
            cout<<p->data<<' ';
            p = p->next;
        }
        cout<<p->data<<'\n';
        return OK;
    }
    
    //14、后插法创建单链表 O(n)
    void CreateList_R(LinkList &L, int n)
    {
        //正位序输入n个元素的值，建立带头结点的单链表L
        L = new LNode;                  //先初始化一个带头结点的空链表
        L->next = NULL;                 
        LNode *r = L;                   //尾指针r先指向头结点
        for(int i = 0; i < n; i++)
        {
        
            LNode *p = new LNode;       //生成新结点*p
            cin>>p->data;               //输入元素值赋给新结点*p的数据域
            p->next = NULL;             //后置空后链             
            r->next = p;                //再接前链
            r = p;                      //r指向新的尾结点*p
        }
    }
    
    //16、单链表并集 O(m * n)
    void MergeList(LinkList &LA, LinkList LB)
    {
        //将所有在线性表LB中但不在LA中的数据元素插入到LA中，无重复
        int m = ListLength(LA), n = ListLength(LB);     //求线性表长度
        for(int i = 1; i <= n; i++) 
        {
        
            ElemType e;
            GetElem(LB, i, e);                          //取LB中的第i个元素赋给e
            if(!LocateElem(LA, e))                      //LA中不存在与e相同的数据元素
                ListInsert(LA, ++m, e);                 //将e插在LA的最后，先++，再传值
        }
    }
    
    //单链表的合并
    int main()
    {
        
        int n;
        cout<<"请输入集合A的元素个数：";
        cin>>n;
        cout<<"请按顺序输入这"<<n<<"个元素：";
        CreateList_R(LA, n);
        cout<<"请输入集合B的元素个数：";
        cin>>n;
        cout<<"请按顺序输入这"<<n<<"个元素：";
        CreateList_R(LB, n);
        cout<<'\n';
        cout<<"集合A为：";
        TraverseList(LA);
        cout<<"集合B为：";
        TraverseList(LB);
        MergeList(LA, LB);
        cout<<"A与B合并后为：";
        TraverseList(LA);
        return 0;
    }

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

[Link 1]: https://zhidao.baidu.com/question/476539140.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70]: /images/20221124/f362108879db42609dfcf5ef9a6756e6.png