сортировка имен в связанном списке

Question

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

#include <iostream>
#include <string>
using namespace std;

struct node{
    string name;
    node *next;
};

node *A;

void addnode(node *&listpointer,string newname){
    node *temp;
    temp = new node;
    if (listpointer == NULL){
        temp->name = newname;
        temp->next = listpointer;
        listpointer = temp;
    }else{
        node *add;
        add = new node;
        while (true){
            if(listpointer->name > newname){
                add->name = newname;
                add->next = listpointer->next;
                break;
            }
            listpointer = listpointer->next;
        }
    }
}

int main(){

    A = NULL;
    string name1 = "bob";
    string name2 = "tod";
    string name3 = "thomas";
    string name4 = "kate";
    string name5 = "alex";
    string name6 = "jimmy";
    addnode(A,name1);
    addnode(A,name2);
    addnode(A,name3);
    addnode(A,name4);
    addnode(A,name5);
    addnode(A,name6);

    while(true){
        if(A == NULL){break;}
        cout<< "name is: " << A->name << endl;
        A = A->next;
    }

    return 0;

}

Answer 1

Вы пытаетесь разыменовать нулевой указатель в addnode. В случае, если listpointer->name > newname никогда не соответствует истине, listpointer в конечном итоге будет установлен в NULL, а затем попытается снова разыменоваться в следующем listpointer->name > newname сравнении.

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

Answer 2

Я считаю, что ошибка в том, что вы думаете:

if (listpointer == NULL){
    temp->name = newname;
    temp->next = listpointer;
    listpointer = temp;
}

гарантирует, что listpointer никогда не будет NULL позже. Однако это не так, например:

void addnode(node *&listpointer,string newname){
   node *temp;
    temp = new node;
    if (listpointer == NULL){
        temp->name = newname;
        temp->next = listpointer;
        listpointer = temp;
    }else{
        node *add;
        add = new node;
        while (true){
            if( (listpointer) == NULL){
            std:cout << "oops (listpointer) == NULL)";
            }

            if(listpointer->name > newname){
                add->name = newname;
                add->next = listpointer->next;
                break;
            }
            listpointer = listpointer->next;
        }
    }
}

Распечатает «oops», затем segfault, поскольку lispointer равен NULL, а использование -> для NULL вызовет segfault. Это происходит потому, что список указателей while (true) в конце концов достигает конца и устанавливается в NULL. Затем вы получаете segfault.

Я думаю, что лучшей идеей было бы сделать что-то вроде:

bool has_inserted;
while ( listpointer != NULL){
  if(listpointer->name > newname){
     add->name = newname;
     add->next = listpointer->next;
     has_inserted = true;
     break;
  }
  listpointer = listpointer->next;
}
if(has_inserted == false){
//insert at end of list
}

Также этот код теряет память, так как вы не удаляете вещи, созданные вами с помощью new. Возможно, вы захотите запустить этот (и другой код) с valgrind, чтобы понять, что я имею в виду.

Answer 3

Я сделал некоторые изменения в вашем коде:

1 - предотвращает утечку памяти, удаляя temp из вашего кода.

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

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

Итак, я исправил ошибки и ваш код теперь в порядке.

Помните, что ваш main () должен быть настроен так, чтобы не изменять указатель списка (A) при печати его элементов. Если это так, вы потеряете контроль над своим списком после его печати и не сможете больше получать доступ к его узлам или удалять их. Если в этом тесте вас это не волнует, просто забудьте об этом.

void addnode(node *&listpointer,string newname){
    node *add,
         *last,
         *current;

    add = new node;
    add->name = newname;

    if (listpointer == NULL){
        add->next = listpointer;
        listpointer = add;
    }else{
        current = listpointer;
        last    = listpointer;
        while (current && current->name < newname){
            last = current;
            current = current->next;
        }

        if (current == listpointer){
            /* Insert before 1st node */
            add->next = listpointer;
            listpointer = add;
        }
        else{
            /* Insert between last and current 
               or at the end of the list */
            last->next = add;
            add->next = current;
        }
    }
}