首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。 设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。 设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算
admin
2015-12-30
33
问题
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为
,请设计一个时间上尽可能高效的算法,找出由str1和str2所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。
要求:
给出算法的基本设计思想。
选项
答案
顺序遍历两个链表到尾结点时,并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另一个链表长k个结点,我们先在长链表上遍历k个结点,之后同步遍历两个链表,这样就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的,所以它们肯定同时到达第一个公共结点。 [*] 算法的基本设计思想: ①分别求出str1和str2所指的两个链表的长度m和n; ②将两个链表以表尾对齐(如上图所示):令指针p、q分别指向str1和str2的头结点,若m>=n,则使p指向链表中的第m-n+1个结点;若m<n,则使q指向链表中的第n-m+1个结点,即使指针p和q所指的结点到表尾的长度相等。 ③反复将指针p和q同步向后移动,并判断它们是否指向同一结点。若p和q指向同一结点,则该点即为所求的共同后缀的起始位置。
解析
转载请注明原文地址:https://kaotiyun.com/show/4Kxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列不属于凯末尔主义内容的是()。
中国历史上第一部资产阶级革命法典《临时约法》公布的时间是()。
重庆谈判的焦点问题是()
简述罗马共和国早期平民反贵族斗争的原因、过程和意义。
简述第二国际建立的社会历史条件。
三大战役的先后顺序是()
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
德里苏丹国前三位苏丹均为奴隶,同时皆属于()。
阅读下列材料,并结合所学知识回答问题:材料一重申粮食垄断和价格都是不可更改的,重申必须同粮食投机商进行无情斗争,同时责成每一者,必须在本法令公布后一周内,把超过播种田地和自己到下次收获前的定额消费量的全部余粮呈报交售,呈报的办法由粮
随机试题
分析仪器的分光能力越强,得到的单色光就越纯,分析的灵敏度就越高。
下列关于Web2.0时代的描述不正确的是
请你说明国际贸易术语的效力有哪些?
初产妇,入院分娩待产。检查:先露头已入盆,胎心正常,胎膜未破,宫颈口开1cm。护士为其采取的护理措施应不包括
连续式平整度仪的标准长度为5m。()
某企业自筹资金新建的工业厂房项目,建设单位采用工程量清单方式招标,并与施工单位按《建设工程施工合同(示范文本)》签订了工程施工承包合同。合同工期270天,施工承包合同约定:管理费和利润按人工费和施工机具使用费之和的40%计取,规费和税金按人材机费、管理费和
甲公司的盈亏临界点销售量为( )万元。2009年甲公司预计净利润为( )万元。
在设计调查问卷时,调查者设定问题,由被调查者用自己的语言自由地表达自己的意愿和想法,准确地表明自己的感觉的调查方法称为()。
ThecurrentFrenchbestsellerlistsarewonderfullyeclectic.In(1)_____,thereiseverything(2)_____blockbusterthrillersto
他一向嘴硬,从不认错。
最新回复
(
0
)