Сортировка слияния не разделяет правую часть списка

Question

Как и названия, мой сортировка слияния разделяет только левую сторону. Все остальное отлично работает, включая мою функцию слияния. Я не могу понять, почему. Я очень благодарен за помощь. В списке, который включает: 7, 4, 10, 2, 6, 1, 3, 7, 11, 5, выдает 1, 2, 3, 4, 6, 7, 7, 10, 11, 5

EDIT: добавлена ​​остальная часть моего класса.

#include <iostream> 
#include <string> 
using namespace std; 

class linkedList 
{ 
private: 
    class node 
    { 
    public: 
     int data; 
     node * next; 
     node * prev; 


    node(int x) 
    { 
     data = x; 
     next = NULL; 
     prev = NULL; 
    } 
}; 

node * head; 
node * tail; 

node * split() 
{ 
    node * finger = head; 
    node * fast = head->next; 
    while (fast != NULL) 
    { 
     fast = fast->next; 
     if (fast != NULL) 
     { 
      fast = fast->next; 
      finger = finger->next; 
     } 
    } 
    tail = finger->next; 
    node * splitB = tail; 
    splitB->prev = NULL; 
    finger->next = NULL; 
    return splitB; 
} 

node * merge(node * a, node * b) 
{ 
    linkedList m; 

    while(a != NULL || b != NULL) 
    { 
     if(b == NULL) 
     { 
      if(m.head != NULL) 
      { 
       a->prev = m.tail; 
       m.tail->next = a; 
       m.tail = a; 

      } 
      else 
      { 
       m.head = a; 
       m.tail = m.head; 
      } 
      a = a->next; 
     } 
     else if(a == NULL) 
     { 
      if(m.head != NULL) 
      {    
       b->prev = m.tail; 
       m.tail->next = b; 
       m.tail = b; 
      } 
      else 
      { 
       m.head = b; 
       m.tail = m.head; 
      } 
      b = b->next; 
     } 
     else if (a->data < b->data) 
     { 
      if(m.head == NULL) 
      { 
       m.head = a; 
       m.tail = m.head; 
      } 
      else 
      { 
       a->prev = m.tail; 
       m.tail->next = a; 
       m.tail = a; 
      } 
      a = a->next; 
     } 
     else 
     { 
      if(m.head == NULL) 
      { 
       m.head = b; 
       m.tail = m.head; 
      } 
      else 
      { 
       b->prev = m.tail; 
       m.tail->next = b; 
       m.tail = b; 
      } 
      b = b->next; 
     } 
    } 
    return m.head; 
} 

node* mergeSort(node * a) 
{ 
    if (head == NULL || head->next == NULL) 
    { 
     return a; 
    } 
    else 
    { 
     node * b = split(); 

     node* right = mergeSort(a); 
     node* left = mergeSort(b); 

     return merge(right, left); 
    } 
} 



public: 
    linkedList() 
    { 
     head = NULL; 
     tail = NULL; 
    } 


void push_back(int x) 
{ 
    node * baby = new node(x); 

    if(head == NULL) 
    { 
     head=baby; 
     tail=baby; 
    } 
    else 
    { 
     baby->prev = tail; 
     tail->next = baby; 
     tail = baby; 
    } 
} 

void mergeSort() 
{ 
    head = mergeSort(head); 
} 

bool empty() 
{ 
    if (head == NULL) 
     return true; 
    else 
     return false; 
} 

int pop() 
{ 
    int popMe = head->data; 
    node * deleteMe = head; 
    if (head->next == NULL) 
    { 
     head = NULL; 
     tail = NULL; 
     delete deleteMe; 
     return popMe; 
    } 
    else 
    { 
     head = head->next; 
     head->prev = NULL; 
     delete deleteMe; 
     return popMe; 
    } 
} 
//test 
void display() 
{ 
    node * finger = head; 
    while(finger!=NULL) 
    { 
     cout << finger->data << endl; 
     finger = finger->next; 
    } 
} 

}; 

Answer 1

Чтобы выполнить сортировку слияния, вам придется разбить список. Например, всегда расщепление на голове и хвосте бессмысленно. Он всегда будет разбиваться на весь список, а не на все меньшие части списка. Таким образом, ваш раскол должен был бы выглядеть примерно так:

