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

admin2017-11-20 79

问题已知一个带头结点单链表的结点类型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://www.kaotiyun.com/show/DNRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

苏台德问题

永嘉之乱后，北方的政局是()。①西晋短暂统一的终结②北方长期处于多个政权分立的战乱状态③氐族人建立的前秦和鲜卑人建立的北魏曾统一过北方④民族交往和民族斗争交织在一起⑤民族大融合是历史发展的主流⑥民族大

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。

南洋兄弟烟草公司的创办者之一是()。

近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

隋朝建立了三省六部制，其中负责审议的部门是()。

试析第三次科学技术革命对人类社会和历史进程的影响。

美国沃尔玛公司的零售业务已开展到墨西哥、中国等国家，成为世界上最大的零售企业。这一现象体现了下列哪种国外分销渠道发展趋势()

外科病人最易发生的缺水是

监事会足我国特有的机构，负责内部监督，对股东大会负责，有权对商业银行业务中涉及的危硷和其他内部控制进行监督，但不得干预H常的经营管理活动。我国应建立健全以监事会为核心的监督机制。()

企业集团多元化经营的优点有()。

下列各项，应确认为企业资产的有()。

A:I’vejustheardthattheticketsforSwanLakehavebeensoldout!B:Oh,no!______

在某一种溶液中，牛奶、酒精、水的比例是4：100：200；现在溶液发生了改变，牛奶、酒精的比例增倍，而牛奶、水的比例减半，如果改变后的溶液一共含有1000立方厘米的酒精，那么溶液中含有多少立方厘米的水?

Theycallthemthenewbreadearners.Theyarewomen,andtheyaresettotakeover.Womenarebeginningtorise【S1】______to

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

计算机408

学硕统考专业

苏台德问题

永嘉之乱后，北方的政局是()。①西晋短暂统一的终结②北方长期处于多个政权分立的战乱状态③氐族人建立的前秦和鲜卑人建立的北魏曾统一过北方④民族交往和民族斗争交织在一起⑤民族大融合是历史发展的主流⑥民族大

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

1923年纳粹党魁希特勒发动了“啤酒馆暴动”，对此叙述不正确的一项是()。

南洋兄弟烟草公司的创办者之一是()。

近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

隋朝建立了三省六部制，其中负责审议的部门是()。

试析第三次科学技术革命对人类社会和历史进程的影响。

美国沃尔玛公司的零售业务已开展到墨西哥、中国等国家，成为世界上最大的零售企业。这一现象体现了下列哪种国外分销渠道发展趋势()

外科病人最易发生的缺水是

监事会足我国特有的机构，负责内部监督，对股东大会负责，有权对商业银行业务中涉及的危硷和其他内部控制进行监督，但不得干预H常的经营管理活动。我国应建立健全以监事会为核心的监督机制。()

企业集团多元化经营的优点有()。

下列各项，应确认为企业资产的有()。

A:I’vejustheardthattheticketsforSwanLakehavebeensoldout!B:Oh,no!______

在某一种溶液中，牛奶、酒精、水的比例是4：100：200；现在溶液发生了改变，牛奶、酒精的比例增倍，而牛奶、水的比例减半，如果改变后的溶液一共含有1000立方厘米的酒精，那么溶液中含有多少立方厘米的水?

Theycallthemthenewbreadearners.Theyarewomen,andtheyaresettotakeover.Womenarebeginningtorise【S1】______to

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