专栏首页C语言入门到精通数据结构 | 每日一练(58)

数据结构 | 每日一练(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-

本文分享自微信公众号 - C语言入门到精通(gh_780327809188)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构 | 每日一练(44)

    ——老子

    闫小林
  • 数据结构 | 每日一练(48)

    1.设 Listhead 为一单链表的头指针,单链表的每个结点由一个整数域 DATA 和指针域 NEXT 组成,整数在单链表中是无序的。编一 PASCAL 过程...

    闫小林
  • 数据结构 | 每日一练(73)

    ——老子

    闫小林
  • 极客算法训练笔记(三),链表详细图解,别再逃避了朋友

    上一篇说的是数组,然后现在来说说链表。链表有个经典应用,就是实现LRU缓存淘汰算法,缓存的作用大家肯定都知道,常见的Redis缓存,CPU缓存,数据库缓存,浏览...

    阿甘的码路
  • 「优质题解」出圈

    https://www.dotcpp.com/oj/problem1160.html

    编程范 源代码公司
  • 数据结构 | 每日一练(48)

    1.设 Listhead 为一单链表的头指针,单链表的每个结点由一个整数域 DATA 和指针域 NEXT 组成,整数在单链表中是无序的。编一 PASCAL 过程...

    闫小林
  • 算法-O(1)时间删除链表的指定结点

    题目:给定一个链表的头指针和一个结点的指针,定义一个函数在O(1)时间删除该结点。链表结点与函数的定义如下: struct ListNode { int v...

    chaibubble
  • 每天一道剑指offer-删除链表中重复的结点

    在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1...

    乔戈里
  • 数据结构 | 每日一练(73)

    ——老子

    闫小林
  • C++链表的创建与操作

    我们知道,数组式计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元,相同数组的位置和距离都是固定的,也就是说,任何一个数组元素的地址都可一个简单的...

    w4979的博客

扫码关注云+社区

领取腾讯云代金券