Почему эти два разных реверсивных двусвязных списка?

Чтобы перевернуть двусвязный список, в чем разница между этими двумя кодами? Разве это не то же самое, что изменить следующий и предыдущий указатели?

void reverse(Node **head_ref) 
{ 
    Node *temp = NULL; 
    Node *current = *head_ref; 

    while (current != NULL) 
    { 
        temp = current->prev; 
        current->prev = current->next; 
        current->next = temp;             
        current = current->prev; 
    } 

    if(temp != NULL ) 
        *head_ref = temp->prev; 
} 

void reverse(Node **head_ref) 
{ 
    Node *temp = NULL; 
    Node *current = *head_ref; 

    while (current != NULL) 
    { 
        temp = current->next;
        current->next; = current->prev; 
        current->prev = temp;             
        current = current->next; 
    } 

    if(temp != NULL ) 
        *head_ref = temp->next;
}

c++ algorithm data-structures doubly-linked-list
person MinKwon Kim    schedule 18.03.2021    source источник
comment
Порядок, в котором вы выполняете обмен, на самом деле не имеет значения, если вы в конечном итоге меняете все узлы. Есть ли у него единственный корневой узел, например, кольцевая структура, или голова и хвост разделены?   -  person tadman    schedule 18.03.2021
comment
1-й обратный метод, вероятно, начинается с конца и меняет список, устанавливая текущий узел на предыдущий узел. Второй обратный метод делает противоположное; вероятно, начиная с начала списка и устанавливая текущий узел на следующий узел. Независимо от того, как вы перевернете список, результат будет тем же.   -  person Evan Bechtol    schedule 18.03.2021
comment
Второй перемещает список в неправильном направлении, поэтому он не сработает. Сработает, если вы начнете с хвоста, а не с головы.   -  person interjay    schedule 18.03.2021
comment
Рассмотрите возможность использования существующих C ++ контейнеров и умные указатели. Прочтите также хорошую книгу по программированию на C ++ ...   -  person Basile Starynkevitch    schedule 18.03.2021
comment
Вдохновляйтесь существующими проектами C ++ с открытым исходным кодом, такими как FLTK, GCC, RefPerSys, рыба   -  person Basile Starynkevitch    schedule 18.03.2021
comment
Скомпилируйте свой код C ++ с помощью GCC, вызываемого как g++ -Wall -Wextra -g, улучшите свой код C ++, чтобы не было предупреждений, затем используйте < отладчик href = "https://www.gnu.org/software/gdb/" rel = "nofollow noreferrer"> GDB, чтобы понять поведение исполняемого файла во время выполнения.   -  person Basile Starynkevitch    schedule 18.03.2021
comment
Второй тоже не скомпилируется;) current->next; = current->prev;   -  person churill    schedule 18.03.2021

Ответы (1)


arrow_upward
1
arrow_downward

Когда вы меняете местами две ссылки, вы действительно можете выбрать, с какой из них начать, т.е. какую из них копировать в переменную temp.

Таким образом, следующие два фрагмента кода успешно выполняют замену:

    temp = current->prev; 
    current->prev = current->next; 
    current->next = temp;

И (если вы удалите точку с запятой наполовину):

    temp = current->next; 
    current->next = current->prev; 
    current->prev = temp;

Однако ваш второй блок кода должен продолжаться так же, как и первый блок кода. Вы должны перейти по ссылке prev (так как до обмена это была ссылка next). Итак, во второй версии вам следует изменить:

    current = current->next;

to:

    current = current->prev;

Тем не менее, проблема во втором коде заключается в том, что в конце каждой итерации ваша ссылка temp равна ссылке current и будет равна нулю при выходе из цикла. Это делает невозможным правильную установку указателя головы после выхода из цикла.

Так что вам действительно стоит придерживаться первой версии.

person trincot    schedule 18.03.2021
comment
Вы получили ответ на свой вопрос? Не могли бы вы дать обратную связь? - person trincot; 21.03.2021