Linked List and Dynamic Array Problem

[daniel88]

Hi guys! I am currently having trouble in the final stages of an assignment which involves linked lists and dynamic arrays. The assignment involves adding books to a library. This means that each record has a title and one or more authors. I have worked out what I think was the hard part, which was how to add the title and authors. However, I have run into a problem when it comes time to print the books by book title. The specs require that when all the books are printed they are printed by book sorted in alphabetical order. I am not sure how best to do this. Should I sort the linked list or should I sort them as I add them and if so how do I do this?

Here is the header file:

class Library{

public:
	Library();
	/*Library(const Library &other);
	Library &operator=(const Library &other);
	~Library(); */
	void add(string title, string authors[], int nAuthors);
	void print() const;
	void printByAuthor(string author) const;
	
private:
	struct book
	{
		string title;
		string *author;
		book *link;
		int numAuthors;
	} *p;
};

Please note: the copy constructor and operator overload form part of a bonus, which I am not concerned with at this stage. My function to add a book is as follows:

void Library::add(string title, string authors[], int nAuthors)
{
	// new node required
	book *q, *t;
	
	if (p == NULL)
	{
		p = new book;
		p->title = title;
		p->author = new string[nAuthors];
		
		for (int i = 0; i < nAuthors; i++)
			p->author[i] = authors[i];
		
		p->link = NULL;
		p->numAuthors = nAuthors;
   }
   else
	{
		q = p;
		while (q->link != NULL)
			q = q->link;
			
		t = new book;
		t->title = title;
		t->author = new string[nAuthors];
		
		for (int i = 0; i < nAuthors; i++)
			t->author[i] = authors[i];
			
		t->link = NULL;
		q->link = t;
		t->numAuthors = nAuthors;
	}
}

Finally, as it currently stands this my print function:

void Library::print() const
{
	book *q;
	
	for (q = p; q != NULL; q = q->link)
	{
		cout << "Title: " << q->title << endl;
		
		for (int i = 0; i < q->numAuthors; i++)
		{
			cout << "Author " << i + 1 << ": " << q->author[i] << endl;
		}
		
		
cout << endl;
	}


}

I really feel like I am close, and that this problem can be rectified. Any help you guys might be able to offer would be greatly appreciated.

Cheers,

Daniel

[Ancient Dragon]

If the list only needs to be sorted by book title then just insert new nodes in sorted order. I didn't test this but it should work something like below. You have to save a copy of the previous link when iterating through the list so that the program can back up one node. If you had a circular, 2-way linked list you wouldn't need to do that.

book* save = p;
q = p;
while (q->link != NULL && q->title < title)
{
      save = q;
      q = q->link;
}
t = new book;
t->title = title;
t->author = new string[nAuthors];
		
for (int i = 0; i < nAuthors; i++)
    t->author[i] = authors[i];
t->numAuthors = nAuthors;

save->link = t;			
t->link = q;

[Sorrofix]

Should I sort the linked list or should I sort them as I add them and if so how do I do this?

Sort them as you add them. It'll be much simpler (and much more efficient) if you do it this way. Accomplishing it involves using the strings' overloaded '<' and '>' operators to figure out the alphabetical order. For example, the expression string1 < string2 will return true if string1 has a higher alphabetical precedence than string2.

You can use this method to find out where you need to insert the book (node). I'll leave implementing how you add a node in the middle of the linked list an exercise for you. If you're unsure, draw out a flowchart on a piece of paper to help understand what needs to be done. Good luck, and have fun. :)

Edit: shoot, a minute too late. Oh well.

[daniel88]

Hi Ancient Dragon! Thanks so much for your quick reply (and also to Sorrofix!). I find the linked lists a little tricky when it comes to tracing what equals what. Could you add some comments to your code just so that I can get an idea of what is happening from the point of view of sequence of events as I am having problems working out where exactly I should insert the code. Thanks in advance.
Kind regards,

Daniel

[Ancient Dragon]

The code I posted is just an extraction of your post, after the else statement that begins on line 18. I added line numbers to your code so just refer to your original post.

[daniel88]

Sorry Ancient Dragon, but the printing function does not seem to be working properly now. I was just wondering whether something was perhaps going wrong with the process of assigning NULL to the last node in the list so that the print function can find the end of the list. Your ongoing help is very much appreciated.

Cheers,

Daniel

[Ancient Dragon]

as I said, the code I posted is untested. Here is correction which works. I removed the array of authors for simplicity, so you will have to add them back into the code.

void add(string title, string author, int nAuthors)
    {
	    // new node required
        book *q = NULL, *t = NULL;
	
        if (p == NULL)
        {
            p = new book;
            p->title = title;
            p->author = author;
		
            p->link = NULL;
            p->numAuthors = nAuthors;
        }
        else
        {
            book* save = NULL;
            q = p;
            while (q != NULL && q->title < title)
            {
                save = q;
                q = q->link;
            }
            t = new book;
            t->title = title;
            t->author = author;
            t->link = NULL;	
            t->numAuthors = nAuthors;
            if(save == NULL)
            {
                // add new book at the beginning of the
                // linked list
                t->link = p;
                p = t;
            }
            else
            {
                // add new book somewhere in the middle 
                // of the linked list
                save->link = t;			
                t->link = q;
            }

        }
     }

[daniel88]

Ancient Dragon, you are a genius!!! Thanks very mucy, it really helped a lot. After a while you can lose hope with the linked lists I find so a helpful nudge in the right direction can make all the difference. Anyway, thanks again.

Kind regards,

Daniel