вставка промежуточного узла в двусвязный список [как сделать] - PullRequest
Новая
       12

вставка промежуточного узла в двусвязный список [как сделать]

0 голосов
/ 22 марта 2011

Я, кажется, поворачиваюсь кругами с этой задачей.Даже рисование не дает мне рабочего решения.Может ли кто-нибудь помочь мне найти, где мой мыслительный процесс ломается здесь? 

// method receives node ins to be inserted
// and node prev in front of which ins should be inserted
public void insertIntermediate(DLLNode ins, DLLNode prev)
{
    ins.pred = prev ; // update node ins' predecessor information
    ins.succ = prev.succ ; // update node ins' successor information 
    prev.succ = ins ; // update list's information
    prev.succ.pred = ins ; // update list's information
}

[EDIT2] (удалено edit1, чтобы уменьшить беспорядок)

@ Эндрю, хорошо, я нашелэто: что было не так с вышеупомянутым, был порядок строк 3 и 4:

строка 3 заставила меня потерять доступ к prev.succ.pred.

Из-за замены двух строк, которые я решилэта проблема.Спасибо за подсказку!

ДОПОЛНИТЕЛЬНЫЙ ВОПРОС:

Я столкнулся с еще одной странной проблемой, и именно поэтому я потерял так много времени, чтобы найти решение: если я снова вставляю уже существующий элемент, по какой-то причине все это входит в бесконечный цикл, когда я его печатаю ... например, 

myList.addBeforeFirst(B) ;
myList.addBeforeFirst(B) ;

вызывает цикл, тогда как: 

myList.addBeforeFirst(B) ;
myList.addBeforeFirst(C) ;

отлично работает

вот метод: 

public void addBeforeFirst(DLLNode ins)
{
    ins.succ = first ;
    ins.succ.pred = ins ;
    first = ins ;
}

и узлы: 

DLLNode B = new DLLNode("Hi", null, null) ;
DLLNode C = new DLLNode("Salut", null, null) ;

почему это происходит?

1 Ответ

1 голос
/ 22 марта 2011

Это список с двойной связью , да?Что это значит?Убедитесь, что вы обновляете все соответствующие ссылки в правильном порядке.Кроме того, убедитесь, что все соответствующие узлы существуют.

Редактировать:

Давайте рассмотрим ваши утверждения по порядку.

Перед началом работы у вас естьprev, свойство которого succ указывает на узел-преемник.(Или так? Может ли быть исключение? Как бы вы справились с таким исключением, если оно существует?) prev.succ.pred должно совпадать с prev при условии, что prev.succ указывает на узел-преемник.

Теперь, ваши первые два оператора устанавливают ins.pred и ins.succ.По сути, это правильная идея, но посмотрите мои вопросы выше.

Теперь вы установите prev.succ на ins.Сосредоточьтесь на этом утверждении.Есть ли информация, которую вы сейчас потеряли?Что именно точно делает следующее утверждение?Это то, что вы хотели?

Я думаю, это лучшее из того, что я могу сделать, не отдавая решения полностью.

Правка для задачи с бесконечным циклом:

Проблема, с которой вы столкнулись, заключается в разнице между передачей параметров по значению и передачей параметров по ссылке.Поскольку вы передаете по ссылке, вы передали ссылку на один и тот же объект (B) дважды.Это означает, что в итоге вы сделали следующее:

Первый вызов: 

B.succ = first;
B.succ.pred = B; /* why not just first.pred = ins? */
first = B;

Теперь для первого установлено значение B. Итак, второй вызов с использованием B: 

B.succ = B;
B.succ.pred = B; /* so, now B is its own pred and succ */
first = B; /* no change here */

Итак, теперь сначала B, first.succ - B, first.succ.succ - B и т. Д., Следовательно, бесконечный цикл.

...