Объединение двух связанных списков с использованием функции множественности в C ++

Question

Мне нужно объединить два неупорядоченных мультимножества, переданных из ввода, используя определение «кратность»: множественность элемента, также называемая абсолютной частотой, представляет собой число вхождений элемента 'x' в неупорядоченном мультимножество В multiSetUnion кратность элемента - это максимум его кратности в двух мультимножествах.

Я уже правильно реализовал функцию множественности int (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) и множественность (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).

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³), а не последним). К сожалению, вы выбрали структуру данных (простой односвязный список - очевидно, не отсортированный!), Который предлагает плохую поддержку для операций, которые вы намереваетесь - и особенно для выбранного вами алгоритма.

Если вы сохраняете два списка отсортированными, вы можете создать алгоритм с линейным временем выполнения. Это будет работать так же, как шаг слияния в сортировке слиянием:

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. г. «Узел» и создайте новый класс MultiSet.
• Сделать класс узла вложенным классом нового набора классов.
• Все модификаторы списка должны быть только членами заданного класса.
• Вы можете предоставить класс узла, но пользователь не должен иметь возможность его изменять. Тогда это будет просто своего рода итератор.