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

缺乏、安全感 2022-11-26 07:59 284阅读 0赞

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

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

> 若线性表中的数据元素相互之间可以比较， 并且数据元素在线性表中依值非递减或非递增有序排列，则称该线性表为有序表(OrderedList)。

现求解有序集合的并集问题。  
【问题描述】  
有序集合是指集合中的元素有序排列。 已知两个有序集合A和B, 数据元素按值非递减有序排列， 现要求一个新的集合C=AUB, 使集合C中的数据元素仍按值非递减有序排列。 例如， 设 A= (3, 5, 8, 11) B=(2, 6, 8, 9, 11, 15, 20) 则 C = (2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20)  
【问题分析】  
与线性表的合并一样， 可以利用两个线性表LA和LB分别表示集合A和B, 不同的是，此例中的 LA和LB有序， 这样便没有必要从LB中依次取得每个数据元素，到LA中进行查访。 如果LA和LB两个表长分别记为m和n, 则合并后的新表LC的表长应该 为m+n。由于LC 中的数据元素或是LA中的元素，或是LB中的元素， 因此只要先设LC为空表， 然后将LA或 LB中的元素逐个插入到LC中即可。 为使LC中的元素按值非递减有序排列， 可设两个指针pa 和pb分别指向LA和LB中的某个元素， 若设pa当前所指的元素为 a, pb当前所指的元素为 b, 则当前应插入到LC中的元素 c为：  
![在这里插入图片描述][20200811113506504.png]  
显然，指针pa和pb的初值分别指向两个有序表的第一个元素， 在所指元素插入LC之后， 在LA或LB中顺序后移。 根据上述分析，分别给出有序表的顺序存储结构和链式存储结构相应合并算法的实现。

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

【算法步骤】  
1、创建一个表长为m+n的空表LC。  
2、指针pc初始化，指向LC的第一个元素。  
3、指针pa和pb初始化，分别指向LA和LB的第一个元素。  
4、当指针pa和pb均未到达相应表尾时， 则依次比较pa和pb所指向的元素值，从LA或 LB中 ＂摘取“ 元素值较小的结点插入到LC的最后。  
5、如果pb巳到达LB的表尾， 依次将LA的剩余元素插入LC的最后。  
6、如果pa已到达LA的表尾， 依次将LB的剩余元素插入LC的最后。

//14、有序顺序表合并 时间O(n + m) 空间O(n + m)
    void MergeList(SqList LA, SqList LB, SqList &LC)
    {
        //已知有序顺序表LA和LB的元素按值非递减排列
     //归并LA和LB得到新的有序顺序表LC，LC的元素也按值非递减排列
        LC.length = LA.length + LB.length;                       //新表长度为待合并量表的长度之和
        LC.elem = new ElemType[LC.length];                       //为合并后的信标分配一个数组空间
        ElemType *pc = LC.elem, *pa = LA.elem, *pb = LB.elem;    //指针均指向表的第一个元素
        ElemType *pa_last = LA.elem + LA.length - 1;             //指向LA的最后一个元素
        ElemType *pb_last = LB.elem + LB.length - 1;             //指向LB的最后一个元素
        while(pa <= pa_last && pb <= pb_last)                    //LA和LB均未到达表尾
        {
        
            if(*pa <= *pb)          //依次“摘取”两表中值较小的结点插入到LC的最后
                *pc++ = *pa++;      //先把*pa赋给*pc，再pa++和pc++，都指向数组的下一个位置
            else
                *pc++ = *pb++;
        }
        while(pa <= pa_last)        //LB已到达表尾，依次将LA的剩余元素插入LC的后面
            *pc++ = *pa++;
        while(pb <= pb_last)        //LA已到达表尾，依次将LB的剩余元素插入LC的后面
            *pc++ = *pb++;
    }

【完整代码】

