Sorting a Doubly LinkedList

Alphabetically sorting names.

Page 1 of 1

10 Replies - 2950 Views - Last Post: 06 September 2009 - 09:31 PM Rate Topic: -----

#1 array  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 08-April 09

Sorting a Doubly LinkedList

Posted 05 September 2009 - 12:04 PM

Trying to do it through a loop that traverses through the list.

In the loop im feeding the head node into a sorting function that I have defined and then im using strcmp to find out which name in the node should come first. We Find that name and print that node.

But Their is a problem, the node that is the least_found_node will be ALWAYS be the least_found_node...Is removing it the only option?
I cant assign it to NULL b/c the loop will end terminate.

The two functions that are most important to me now are defined as follows: I have tried my best to do what I think is right for the sorting function.

void list::displayByName(ostream& out) const
{
	node *current_node  = headByName;
	node *returned_node = NULL;

	while ( current_node != NULL )
	{
		current_node = sort( current_node );
		out << current_node->item.getName() << endl;
	}
}



list::node * const list::sort( node *given_node ) const
{
	node *least_found_node = NULL;
	node *current_node	   = given_node->nextByName;

	while ( current_node && current_node != given_node )
	{
		if ( strcmp( current_node->item.getName(), given_node->item.getName() ) < 0 )
		{
	  // Is this node smaller than the smallest node we know of?
			if ( least_found_node == NULL || 
			   ( strcmp( least_found_node->item.getName(), current_node->item.getName() ) > 0 ) )
			{
		 // we found a better node!
				least_found_node = current_node;
			}
		}
		current_node = current_node->nextByName;
	}
	return least_found_node; 
}



And I started to develop my nodes here: BTW, the winery below is a class object type completely seperate from the class list and the struct node.
void list::insert(const winery& winery)
{
	node *current_node = new node( winery );

	if ( headByName == NULL )
	{
		headByName   = current_node;
		headByRating = current_node;
		tail		 = headByName;
		current_node->prev = current_node;
	}
	else
	{
		current_node->prev = tail;
		tail->nextByName   = current_node;
	}

	tail = current_node;
	current_node = NULL;
}



I think its correct in that function above. Could I possible get a way with sorting it their? One question at a time right? hehe.

A correct working remove function. ( I can remove the tail and head with no crash )
bool list::remove (const char * const name)
{
	node *current = headByName;
	
	while ( current != NULL )
	{
		if ( strcmp( name, current->item.getName() ) != 0 )  
		current = current->nextByName;
		else
		{//this must be the one.
			if ( current == headByName )
			{
				current = current->nextByName;
				headByName->prev = NULL;
				return true;
			}
			else if ( current == tail )
			{
				tail = tail->prev;
				tail->nextByName = NULL;
				return true;
			}
			else
			{
				current->prev->nextByName = current->nextByName;
				current->nextByName->prev = current->prev;
				return true;
			}
		}
	}	
	return false;
}



Skipping over the node is a possibility. But I have tried calling this function where appropriate (lol) and i get a crash because of the second assignment in the function above. current = head.
Anyways below are my varaibles that I am working with:

public list
{
		 ...
	void insert(const winery& winery);
	void displayByName(ostream& out) const;
}
private:
	struct node
	{
		node(const winery& winery);	 // constructor
		winery item;
		node * prev;
		node * nextByName;
		node * nextByRating;
	};

	winery * const sort(node*) const;
	node * headByName;
	node * headByRating;
	node * tail;
};


Any help is appreciated. Thanks very much =)

This post has been edited by array: 05 September 2009 - 04:40 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Sorting a Doubly LinkedList

#2 array  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 08-April 09

Re: Sorting a Doubly LinkedList

Posted 05 September 2009 - 08:19 PM

well that didnt work ;x

This post has been edited by array: 05 September 2009 - 08:26 PM

Was This Post Helpful? 0
  • +
  • -

#3 Guest_c.user*


Reputation:

Re: Sorting a Doubly LinkedList

Posted 05 September 2009 - 09:29 PM

struct data {
	char *p;
	int a, b, c;
	void *anyPointer;
};