void split(node *& a, node *& b) 
{ 
    node * finger = a; 
    node * fast = a->next; 
    while (fast != NULL) 
    { 
     fast = fast->next; 
     if (fast != NULL) 
     { 
      fast = fast->next; 
      finger = finger->next; 
     } 
    } 
    b = finger->next; 
    b->prev->next = NULL; 
    b->prev = NULL; 
} 

Я рекомендую изменять имена переменных fast и finger к чему-то более описательное.

Для слияния и mergeSort потребуются аналогичные модификации.

Отредактировано сообщение, чтобы сделать что-то на C++. Извини за это.

Answer 2

СТОП ИСПОЛЬЗОВАНИЕ ГЛОБАЛЬНЫХ ПЕРЕМЕННЫХ!
Удалите ВСЕ объявления переменных, которые появляются перед вашими функциями.
Опираясь исключительно на данные, переданные функциям в качестве их параметров.

EDIT

Здесь (возможно минимальное) изменение исходного кода, который не использует внешние переменные (за исключением без параметров mergeSort(), который должен быть только открытый метод, если вы реализуете код в некотором классе sortableList).
Код также не использует указатель last или prev, поскольку они не нужны в mergeSort и могут быть легко восстановлены после сортировки (легко означает здесь «в O (n) time» с одним проходом по отсортированному списку).

// split the list and return a pointer to a second half 
node * split(node * fast) 
{ 
    // assert(fast != NULL) 

    node * finger = fast; 
    fast = fast->next; 

    while (fast != NULL) 
    { 
     fast = fast->next; 
     if (fast != NULL) 
     { 
      fast = fast->next; 
      finger = finger->next; 
     } 
    } 

    node * splitB = finger->next; 
    finger->next = NULL; 
    return splitB; 
} 

// sort the (sub)list and return its new head 
node* mergeSort(node * a) 
{ 
    // assert(a != NULL) // list not empty 

    node * b = split(a); // take second half 

    if (b != NULL) 
    { 
     a = mergeSort(a); 
     b = mergeSort(b); 

     a = merge(a, b); 
    } 
    return a; 
} 

void mergeSort() 
{ 
    if (head != NULL)  // make sure list isn't empty 
     head = mergeSort(head); 
} 

EDIT 2

Ваш merge рутина кажется слишком длинным и усложненной. См. Более короткую версию ниже. Разве это не более красноречиво?

node * merge(node * a, node * b) 
{ 
    // assert(a != NULL) 
    // assert(b != NULL) 

    node * head, * tail; 

    if (a->data <= b->data) 
     head = a, a = a->next; 
    else 
     head = b, b = b->next; 
    tail = head; 

    while (a != NULL && b != NULL) 
    { 
     if (a->data <= b->data) 
      tail->next = a, a = a->next; 
     else 
      tail->next = b, b = b->next; 
     tail = tail->next; 
    } 

    if (a != NULL) 
     tail->next = a; 
    else 
     tail->next = b; 

    return head; 
} 

Вы можете также избавиться от первого if, если вы создаете временную node переменные (но иногда не допускаются, скажем, если node класса является слишком сложным или его конструкция может вызвать некоторые нежелательные побочные эффекты):

node * merge(node * a, node * b) 
{ 
    // assert(a != NULL) 
    // assert(b != NULL) 

    node head, * tail = &head; 

    while (a != NULL && b != NULL) 
    { 
     if (a->data <= b->data) 
      tail = tail->next = a, a = a->next; 
     else 
      tail = tail->next = b, b = b->next; 
    } 

    tail->next = a ? a : b; 

    return head->next; 
} 

И это, как восстановить prev ссылки, как только вперед связанный список сортируется:

void restoreBacklinks() 
{ 
    node * prev = NULL; 

    for (node * p = head; p != NULL; p = p->next) 
    { 
     p->prev = prev; 
     prev = p; 
    } 

    tail = prev; 
} 

void mergeSort() 
{ 
    if (head != NULL)  // make sure list isn't empty 
    { 
     head = mergeSort(head); 
     restoreBacklinks(); 
    } 
}