C ++ Merge сортирует связанный список не сортируя первые два индекса - PullRequest
Новая
       65

C ++ Merge сортирует связанный список не сортируя первые два индекса

2 голосов
/ 16 марта 2020

Я немного теряюсь, пытаясь понять, как рекурсивно объединить сортировку моего связанного списка. Я пытался следовать некоторым руководствам, но я немного теряюсь со всеми указателями и рекурсией. Такое ощущение, что проблема в функции слияния, когда списки имеют по одному узлу.

У меня есть класс Node и класс списка. Я упустил другие функции-члены, чтобы сделать его более читабельным. Вот классы. Извините, некоторые имена переменных не являются лучшими в функциях. 

class Node {
  public:
    int val;
    Node *next;
};

class Linked_list {
  private:
    unsigned int length;
    Node *head;
    Node *tail;
  public:
    void sort_ascending();
    void merge_sort(Node **);
    void halve(Node *&, Node *&, Node *&);
    Node* merge(Node *, Node *);
};

Я начинаю с sort_ascending(), который создает указатель Node и устанавливает его на первый узел в списке, а затем вызывает merge_sort с указателем в качестве параметра. 

void Linked_list::sort_ascending() {
    Node *h = head->next;
    merge_sort(&h);
}

merge_sort проверяет, являются ли первые два индекса NULL, возвращает, если они есть. В противном случае связанный список делится пополам. 

void Linked_list::merge_sort(Node **h) {
    Node *t = *h;
    Node *a;
    Node *b;
    if ((t == NULL) || (t->next == NULL)) {
        return;
    }
    halve(t, a, b);
    merge_sort(&a);
    merge_sort(&b);
    *h = merge(a, b);
    return;
}

Здесь приведена функция разбиения списка на две половины. 

void Linked_list::halve(Node *&t, Node *&a, Node *&b) {
    Node *h1 = t;
    Node *h2 = t->next;
    while (h2 != NULL) {
        h2 = h2->next;
        if (h2 != NULL) {
            h1 = h1->next;
            h2 = h2->next;
        }
    }
    a = t;
    b = h1->next;
    h1->next = NULL;
}

Наконец, функция слияния. 

Node *Linked_list::merge(Node *a, Node *b) {
    Node *h = NULL;
    if (a == NULL) {
        return b;
    }
    if (b == NULL) {
        return a;
    }
    if (a->val <= b->val) {
        h = a;
        h->next = merge(a->next, b);
    } else {
        h = b;
        h->next = merge(a, b->next);
    }
    return h;
}

Когда я запускаю свою программу и ввожу / печатаю несколько значений, я получаю: 

9 4 32 2 6

Затем, когда я сортировать это, вывод становится: 

9 4 2 6 32

Ответы [ 2 ]

2 голосов
/ 16 марта 2020

Иная причина, чем та, на которую указал @VeryBhatti, 

while(h2 != NULL){
    h2 = h2->next;
    if(h2 != NULL){
        h1 = h1->next;
        h2 = h2->next;
    }
}

Я не получаю логи c вашей halve функции. Поскольку h1 также движется вдоль h2, когда оператор while прерывается, h1 всегда будет указывать в секунду на последний элемент вместо центра.

Почему бы не использовать переменную length вдвое сократить список? Упрощение вашего кода значительно поможет вам отладить код самостоятельно.

Кроме того, одновременное использование reference и pointer, кажется, усложняет ваш код. Я бы порекомендовал сначала попробовать реализовать его в стиле c вместо стиля cpp. Поскольку вы используете связанный список, вы сможете реализовать это без использования указателя на указатель.

Опять попробуйте упростить свой код, насколько это возможно, и найдите другие примеры сортировки слиянием.

2 голосов
/ 16 марта 2020

В функции sortAscending 

void Linked_list::sort_ascending(){
   Node *h = head->next;
   merge_sort(&h);
}

Смотрите выше, что вы указываете узел * h на следующую голову. Не голова сама. И, возможно, именно поэтому он исключает первый элемент, т.е. сам заголовок при сортировке связанного списка.

...