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

Я пытаюсь отсортировать односвязный список, используя пузырьковую сортировку, манипулируя ТОЛЬКО указателями, без ключей.

Следующее застревает в цикле for и бесконечно зацикливается. Я не понимаю, почему это так. Может ли кто-нибудь объяснить мне, почему конец списка не найден?

Node* sort_list(Node* head)
{
    Node * temp;
    Node * curr;
    for(bool didSwap = true; didSwap; ) {
            didSwap = false;
            for(curr = head; curr->next != NULL; curr = curr->next) {
                    if(curr->key > curr->next->key) {
                            temp = curr;
                            curr = curr->next;
                            curr->next = temp;
                            didSwap = true;
                    }
                    cout << curr->next->key << endl;
            }
    }
    return head;

}

Если я изменю код так, чтобы ключи (данные) поменялись местами, то функция работает правильно, но по какой-то причине я не могу заставить ее работать, манипулируя только указателями.


c++ singly-linked-list bubble-sort
person Mark S.    schedule 24.10.2013    source источник

Ответы (4)


arrow_upward
3
arrow_downward

Логическая ошибка, вы создаете бесконечный цикл со следующим кодом:

temp = curr;
curr = curr->next;
curr->next = temp;

I,e next_of_current указывает на текущий, поэтому curr->next всегда будет curr и никогда не будет NULL;

Затем вы должны использовать предыдущий указатель, чтобы исправить свой список, потому что ваш список можно пройти в одном направлении. Итак, подумайте - если A->B->C->NULL; и вы меняете местами C и B, тогда новый список по-прежнему будет указывать на A-> B, и следующая итерация будет неправильной ... потому что вы не изменяете свой предыдущий следующий.

Итак, другая реализация может быть -

Node* sort_list(Node* head) {
    Node * curr;
    Node * prev;
    for(bool didSwap = true; didSwap; ) {
        didSwap = false;
        prev = head;
        for(curr = head; curr->next != NULL; curr = curr->next) {
                if(curr->key > curr->next->key) {
                        if (head == curr) {
                            head = curr->next;      
                            curr->next = head->next; 
                            head->next = curr; 
                            prev = head;
                        } else {
                            prev->next = curr->next;
                            curr->next = prev->next->next;
                            prev->next->next = curr
                        }
                        didSwap = true;
                } else if (head != curr) {
                    prev = prev->next;
                } 
                //cout << curr->next->key << endl; // <- this may cause crash if curr->next now points to NULL; (i,e last element)
            }
    }
    return head;
}

Надеюсь, это поможет, с уважением.

person fadedreamz    schedule 24.10.2013

arrow_upward
0
arrow_downward

У вас следующая проблема:

Пусть у вас есть список из трех членов: ptr1->ptr2->ptr3. Перед заменой у вас установлен следующий указатель: curr=ptr1; curr->next=ptr2; curr->next->next=ptr3. Когда вы выполняете обмен, вы получаете curr=ptr2; curr->next=ptr1; curr->next->next=ptr2.

Например. ты потерял птр3. Вам нужно изменить код внутреннего цикла следующим образом:

temp = curr;
temp->next = curr->next->next;    // Save ptr3
curr = curr->next;
curr->next = temp;
didSwap = true;
person Danil Asotsky    schedule 24.10.2013
comment
Я думаю, вам, вероятно, следует учитывать то, что вы находитесь в конце списка Node. curr->next->next произойдет сбой, если вы находитесь на последнем элементе Node. - person miqh; 24.10.2013

arrow_upward
0
arrow_downward

Поле, которое вы хотите поменять местами, это value. Однако, если вы поменяете местами node, поле next изменится, вопрос станет немного сложнее, вам нужно сохранить правильное поле next. Словом, изменить value — простой и хороший метод.

person YaleCheung    schedule 24.10.2013
comment
Я пытаюсь выполнить сортировку БЕЗ изменения каких-либо значений. Только указатели. - person Mark S.; 24.10.2013

arrow_upward

arrow_downward

person    schedule
comment
Пожалуйста, не публикуйте только ответы с кодом. Объясните, что вы делаете для решения проблемы. Этот пост также может быть связан с форматированием кода. - person Milk; 11.09.2017