Linked List Sorting with Strings In C

Question

I have a struct, with a Name and a single Node called nextName

It's a Singly Linked list, and my task is to create the list, based on alphabetical order of the strings.

So iff i enter Joe Zolt and Arthur i should get my list structured as

Joe

Than

Joe Zolt

Than

Arthur Joe Zolt

I'm having trouble implementing the correct Algorithm, which would put the pointers in the right order.

This is What I have as of Now. Temp would be the name the user just entered and is trying to put into the list, namebox is just a copy of my root, being the whole list

 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;

This Works right now, if i enter names like CCC BBB than AAA

I Get Back AAA BBB CCC when i print

But if i put AAA BBB CCC , When i print i only get CCC, it cuts the previous off.

Edit:

Can someone show me what the code would look like, i cant get it down.

Answer 1

When you enter AAA, BBB and then CCC namebox is always NULL when while loop finishes.

And then you are doing:

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

So that's why you are getting only CCC.

Now, what you need to do in those cases is make sure CCC is added at the end of the list and do not change root.

Answer 2

What you're describing is Insertion Sort.

When you enter AAA, BBB, and finally CCC, namebox is NULL when the while loop is done.

Then when you do temp->nextName = namebox, namebox is NULL. After that you set namebox to temp (which holds CCC). Finally you set root to namebox which sets it to CCC also. This is why you get CCC.

In your algorithm you need to handle the case where you're adding something at the end or the middle of the list and not change root in those cases. In fact, this should be the general case. Adding things at the front and end should be your special cases.

Answer 3

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;
    }
}

this is for general insertion but you have to do special cases when you add the first name and add to the beginning of the list