合并有序顺序表的C语言实现

在C语言中，我们通常使用结构体来定义顺序表，包括元素数组和当前长度等属性。

合并算法

合并两个有序顺序表的算法核心在于比较两个表中元素的大小，并按顺序将它们添加到新表中。算法步骤如下：

1. 初始化两个顺序表的索引，以及新顺序表的索引。
2. 比较两个顺序表当前索引指向的元素，将较小的元素添加到新顺序表中，并移动对应顺序表的索引。
3. 当一个顺序表的元素全部被添加到新表后，若另一个顺序表还有剩余元素，则将剩余的元素全部添加到新表。

C语言实现

以下是合并有序顺序表的C语言实现代码，包括顺序表的定义、初始化、合并函数以及打印函数。

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

// 定义元素类型
typedef int ElemType;

// 定义顺序表的最大容量
#define MAXSIZE 100

// 定义顺序表的结构体
typedef struct {
    ElemType *elem;      // 元素数组
    int length;          // 当前长度
} SqList;

// 初始化顺序表
int InitList(SqList *L) {
    L->elem = (ElemType *)malloc(MAXSIZE * sizeof(ElemType)); // 分配最大容量
    if (!L->elem) return -1; // 存储分配失败
    L->length = 0;
    return 1; // 初始化成功
}

// 合并两个顺序表
int MergeList(SqList La, SqList Lb, SqList *Lc) {
    int i = 0, j = 0, k = 0;
    Lc->length = La.length + Lb.length;
    Lc->elem = (ElemType*)malloc(Lc->length * sizeof(ElemType));
    if (!Lc->elem) return -1; // 存储分配失败

    while (i < La.length && j < Lb.length) {
        if (La.elem[i] <= Lb.elem[j]) Lc->elem[k++] = La.elem[i++];
        else Lc->elem[k++] = Lb.elem[j++];
    }
    while (i < La.length) Lc->elem[k++] = La.elem[i++];
    while (j < Lb.length) Lc->elem[k++] = Lb.elem[j++];

    return 1; // 归并成功
}

// 打印顺序表
void TraverseList(SqList L) {
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.elem[i]);
    }
    printf("\n");
}

// 主函数，用于测试
int main() {
    SqList La, Lb, Lc;

    // 测试用例1：两个顺序表都包含基本的递增序列
    if (InitList(&La) != 1 || InitList(&Lb) != 1) {
        printf("Initialization failed.\n");
        return -1;
    }
    La.elem[0] = 1; La.elem[1] = 3; La.elem[2] = 5; La.length = 3;
    Lb.elem[0] = 2; Lb.elem[1] = 4; Lb.elem[2] = 6; Lb.length = 3;
    printf("Test Case 1:\nInput La: ");
    TraverseList(La);
    printf("Input Lb: ");
    TraverseList(Lb);
    if (MergeList(La, Lb, &Lc) != 1) {
        printf("Merge failed.\n");
        return -1;
    }
    printf("Output Lc: ");
    TraverseList(Lc);

    // 测试用例2：其中一个顺序表为空
    Lb.length = 0; // Lb为空
    printf("\nTest Case 2:\nInput La: ");
    TraverseList(La);
    printf("Input Lb: ");
    TraverseList(Lb);
    if (MergeList(La, Lb, &Lc) != 1) {
        printf("Merge failed.\n");
        return -1;
    }
    printf("Output Lc: ");
    TraverseList(Lc);

    // 测试用例3：其中一个顺序表仅包含一个元素
    Lb.length = 1; // Lb仅包含一个元素
    printf("\nTest Case 3:\nInput La: ");
    TraverseList(La);
    printf("Input Lb: ");
    TraverseList(Lb);
    if (MergeList(La, Lb, &Lc) != 1) {
        printf("Merge failed.\n");
        return -1;
    }
    printf("Output Lc: ");
    TraverseList(Lc);

    // 测试用例4：两个顺序表中有重复的元素
    Lb.elem[0] = 2; Lb.elem[1] = 3; Lb.elem[2] = 4; Lb.length = 3;
    printf("\nTest Case 4:\nInput La: ");
    TraverseList(La);
    printf("Input Lb: ");
    TraverseList(Lb);
    if (MergeList(La, Lb, &Lc) != 1) {
        printf("Merge failed.\n");
        return -1;
    }
    printf("Output Lc: ");
    TraverseList(Lc);

    // 清理内存
    free(La.elem);
    free(Lb.elem);
    free(Lc.elem);

    return 0;
}

测试用例

为了验证合并算法的正确性，我们设计了四个测试用例：

1. 两个顺序表都包含基本的递增序列。
2. 其中一个顺序表为空。
3. 其中一个或两个顺序表仅包含一个元素。
4. 两个顺序表中有重复的元素。

具体测试用例如下：

实际测试结果如下：