数据结构问题求两个集合的差?
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
}Node;
Node* getNewLinklist(int val) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = val;
node->next = NULL;
return node;
}
Node* insert(Node* head,int val) {
Node* new_node = getNewLinklist(val);
if (head == NULL) {
return new_node;
}
new_node->next = head;
return new_node;
}
Node* compare(Node* A, Node* B) {
Node new_nodeb;
new_nodeb.next = B;
Node* prevb = &new_nodeb,*tempor = prevb->next;
while (tempor) {
for (Node* p = A; p; p = p->next) {
if (p->data == tempor->data) {
prevb->next = tempor->next;
}
}
prevb = tempor;
tempor = tempor->next;
}
return new_nodeb.next;
}
int main() {
Node* A = NULL,*B = NULL;
int arr1[] = { 1,2,3,4,5 };
int arr2[] = { 4,5,6,7,8 };
for (int i = 0; i < 5; i++) {
A = insert(A, arr1[i]);
B = insert(B, arr2[i]);
}
Node* C = compare(A, B);
for (Node* p = C; p; p = p->next) {
printf("%d ",p->data);
}
}
1.问题描述以单链表表示集合,求先后输入的两个集合的差。2.基本要求
输入集合A和集合B,计算集合A、B的差C并输出。
3.算法提示
假设两个已知集合A和B。根据集合运算的规则可知,集合A-B中包含所有属于集合A而不属于集合B的元素。因此,为了求A-B,需建立表示集合A 的单链表,然后对B中的每个元素X,在集合A的链表中进行查找,若存在和X相同的元素,则从该链表中删除。
运行结果的话只有5被删除了,而4并没有删除是什么原因对代码进行下面的修改后,代码运行反而不会出现结果了
while (tempor) {
int k = 0;
for (Node* p = A; p; p = p->next) {
if (p->data == tempor->data) {
prevb->next = tempor->next;
k = 1;
}
}
if (k == 0) {
prevb = prevb->next;
tempor = tempor->next;
}
}
回复
1个回答
test
2024-06-25
while (tempor) {
for (Node* p = A; p; p = p->next) {
if (p->data == tempor->data) {
prevb->next = tempor->next;
}
}
/*
prevb 应该为链表中 tempor 的前一个节点。
但是如果 tempor 被删除了,tempor->next 还在链表中,tempor 本身已经不在链表中了。
这时令 prevb = tempor ,那么 prevb 这个节点就已经不链表中了。所以通过
prev->next = tempor->next 不能从链表中删除 tempor 。
所以 5, 4 连续两个删除只有第一个成功了。
*/
prevb = tempor;
tempor = tempor->next;
}
回复
适合作为回答的
- 经过验证的有效解决办法
- 自己的经验指引,对解决问题有帮助
- 遵循 Markdown 语法排版,代码语义正确
不该作为回答的
- 询问内容细节或回复楼层
- 与题目无关的内容
- “赞”“顶”“同问”“看手册”“解决了没”等毫无意义的内容