Sorting Nodes in a Linked List

[Shuruki]

as the title says, I need to sort the Linked list from highest to lowest or in this case. The highest Bribe gets the higher priority on the list. I have looked all over the internet and have found some pretty decent examples but I still don't truly understand how to sort it. I think from looking at so many examples I have confused myself even more. I was reading about using Doubly Linked list but I don't even know if were allowed to use that. Either way, I still don't know how to do it. If someone can forward me to a good example or help me on my specific case, it would be great. At this point, I might just turn it in incomplete, its been very frustrating. I rather just study for my Calculus Exam coming up, instead of stressing over this.

1. The program runs perfectly at the moment. It prints out the list but does not sort it.
2. I've also need someone to tell me if I am deleting the allocated memory correctly in the deconstructor.


Header File

#include <iostream>

#ifndef PERSON_H
#define PERSON_H

struct PersonRec;

class PersonList {

public:
	PersonList();
	~PersonList();
	void ViewList();
	void AddToList();

private:
//I believe I have all the necessary helper functions.
	PersonRec* head;
	bool IsEmpty();
	void InsertBefore(PersonRec*&, int&);
	PersonRec PrevPtr(PersonRec*); // This should be assisting or being called on InsertBefore Function. I also have no idea if I should make it a "Int" or "PersonList" function. 


//Wouldn't it have been easier if I just simply made a "PersonRec* prev;" on here instead of a function? just like head?

};
#endif 

Implementation File

#include "personlist.h"
#include <iostream>
#include <string>

using namespace std;


struct PersonRec
{
	int bribe;
	char name[20];
	PersonRec *link;
};

PersonList::PersonList()
{
	head = NULL;
}
PersonList::~PersonList()
{
	delete head; //I'm also not sure if I am deleting the allocated memory correctly. Link/Head/Temp/N are all pointers, do I delete all of them? .

}
void PersonList::ViewList()
{
	
	
	PersonRec* temp = new PersonRec;
	

	if (IsEmpty())
	{
		cout << "The List is Empty\n" << endl;
	}
	else
	{
		cout << "# Name Contribution " << endl;
		cout << "====================================== \n";
		temp = head;
		while (temp != NULL)
		{
			cout << temp->name << " $" << temp->bribe << endl;
			temp = temp->link;

		}

	}


}
void PersonList::AddToList()
{
	char aName[20];
	int aBribe;
	cout << "\nEnter the person's name: ";
	cin.getline(aName, 20);
	cout << "\nEnter the person's contribution: ";
	cin >> aBribe;

	PersonRec *n = new PersonRec;
	PersonRec *temp = NULL;

	n->link = NULL;
	n->bribe = aBribe;
	strcpy_s(n->name, aName);

	if (IsEmpty())
	{
		head = n;
	}
	else
	{
		
		temp = head;
		while (temp->link != NULL)
		{
			temp = temp->link;
		}
		temp->link = n;
	}
	

}
bool PersonList::IsEmpty()
{

	if (head == NULL)
		return true;
	else
		return false;
}
void PersonList::InsertBefore(PersonRec *&head, int &money)
{
// my embarrassing fail attempt . I know there should be a validation. Should the validation be here? or in the "AddtoList" function?
//I've seen so many examples, at this point I am really confused. So please, have mercy.
	head = NULL;

	PersonRec *n;

	n = new PersonRec;

	n->bribe = money;
	n->link = head;
	head = n;

	
	
}

PersonRec PersonList::PrevPtr(PersonRec *n)
{
	
	/*This function returns a pointer to the node before the one pointed to by currPtr.
	This assumes the list is not empty and that currPtr does not point to the first node.*/

}

Test.cpp (If you guys want to run the entire program)

#include "personlist.h"
#include <iostream>
using namespace std;

int displayMenu(void);
void processChoice(int, PersonList&);

