求解集合A和集合B的差集
求解集合A和集合B的差集 题目:已知集合A和B的元素分别用不含头结点的单链表存储,函数difference()用于求解集合A与B的差集,并将结果保存在集合A的单链表中。例如,若集合A={5,10,20,15,25,30},集合B={5,15,35,25},完成计算后A={10,20,30}。
算法思想:取出集合A中每一个元素,与集合B中对比,找到即可删除此节点,否则保留。 prev实现删除节点后的连接 当prev=NULL时,说明是首次找到A和B的公有元素,此时*LA指向pa->next,*LA仍然是头结点; 当prev!=NULL时,prev指向pa->next,实现删除结点的链接。 代码实现:
#include
#include
#include
typedef struct ListNode
{
int elem;
struct ListNode* next;
}Node,*pNode,*pList;
void Init(pList* pplist)
{
assert(pplist);
*pplist = NULL;
}
pNode BuyNode(int x)
{
pNode cur = (pNode)malloc(sizeof(Node));
if (cur == NULL)
{
perror("malloc");
return NULL;
}
cur->elem = x;
cur->next = NULL;
return cur;
}
void Push(pList* pplist, int x)
{
pNode NewNode = BuyNode(x);
if (*pplist == NULL)
{
*pplist = NewNode;
}
else
{
pNode cur = *pplist;
while (cur->next)
{
cur = cur->next;
}
cur->next = NewNode;
}
}void Print(pList plist)
{
pNode cur = plist;
while (cur)
{
printf("%d ", cur->elem);
cur = cur->next;
}
printf("NULL\n");
}void difference(pNode* LA, pNode LB)
{
pNode pa, pb, q;
pNode prev = NULL;
pa = *LA;
//*LA是指向指针的指针,pa指向集合的元素
while (pa)
{
pb = LB;
//pb指向集合的元素
while (pb && pa->elem != pb->elem)
pb = pb->next;
if (pb)//pa所指向元素与pb所指的元素相等
{
if (!prev)
{
*LA = pa->next;
}
else
{
prev->next = pa->next;
}
q = pa;
//求差集,即删除pa结点
pa = pa->next;
free(q);
}
else
{
prev = pa;
pa = pa->next;
}
}
}void Test()
{
pList plist1;
Init(&plist1);
Push(&plist1, 12);
Push(&plist1, 2);
Push(&plist1, 92);
Push(&plist1, 1);
Push(&plist1, 11);
Print(plist1);
pList plist2;
Init(&plist2);
Push(&plist2, 12);
Push(&plist2, 21);
Push(&plist2, 92);
Push(&plist2, 1);
Print(plist2);
difference(&plist1, plist2);
Print(plist1);
}
测试结果:
文章图片
推荐阅读
- 急于表达——往往欲速则不达
- 第三节|第三节 快乐和幸福(12)
- 20170612时间和注意力开销记录
- 2.6|2.6 Photoshop操作步骤的撤消和重做 [Ps教程]
- 对称加密和非对称加密的区别
- 眼光要放高远
- 樱花雨
- 图书集合完毕
- 前任
- 2020-04-07vue中Axios的封装和API接口的管理