实现线性表合并的代码

Question

问题描述：
已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。
La=(1,7,8) Lb=(2,4,6,8,10,11) ——> Lc=(1,2,4,6,7,8,8,10,11)
如何将这两个表用C++实现出来呢？

void union(List &La, List Lb)
{
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    for(i = 1;i <= Lb_len; i++)
    {
        GetElem(Lb, i, e);
        if(!LocateElem(La, e))
        {
            ListInsert(&La, ++La_len, e);
        }
    }
}

Answer 1

#include<iostream>
using namespace std;
#define MaxSize 10

//有序表的合并

//顺序表的存储结构
struct SqList
{
    int * elem;
    int length;
};

//已知顺序有序表LA和LB的元素按照值非递减排序
//归并LA和LB得到新的顺序有序表LC，LC的元素也按值非递减排列
void MergeList_Sq(SqList LA, SqList LB, SqList *LC)
{
    int m = LA.length;
    int n = LB.length;
    LC->length = m + n;//新表长度为待合并的两表的长度之和

    LC->elem = (int*)malloc(MaxSize * sizeof(int));//为合并后的新表分配一个数组空间
    int *pc = LC->elem;//指针pc指向新表的第一个元素

    //指针pa和pb的初值分别指向两个表的第一个元素
    int *pa = LA.elem;
    int *pb = LB.elem;

    int *pa_last = LA.elem + m - 1;//指针pa_last指向LA的最后一个元素
    int *pb_last = LB.elem + n - 1;//指针pb_last指向LB的最后一个元素

    while((pa <= pa_last) && (pb <= pb_last))//两表均未达到表尾
    {
        if(*pa <= *pb)
        {
            *pc++ = *pa++;//依次“摘取”两表中值较小的结点插入到LC的最后
        }
        else 
        {
            *pc++ = *pb++;
        }
    }
    while(pa <= pa_last)
    {
        *pc++ = *pa++;//LB已到达表尾，依次将LA的剩余元素插入LC的最后
    }

    while(pb <= pb_last)
    {
        *pc++ = *pb++;//LA已到达表尾，依次将LB的剩余元素插入LC的最后
    }
}

//创建顺序表
void initList(SqList* L)
{
    L->elem = (int*)malloc(MaxSize * sizeof(int));//创建一个空的顺序表
    
    if(!L->elem)
    {
        cout << "初始化失败！" << endl;
        exit(0);
    }
    L->length = 0;//空表的长度初始化为0
}

//遍历表
void displayList(SqList L)
{
    for(int i = 0;i < L.length; i++)
    {
        cout << L.elem[i] << " ";
    }
    cout << endl;
}
                         

//测试代码
void test()
{
    SqList LA, LB, LC;
    
    initList(&LA);
    initList(&LB);
    initList(&LC);
    
    for(int i = 1;i <= MaxSize; i++)
    {
        LA.elem[i - 1] = i;
        LA.length++;
    }
    
    for(int j = 1;j <= MaxSize; j++)
    {
        LB.elem[j - 1] = j + 2;
        LB.length++;
    }
    
    cout << "顺序表LA（元素按值非递减排序）：" << endl;
    displayList(LA);

    cout << "顺序表LB（元素按值非递减排序）：" << endl;
    displayList(LB);

    cout << "归并LA和LB得到新的顺序有序表 LC：" << endl;
    MergeList_Sq(LA, LB, &LC);
    displayList(LC);
}

int main()
{
    test();//测试代码
    return 0;
}