#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, LC;
    
    //1、顺序表初始化 O(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;
    }
    
    //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、顺序表遍历 O(n)
    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;
    }
    
    //14、有序顺序表合并 时间O(n + m) 空间O(n + m)
    void MergeList(SqList LA, SqList LB, SqList &LC)
    {
        //已知4顺序有序表LA和LB的元素按值非递减排列
     //归并LA和LB得到心的顺序有序表LC，LC的元素也按值非递减排列
        LC.length = LA.length + LB.length;                       //新表长度为待合并量表的长度之和
        LC.elem = new ElemType[LC.length];                       //为合并后的信标分配一个数组空间
        ElemType *pc = LC.elem, *pa = LA.elem, *pb = LB.elem;    //指针均指向表的第一个元素
        ElemType *pa_last = LA.elem + LA.length - 1;             //指向LA的最后一个元素
        ElemType *pb_last = LB.elem + LB.length - 1;             //指向LB的最后一个元素
        while(pa <= pa_last && pb <= pb_last)                    //LA和LB均未到达表尾
        {
        
            if(*pa <= *pb)          //依次“摘取”两表中值较小的结点插入到LC的最后
                *pc++ = *pa++;      //先把*pa赋给*pc，再pa++和pc++，都指向数组的下一个位置
            else
                *pc++ = *pb++;
        }
        while(pa <= pa_last)        //LB已到达表尾，依次将LA的剩余元素插入LC的后面
            *pc++ = *pa++;
        while(pb <= pb_last)        //LA已到达表尾，依次将LB的剩余元素插入LC的后面
            *pc++ = *pb++;
    }
    
    //有序顺序表的合并
    int main()
    {
        
        int n;
        ElemType e;
        cout<<"请输入集合A的元素个数：";
        cin>>n;
        cout<<"请按顺序输入这"<<n<<"个元素：";
        InitList(LA);
        for(int i = 1; i <= n; i++)
        {
        
            cin>>e;
            ListInsert(LA, i, e);
        }
        cout<<"请输入集合B的元素个数：";
        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, LC);
        cout<<"A与B的并集C（仍按值非递减有序排列）为：";
        TraverseList(LC);
        return 0;
    }

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

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

【算法步骤】  
1、指针pa和pb初始化，分别指向LA和LB的第一个结点。  
2、LC的结点取值为LA的头结点。  
3、指针pc初始化，指向LC的头结点。  
4、当指针 pa 和 pb 均未到达相应表尾时，则依次比较 pa 和 pb 所指向的元素值，从 LA 或 LB 中 ＂摘取“ 元素值较小的结点插入到LC的最后。  
5、将非空表的剩余段插入到pc所指结点之后。  
6、释放 LB的头结点。

//18、有序单链表并集_非递减 空间O(1)
    void MergeOrderList(LinkList &LA, LinkList &LB, LinkList &LC)
    {
        //已知单链表LA和LB的元素按值非递减排列
     //归并LA和LB得到新的单链表LC，LC的元素也按值非递减排列，允许有重复
        LC = new LNode;                 
        LC = LA;                        //用LA的头结点作为LC的头结点
        LNode *pa = LA->next;           //指针pa和pb的初值分别指向两个表的首元结点
        LNode *pb = LB->next;
        LNode *pc = LC;                 //指针pc的初值指向LC的头结点
        while(pa && pb)                 //LA和LB均未到达表尾
        {
        
            if(pa->data > pb->data)     //“摘取”两表中值较小的结点插入到LC的最后
            {
        
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }
            else
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next; 
            }
        }
        pc->next = pa ? pa: pb;         //将非空表的剩余端插入到所指结点之后
        delete LB;                      //释放LB的头结点
    }

【完整代码】

#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, LC;
    
    //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
        }
    }
    
    //18、有序单链表并集_非递减 空间O(1)
    void MergeOrderList(LinkList &LA, LinkList &LB, LinkList &LC)
    {
        //已知单链表LA和LB的元素按值非递减排列
     //归并LA和LB得到新的单链表LC，LC的元素也按值非递减排列，允许有重复
        LC = new LNode;                 
        LC = LA;                        //用LA的头结点作为LC的头结点
        LNode *pa = LA->next;           //指针pa和pb的初值分别指向两个表的首元结点
        LNode *pb = LB->next;
        LNode *pc = LC;                 //指针pc的初值指向LC的头结点
        while(pa && pb)                 //LA和LB均未到达表尾
        {
        
            if(pa->data > pb->data)     //“摘取”两表中值较小的结点插入到LC的最后
            {
        
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }
            else
            {
        
                pc->next = pa;
                pc = pa;
                pa = pa->next; 
            }
        }
        pc->next = pa ? pa: pb;         //将非空表的剩余端插入到所指结点之后
        delete LB;                      //释放LB的头结点
    }
    
    
    //有序单链表的合并
    int main()
    {
        
        int n;
        ElemType e;
        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);
        MergeOrderList(LA, LB, LC);
        cout<<"A与B的并集C（仍按值非递减有序排列）为：";
        TraverseList(LC);
        return 0;
    }

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

[20200811113506504.png]: /images/20221124/905c9ee7f1124ab882c7b9c444b37a54.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70]: /images/20221124/54b1d278369f41339a6e286d052ab6dd.png