Сортировка связанного списка с помощью указателей - PullRequest
Новая
       69

Сортировка связанного списка с помощью указателей

2 голосов
/ 29 апреля 2020

Я пытаюсь реализовать сортировку Shell в связанном списке. Я делю свой исходный связанный список на подчиненный список, который содержит узлы с пробелом 'k' относительно алгоритма сортировки оболочки. Я хочу отсортировать подсвязанный список, манипулируя указателями 'next' вместо изменения его поля данных. Итак, у меня есть функция sortList, которая пересекает связанный список и меняет узлы на swapNodes, если встречает какие-либо неупорядоченные узлы.

Когда я передаю неупорядоченный связанный список с двумя элементами в sortList, я продолжаю терять один из узлов в моем списке. Например, в моем списке 50 и -84, я передаю его в sortList. После sortList цифр, которые они неупорядочены, он вызывает swapNodes, но как только swapNodes завершается, результирующий список имеет только 50.

Я попытался GDB и обнаружил, что когда я в swapNodes scope список успешно сортируется без потери узла, но когда он завершается и возвращается к sortList scope, и head, и curr указывают только на 50, а их поле 'next' равно NULL.

Мои функции: 

void sortList(Node * head, long * n_comp) {
    Node * curr;
    int didSwap = 1;
    while(didSwap) {
        didSwap = 0;
        for(curr = head; curr -> next != NULL; ) {
                *n_comp += 1; //number of comparison
                if(curr->value > curr->next->value) {
                    swapNodes(curr, curr->next, &head);
                    didSwap = 1;
                } 
                curr = curr -> next;
                if (!curr) break;
            }
    }
}

void swapNodes(Node * p1, Node * p2, Node ** start) 
{
    Node *p1pre = NULL;
    Node *p1curr = *start;
    while (p1curr && p1curr!=p1)
    {
        p1pre = p1curr;
        p1curr = p1curr->next;
    }
    Node *p2pre = NULL;
    Node *p2curr = *start;
    while (p2curr && p2curr != p2)
    {
        p2pre = p2curr;
        p2curr = p2curr->next;
    }

    if (p1pre != NULL)
    {
        p1pre->next = p2curr;
    }
    else
    {
        *start = p2curr;
    }
    if (p2pre != NULL)
    {
        p2pre->next = p1curr;
    }
    else
    {
        *start = p1curr;
    }
    Node *temp = p2curr->next;
    p2curr->next = p1curr->next;
    p1curr->next = temp;
    return;
}  
``

1 Ответ

1 голос
/ 02 мая 2020

Это происходит по той же причине, по которой вы вначале указали start type Node**: ваш узел [50] перемещается, а head перемещается вместе с ним, а не остается в начале списка. Вам нужно изменить метод sortList, чтобы параметр head также имел тип Node**: 

void sortList(Node ** head, long * n_comp) {
    Node * curr;
    int didSwap = 1;
    while(didSwap) {
        didSwap = 0;
        for(curr = *head; curr -> next != NULL; ) {
            std::cout<< "It: " << *n_comp<< std::endl;
            *n_comp += 1; //number of comparison
            if(curr->value > curr->next->value) {
                swapNodes(curr, curr->next, head);
                didSwap = 1;
            }
            curr = curr -> next;
            if (!curr) break;
        }
    }
}

Теперь ваша голова останется в начале списка.

Примечание: это одна из причин, по которой сторожевые узлы - это вещь.

...