Sign in to follow this  
Twinsen2

Link List Sort not working.

Recommended Posts

Twinsen2    110
Hey all. Ur all proberely gettn sick of me posting about errors with linked lists, well i'm please 2 announce that this is the last 1, with the help from this forum i have successfully created a functional linked list and i thank every1 who help me along the way. okay. I need to be able to sort the elements by total kills in the list and i thought to myself that i could use a bubble sort....okay...after a few more minutes thinking i figured that when inserting the new element i can check the nodes already inplace and compare them and insert the new element in the rigth place. No heres my insert function...lol, uve proberly seen it 1000 times b4 but newat:
void Node::Insert(Node * newNode)						//insert function,  where the pointerNewNode is passed as a parramater.
{

	// If there is no elements in the list then:
	if(!itsNext)										
	{	
		itsNext = newNode;								// the reason we need this peice of code is that because when we 
														// are placeing an object in the list we want to insert it in order
														// and as you can see below we initalize a few temporary varibles
														// that go and get other soldiers kills.
														// if there is no soldiers and these local varibles are initalized
														// then the program will crash because the data doesnt exist.
														// so by using this simple if statement we can check if there is a next node
														// and if there isnt then create one, and omit the sorting code below
														// because this will be the first node.
	}
	else												// If this new node isnt the first then:
	{
		//Sorting Code local varibles;
		int NextSoldiersKills = itsNext->GetSoldier()->GetKills();	// Stores the next soldiers kills
		int NewKills = newNode->GetSoldier()->GetKills();			// gets the current soldiers kills
		int ThisNodeKills = itsSoldier->GetKills();					// stroes the new soldiers kills

		// The above local varibles are initalized so that they may go into the for loop below,
		// This will insert the soldier in a sorted position and there is no need for any bubble sort functions.
		// in the end this saves alot of time, you think a little at the start and...save alot of time ;).

		if(NewKills > ThisNodeKills && NewKills < NextSoldiersKills) // if the current soldiers kills, is greater than the new soldiers kills and 
																	 // the current soldiers kills is lower than the next soldiers kills then:
		{
			
			newNode->setNext(itsNext);								// set the newnode to next
			itsNext = newNode;										// initalize its next to newNode;
		}
		else
		{
			itsNext->Insert(newNode);								//If the soldier doesnt need to be ranked and is allready in order then:
																	// insert the object into the current position
														
		}
	}//end if
}

okay the nested if statement if i'm right should work, it checks the next soldier, current soldier and new soldier, this is a single linked list btw. Okay the problem is that for some reason it doesnt sort them in order. and i cant figure out the problem. thankz once again all, 4 ur help.

Share this post


Link to post
Share on other sites
ToohrVyk    1595
In a list with one node, a second node will always be inserted at the end because of your initial if clause.

EDIT: To insert in a sorted list, this code works:


void List::Insert( Node* inserted ) {

Node** from = &first;

while( (*from) &&
(*from)->value < inserted->value ) {

from = &((*from)->next);
}

inserted->next = (*from);
(*from) = inserted;
}

Share this post


Link to post
Share on other sites
Twinsen2    110
Quote:
Original post by ToohrVyk
In a list with one node, a second node will always be inserted at the end because of your initial if clause.

EDIT: To insert in a sorted list, this code works:

*** Source Snippet Removed ***


yeah thankz 4 that.

i have actually just started linked lists, and dont really understand ur code.

could some1 please explain this to me as i havent seen this before, and should that code replace my whole insert function??

thankz again 4 ur help man :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this