首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。 设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。 设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算
admin
2015-12-30
67
问题
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“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
学硕统考专业
相关试题推荐
北魏建立和统一的时间分别是()。
洋务运动时期,首批赴欧海军留学生派出的时间是()。
蒙古军第一次大规模进攻南宋是在()时期
第一次鸦片战争过程中,清政府在()时对英国侵略者的态度发生了转变。
论述近代法国专制制度形成的过程及其影响
如何全面分析十月革命的历史条件及特点?
()是一部上起传说中的黄帝,下迄汉武帝时期的中国通史,是中国历史上第一部内容完整、结构周密的历史著作。
阅读材料,回答以下问题:材料一:甘地认为,非暴力抵抗是印度争取摆脱殖民桎梏的唯一正确办法;同时,他认为非暴力抵抗并不意味着对外国统治和其他罪恶的屈服。他写道:“我深信假如只有在怯懦和暴力两者之间加以选择时,我将劝人选择暴力……我宁愿要印度用暴力来保护自己
阅读下列材料,结合所学知识回答问题:材料一16—17世纪西欧医生的地位还很低,尽管主要的宫廷医生有很高的经济收入,但医生并不被认为是一个很光荣的职业,直到17世纪中叶,一位绅士还拒绝同一位有钱的医生的女儿结婚。律师职业虽然不被视为低等,
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
随机试题
互惠式谈判
对待中华民族道德传统,正确的做法是()
甲在建筑工地开翻斗车。某夜,甲开车时未注意路况,当场将工友乙撞死、丙撞伤。甲背丙去医院,想到会坐牢,遂将丙弃至路沟后逃跑。丙不得救治而亡。关于本案,下列哪一选项是错误的?(2013年卷二12题)
机车车辆脱轨事故是铁路运输生产中的典型事故,防止机车车辆脱轨事故的安全措施主要有()。
生产经营单位新建、改建、扩建工程项目的( ),必须与主体工程同时设计、同时施工、同时投入生产和使用。
由影响所有公司的因素引起的风险,可以称为()。
社会保险是国家通过立法,采取强制手段对国民收入进行分配与再分配,形成专门消费基金,对劳动者在丧失劳动力或失去工作机会时进行社会帮助以保障其基本生活的一种制度。下列属于社会保险的是()。
劳动纠纷是指劳动者与用人单位之间因执行劳动法律、法规或履行劳动合同、集体合同而发生的争执。根据上述定义,下列行为属于劳动纠纷的是:
抗战时期,美国陆军部长史汀生称:“中国人已经做的和正在做的对侵略之卓越抵抗,以及他们对共同事业的贡献,值得我们给予最充分的支援。”他所说的“贡献”指的是:
Thesetechnicalachievementsshouldbe______byacommitteeofexpertsbeforetheyareputintouse.
最新回复
(
0
)