Дважды связанного списка вставки элемент алгоритма недостатки

Question

я написал двойной связанный список:

class doubled { 
private: 
    class sublink { 
    private: 
    char data[30]; 
    sublink *next_ptr; 
    sublink *previous_ptr; 
    friend doubled; 
    }; 
public: 
    sublink *first_ptr; 
    doubled(){first_ptr = NULL;}; 
    void add_item(char *item); 
    void rm_item(char *item); 
}; 

Проблема с функцией, чтобы добавить элемент в список:

void doubled::add_item(char *item){ 
    sublink *new_data; 
    sublink *n_insert; 
    sublink *p_insert; 
    new_data = new sublink; 
    n_insert = new sublink; 
    p_insert = new sublink; 

    if(first_ptr == NULL){ 
    strcpy(new_data->data, item); 
    new_data->previous_ptr = NULL; 
    new_data->next_ptr = first_ptr; 
    first_ptr = new_data; 
    } else { 
    strcpy(new_data->data, item); 
    n_insert = first_ptr; 
    while(1){ 
     n_insert = n_insert->next_ptr; 

     if(n_insert == NULL) 
     break; 

     if(strcmp(n_insert->data, new_data->data) >= 0){ 
     new_data->next_ptr = n_insert; 
     n_insert->previous_ptr = new_data; 
     } 
    } 
    p_insert = first_ptr; 
    while(1){ 
     p_insert = p_insert->next_ptr; 

     if(p_insert == NULL) 
     break; 

     if((strcmp(p_insert->data, new_data->data)) < 0){ 
     new_data->previous_ptr = p_insert; 
     p_insert->next_ptr = new_data; 
     } 
    } 
    } 

    std::cout << first_ptr->data << '\n'; 
    std::cout << new_data->data << '\n'; 
    if(new_data->next_ptr != NULL) 
    std::cout << new_data->next_ptr->data << '\n'; 
} 

Введенный выше код вставляет данный элемент в список в алфавитном порядке.

Программа выводит first_ptr->data и new_data->data, но не выводит на new_data->next_ptr->data, ни first_ptr->next_ptr->data. Таким образом, утверждение if(new_data->next_ptr != NULL) всегда верно и не должно быть.

У кого-нибудь есть проблемы с этой программой?

Answer 1

Возможно, вы получили от забывания установить предыдущий или следующий ptr в NULL.

Здесь я установил логику немного и избавился от Segfault (я пытался комментарии, как лучше всего, как я мог о том, что каждый случай проверяется есть):

#include <iostream> 
#include <string.h> 

class doubled 
{ 
private: 
    class sublink 
    { 
    private: 
     char data[30]; 
     sublink *next_ptr; 
     sublink *previous_ptr; 
     friend doubled; 
    }; 

public: 
    sublink *first_ptr; 
    doubled(){first_ptr = NULL;}; 
    void add_item(char *item); 
    void rm_item(char *item); 
}; 

void doubled::add_item(char *item) 
{ 
    sublink *new_data; 
    new_data = new sublink; 

    strcpy(new_data->data, item); 

    // empty list case 
    if(first_ptr == NULL) 
    { 
     // Only item in the list, I have no next or previous element 
     new_data->previous_ptr = NULL; 
     new_data->next_ptr = NULL; 

     // Make the list point to this element 
     first_ptr = new_data; 
    } 
    else 
    { 
     sublink* iter; 
     iter = first_ptr; 

     // 1 element list 
     if(iter->next_ptr == NULL) 
     { 
      // I'm after the first and only node 
      if(strcmp(iter->data, new_data->data) <= 0) 
      { 
       iter->next_ptr = new_data; 
       new_data->previous_ptr = iter; 
       new_data->next_ptr = NULL; 
      } 
      // I'm before the first and only node and thefore I become the new first 
      else 
      { 
       iter->previous_ptr = new_data; 
       new_data->next_ptr = iter; 
       first_ptr = iter; 
      } 
     } 
     // 2+ element list 
     else 
     { 
      // this is never null the first time because empty list case is take care of above 
      while(iter != NULL) 
      { 
       // Should I be inserted before the current node? 
       if(strcmp(iter->data, new_data->data) >= 0) 
       { 
        // first node case 
        if(iter->previous_ptr == NULL) 
        { 
         new_data->previous_ptr = NULL; 
         new_data->next_ptr = iter; 
         iter->previous_ptr = new_data; 
         first_ptr = new_data; 

        } 
        // intermediate node case 
        else if(iter->next_ptr != NULL) 
        { 
         iter->previous_ptr->next_ptr = new_data; 
         new_data->previous_ptr = iter->previous_ptr; 
         new_data->next_ptr = iter; 
         iter->previous_ptr = new_data; 
        } 
        // last node case 
        else 
        { 
         iter->next_ptr = new_data; 
         new_data->previous_ptr = iter; 
         new_data->next_ptr = NULL; 
        } 

        break; 
       } 

       // Move to next node 
       iter = iter->next_ptr; 
      } 
     } 
    } 

    // Print the list 
    std::cout << "List: " << std::endl; 
    sublink* printer = first_ptr; 
    while(printer != NULL) 
    { 
     std::cout << '\t' << printer->data << std::endl; 

     printer = printer->next_ptr; 
    } 
    std::cout << std::endl; 
} 

int main(int argc, char* argv[]) 
{ 
    doubled d; 

    char item[30] = "bla bla bla\0"; 
    char item2[30] = "meh\0"; 
    char item3[30] = "ahhhhhhhh\0"; 
    char item4[30] = "dayummmmm\0"; 
    d.add_item(item); 
    d.add_item(item2); 
    d.add_item(item3); 
    d.add_item(item4); 

    std::cin.get(); 
    return 0; 
} 

Вы можете увидеть результат здесь: http://ideone.com/EAzsPZ