用单链表保存单词,两个单词的相同后缀共享存储空间,找出后缀起始位置
问题描述:
假定釆用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀存储空间,例如,“loading”和“being”的存储映像如下图所示。设str1和str2分别指向两个单词所在单链表的头结点,链表结点结构为,请设计一个时间上尽可能高效的算法,找出由str1和str2所指向两个链表共同后缀的起始位置 (如图中字符i所在结点的位置p)。要求:
1)给出算法的基本设计思想。
2)根据设计思想,釆用C或C++或Java语言描述算法,关键之处给出注释。
3)说明你所设计算法的时间复杂度。
问题解答:
本题的结构体是单链表,釆用双指针法。用指针p、q分别扫描strl和str2,当p、q指向同一个地址时,即找到共同后缀的起始位置。1)算法的基本设计思想如下:
①分别求出strl和str2所指的两个链表的长度m和n。
②将两个链表以表尾对齐:令指针p、q分别指向strl和str2的头结点,若m>=n,则指针P先走,使p指向链表中的第m-n+1个结点;若m<n,则使q指向链表中的第n-m+1 个结点,即使指针p和q所指的结点到表尾的长度相等。
③反复将指针p和q同步向后移动,当p、q指向同一位置时停止,即为共同后缀的其实位置,算法结束。
2)本题代码如下:
typedef struct Node{ char data; struct Node *next; }SNode; /*求链表长度的函数*/ int listlen(SNode *head){ int len=0; while(head->next!=NULL){ len++; head=head->next; } return len; } /*找出共同后缀的起始地址*/ SNode* find_addr(SNode *strl,SNode *str2){ int m,n; SNode *p, *q; m=listlen (strl) ; //求 strl 的长度 n=listlen (str2) ; //求 str2 的长度 for (p=str1;m>n;m--) //若m>n,使p指向链表中的第m-n+1个结点 p=p->next; for (q=str2;m<n;n--) //若m<n,使q指向链表中的第n-m+l个结点 q=q->next; while (p->next !=NULL && p->next!=q->next) { //将指针 p 和 q 同步向后移动 p=p->next; q=q->next; }//while return p->next; //返回共同后缀的起始地址 }