顺序表的合并c语言pta

顺序表是一种线性的数据结构，它的元素按照一定的顺序存储在内存中的连续位置上。当需要合并两个已排序的顺序表时，在C语言中可以采用分治策略，通常会创建一个新的顺序表来保存合并后的结果。以下是合并操作的基本步骤：

1. 定义新的数组（如果原始表是动态分配的），用于存放合并后的顺序表。
2. 初始化两个指针，分别指向两个待合并列表的起始位置。
3. 比较当前指针所指向的元素，将较小的一个放入新数组，并将对应的指针向后移动一位。
4. 重复步骤3，直到其中一个列表遍历完。
5. 将另一个未遍历完的列表剩余部分复制到新数组中。

示例代码（假设两个顺序表已排序）:

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

// 函数声明
void merge(int arr[], int l1, int m, int r2); // 合并函数

int main() {
    int a[] = {1, 3, 5, 7}; // 第一个有序列表
    int b[] = {2, 4, 6, 8}; // 第二个有序列表
    int n1 = sizeof(a) / sizeof(a[0]);
    int n2 = sizeof(b) / sizeof(b[0]);

    // 合并两个列表
    int merged[n1 + n2]; // 新数组大小
    merge(merged, 0, 0, n1 - 1);
    merge(merged, 0, n1, n1 + n2 - 1);

    // 输出合并后的顺序表
    for (int i = 0; i < n1 + n2; ++i)
        printf("%d ", merged[i]);

    return 0;
}

// 合并函数
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    i = l;   // 列表1起始索引
    j = m + 1; // 列表2起始索引
    k = l;   // 新数组起始索引

    while (i <= m && j <= r) {
        if (arr[i] <= arr[j]) {
            arr[k++] = arr[i++];
        } else {
            arr[k++] = arr[j++];
        }
    }

    // 如果有剩余元素，将其添加至新数组
    while (i <= m)
        arr[k++] = arr[i++];

    while (j <= r)
        arr[k++] = arr[j++];
}