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

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

数据结构

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

——老子

1

每日一练

1.设有一头指针为 L 的带有表头结点的非循环双向链表,其每个结点中除有 pred(前驱指针),data(数据)和 next(后继指针)域外,还有一个访问频度域 freq。在链表被起用前,其值均初始化为零。每当在链表中进行一次 Locate(L,x)运算时,令元素值为 x 的结点中 freq 域的值增 1,并使此链表中结点保持按访问频度非增(递减)的顺序排列,同时最近访问的结点排在频度相同的结点的最后,以便使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate(L,x)运算的算法,该运算为函数过程,返回找到结点的地址,类型为指针型。

正确答案

PS:||代表注释

1.[题目分析]首先在双向链表中查找数据值为x的结点,查到后,将结点从链表上摘下,然后再顺结点的前驱链查找该结点的位置。

DLinkList locate(DLinkList L,ElemType x)∥ L是带头结点的按访问频度递减的双向链表,本算法先查找数据x,查找成功时结点的访问频度域增1,最后将该结点按频度递减插入链表中适当位置。

{ DLinkList p=L->next,q; ∥p为L表的工作指针,q为p的前驱,用于查找插入位置。

while (p && p->data !=x) p=p->next; ∥ 查找值为x的结点。

if (!p) {printf(“不存在值为x的结点\n”); exit(0);}

else { p->freq++; ∥ 令元素值为x的结点的freq域加1 。

p->next->pred=p->pred; ∥ 将p结点从链表上摘下。

p->pred->next=p->next;

q=p->pred; ∥ 以下查找p结点的插入位置

while (q !=L && q->freq<p->freq) q=q->pred;

p->next=q->next; q->next->pred=p;∥ 将p结点插入

p->pred=q; q->next=p;

}

return(p); ∥返回值为x的结点的指针

} ∥ 算法结束

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

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    ——老子

    C语言入门到精通
  • 数据结构 | 每日一练(21)

    ——老子

    C语言入门到精通
  • 数据结构 | 每日一练(48)

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

    C语言入门到精通
  • 数据结构 | 每日一练(44)

    ——老子

    C语言入门到精通
  • 每天一道剑指offer-删除链表中重复的结点

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

    乔戈里
  • 「优质题解」出圈

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

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

    ——老子

    C语言入门到精通
  • 数据结构 | 每日一练(48)

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

    C语言入门到精通
  • 极客算法训练笔记(三),链表详细图解,别再逃避了朋友

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

    阿甘的码路
  • 编程小白 | 每日一练(42)

    这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从编程小白进阶到高手,需要经历的是日积月累的学习,那么如何学习呢?当然是每天都...

    C语言入门到精通

扫码关注云+社区

领取腾讯云代金券