| [数据结构]算法设计题 | 您所在的位置：网站首页 › 数据结构算法设计题100题 › [数据结构]算法设计题 |
[数据结构]算法设计题
|
问题
采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可以共享相同的后缀存储空间。例如，“loading”和“being”的存储空间影像如图。 设str1和str2分别指向两个单词所在链表的头结点，链表结点结构为(data,next)，请设计一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表共同 后缀的起始位置。要求： 给出算法的基本设计思想说明算法的时间复杂度。 解答 算法思想因为两个链表长度不一定相同，所以从头开始同时遍历到尾结点，并不能保证同时到达。假设一个链表比另一个长k个结点，将长链表先移动k个位置，然后再与短链表同时开始遍历，检查指针是否指向同一个结点，如果是则为共同后缀的起始位置。 算法分析时间复杂度为O(m+n)，空间复杂度为O(1)。 /* 采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可以共享相同的后缀存储空间。例如，“loading”和“being”的存储空间影像如图。 设str1和str2分别指向两个单词所在链表的头结点，链表结点结构为(data,next)，请设计一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表共同 后缀的起始位置。要求： 1. 给出算法的基本设计思想 2. 说明算法的时间复杂度。 */ #include #include using namespace std; typedef struct LNode { char data; struct LNode *next; }LNode, *LinkList; void createList(LinkList &L, string s) { L = new LNode; L->next = NULL; LinkList pc = L, p; for (int i = 0; i LinkList p = L->next; while (p) { cout next; } cout tmp = tmp->next; len1++; } tmp = p2; while (tmp) { tmp = tmp->next; len2++; } // 计算表长之差，找出长str对应的链表 int advance = 0; LinkList longPoint, shortPoint; if (len1 > len2) { longPoint = p1; shortPoint = p2; advance = len1 - len2; } else { longPoint = p2; shortPoint = p1; advance = len2 - len1; } // 长链表上遍历advance个结点 while (advance--) { longPoint = longPoint->next; } // 同步遍历两个链表，寻找共用存储空间的位置 while (longPoint) { if (longPoint == shortPoint) { return longPoint; } else { longPoint = longPoint->next; shortPoint = shortPoint->next; } } // 查找失败 return NULL; } int hasSuffix(string s1, string s2) { int len1 = s1.size() - 1; int len2 = s2.size() - 1; int ans = 0; while (len1 >= 0 && len2 >= 0) { if (s1[len1] == s2[len2]) { ans++; len1--; len2--; } else { break; } } if (ans > 0) { return len1 + 1; } else { return -1; } } int main() { LinkList L1 = NULL, L2 = NULL; string s1, s2; cin >> s1 >> s2; int len1 = s1.size(), len2 = s2.size(); // 判断共同后缀空间位置 int position = hasSuffix(s1, s2); if (position == -1) { cout p = new LNode; p->data = s1[i]; p->next = pc->next; pc->next = p; pc = p; } // 接在L1和L2的后面 LinkList p1 = L1; while (p1->next) { p1 = p1->next; } LinkList p2 = L2; while (p2->next) { p2 = p2->next; } p1->next = head->next; p2->next = head->next; // printList(L1); // printList(L2); // 查找后缀开始的结点 LinkList findNode = findSuffix(L1, L2); if (findNode == NULL) { cout |
【本文地址】
公司简介
联系我们