Удаление случайного узла как из односвойных, так и двусвязных списков - PullRequest
Новая
       37

Удаление случайного узла как из односвойных, так и двусвязных списков

0 голосов
/ 01 декабря 2011

Мне трудно придумать логику для удаления некоторого узла как из двусвязного, так и односвязного списка.Я посмотрел онлайн с помощью, но я не мог найти простой пример этого.Вот что у меня есть:

Двойное удаление.dCurrent - это узел, который мы хотим удалить. 

if (dCurrent == dHead){
   dHead = dCurrent->next;
   dHead->prev = NULL;
}
else if(dCurrent == dTail){
   dTail = dCurrent->prev;
   dTail->next = NULL;
}
else{
   dCurrent->next->prev = dCurrent->prev;
   dCurrent->prev->next = dCurrent->next;   
}

Вот что у меня есть для односвязного списка.Опять же, sCurrent - это узел для удаления.и sPrev = sCurrent->prev. 

if(sPrev == NULL){
   sHead = sCurrent->next;
}
else{
   sPrev->next = sCurrent->next;
}

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

Ответы [ 2 ]

3 голосов
/ 01 декабря 2011

Ваша логика двусвязных списков выглядит хорошо для меня. Меня беспокоит только то, что если dCurrent является единственным элементом в списке, то это: 

if (dCurrent == dHead){
    dHead = dCurrent->next;
    dHead->prev = NULL;
}

скорее всего попытается сослаться на нулевой указатель. (Это зависит от того, как вы создаете свой список. Но в типичном дизайне, если dCurrent является единственным узлом, тогда dCurrent->next равен NULL.)

Ваша логика с односвязными списками также выглядит хорошо для меня, в абстрактном виде, учитывая предположение, что "sPrev = sCurrent-> prev"; но я не понимаю, как это предположение может быть правильным. Если это односвязный список, то sCurrent не имеет a prev указатель.

0 голосов
/ 01 декабря 2011

Единственные проблемы, которые я вижу, это то, что ваш код не будет работать должным образом для сценариев, когда голова или хвост обновляются до NULL.

В основном, если вы удаляете единственный узел, dHead будет указывать на ноль, поэтомувам нужно поставить «охранники» вокруг последующих операторов, таких как 

dHead->prev = NULL;

примерно так 

if (dHead != NULL) {
  dHead->prev = NULL;
}

Один из способов «обойти», имея так много условных выражений, - это присвоить NIL (неtype) element.

NIL - это «узел», который заменяет NULL.Он представляет «вне части данных списка», поэтому его следующим является ВСЕГДА NIL (циклическая ссылка), а его предыдущим является ВСЕГДА NIL (циклическая ссылка).В таких случаях вы гарантируете, что NIL никогда не будет доступен вне списка, и что head-> prev == NIL и tail-> next == NIL.Таким образом, вы можете избежать многих операторов типа if (tail != null) { ... }.

При такой конструкции пустой список будет таким, где head == NIL && tail == NIL.Это значительно уменьшает количество операторов if (something == null), но у вас все еще есть один оператор if, который нужно учитывать, когда head равен NIL (после удаления чего-либо), вам необходимо установить tail в NIL для согласованности.

...