问题
假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可以共享相同的后缀存储空间。例如“loading”和“beging”的存储映像如下图所示。
设str1和str2分别指向两个单词所在的单链表的头结点,链表结点结构为(data,next)。请设计一个时间上尽可能高效的算法,找出由str1和str2所指的两个链表的共同后缀的起始位置(如上图中字符i所在结点的位置p)
分析
求出str1和str2的长度,如果长度相等,则单词长度相同,否则,移动指针使两个单词的词尾对齐,然后找出公共部分的起始位置(并不是第一个字符相等的位置就是所求位置)。
和王道的代码不一样,正确与否自己想想。
代码
LinkList findSame(LinkList str1, LinkList str2) {///找公共后缀int str1Num = getLength(str1);///求str1的长度int str2Num = getLength(str2);///求str2的长度LNode *p, *q;///移动p、q指针,使单词的尾对齐if(str1Num == str2Num) {p = str1 -> next;q = str2 -> next;}else if(str1Num < str2Num) {p = str1 -> next;q = str2 -> next;int i = 0;for(int i = 0; i < str2Num - str1Num; i++) {q = q -> next;}}else {p = str1 -> next;q = str2 -> next;int i = 0;for(int i = 0; i < str1Num - str2Num; i++) {p = p -> next;}}///找公共后缀while(p) {int temp;if(p -> data != q -> data) {///当前节点值不相等,向后找p = p -> next;q = q -> next;} else {///当前节点值相等,则向后遍历,之后的每一个节点值都相等,此节点///才是所求,一个结点值不相等,就不是所求LNode *p1 = p -> next;LNode *q1 = q -> next;while(p1) {temp = 1;if(p1 -> data != q1 -> data) {temp = 0;break;}p1 = p1 -> next;q1 = q1 -> next;}if(temp == 1) {return p;}else {p = p1 -> next;q = q1 -> next;}}}
}