Удалить указатель в двух списках

Question

У меня есть массив связанных списков, каждый индекс массива содержит связанный список.

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

Так, например. В моем массиве 500 индексов. Я ввожу один узел из индекса 1 и один узел в индекс 2. Когда я печатаю связанный список по индексу 1, он печатает только один узел. Однако, когда я печатаю связанный список, который содержит точный порядок ввода узла, он будет печатать оба из них, чтобы я их ввел.

Я реализовал это с помощью этого кода

class CHash{ 

public: 
    CHash(){ 
     for(int i = 0; i < 500 ;i++){ 
      holder[i] = NULL; 
     } 
     first = NULL; 
     last = NULL; 
    }; 
    void insert(string key , string value){ 
     size_t num = index(key); 
     Node *tmp; 
     if(holder[num] == NULL){ 
      tmp = new Node(key , value , NULL); 
      holder[num] = tmp; 
     }else{ 
      tmp = new Node(key, value , holder[num]); 
      holder[num] = tmp; 
     } 
     if(first == NULL){ 
      tmp -> nextNode = NULL; 
      tmp -> prevNode = NULL; 
      first = tmp; 
      last = tmp; 
     }else{ 
      tmp -> prevNode = last; 
      last -> nextNode = tmp; 
      last = tmp; 
     } 
    } 
    void Print(size_t number){ 
     Node *tmp = holder[number]; 
     while(tmp!= NULL){ 
      cout << tmp -> value << endl; 
      tmp = tmp -> next; 
     } 
    } 
    void PrintAll(){ 
     Node *tmp = first; 
     while(tmp != NULL){ 
      cout << tmp -> value << endl; 
      tmp = tmp -> nextNode; 
     } 
    } 
    size_t index(string name){ 
     return name.length(); 
    } 
    void de(string val){ 
     size_t num = index(val); 
     if(holder[num] == NULL){ 
      return; 
     } 
     Node *tmp = holder[num]; 
     Node *help; 
     Node *help1; 
     while(tmp != NULL){ 
      if(tmp -> key == val){ 
       Node *temp = tmp; 
       if(tmp -> prevNode != NULL) 
        help = tmp -> prevNode; 
       else 
          help = NULL; 
       if(tmp -> nextNode != NULL) 
        help1 = tmp -> nextNode; 
       else 
          help1 = NULL; 
       if(tmp -> next != NULL){ 
        tmp = tmp -> next; 
        tmp -> nextNode = help1; 
        tmp -> prevNode = help; 
       } 
       else 
        tmp = NULL; 

       delete temp; 
       return ; 
      } 
      tmp = tmp -> next; 
     } 
    } 

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

Пример использования.

CHash one; 
    one.insert("two","cauko"); 
    one.insert("tuk","hello"); 
    one.insert("three","hrello"); 
    one.Print(3) // should print "hello" , "cauko" 
    one.PrintAll() // should print "cauko" , "hello" , "hrello" 
    one.de("tuk"); 
    one.Print(3); // should print only "cauko" 
    one.PrintAll(); // should print "cauko" , "hrello" 

Где я совершил ошибку?

Answer 1

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

Код, указанный ниже для de предполагает, что связанный список с использованием ->next не имеет соответствующего prev, так как на данном этапе информации не имеется.

void deleteVal(string val){ 
    size_t num = index(val); 
    if(holder[num] == NULL){ 
     return; 
    } 

    /* Find the key first */ 
    Node* tmp = holder[num]; 
    Node *prev = NULL; 
    while (tmp != NULL) { 
     if (tmp->key == val) { 
      break; 
     } 
     prev = tmp; 
     tmp = tmp->next; 
    } 

    if (tmp->key != val) { 
     //key not found 
     return; 
    } 

    /* remove the element from the global linked list */ 
    if (tmp->prevNode) { 
     tmp->prevNode->nextNode = tmp->nextNode; 
    } 
    if (tmp->nextNode) { 
     tmp->nextNode->prevNode = tmp->prevNode; 
    } 

    if (first == tmp) { 
     first = tmp->nextNode; 
    } 
    if (last == tmp) { 
     last = tmp->prevNode; 
    } 

    /* Now remove the element from the linked list corresponding to index */ 
    if (holder[num] == tmp) { 
     holder[num] = tmp->next; 
    } else { 
     prev->next = tmp->next; 
    } 
//uncomment if the ->prev member exists in your class 
//  if (tmp->next) tmp->next->prev = tmp->prev; 
    /* Delete. */ 
    delete tmp; //maybe tmp->next = tmp->nextNode = NULL before depending on your destructor 
} 

Основная проблема заключалась в том, что вы смешивания двух связанных списков здесь в вашем коде:

  if(tmp -> next != NULL){ 
       tmp = tmp -> next; 
       tmp -> nextNode = help1; 
       tmp -> prevNode = help; 
      } 

две связанные списки не имеют ничего общего друг с другом.

Answer 2

У меня есть массив связанных списков, каждый индекс массива содержит связанный список.

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

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

struct Node { 
    // ... 
    std::shared_ptr<Node> prev_node; 
    std::shared_ptr<Node> next_node; 
}; 

также посмотреть на What is the Rule of Three.

Answer 3

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

В частности, проблема здесь:

if(tmp -> next != NULL){ 
    tmp = tmp -> next; 
    tmp -> nextNode = help1; 
    tmp -> prevNode = help; 
} 
else 
tmp = NULL; 

Вы полностью пренебрегаем узел которого next указывает на tmp. И вместо соединения двух узлов друг с другом с помощью help и help1 (ваши имена переменных ужасны), вы соединяете их как с несвязанным узлом.