两个有序顺序表的合并，数据结构，c++

在数据结构中，将两个有序顺序表合并成一个新的有序顺序表是一个常见的操作，通常可以通过线性时间复杂度完成。顺序表是一种线性表的存储结构，通常由一系列连续的存储单元组成，用于存储相同类型的数据元素。在C++中，顺序表可以使用数组或`std::vector`来实现。

合并两个有序顺序表的基本思想是从两个表的起始位置开始，逐个比较两个表的元素，将较小的元素放入新的顺序表中，直到所有元素都被合并。这种方法称为“归并排序”中的合并操作。

以下是使用C++实现两个有序顺序表合并的示例代码：

#include <iostream>
#include <vector>

// 合并两个有序顺序表的函数
std::vector<int> mergeSortedLists(const std::vector<int>& list1, const std::vector<int>& list2) {
    std::vector<int> mergedList;
    int i = 0, j = 0;

    // 遍历两个列表，直到任一列表到达末尾
    while (i < list1.size() && j < list2.size()) {
        if (list1[i] < list2[j]) {
            mergedList.push_back(list1[i++]);
        } else {
            mergedList.push_back(list2[j++]);
        }
    }

    // 如果第一个列表还有剩余元素，将它们添加到合并后的列表
    while (i < list1.size()) {
        mergedList.push_back(list1[i++]);
    }

    // 如果第二个列表还有剩余元素，将它们添加到合并后的列表
    while (j < list2.size()) {
        mergedList.push_back(list2[j++]);
    }

    return mergedList;
}

int main() {
    // 创建两个有序顺序表
    std::vector<int> list1 = {1, 3, 5, 7};
    std::vector<int> list2 = {2, 4, 6, 8};

    // 合并两个有序顺序表
    std::vector<int> mergedList = mergeSortedLists(list1, list2);

    // 输出合并后的结果
    for (int num : mergedList) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个示例中，我们定义了一个`mergeSortedLists`函数，它接受两个整型向量`list1`和`list2`作为输入，并返回一个新的整型向量`mergedList`作为输出，该输出向量是输入两个有序列表的合并结果。