用C语言写一个算法,已知两个链表A和B分别表示两个集合,其元素递增排列。请设计一个算法,用户求出A和B的差集(即仅由在A中出现而在B中不出现的元素构成的集合),并用递增的方式保存在表A中,同时返回该集合的元素数目
时间: 2023-05-14 10:05:01 浏览: 86
以下是算法的C语言实现:
```
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* createList(int* nums, int size) {
struct ListNode* head = NULL;
struct ListNode* tail = NULL;
for (int i = 0; i < size; i++) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = nums[i];
node->next = NULL;
if (head == NULL) {
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
}
return head;
}
void printList(struct ListNode* head) {
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
struct ListNode* subtractLists(struct ListNode* A, struct ListNode* B, int* size) {
struct ListNode* head = NULL;
struct ListNode* tail = NULL;
int count = 0;
while (A != NULL && B != NULL) {
if (A->val < B->val) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = A->val;
node->next = NULL;
if (head == NULL) {
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
A = A->next;
count++;
} else if (A->val == B->val) {
A = A->next;
B = B->next;
} else {
B = B->next;
}
}
while (A != NULL) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = A->val;
node->next = NULL;
if (head == NULL) {
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
A = A->next;
count++;
}
*size = count;
return head;
}
int main() {
int nums1[] = {1, 2, 3, 4, 5};
int nums2[] = {3, 4, 5, 6, 7};
struct ListNode* A = createList(nums1, 5);
struct ListNode* B = createList(nums2, 5);
int size;
struct ListNode* C = subtractLists(A, B, &size);
printf("A - B = ");
printList(C);
printf("size = %d\n", size);
return 0;
}
```
输出结果为:
```
A - B = 1 2
size = 2
```
其中,函数`createList`用于创建链表,函数`printList`用于打印链表,函数`subtractLists`用于求两个链表的差集,函数`main`用于测试。
阅读全文