sorting a linked list?

[dan_e6]

hey guys. i have a linked list set out like this

struct node
          {
           string bookTitle;
           string *authors;
           int nAuthors;
           node *next;
          };
          
          node *start_ptr;

and i need to sort the linked list based on bookTitle alphabetically. how would i go about doing this?

[n1337]

Well....first you need to decide on a sorting algorithm. There are TONS of different ways to sort, I saw a post about a bubble sort, which is a very easy-to-write but inefficient sort, you could do some research about insertion sorts, quick sorts, merge sorts...Like I said, there are tons of sorts. You need to weigh the advantages and disadvantages of each to meet your needs (i.e. speed and efficiency in terms of memory versus ease of writing). I don't know if you have discussed order notation in your CS studies yet...if not then maybe its not important, just choose an easy sorting algorithm...

Secondly, you will need a comparison function...I'm not familiar with standard string functions for C++ (I tended to just implement them as I needed in C), but I would imagine there is a strcmp function somewhere...(you can likely use this to compare the authors)...in any case, strcmp is not difficult to implement.

It might be a useful exercise to think about the type of data you will be comparing...in this case its just an authors name, so you probably don't need to worry too much...(I just mentioned this because the strcmp function, depending on how it is implemented, takes time, which is sometimes neglected, and in certain cases, it would be a useful exercise to take this into account when choosing and optimizing the sort..I'm sorry I don't know if I just made any sense...getting tired...)

Then I would suggest that the actual sorting be done by manipulating pointers to save space...just make sure you don't have any memory leaks!!!

Sorry if that is kind of vague...but I'm starting to get tired, no time to write code examples...should lead you in a direction to start.

[Ancient Dragon]

The nodes might be easier to sort if you put the data in another structure

struct data
{
   string bookTitle;
   vector<string> authors;
};
struct node
{
    struct data* pData;
    node *next;
};
          
node *start_ptr

Now when a swap needs to take place all you have to do is swap the data pointers and leave all the node pointers alone.

Also, don't use a pointer to a std::string object. It doesn't save you a thing, and actually causes more trouble than its worth. If you want an array of authors then use a vector. And if you use vectors you don't need int nAuthors; because the vector class keeps track of that value.

[dan_e6]

i know about vectors but we cant use anything from STL which includes vectors :(

[Ancient Dragon]

>>we cant use anything from STL
Ok, in that case you can't use std::string objects either.

struct data
{
   char* bookTitle;
   char **authors;
  int nAuthors;
 };
struct node
{
    struct data* pData;
    node *next;
};
          
node *start_ptr

[dan_e6]

we can use strings. forgot to mention that. lol.

[Ancient Dragon]

Ok, so now what's the problem ? I forgot. Oh yea, I remember now -- how to sort a linked list. If you know how to sort a normal array then its not all that hard to sort the linked list. With the new node class I posted all you have to swap is pData pointers.

[Ancient Dragon]

Here is a working example of one way to sort a linked list. It adds 5 nodes to the linked list then sorts the list based on book title.

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

struct data
{
   string bookTitle;
   string *authors;
   int nAuthors;

   data()
   {
       authors = 0;
       nAuthors = 0;
   }
   ~data()
   {
       if(authors)
           delete[] authors;
   }
};


struct node
{
    struct data* pData;
    node *next;

    node()
    {
        next = 0;
        pData = 0;
    }
    ~node()
    {
        if(pData)
            delete[] pData;
    }
};
          
node *head = NULL;

node* AddHead(data* pData)
{
    node* newNode = new node;
    newNode->pData = pData;
    newNode->next = head;
    head = newNode;
    return newNode;
}

void SortList()
// This just uses the standard bubble sort.
{
    node* i;
    node* j;
    for(i = head; i->next != NULL; i = i->next)
    {
        for(j = i->next; j != NULL; j = j->next )
        {
            if( i->pData->bookTitle > j->pData->bookTitle)
            {
                data* tmp = i->pData;
                i->pData = j->pData;
                j->pData = tmp;
            }
         }
    }
}


int main()  
{
    string names[5] = { "James", "King", "Arnold","Bellairs","Johnson" };
    struct data* pData;
    // add 5 nodes to the linked list
    for(int i = 0; i < 5; i++)
    {
        pData = new data;
        pData->bookTitle = names[i];
        AddHead(pData);
    }
    // sort them by book title
    SortList();
    // print them to the console screen
    node* curr = head;
    while(curr)
    {
        cout << curr->pData->bookTitle << "\n";
        curr = curr->next;
    }
    // delete the linked list
    curr = head;
    while(curr)
    {
        node* tmp = curr;
        curr = curr->next;
        delete tmp;
    }
    head = NULL;    
}

[dan_e6]

thanks i'll go through it :-)

what's with the data() and ~data() in the data node? im guessing these are the constructor/destructors for the structure? i didn't know you could do that with structures i thought only classes!

edit: now it is kicking up on the constructor of my Library class highlighting:

Library::Library()
{
start_ptr = NULL;
}

it highlights the { for some reason. it says "new types may not be defined in a return type".

my bad.....at the end of my class i didnt have ;
lol.

edit again: program crashed now when i try to add to the node list.

void Library::add(string title, string authors[], int nAuthors)
{
     node *temp = new node;            //store input data into temp node
     temp->pdata->bookTitle = title;
     temp->pdata->authors = new string[nAuthors];     //make enough space for all of the authors
     temp->pdata->nAuthors = nAuthors;
     
     for (int i = 0; i<nAuthors; ++i)          //store all of the authors
     {
         temp->pdata->authors[i] = authors[i];
     }
     temp->next = NULL;
     
         if (start_ptr == NULL)                //add to the linked list
        start_ptr = temp;
    else
    {
        node *p = start_ptr;
        while (p->next != NULL)
            p = p -> next;

        p->next = temp;
    }
         cout << "\n================ FINISHED STORING INFORMATION ================\n" << endl;
}

that's my add function. going through it now

[Ancient Dragon]

>> i didn't know you could do that with structures i thought only classes!
In c++ structures are almost identical to classes.

>>temp->pdata->bookTitle = title;
You forgot to allocate pdata too. temp->pdata = new data;

[dan_e6]

>> i didn't know you could do that with structures i thought only classes!
In c++ structures are almost identical to classes.

>>temp->pdata->bookTitle = title;
You forgot to allocate pdata too. temp->pdata = new data;

ahhh thanku. i totally overlooked that my bad.