Сортировка связанного списка со строками в C

Question

У меня есть структура с именем и одним узлом с именем nextName

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

Так что, если я войду в Джо Золта и Артура, я должен структурировать свой список как

Джо

Чем

Джо Золт

Чем

Артур Джо Золт

У меня проблемы с реализацией правильного Алгоритма, который установил бы указатели в правильном порядке.

Это то, что у меня есть сейчас. Temp будет именем, которое пользователь только что ввел и пытается добавить в список, namebox - это просто копия моего корня, являющаяся целым списком

 if(temp != NULL)
      {
              struct node* namebox = root;
              while (namebox!=NULL && (strcmp((namebox)->name,temp->name) <= 0))
              {
                      namebox = namebox->nextName;
                      printf("here");
                 }
                temp->nextName = namebox;
    namebox = temp;
    root = namebox;

Это работает прямо сейчас, если я ввожу такие имена, как CCC BBB, чем AAA

Я получаю обратно AAA BBB CCC, когда я печатаю

Но если я ставлю AAA BBB CCC, когда я печатаю, я получаю только CCC, он отключает предыдущее.

Edit:

Может кто-нибудь показать мне, как будет выглядеть код, я не могу его записать.

Answer 1

Когда вы вводите AAA, BBB, а затем CCC namebox, всегда, когда цикл завершается.

И тогда вы делаете:

// namebox is null
temp->nextName = namebox;
// namebox = CCC
namebox = temp;
// root = CCC
root = namebox;

Так вот почему вы получаете только CCC.

Теперь, что вам нужно сделать в этих случаях, это убедиться, что CCC добавлено в конец списка, и не изменять root.

Answer 2

if(temp != NULL)
{
    struct node* namebox = root;
    while (namebox!=NULL)
    {
        if(strcmp(namebox->Name,temp->Name) > 0) // if temp comes before this
        {
            temp->nextName = namebox->nextName;
            namebox->nextName = temp;
            //printf("here"); I'm guessing this is debugging stuff?
        }
        namebox = namebox->nextName;
    }
}

это для общей вставки, но вы должны делать особые случаи, когда вы добавляете имя и добавляете в начало списка

Answer 3

Что вы описываете это Сортировка вставки .

Когда вы вводите AAA, BBB и, наконец, CCC, namebox равно NULL, когда цикл while завершен.

Тогда, когда вы делаете temp->nextName = namebox, namebox равно NULL. После этого вы устанавливаете namebox на temp (который содержит CCC). Наконец, вы устанавливаете root на namebox, что также устанавливает CCC. Вот почему вы получаете CCC.

В вашем алгоритме вам нужно обработать случай, когда вы добавляете что-то в конец или середину списка, и не менять корень в этих случаях. На самом деле, это должно быть общим случаем. Добавление вещей в начало и конец должно быть вашими особыми случаями.