用C++,设有两条有序链表(即 data 域元素的关键字由前往后不断增大),试设计算法,将这两 条链表合并为一条新的有序链表,原链表不变。两条链表中 data 域关键字相同的元素只选 取一个存储到新的有序链表中,不同的元素都存储到新的有序链表中。 要求: ➢ 直接编写链表的友元函数完成该功能。 ➢ 链表的 data 域可存储用户自定义类对象。 ➢ 编写测试 main()函数测试线性表的正确性
时间: 2023-05-30 18:03:26 浏览: 28
以下是用C++实现的代码:
#include <iostream>
using namespace std;
template <typename T>
class Node {
public:
T data;
Node<T>* next;
Node(T d = 0, Node<T>* n = nullptr) : data(d), next(n) {}
};
template <typename T>
class List {
public:
List() : head(nullptr) {}
void push_back(T d);
void merge(List<T>& l1, List<T>& l2);
void display();
private:
Node<T>* head;
};
template <typename T>
void List<T>::push_back(T d) {
if (head == nullptr) {
head = new Node<T>(d);
} else {
Node<T>* p = head;
while (p->next != nullptr) {
p = p->next;
}
p->next = new Node<T>(d);
}
}
template <typename T>
void List<T>::merge(List<T>& l1, List<T>& l2) {
if (l1.head == nullptr) {
head = l2.head;
return;
}
if (l2.head == nullptr) {
head = l1.head;
return;
}
Node<T>* p1 = l1.head;
Node<T>* p2 = l2.head;
Node<T>* p = nullptr;
if (p1->data < p2->data) {
head = new Node<T>(p1->data);
p = head;
p1 = p1->next;
} else {
head = new Node<T>(p2->data);
p = head;
p2 = p2->next;
}
while (p1 != nullptr && p2 != nullptr) {
if (p1->data < p2->data) {
if (p1->data != p->data) {
p->next = new Node<T>(p1->data);
p = p->next;
}
p1 = p1->next;
} else if (p1->data > p2->data) {
if (p2->data != p->data) {
p->next = new Node<T>(p2->data);
p = p->next;
}
p2 = p2->next;
} else {
if (p1->data != p->data) {
p->next = new Node<T>(p1->data);
p = p->next;
}
p1 = p1->next;
p2 = p2->next;
}
}
while (p1 != nullptr) {
if (p1->data != p->data) {
p->next = new Node<T>(p1->data);
p = p->next;
}
p1 = p1->next;
}
while (p2 != nullptr) {
if (p2->data != p->data) {
p->next = new Node<T>(p2->data);
p = p->next;
}
p2 = p2->next;
}
}
template <typename T>
void List<T>::display() {
Node<T>* p = head;
while (p != nullptr) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int main() {
List<int> l1, l2, l3;
l1.push_back(1);
l1.push_back(3);
l1.push_back(4);
l2.push_back(2);
l2.push_back(3);
l2.push_back(5);
l3.merge(l1, l2);
l1.display();
l2.display();
l3.display();
return 0;
}