我需要使用“多重性”定义来对从输入传递来的两个无序多重集进行并集：元素的多重性（也称为绝对频率）是元素“ x”在无序多重集中的出现次数'。
在multiSetUnion中，元素的多重性是两个多重集中其多重性的最大值。
我已经正确实现了int multiplicity（const Elem e，const MultiSet＆s）函数（返回多重集中的出现次数）。
多集是单链表。
这是我想出的算法：
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库）。
我提出的算法故意是解决方案的一半（我遇到问题的部分）。
我没有遇到任何特定的错误，但是程序只是停顿了（它应该打印两个多重集的第一个，第二个和并集-打印功能正确并且直接在主函数中调用；至于现在我只得到了一个或两个多集为空时，请更正输出），并返回以下内容：“返回-1073741819的进程”（我目前在Windows上进行调试）。
最佳答案
考虑以下示例：
MultiSet s1({7, 7});
MultiSet s2({5});
如果您现在遍历s1：
1st iteration: 7 7
^
aux1
2nd iteration: 7 7
^
aux1
如果
s1中有多个相等的元素，则将不止一次发现它们，最终导致增加多重平方（如果s2之一较大，则等于两个多重乘积）。另一方面，由于
s1中不包含5，因此您也不会尝试在s2中查找它–仍然存在。要解决第一个问题，您需要检查当前元素是否已包含在
s3中，如果已包含，则跳过该元素。要解决第二个问题，您还需要遍历
s2，添加所有尚未包含在s3中的元素。照原样，最终结果将是相当差的性能（应该在
O(n²)和O(n³)之间，而不是后者）。不幸的是，您选择了一个数据结构（一个简单的单链列表–显然未排序！），它无法为您想要的操作提供很好的支持，尤其是您选择的算法。如果使两个列表保持排序，则可以创建具有线性运行时间的算法。它的工作方式与合并排序中的合并步骤类似：
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)
但是，当您直接暴露列表的节点时，始终有危险，即插入操作不会从head元素开始–排序顺序可能会中断。
您应该适当地封装：
将您当前的MultiSet重命名为e。 G。 '节点'并创建一个新类
MultiSet。使节点类成为新集合类的嵌套类。
列表的所有修饰符应仅是set类的成员。
您可能公开了节点类，但是用户必须不能修改它。然后它将仅用作一种迭代器。