将两个有序的线性表进行合并,要求同样的数据元素只出现一次c++ 源代码
时间: 2024-09-29 11:01:19 浏览: 18
在C++中,将两个有序的线性表(通常称为数组或者向量)进行合并,并保证相同的元素仅出现一次,你可以使用递归或者迭代的方式来实现。这里是一个简单的迭代方法,它创建了一个新的数组来存储结果:
```cpp
#include <vector>
std::vector<int> mergeAndRemoveDuplicates(std::vector<int>& arr1, std::vector<int>& arr2) {
int i = 0, j = 0, k = 0;
std::vector<int> merged;
// 遍历两个输入数组
while (i < arr1.size() && j < arr2.size()) {
if (arr1[i] < arr2[j]) {
merged.push_back(arr1[i++]);
} else if (arr1[i] > arr2[j]) {
merged.push_back(arr2[j++]);
} else { // 同样的元素,只添加一次
merged.push_back(arr1[i++]);
j++; // 跳过已处理的元素
}
}
// 添加剩余未遍历部分
while (i < arr1.size()) {
merged.push_back(arr1[i++]);
}
while (j < arr2.size()) {
merged.push_back(arr2[j++]);
}
return merged;
}
// 示例
int main() {
std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {4, 5, 6, 7, 8};
std::vector<int> result = mergeAndRemoveDuplicates(a, b);
for (const auto& num : result) {
std::cout << num << " ";
}
return 0;
}
```
在这个例子中,`mergeAndRemoveDuplicates`函数接收两个输入数组,然后逐个比较它们的元素,将较小的元素添加到结果数组,并跳过相等的元素。最后,如果还有未处理完的数组,则将其余元素追加到结果中。