用C++,设有两条有序链表(即 data 域元素的关键字由前往后不断增大),试设计算法,将这两 条链表合并为一条新的有序链表,原链表不变。两条链表中 data 域关键字相同的元素只选 取一个存储到新的有序链表中,不同的元素都存储到新的有序链表中。 要求: ➢ 直接编写链表的友元函数完成该功能。 ➢ 链表的 data 域可存储用户自定义类对象。 ➢ 编写测试 main()函数测试线性表的正确性
时间: 2023-05-30 13:03:15 浏览: 22
#include <iostream>
using namespace std;
template <class T>
class Node {
public:
T data;
Node<T>* next;
Node() {
next = NULL;
}
};
template <class T>
class LinkedList {
private:
Node<T>* head;
public:
LinkedList() {
head = new Node<T>();
}
void insert(T x) {
Node<T>* p = head;
while (p->next != NULL && p->next->data < x) {
p = p->next;
}
if (p->next == NULL || p->next->data != x) {
Node<T>* q = new Node<T>();
q->data = x;
q->next = p->next;
p->next = q;
}
}
friend LinkedList<T> MergeList(LinkedList<T>& list1, LinkedList<T>& list2) {
LinkedList<T> newList;
Node<T>* p = list1.head->next;
Node<T>* q = list2.head->next;
while (p != NULL && q != NULL) {
if (p->data < q->data) {
newList.insert(p->data);
p = p->next;
} else if (p->data > q->data) {
newList.insert(q->data);
q = q->next;
} else {
newList.insert(p->data);
p = p->next;
q = q->next;
}
}
while (p != NULL) {
newList.insert(p->data);
p = p->next;
}
while (q != NULL) {
newList.insert(q->data);
q = q->next;
}
return newList;
}
void print() {
Node<T>* p = head->next;
while (p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
};
int main() {
LinkedList<int> list1;
LinkedList<int> list2;
list1.insert(1);
list1.insert(3);
list1.insert(5);
list1.insert(7);
list1.insert(9);
list2.insert(2);
list2.insert(4);
list2.insert(6);
list2.insert(8);
LinkedList<int> newList = MergeList(list1, list2);
newList.print();
return 0;
}