首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为请设计一个时间上尽可能高效的算法,找出
admin
2014-01-14
99
问题
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享卡H同的后缀存储空间。例如,“loading”和“being”的存储映像如下图所示。
设str1和m2分别指向两个单词所在单链表的头结点,链表结点结构为
请设计一个时间上尽可能高效的算法,找出由str1和str2所指的两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。要求:
根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
选项
答案
算法实脱: IvedefstructNodde{ chardata; structNode*next; }SNODE; SNODE*Eindlist(SNODE*str1,SNODE*str2){ intm,n; SNODE*P,*q; m=listlen(str1);/*求str0的长度。0(m)*/ n=listlen(str2);/*求str2的长度。O(n)*/ /*以下3个循环的时间复杂度为:O(max(m,n))*/ for(P=strl;m>n;mm-)/术使P指向的链表与q指向的链表等长*/ P=P一>next: for(q=str2;m
next: while(p->next!=NULL&&p->next!=q->next){ /*查找共同后缀起始点*/ P=p->next;/*两个指针同步向后移动*/ q=q一>next: } 一>next;/*返回共同后缀的起始点*/returnP>next// } intlistlen(SNODE*head){/*求链表长度*/ intlen=0; while(head->next!=NULL){ len++: head=head->next; } returnlen; }
解析
转载请注明原文地址:https://www.kaotiyun.com/show/Bqxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
略论中国近现代历史上的“军阀”问题。(北京大学2003年中国通史真题)
周王室的两大官僚系统是()。
简述英法百年战争爆发的原因、过程和影响。
关于明朝“缇骑”的叙述,不正确的是()
《吕氏春秋》载:“公作则迟,有所匿其力也;分地则速,无所匿其力也。”这条材料反映的实质问题是()。
中古时代实行索贡巡行赋税征收方式的国家是()。
巴拉圭战争中的交战双方是()。
清朝在中央设置的掌管少数民族事务的机构是()。
某计算机有8个主设备需要竞争总线的使用权,其设备号为0~7。现欲设计其判优控制方法,试回答下述问题。(1)集中式总线判优控制与分布式总线判优控制的区别是什么?(2)若采用集中式判优控制,则在链式查询、计数器定时查询和独立请求三种方式下,
计算机系统中存储器为何采用分级结构?
随机试题
下列关于衰退型种群年龄结构特征的叙述,正确的是()
慢性肺源性心脏病患者,近一周来咳嗽加剧,双肺有湿啰音,双下肢水肿,血WBC及中性分类均增高。动脉血气分析:pH7.30,PaCO280mmHg,PaO230mmHg,BE+4.0mmol/L,HCO3—:34mmol/L。该患者目前不存在
腊肠犬,10岁,头颈僵直,耳竖起,鼻尖抵地,运步小心,触诊颈部敏感。该犬最可能患有()
渗透性利尿的作用机制是
正常恶露持续
奶瓶龋好发的牙面是
某企业于1998年11月以出让方式取得某一商业用地40年使用权,地价为2000元/m2。假设土地还原率为6%,在其他条件不变的情况下,则该宗地2004年11月的剩余年期地价为()元/m2。
传统工业的生产活动是以( )为特征的不可持续的发展模式。
下列关于调解建设工程纠纷时,调解人的表述中错误的说法有( )。
Acertainjarcontains100jellybeans:50white,30green,10yellow,5red,4purple,and1black.Ifajellybeanistobech
最新回复
(
0
)