要求: (1)已知两个带头结点的单链表 A 和 B 分别表示两个集合,元素值递增有序,设计算法求出 A,B 的差集 C,并同样以递增的形式存储。 (2)利用编程模板中提供的主函数,测试算法正确性。
时间: 2024-05-13 18:20:13 浏览: 57
已知有两个按元素值递增有序的顺序表A和B,设计一个算法将表A和表B的全部元素归并为一个按元素值递增有序的顺序表C。
5星 · 资源好评率100%
对于您的问题,我可以回答。
以下是算法实现:
```
struct Node {
int val;
Node* next;
Node(int x=0, Node* ptr=nullptr): val(x), next(ptr) {}
};
Node* difference(Node* A, Node* B) {
Node *p = A->next, *q = B->next;
Node* C = new Node();
Node* rear = C;
while (p!=nullptr && q!=nullptr) {
if (p->val < q->val) {
rear->next = p;
rear = p;
p = p->next;
} else if (p->val > q->val) {
q = q->next;
} else {
p = p->next;
q = q->next;
}
}
while (p!=nullptr) {
rear->next = p;
rear = p;
p = p->next;
}
rear->next = nullptr;
return C;
}
```
对于测试代码,请使用以下主函数:
```
int main() {
/*
* 集合A:1 2 3 5 7
* 集合B:2 4 5 6 8 9
* 结果集合C:1 3 7
*/
Node* A = new Node(-1, new Node(1, new Node(2, new Node(3, new Node(5, new Node(7))))));
Node* B = new Node(-1, new Node(2, new Node(4, new Node(5, new Node(6, new Node(8, new Node(9)))))));
Node* C = difference(A, B);
Node* p = C->next;
while (p!=nullptr) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
return 0;
}
```
输出应该是 `1 3 7`。
希望这个回答对您有帮助。
阅读全文