int main()
{
	int num;
	PersonList myList;
	do
	{
		num = displayMenu();
		if (num != 3)
			processChoice(num, myList);
	} while (num != 3);
	return 0;
}

int displayMenu(void)
{
	int choice;
	cout << "\nMenu\n";
	cout << "==============================\n\n";
	cout << "1. Add student to waiting list\n";
	cout << "2. View waiting list\n";
	cout << "3. Exit program\n\n";
	cout << "Please enter choice: ";
	cin >> choice;
	cin.ignore();
	return choice;
}

void processChoice(int choice, PersonList& p)
{
	switch (choice)
	{
	case 1: p.AddToList();
		break;
	case 2: p.ViewList();
		break;
	}
}

[kbw]

You could start by having a sort method on PersonList, a Bubble Sort is a reasonable place to start. Make a start and someone on the forum can help when you're stuck.

Also, as you keep needing to get to the end of your linked list, it may be worth holding a pointer to the last item, tail, to save you walking to the end each time.

[Shuruki]

Thanks for the reply kbw,

I won't be able to add a Private function for sorting :( . He gave us a specific list to choose from. None are described to be a function for sorting. From what I believe, he just wants us to validate inside "AddtoList" Then Call InsertBefore OR InsertAfter functions both must have two parameters. If the Bribe is higher then the current "head" then InsertBefore but if its lower, then you simply keep checking each upcoming node and just insert the Bribe into the list. Easier said than done though haha.


Oh okay, I understand what you're saying here. I'll take note of it, because that would be helpful.


I'll post my attempt tomorrow, 12am over here, and have a huge headache

[kbw]

I won't be able to add a Private function for sorting :( . He gave us a specific list to choose from.

Teachers ...

An alternative way to do the sort, is to insert the values in sorted order to begin with. That's called an insertion sort.

As it happens, that's what PersonList::InsertBefore is for. So PersonList::AddToList should search for the insertion point, and call PersonList::InsertBefore to do the insertion.

Once you start implementing PersonList::InsertBefore, you're expected to need PersonList::PrevPtr.

BTW, why does PersonList::ViewList() create a new node? It should just traverse the existing linked list without chaning it or creating anything.

[Shuruki]

PersonList::PrevPtr I noticed I put the wrong info on my comments haha. I was all trying to make sense of it, I was so confused.


I might be wrong here, but this is how it made sense to me. The reason PersonList::ViewList() has a new node is because when the user decides to Display the list, I don't want the List to be deleted after its displayed. That way, if the user decides to input more names/bribes, and displays the list once again. All the previous names that were displayed the first time are still on the list. So passing the values from the previous node to the new node saves it from being deleted.

[Shuruki]

This is my attempt on implementing PrevPtr Functions. I believe I have it right...maybe...haha

PersonRec PersonList::PrevPtr(PersonRec *n)
{
//I'm having second thoughs, does this function need a parameter? because
//PersonRec *head is a Private function.

	n = new PersonRec;
	PersonRec *temp1;
	PersonRec *temp2;
	/*This function returns a pointer to the node before the one pointed to by currPtr.
	This assumes the list is not empty and that currPtr does not point to the first node.*/
	if (IsEmpty())
	{
		head = n; // Not to sure about this, I just made this condition up.
	}
	else
	{
		temp2 = n;
		while (temp2->link != NULL)
			temp2 = temp2->link;
		temp2->link = temp1;

		return *temp2->link;
	}
	
}

[Shuruki]

Not sure if I have the Parameters correctly, and I haven't used PrevPtr inside InsertBefore

void PersonList::InsertBefore(PersonRec *node, PersonRec *newNode)
{
	PersonRec *current;

	if (IsEmpty() || (node->bribe) >= newNode->bribe)
	{
		newNode->link = node;
		node = newNode;
	}
	else
	{
		current = node;
		while (current->link != NULL &&
			current->link->bribe < newNode->bribe)
		{
			current = current->link;
		}
		newNode->link = current->link;
		current->link = newNode;
	}
	
}