C语言顺序表合并算法实现

本代码实现了一个简单的顺序表合并算法，将两个已排序的顺序表合并成一个新的已排序的顺序表。

#include <stdio.h>
#include <stdlib.h>

#define MAX_LIST_SIZE  100
#define LISTINCREMENT  10

#define OK 1
#define OVERFLOW 0
typedef int Status;

typedef struct {
    int *elem;
    size_t length;
    size_t listsize;
} SqList;

Status InitList(SqList& L, size_t length, size_t listsize) {
    L.elem = (int *)calloc(listsize, sizeof(int));
    L.length = length;
    L.listsize = listsize;
    if (!L.elem) {
        exit(OVERFLOW);
    }
    return OK;
}

Status MergeList_Sq(const SqList& La, const SqList& Lb, SqList& Lc) {
    size_t length1 = La.length;
    size_t length2 = Lb.length;
    size_t i = 0, j = 0, k = 0;

    while (i < length1 - 1 && j < length2 - 1) {
        int ai = La.elem[i];
        int bj = Lb.elem[j];
        if (ai <= bj) {
            Lc.elem[k] = ai;
            i++;
        } else {
            Lc.elem[k] = bj;
            j++;
        }
        k++;
    }

    while (i < length1 - 1) {
        Lc.elem[k] = La.elem[i];
        i++;
        k++;
    }
    while (j < length2 - 1) {
        Lc.elem[k] = Lb.elem[j];
        j++;
        k++;
    }

    Lc.length = k;
    return OK;
}

int main() {
    SqList La, Lb, Lc;
    size_t length1, length2;

    printf('请输入第一个顺序表的长度：\n');
    scanf('%zu', &length1);
    if (!InitList(La, length1, MAX_LIST_SIZE)) {
        printf('La初始化出错！\n');
        return 0;
    }
    printf('请输入第一个顺序表的序列值：\n');
    for (size_t i = 0; i < length1; i++) {
        scanf('%d', &La.elem[i]);
    }

    printf('请输入第二个顺序表的长度：\n');
    scanf('%zu', &length2);
    if (!InitList(Lb, length2, MAX_LIST_SIZE)) {
        printf('Lb初始化出错！\n');
        return 0;
    }
    printf('请输入第二个顺序表的序列值：\n');
    for (size_t j = 0; j < length2; j++) {
        scanf('%d', &Lb.elem[j]);
    }

    if (!InitList(Lc, length1 + length2, MAX_LIST_SIZE)) {
        printf('Lc初始化出错！\n');
        return 0;
    }
    if (!MergeList_Sq(La, Lb, Lc)) {
        printf('顺序表合并出错！\n');
        return 0;
    }

    printf('合并后的顺序表Lc为：');
    for (size_t k = 0; k < Lc.length; k++) {
        printf('%d ', Lc.elem[k]);
    }
    printf('\n');

    free(La.elem);
    free(Lb.elem);
    free(Lc.elem);
    return 0;
}

代码解释

数据结构定义: 使用 SqList 结构体来表示顺序表，包含三个成员变量：
- elem: 指向顺序表元素的指针
- length: 顺序表长度
- listsize: 顺序表容量
初始化函数 InitList: 用于初始化一个顺序表，分配内存空间，并设置长度和容量。
合并函数 MergeList_Sq: 实现两个已排序顺序表的合并算法：
- 使用两个指针 i 和 j 分别指向 La 和 Lb 的第一个元素
- 使用指针 k 指向 Lc 的第一个元素
- 循环比较 La 和 Lb 的当前元素，将较小的元素添加到 Lc 中，并移动对应的指针
- 最后将剩余的元素添加到 Lc 中
主函数 main:
- 获取用户输入的两个顺序表的长度和元素值
- 初始化三个顺序表 La, Lb 和 Lc
- 调用 MergeList_Sq 函数合并 La 和 Lb 到 Lc
- 打印合并后的顺序表 Lc
- 释放分配的内存

注意

本代码假设两个输入的顺序表已经按照升序排序
在读取顺序表元素时，请确保输入的元素数量与长度一致，否则会导致合并结果错误。
程序运行时可能会出现内存泄漏问题，建议在程序结束时释放所有分配的内存。

扩展

可以对本代码进行扩展，支持降序排序的顺序表合并
可以增加判断输入顺序表是否已经排序的逻辑，以确保合并结果的正确性
可以将 MergeList_Sq 函数封装成一个通用的函数，支持不同数据类型的顺序表合并