在 C++ 中使用多重函数合并两个链表

Question

我需要通过使用 "multiplicity" 定义对从输入传递的两个无序多重集进行并集：元素的多重性，也称为绝对频率，是元素出现的次数 'x' 在无序多重集中 's'。在 multiSetUnion 中，元素的多重性是其在两个多重集中的多重性的最大值。

我已经正确实现了 int multiplicity(const Elem e, const MultiSet& s) 函数（returns 多重集中的出现次数）。

多重集是单链表。

这是我想出的算法：

for as long as the first list isn't empty
   if elem of the first list (multiset) is not in the second list (multiset)
      add elem in unionlist
   if elem of the first list (multiset) is in the second list (multiset)
      if multiplicity of elem is bigger in the first list than in the second one
         add elem in unionlist as many times as its multiplicity in list1
      if multiplicity of elem is bigger in the second list than in the first one
         add elem in unionlist as many times as its multiplicity in list2  
analyze the second element of the first list

这是我的算法实现，但是当两个列表都不为空并且我不知道为什么时它会给我错误：

MultiSet multiset::multiSetUnion(const MultiSet& s1, const MultiSet& s2)
{
    if (isEmpty(s1) && isEmpty(s2))
        return emptySet;
    if (isEmpty(s1) && !isEmpty(s2))
        return s2;
    if (!isEmpty(s1) && isEmpty(s2))
        return s1;
    MultiSet s3 = emptySet;    
    MultiSet aux2 = s2;            //THE FUNCTION DOESN'T WORK FROM HERE ON
    for (MultiSet aux1 = s1; !isEmpty(aux1); aux1 = aux1->next) { 
        if (!isIn(aux1->elem, aux2))
            insertElemS(aux1->elem, s3);
        if (isIn(aux1->elem, aux2)) {
            if (multiplicity(aux1->elem, aux1) > multiplicity(aux1->elem, aux2)) {
                for (int n = 0; n < multiplicity(aux1->elem, aux1); ++n)
                    insertElemS(aux1->elem, s3);
            }
            else {
                for (int m = 0; m < multiplicity(aux1->elem, aux2); ++m)
                    insertElemS(aux1->elem, s3);
            }
        }
    }
    return s3;
}

有人能指出我哪里做错了吗？我是否忘记了算法中的某些内容，或者这是一个实现问题？

编辑：这是我如何实现函数 IsIn(const Elem x, MultiSet& s) 和 multiplicity(const Elem e, MultiSet& s):

bool isIn(const Elem x, MultiSet& s) {
    if (s->elem == x) return true;
    while (!isEmpty(s)) {
        if (s->elem!=x)
            s = s->next;
        else    return true;
    }
    return false;
}

int multiset::multiplicity(const Elem e, const MultiSet& s)
{
    if (isEmpty(s))    return 0;
    int count = 0;
    MultiSet aux = s;
    while (!isEmpty(aux)) {
        if (aux->elem==e) {
            ++count;
        }
        aux = aux->next;
    }
    return count;
}

不幸的是我不能使用矢量库（或任何 STL 库）。我提出的算法是解决方案的一半（我遇到问题的部分）。我没有收到任何具体错误，但程序只是停滞了（它应该打印第一个、第二个和两个多重集的并集——打印函数是正确的，直接在 main 中调用；至于现在我只得到当一个或两个多集为空时正确输出）和returns这个："Process returned -1073741819"（我目前正在Windows上调试）。

Answer 1

考虑以下示例：

MultiSet s1({7, 7});
MultiSet s2({5});

如果你现在遍历 s1:

1st iteration:        7    7
                      ^
                     aux1

2nd iteration:        7    7
                           ^
                          aux1

如果 s1 中有多个相等的元素，您会不止一次地发现它们，最终导致添加重数的平方（或两个重数的乘积，如果 s2 中的一个更大）。

另一方面，由于 5 不包含在 s1 中，您也不会尝试在 s2 中查找它 – 但它仍然存在...

要解决第一个问题，您需要检查当前元素是否已包含在 s3 中，如果是，则跳过它。

要解决第二个问题，您还需要遍历 s2，添加所有尚未包含在 s3 中的元素。

照原样，最终结果的性能会很差（应该介于 O(n²) 和 O(n³) 之间，而不是后者）。不幸的是，您选择了一种数据结构（一个简单的单链表——显然是未排序的！），它对你想要的操作提供的支持很差——尤其是你选择的算法。

如果您对两个列表进行排序，则可以创建线性算法 run-time。它的工作方式与合并排序中的合并步骤类似：

while(elements available in both lists):
    if(left element < right element):
        append left element to s3
        advance left
    else
        append right element to s3
        if(left element == right element):
            advance left // (too! -> avoid inserting sum of multiplicities)
        advance right
append all elements remaining in left
append all elements remaining in right
// actually, only in one of left and right, there can be elements left
// but you don't know in which one...

在插入期间保持列表排序非常简单：

while(current element < new element):
    advance
insert before current element // (or at end, if no current left any more)

但是，当您直接公开列表的节点时，您总是面临着插入不会从头元素开始的危险——并且您的排序顺序可能会被破坏。

你应该适当封装：

将您当前的 MultiSet 重命名为 e。 G。 'Node' 并创建一个新的 class MultiSet.
使节点 class 成为新集合 class 的嵌套 class。
列表的所有修饰符只能是集合 class 的成员。
您可以公开节点 class，但用户不能修改它。然后它将作为一种迭代器。

在 C++ 中使用多重函数合并两个链表

Union of two linked lists using multiplicity function with in C++

c++

linked-list

list

find-occurrences