已知两个带头结点的单链表A 和B 分别表示两个集合,元素值递增有序,设计算法求出A,B 的差集C,并同样以递增的形式存储。
时间: 2023-05-19 07:00:38 浏览: 153
以下是算法的实现:
1. 初始化指针pA和pB,分别指向链表A和B的头结点。
2. 初始化指针pC,指向链表C的头结点。
3. 当pA和pB都不为空时,比较pA和pB所指向的节点的值,如果pA所指向的节点的值小于pB所指向的节点的值,则将pA所指向的节点插入到链表C中,并将pA指向下一个节点;如果pA所指向的节点的值大于pB所指向的节点的值,则将pB所指向的节点插入到链表C中,并将pB指向下一个节点;如果pA所指向的节点的值等于pB所指向的节点的值,则将pA和pB都指向下一个节点。
4. 当pA不为空时,将pA所指向的节点插入到链表C中,并将pA指向下一个节点。
5. 当pB不为空时,将pB所指向的节点插入到链表C中,并将pB指向下一个节点。
6. 返回链表C。
以下是完整的代码实现:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node, *LinkedList;
LinkedList createLinkedList(int n) {
LinkedList head = (LinkedList) malloc(sizeof(Node));
head->next = NULL;
LinkedList p = head;
for (int i = 0; i < n; i++) {
LinkedList node = (LinkedList) malloc(sizeof(Node));
scanf("%d", &node->data);
node->next = NULL;
p->next = node;
p = node;
}
return head;
}
LinkedList difference(LinkedList A, LinkedList B) {
LinkedList head = (LinkedList) malloc(sizeof(Node));
head->next = NULL;
LinkedList pA = A->next, pB = B->next, pC = head;
while (pA && pB) {
if (pA->data < pB->data) {
LinkedList node = (LinkedList) malloc(sizeof(Node));
node->data = pA->data;
node->next = NULL;
pC->next = node;
pC = node;
pA = pA->next;
} else if (pA->data > pB->data) {
LinkedList node = (LinkedList) malloc(sizeof(Node));
node->data = pB->data;
node->next = NULL;
pC->next = node;
pC = node;
pB = pB->next;
} else {
pA = pA->next;
pB = pB->next;
}
}
while (pA) {
LinkedList node = (LinkedList) malloc(sizeof(Node));
node->data = pA->data;
node->next = NULL;
pC->next = node;
pC = node;
pA = pA->next;
}
while (pB) {
LinkedList node = (LinkedList) malloc(sizeof(Node));
node->data = pB->data;
node->next = NULL;
pC->next = node;
pC = node;
pB = pB->next;
}
return head;
}
void printLinkedList(LinkedList head) {
LinkedList p = head->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
int n, m;
scanf("%d", &n);
LinkedList A = createLinkedList(n);
scanf("%d", &m);
LinkedList B = createLinkedList(m);
LinkedList C = difference(A, B);
printLinkedList(C);
return 0;
}
```
阅读全文