2. 考研
  3. 已知一个带头结点单链表的结点类型nextNode定义为struct nextNode{int data；int freq；struct nextNode *next； }；其中，data为结点值域，freq为该结点元素的访问计数，初始为O；next为指向链

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

admin2017-04-28  107
问题 已知一个带头结点单链表的结点类型nextNode定义为struct nextNode{int data；int freq；struct nextNode *next； }；其中，data为结点值域，freq为该结点元素的访问计数，初始为O；next为指向链表中该结点后继结点的指针域，设该链表所有结点按照freq值从大到小链接。请设计一个时间和空间上尽可能高效的算法，编写一个查找函数Search，从链表首结点开始查找结点data值与给定值相等的结点。如果找到，则将该结点的freq值加1，然后把它前移到与结点freq值相等的结点的后面，使得所有结点仍然都保持按照freq值从大到小链接。
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案空间复杂度分析：除去链表本身的空间外，额外的空间消耗为O(1)。 时间复杂度分析：整个算法只会对链表进行一次扫描，扫描的时候把需要的信息都记录下来，然后用O(1)的时间完成链表的修改。因此，整个算法的时间复杂度为O(n)。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/RWRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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