数据结构 | 每日一练（58）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．已知递增有序的单链表 A,B 分别存储了一个集合，请设计算法以求出两个集合 A 和 B 的差集 A-B（即仅由在 A 中出现而不在 B 中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。

正确答案

ps：||代表注释

1．[题目分析] 求两个集合A和B的差集A-B，即在A中删除A和B中共有的元素。由于集合用单链表存储，问题变成删除链表中的结点问题。因此，要记住被删除结点的前驱，以便顺利删除被删结点。两链表均从第一元素结点开始，直到其中一个链表到尾为止。

void Difference（LinkedList A，B，*n）∥A和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中，*n是结果集合中元素个数，调用时为0

{p=A->next； ∥p和q分别是链表A和B的工作指针。

q=B->next； pre=A； ∥pre为A中p所指结点的前驱结点的指针。

while（p!=null && q!=null）

if（p->data<q->data）{pre=p；p=p->next；*n++；} ∥ A链表中当前结点指针后移。

else if（p->data>q->data）q=q->next； ∥B链表中当前结点指针后移。

else {pre->next=p->next； ∥处理A，B中元素值相同的结点，应删除。

u=p； p=p->next； free（u）；} ∥删除结点

转发朋友圈，点下“在看”就是对小编的最大帮助！

-end-