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

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

Это обратная функция, которую я использую, head — это локальная переменная, объявленная в main, например Node* head = NULL;, и она уже заполнена набором значений.

Node* reverse_iterative(Node* head)
{
    if(head == NULL || head->next == NULL)
        return head;

    Node *prev, *current=head, *temp;
    while(current != NULL)
    {
        current->prev = current->next;
        current->next = temp;
        temp = current;
        current = current->prev;
    }
    return temp;
}

Вот как я использовал это в main :

Node* rev = NULL;
rev = reverse_iterative(head);

Вот результат, который я получил:

original list: 15 <=>25 <=>35 <=>45 <=>55 <=>65 <=>75 <=>
making the list actually reverse: 75 <=>65 <=>55 <=>45 <=>35 <=>25 <=>15 <=>
after reversing, the original list now: 15 <=>

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


c pointers doubly-linked-list
person zolo    schedule 29.10.2012    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Внимательно посмотрите на свой цикл while и рассмотрите следующее утверждение на начальной итерации цикла:

current->next = temp;

Что находится в temp во время этого задания? Раскрывая больше кода, мы имеем:

Node *prev, *current=head, *temp;
while(current != NULL)
{
    current->prev = current->next;
    current->next = temp;
    temp = current;
    current = current->prev;
}

Обратите внимание, что temp не инициализирован и, следовательно, имеет неопределенное значение указателя. Ваш исходный следующий указатель head-ptr сбрасывается на мусор, хранящийся в неинициализированном файле temp.

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

Node *current=head, *temp=NULL;
while(current != NULL)
{
    temp = current->prev;
    current->prev = current->next;
    current->next = temp;
    temp = current;
    current = current->prev;
}

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

person WhozCraig    schedule 29.10.2012
comment
я изменил код, включая ваши изменения, но это ничего не меняет. если я вызываю reverse_iterative(head), любые изменения, вносимые в head внутри функции, не должны действительно влиять на указатель заголовка основного права? - person zolo; 29.10.2012
comment
@Abhilash Они не будут влиять на указатель головы, но они будут влиять на узел, на который он указывает. Этот узел теперь находится в хвосте списка. вы должны установить свой указатель головы как результат вашей обратной функции. Когда вы переворачиваете список, новый указатель головы должен быть установлен на новую голову (которая раньше была хвостом). Без этого ваш старый указатель головы будет ссылаться на последний узел в списке. Попробуйте head = reverse_iterative(head);, чтобы понять, что я имею в виду. - person WhozCraig; 29.10.2012
comment
@Abhilash, если вы не хотите изменять исходный список, вы можете либо (а) сделать копию и отменить его, либо (б) отменить его снова после сброса измененного содержимого. т.е. запустить head = reverse_iterative(head); во второй раз. - person WhozCraig; 29.10.2012
comment
спасибо что помогло. но лучше ли не изменять исходный список и при этом получить обратный список, кроме создания копии или повторения этого дважды? - person zolo; 29.10.2012
comment
@Abhilash Пожалуйста, уточните. Целью вашей функции реверса является реверс списка или создание реверсивной копии списка. Последнее будет достаточно легко. Просто сделайте копию списка, затем переверните копию. У вас будет два списка, один за другим. - person WhozCraig; 30.10.2012
comment
целью было сделать обратную копию. я собираюсь использовать копию, чтобы отменить его. Спасибо :) - person zolo; 30.10.2012

arrow_upward
3
arrow_downward

Если я правильно вас понял, вы вообще не хотите, чтобы исходный список изменялся.

Но цикл изменяет исходный элемент. Например, current начинает указывать на элемент head, а затем вы изменяете его next и prev. Это означает, что исходный элемент заголовка теперь изменен.

person Mikkel K.    schedule 29.10.2012
comment
Да, я не хочу, чтобы мой первоначальный список был изменен, есть ли способ сделать это без фактического создания копии или повторения дважды? - person zolo; 30.10.2012
comment
Не на самом деле нет. Если вам нужен список с обратным порядком, вы не можете повторно использовать старые элементы. Вам нужны отдельные элементы, если они должны указывать в противоположных направлениях. - person Mikkel K.; 30.10.2012