C++ 实现两个有序顺序表的合并

本文将介绍如何使用 C++ 代码实现两个有序顺序表的合并算法。该算法会将两个有序顺序表合并成一个新的有序顺序表，并去除重复元素。

问题描述:

创建两个有序的顺序表 Ll 和 L2，表中元素值由键盘随机输入，再将它们合并为一个新的顺序表 L3, 合并后 L3 仍然有序 (重复元素只保留一个)，最后输出顺序表中的各个元素值。

C++ 代码实现:

#include <iostream>
#include <vector>
using namespace std;

vector<int> mergeLists(vector<int>& list1, vector<int>& list2) {
    vector<int> mergedList;
    int i = 0, j = 0;
    int n1 = list1.size();
    int n2 = list2.size();
    
    while (i < n1 && j < n2) {
        if (list1[i] < list2[j]) {
            mergedList.push_back(list1[i]);
            i++;
        } else if (list1[i] > list2[j]) {
            mergedList.push_back(list2[j]);
            j++;
        } else {
            mergedList.push_back(list1[i]);
            i++;
            j++;
        }
    }
    
    while (i < n1) {
        mergedList.push_back(list1[i]);
        i++;
    }
    
    while (j < n2) {
        mergedList.push_back(list2[j]);
        j++;
    }
    
    return mergedList;
}

int main() {
    vector<int> list1, list2;
    int n1, n2;
    
    cout << "Enter the number of elements in list1: ";
    cin >> n1;
    cout << "Enter elements of list1 in ascending order: ";
    for (int i = 0; i < n1; i++) {
        int num;
        cin >> num;
        list1.push_back(num);
    }
    
    cout << "Enter the number of elements in list2: ";
    cin >> n2;
    cout << "Enter elements of list2 in ascending order: ";
    for (int i = 0; i < n2; i++) {
        int num;
        cin >> num;
        list2.push_back(num);
    }
    
    vector<int> mergedList = mergeLists(list1, list2);
    
    cout << "Merged list: ";
    for (int i = 0; i < mergedList.size(); i++) {
        cout << mergedList[i] << " ";
    }
    
    return 0;
}

示例输入:

Enter the number of elements in list1: 5
Enter elements of list1 in ascending order: 1 3 5 7 9
Enter the number of elements in list2: 4
Enter elements of list2 in ascending order: 2 4 6 8

示例输出:

Merged list: 1 2 3 4 5 6 7 8 9

代码解释:

mergeLists 函数接收两个有序的 vector 作为参数，并返回一个新的 vector 作为合并后的结果。
函数使用两个指针 i 和 j 分别指向两个输入 vector 的起始位置。
循环遍历两个 vector，比较当前指针指向的元素，将较小的元素添加到合并后的 vector 中，并移动相应的指针。
如果两个 vector 中的元素相等，只将其中一个元素添加到合并后的 vector 中，并移动两个指针。
当其中一个 vector 遍历完毕后，将另一个 vector 中剩余的元素添加到合并后的 vector 中。
main 函数读取用户输入的两个有序顺序表，调用 mergeLists 函数进行合并，并输出合并后的顺序表。

总结:

本文详细介绍了使用 C++ 代码实现两个有序顺序表的合并算法，并提供了示例代码和输入输出示例。该算法简单易懂，且效率较高，适合处理有序数据的合并操作。