已知一个带头结点单链表的结点类型nextNode定义为 struct nextNode{int data;int freq;struct nextNode*next;}; 其中,data为结点值域,freq为该结点元素的访问计数,初始为0;next

admin2017-11-20  33

问题 已知一个带头结点单链表的结点类型nextNode定义为
    struct nextNode{int data;int freq;struct nextNode*next;};
其中,data为结点值域,freq为该结点元素的访问计数,初始为0;next为指向链表中该结点后继结点的指针域,设该链表所有结点按照freq值从大到小链接。请实现一个时间和空间上尽可能高效率的算法,编写一个查找函数Search,从链表首结点开始查找结点data值与给定值相等的结点。如果找到,则将该结点的freq值加1,然后把它前移到与结点freq值相等的结点的后面,使得所有结点仍然都保持按照freq值从大到小链接。
给出算法的基本设计思想。

选项

答案基本设计思想:设置3个指针p、pre和q,从链表的首元结点开始,用p作为检测指针顺序检测,比较给定值value与p->data,指针pre是亦步亦趋跟在*p后面的前驱指针,为从链中摘下*p而用。另外指针q用于记忆freq下降的结点,为插入结点*p而用。若设链表有n个结点,查找成功时指针*cp停留在第i(1≤i≤n)个结点,则算法的平均查找长度为n(n-1)/2。删除和插入结点*p时仅修改指针。 [*]

解析
转载请注明原文地址:https://kaotiyun.com/show/DNRi777K
0

相关试题推荐
随机试题
最新回复(0)