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

数据结构 | 每日一练(65)

数据结构

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

——老子

1

每日一练

1.在一个递增有序的线性表中,有数值相同的元素存在。若存储方式为单链表,设计算法去掉数值相同的元素,使表中不再有重复的元素。例如:(7,10,10,21,30,42,42,42,51,70)将变作(7,10,21,30,42,51,70),分析算法的时间复杂度。

正确答案

ps:||代表注释

1.[题目分析] 在递增有序的线性表中,删除数值相同的元素,要知道被删除元素结点的前驱结点。

LinkedList DelSame(LinkedList la)∥la是递增有序的单链表,本算法去掉数值相同的元素,使表中不再有重复的元素。

{pre=la->next;∥pre是p所指向的前驱结点的指针。

p=pre->next;∥p是工作指针。设链表中至少有一个结点。

while(p!=null)

if(p->data==pre->data) ∥处理相同元素值的结点

{u=p;p=p->next;free(u);} ∥释放相同元素值的结点

else {pre->next=p;pre=p;p=p->next;} ∥处理前驱,后继元素值不同

pre->next=p;∥置链表尾。

}∥DelSame

[算法讨论] 算法中假设链表至少有一个结点,即初始时pre不为空,否则p->next无意义。算法中最后pre->next=p是必须的,因为可能链表最后有数据域值相同的结点,这些结点均被删除,指针后移使p=null而退出 while循环,所以应有pre->next=p使链表有尾。若链表尾部没数据域相同的结点,pre和p为前驱和后继,pre->next=p也是对的。顺便提及,题目应叙述为非递减有序,因为“递增”是说明各结点数据域不同,一个值比一个值大,不会存在相同值元素。

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

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

    ——老子

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

    ——老子

    闫小林
  • 《算法图解》第二章笔记与课后练习

    Zoctopus
  • 《算法图解》第二章笔记与课后练习_选择排序算法

    Zoctopus
  • BAT算法面试题(12)--环形链表(哈希表法)

    给定一个链表,判断链表中是否有环. 难度升级: 试试能否在不使用额外空间解决此问题?

    CC老师
  • Elasticsearch Mapping之字段类型(field datatypes)

    long、integer、short、byte、double、float、half_float、scaled_float。

    丁威
  • kubernetes之pod健康检查

    LivenessProbe和ReadinessProbe均可配置以下三种探针实现方式: 可参考官方文档:https://kubernetes.io/docs/...

    山山仙人
  • 《上瘾:让用户养成使用习惯的四大产品逻辑》

    《上瘾》这本书总结了产品让用户上瘾的四大逻辑:触发、行动、多变的酬赏和投入。如果你想互联网创业,或者想了解互联网爆品背后的秘密,这四大产品逻辑会给你很多启发。

    Vaccae
  • 互联网浪潮中做基础网络服务的几小招

    "鹅厂网事"由深圳市腾讯计算机系统有限公司技术工程事业群网络平台部运营,我们希望与业界各位志同道合的伙伴交流切磋最新的网络、服务器行业动态信息,同时分享腾讯在网...

    鹅厂网事

扫码关注云+社区

领取腾讯云代金券