struct node {
	struct data *pData;
	struct node *pNext, *pPrev;
};

typedef struct list {
	struct node *pHead, *pTail;
	unsigned nelems;
} List;



you can have one list and move data structures while the sorting between nodes

also you can create temporary array for those pointers, sort them and your list will not be changed while the sorting
Was This Post Helpful? 0

#4 array  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 08-April 09

Re: Sorting a Doubly LinkedList

Posted 05 September 2009 - 10:13 PM

that changes everything..

I was hoping for something along the lines of what i've written thus far.

It doesnt seem to work when i skip the node ( after printing it ) that i've sorted.

My Sort function only seems to sort 1 of the nodes out of the many that I have.

I am still trying everything that I know of to get it to sort properly W/O the use of an array. Call me stubborn.

But thanks for the reply! =)

This post has been edited by array: 05 September 2009 - 10:43 PM

Was This Post Helpful? 0
  • +
  • -

#5 Guest_c.user*


Reputation:

Re: Sorting a Doubly LinkedList

Posted 05 September 2009 - 10:40 PM

array said:

I was hoping for something along the lines of what i've written thus far.

I don't see where nodes are moving, only where you search the last least node but the sort method presupposes the moving

This post has been edited by c.user: 05 September 2009 - 10:40 PM

Was This Post Helpful? 0

#6 array  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 08-April 09

Re: Sorting a Doubly LinkedList

Posted 05 September 2009 - 11:24 PM

I found the one that we want, so it should no longer be a factor in the sorting.

if we come across it, disregard it.

This post has been edited by array: 05 September 2009 - 11:25 PM

Was This Post Helpful? 0
  • +
  • -

#7 array  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 08-April 09

Re: Sorting a Doubly LinkedList

Posted 06 September 2009 - 11:47 AM

anyone think i could get a little more help with this sorting thing?


void list::displayByName(ostream& out) const
{
	node *current_node  = headByName;
	
while ( current_node != NULL )
{
			  current_node = sort( current_node );
			  out << current_node->item.getName() << endl;
			
}
}


list::node * const list::sort( node *given_node ) const
{	
	node *least_found_node = NULL;
	node *current_node	  = given_node->nextByName;
	node *evil_node	   = NULL;

	while ( current_node && current_node != given_node )
	{
		if ( strcmp( current_node->item.getName(), given_node->item.getName() ) < 0 )
		{
			if ( least_found_node == NULL || 
			   ( strcmp( least_found_node->item.getName(), current_node->item.getName() ) > 0 ) )
			{
				least_found_node = current_node;
				evil_node = least_found_node;
			}
		}
		current_node = current_node->nextByName;
		
	}
	return least_found_node; // return that sorted node
}


Was This Post Helpful? 0
  • +
  • -

#8 poncho4all  Icon User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,405
  • Joined: 15-July 09

Re: Sorting a Doubly LinkedList

Posted 06 September 2009 - 12:05 PM

This is a program that orders numbers in the double liked list it might give you an idea.

http://www.dreaminco...snippet4343.htm
Was This Post Helpful? 0
  • +
  • -

#9 Guest_c.user*


Reputation:

Re: Sorting a Doubly LinkedList

Posted 06 September 2009 - 04:08 PM

array, if you want to get the least node it should be done by the simple selection

you take every node and compare it with the first node
if this node is less than the first node you write this node instead the first node, continuing the selection

in the sorting you should move all elements, but I don't see where do you move them
Was This Post Helpful? 0

#10 array  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 08-April 09

Re: Sorting a Doubly LinkedList

Posted 06 September 2009 - 05:51 PM

thats because i am searching it. I think I got the terms "search" and "sort" mixed up.
Was This Post Helpful? 0
  • +
  • -

#11 Guest_c.user*


Reputation:

Re: Sorting a Doubly LinkedList

Posted 06 September 2009 - 09:31 PM

you could make two methods one for the searching and second for the deleting, they should be independent from themselfs

because I see the method for the deleting, I suppose this is for delete least element after its printing
Was This Post Helpful? 0

Page 1 of 1