2. 考研
  3. 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享卡H同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点，链表结点结构为请设计一个时间上尽可能高效的算法，找出

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享卡H同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。设str1和m2分别指向两个单词所在单链表的头结点，链表结点结构为请设计一个时间上尽可能高效的算法，找出

admin2014-01-14  62
问题 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享卡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；mnext： 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://kaotiyun.com/show/Bqxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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