有序顺序表合并

---

将两个有序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

//[顺序表合并]将两个（有序）顺序表 合并为一个 新的（有序）顺序表，并由函数返回结果顺序表
#include "preset.h"

//顺序表合并（利用三个int类型指针i\j\k）
bool merge(SqList a, SqList b, SqList &c) {
    if (c.length < a.length + b.length) return false;
    int i = 0, j = 0, k = 0;
    //逐个比较 将较小的插入顺序表c中
    while (i < a.length && j < b.length) {
        if (a.elem[i] <= b.elem[j]) {
            c.elem[k] = a.elem[i]; i++; k++;
        } else {
            c.elem[k] = b.elem[j]; j++; k++;
        }
    }
    //剩余元素直接插入结果
    while (i < a.length) {
        c.elem[k] = a.elem[i]; k++; i++;
    }
    while (j < b.length) {
        c.elem[k] = b.elem[j]; k++; j++;
    }
    //修改顺序表c的长度
    c.length = a.length + b.length;
    return true;
}

//顺序表合并（利用三个int*类型指针pa\pb\pc）
bool mergeList(SqList La, SqList Lb, SqList &Lc) {
    if (Lc.length < La.length + Lb.length) return false;
    //1.准备指向有序数组首元素的各个指针
    int *pa = La.elem;
    int *pb = Lb.elem;
    int *pc = Lc.elem;
    Lc.length = La.length + Lb.length;

    //2.准备指向有序数组尾元素的指针
    int *paLast = La.elem + La.length - 1;
    int *pbLast = Lb.elem + Lb.length - 1;
    
    //3.依次摘取两表中较小的结点进行插入操作
    while (pa <= paLast && pb <= pbLast) {
        if (*pa <= *pb) {
            *pc = *pa; pc++; pa++;
        } else {
            *pc = *pb; pc++; pb++;
        }
    }

    //4.将某一个表中剩余的元素全部添加到Lc中
    while (pa <= paLast) *pc++ = *pa++;
    while (pb <= pbLast) *pc++ = *pb++;
    return true;
}

int main() {
    SqList a = {{2, 2, 3, 3, 4, 5}, 6}; print(a);
    SqList b = {{4, 4, 4, 5, 5, 6, 8, 10}, 8}; print(b);
    SqList c;
    if (!merge(a, b, c)) cout << "合并出现错误" << endl;
    else print(c);
    return 0;
}