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

【问题描述】
已知两个集合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的最后
    }
}

在一个沙雕问题上纠结了好久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;
}

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;
}