用c语言写程序,创建A和B两个链表分别表示两个集合,其元素递增,求出A和B的交集,并将结果存放在A链表中
时间: 2024-09-28 10:13:05 浏览: 35
在C语言中,你可以通过遍历两个链表并检查每个节点是否同时存在于A和B链表中来找到它们的交集。这里是一个基本的示例,假设我们已经有了`Node`结构体代表链表节点,其中包含一个整数数据和指向下一个节点的指针:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建链表函数
Node* createList(int start, int end) {
Node* head = (Node*)malloc(sizeof(Node));
if (!head) {
printf("Memory allocation failed.\n");
return NULL;
}
head->data = start;
head->next = NULL;
Node* current = head;
for (int i = start + 1; i <= end; ++i) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
free(head);
return NULL;
}
newNode->data = i;
newNode->next = current->next;
current->next = newNode;
current = newNode;
}
return head;
}
// 查找交集并更新A链表
void findIntersection(Node** aHeadRef, Node** bHeadRef) {
Node* aCurrent = *aHeadRef;
Node* bCurrent = *bHeadRef;
// 如果A比B大,则交换当前指针
if (aCurrent->data > bCurrent->data) {
Node* temp = aCurrent;
aCurrent = bCurrent;
bCurrent = temp;
}
while (aCurrent && bCurrent) {
if (aCurrent->data == bCurrent->data) {
// 添加到A链表
aCurrent->next = (*aHeadRef)->next;
(*aHeadRef)->next = aCurrent;
// 移动bCurrent指针继续查找
bCurrent = bCurrent->next;
} else if (aCurrent->data < bCurrent->data) {
aCurrent = aCurrent->next;
} else {
bCurrent = bCurrent->next;
}
}
}
// 打印链表
void printList(Node* head) {
Node* currentNode = head;
while (currentNode != NULL) {
printf("%d -> ", currentNode->data);
currentNode = currentNode->next;
}
printf("NULL\n");
}
int main() {
int A[] = {1, 2, 3, 4, 5};
int B[] = {3, 4, 5, 6, 7};
Node* aList = createList(A[0], A[4]);
Node* bList = createList(B[0], B[4]);
if (aList && bList) {
Node** aHeadRef = &aList;
Node** bHeadRef = &bList;
findIntersection(aHeadRef, bHeadRef);
printList(aList);
} else {
printf("Failed to create lists.\n");
}
return 0;
}
```
这个程序首先创建了A和B两个递增链表,然后通过`findIntersection`函数找出并合并A链表中的交集部分。注意,实际应用中需要处理内存分配失败的情况。
阅读全文