Удаление узла из дважды связанного списка

Question

Я смотрел другие темы здесь, по этой теме, но не смог использовать их для решения моей проблемы.

---

это основное определение класса узла в связанном списке:

class node { 

public: 

    // default constructor 
    node() {name = ""; prev = NULL; next = NULL;}; 

    // default overloaded 
    node(string s) {name = s; prev = NULL; next = NULL;}; 

    // item in the list 
    string name; 

    // links to prev and next node in the list 
    node * next, * prev; 

}; 

---

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

Функция для удаления узла: http://pastebin.com/HAbNRM5W

^это код, мне нужна помощь, есть слишком много, чтобы перепечатать

---

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

tmp->prev = prev; 

Я пытаюсь установить ссылку на предыдущий узел, чтобы быть правильным. случай, с которым я пытаюсь работать с аналогичными циклами if/else, - это то, является ли текущий узел последним элементом в списке. если это последний элемент (aka curr->next = NULL), то не устанавливайте связь с помощью curr->next и прекратите итерацию цикла.

любая помощь/идеи/рекомендации/обратная связь будут очень благодарны!

void linkedList::remove(string s) 
{ 
     bool found = false; 
     node * curr = getTop(), * prev = NULL; 
     node * tmp = new node(); 
     while(curr != NULL) 
     { 
       // match found, delete 
       if(curr->name == s) 
       { 
         found = true; 
         // found at top 
         if(prev == NULL) 
         { 
          node * temp = getTop(); 
          setTop(curr->next); 
          getTop()->prev = NULL; 
          delete(temp); 
         } // end if 
         else 
         { 
          // determine if last item in the list 
          if (curr->next = NULL) 
          { 
           // prev node points to next node 
           prev->next = curr->next; 
           // delete the current node 
           delete(curr); 
          } // end if 
          // if not last item in list, proceed as normal 
          else 
          { 
           // prev node points to next node 
           prev->next = curr->next; 
           // set the next node to its own name 
           tmp = prev->next; 
           // set prev-link of next node to the previous node (aka node before deleted) 
           tmp->prev = prev; 
           // delete the current node 
           delete(curr); 
          } // end else 
         } // end else 
        } // end if 

       // not found, advance pointers 
       if(!found) 
       { 
        prev = curr; 
        curr = curr->next; 
       } // end if 

       // found, exit loop 
       else curr = NULL; 
     } // end while 

     if(found) 
      cout << "Deleted " << s << endl; 
     else 
      cout << s << " Not Found "<< endl; 
} // end remove 

Answer 1

Для вашего кода я предлагаю несколько вещей. Изолируйте код, чтобы найти узел с именем, которое вы ищете. Метод remove СЛЕДУЕТ удалять только дважды связанный узел при условии, что ему задан один.

Я знаю, что ваш метод remove принимает строковый параметр, но передает это другой функции и возвращает эту функцию узлу, который вы ищете.

Это должно выглядеть примерно так:

Node *cur = find("abcd"); 
Node *prev = cur->prev; 
prev->next = cur->next; 

Node *n = cur->next; 
n->next = cur->prev; 

cur->next = NULL; //or nullptr 
cur->prev = NULL; //or nullptr 

delete cur; 

Answer 2

NULL следует заменить nullptr

if (curr->next = NULL) { ... 

То есть задание, вы хотите:

if (curr->next == nullptr) { ... 

В строке 47 I думаете, что вы говорите: если prev == nullptr, а затем не nullptr, но вы используете

prev->next = curr->next; 

Который не работает с тех пор, как предыдущий является nullptr.

Answer 3

Должно выглядеть так:

prev->next = curr->next; 
prev->next->prev = prev; 
delete (curr); 

Answer 4

Я заблудился во всех ваших различных условными.Все, что вам нужно сделать, это следующее:

void linkedList::remove(const std::string& s) 
{ 
    node* current = getTop(); // get head node 
    while (current != nullptr) // find the item you are trying to remove 
    { 
     if (current->name == s) 
     { 
      break; // when you find it, break out of the loop 
     } 
    } 

    if (current != nullptr) // if found, this will be non-null 
    { 
     if (current->prev) // if this is not the head node 
     { 
      current->prev->next = current->next; 
     } 
     else 
     { 
      // update head node 
     } 

     if (current->next) // if this is not the tail node 
     { 
      current->next->prev = current->prev; 
     } 
     else 
     { 
      // update tail node 
     } 

     // at this point, current is completely disconnected from the list 
     delete current; 
    } 
}