Слияние для связанного списка - PullRequest
Новая
       5

Слияние для связанного списка

2 голосов
/ 09 февраля 2020

У меня есть исходный код Mergesort для неупорядоченного связанного списка следующим образом. Предположим, что я уже выполнил функцию merge, а z - это сторожевой ключ. 

node *mergesort(node *c)
{
    node *a, *b;
    if (c->next != z)
    {
        a = c;
        b = c->next->next->next;
        while (b != z)
        {
            c = c->next;
            b = b->next->next;
        }
        b = c->next;
        c->next = c;
        return merge(mergesort(a), mergesort(b));
    }
    return c;
}

У меня есть 3 подозрения относительно этой реализации:

  1. Как видите, b указывает на третий элемент связанного списка. Я не знаю почему, потому что я думаю, что этого просто должно быть достаточно b = c->next.

  2. В l oop while он также имеет b = b->next->next, так как Насколько я понимаю, он продолжает указывать на четвертый элемент после c в этом массиве. Это нормально, если я напишу b = b->next?

  3. Как я понимаю алгоритм mergesort, он делит массив на два подмассива a и b, а затем выполняет сортировку слиянием каждый subarray рекурсивно, но я просто вижу, что он работает только с массивом b. Что-то не так с этой реализацией?

1 Ответ

0 голосов
/ 09 февраля 2020

В этом коде есть несколько проблем:

  • b = c->next->next->next; имеет неопределенное поведение, если c->next->next равно нулю
  • b = b->next->next; имеет неопределенное поведение, если b->next равно нулю
  • список не разделен должным образом до b, кроме того c->next = c; создает al oop, что приведет к сбою алгоритма с бесконечным l oop.

Для исправления этих проблем функция нуждается в существенных изменениях.

Вот модифицированная версия: 

node *mergesort(node *c) {
    node *a, *b;
    /* test if list has at least 2 elements */
    if (c != z && c->next != z) {
        /* locate the middle node */
        a = b = c;
        while (b->next != z && b->next->next != z) {
            c = c->next;
            b = b->next->next;
        }
        /* split the list between c and c->next */
        b = c->next;
        c->next = z;
        /* sort both sublists and merge them */
        return merge(mergesort(a), mergesort(b));
    }
    return c;
}
...