help with sorting a list :(

**yxunomei** · 10-15-2006

what happened when you used my exact original code?? compiler error?

can you paste me the exact output and with the corrected code output?

im getting there i think

Code:

charNode *sort(charNode *start)
{
   charNode *prev = NULL, *temp = NULL;
   charNode *current = NULL;
   
   if(start == NULL || start->next == NULL) { // have you tried this?? 
      return start;
   } 

   current = start->next;
   prev = current;

   while (current != NULL) {
      printf("%p %p %p %p\n", prev, current, temp, start);
      if ( strcmp(current->petName, prev->petName) < 0) {
         swap(&current, &prev); // I'm not sure about this, try it
      }
      prev = current;
      current = current->next;   
   }
   return start;
}

**Axel** · 10-15-2006

warning passing arg 1 of 'swap' from an incompatible pointer type
warning passing arg 2 of 'swap' from an incompatible pointer type

(hence why i provided the address the swap)

but i compiled it anyway and it crashed:

00000000 003D2C78 00000000 003D2C60

**yxunomei** · 10-15-2006

refer to my msg above (we should avoid posting more message

, it's 3 pages already

)

**Happy_Reaper** · 10-15-2006

Ok, here's how to swap correctly. Assume you're trying to swap 2 nodes, a and b, from a singly linked list LList :

1) swap a->next and b->next correctly (Make sure you're actually swapping the addresses)
2) find the predecessors of a and b. Call them P(a) and P(b), respectively. You can find the predecessor of a node a in the Linked List LList doing this :

Code:

Node pred(Node * a, Node*List)
{
	if(a == List){return NULL;}
       
	if((*a) == (*List).next)
	{
		return *List;
	}
	else
	{
		if((*List).next == NULL)
		{
			printf("Not in list.");
		}
		else
		{
			return pred(a,(*List).next);
		}
	}
}

3) Swap the next pointer of the predecessors accordingly.

After that, you've swapped your nodes in your list correctly. Right now, you're not swapping correctly, so sorting, NO MATTER WHAT, will almost never work.

**yxunomei** · 10-15-2006

Originally Posted by Happy_Reaper

Ok, here's how to swap correctly. Assume you're trying to swap 2 nodes, a and b, from a singly linked list LList :

1) swap a->next and b->next correctly (Make sure you're actually swapping the addresses)
2) find the predecessors of a and b. Call them P(a) and P(b), respectively. You can find the predecessor of a node a in the Linked List LList doing this :

Code:

Node pred(Node * a, Node*List)
{
	if(a == List){return NULL;}
       
	if((*a) == (*List).next)
	{
		return *List;
	}
	else
	{
		if((*List).next == NULL)
		{
			printf("Not in list.");
		}
		else
		{
			return pred(a,(*List).next);
		}
	}
}

3) Swap the next pointer of the predecessors accordingly.

After that, you've swapped your nodes in your list correctly. Right now, you're not swapping correctly, so sorting, NO MATTER WHAT, will almost never work.

ouch... you ruined the fun

...

**Happy_Reaper** · 10-15-2006

Originally Posted by yxunomei

ouch... you ruined the fun

...

Perhaps, but it's pointless to try and explain sorting if he can't swap right.

**Axel** · 10-15-2006

Happy_Reaper,

with your code im having trouble with the following lines:

Code:

if( (*a) == (*List).next)
	{
		return *List;
	}

error: invalid operands to binary ==

if( (*a) == (*List).next)

**Happy_Reaper** · 10-15-2006

If you were to understand what I was doing, you'd know what I'm doing wrong. Anyhow, it's supposed to be a, not (*a)

**Axel** · 10-15-2006

ok...

i ran it like this:

swap(&start, &start->next, start);

Code:

void swap(charNode **a, charNode **b, charNode *start) {
  charNode *temp;
  charNode *preA = pred(start->next, start);
  charNode *preB = pred(start, start);

  preB = preA;
  temp = *a;
  *a = *b;
  *b = temp;
  
  
}

and

Code:

charNode *pred(charNode *a, charNode *List)
{
	if(a == List)
	{
		//printf ("BLAH");
		return NULL;
	}
	if( a == (*List).next)
	{
		return List;
	}

		if((*List).next == NULL)
		{
			printf("Not in list.");
		}
		else
		{
			printf("RETURNED");
			return pred(a,(*List).next);
		}
	
}

it just returns

Androd
Bat

Dog is still missing...

original list:

Dog
Androd
Bat

**Happy_Reaper** · 10-15-2006

For one thing, you're not swapping the pred pointers right. You have to swap (preA.next) and (preB.next) (see my above comment, where I gave you instructions)

Also, you're missing the point. Swap won't sort the list for you. It'll just change the positions of two nodes in your linked list without breaking the structure.

**Axel** · 10-15-2006

changed:

Code:

 preB = preA;

to :

Code:

 preA->next = preB->next;

now it just crashes *dies*

Also, you're missing the point. Swap won't sort the list for you. It'll just change the positions of two nodes in your linked list without breaking the structure.

it does break the structure does it not? i mean i previously had 3 nodes but after swap runs im left with 2.

**Happy_Reaper** · 10-15-2006

Originally Posted by Axel

it does break the structure does it not? i mean i previously had 3 nodes but after swap runs im left with 2.

It shouldn't. You've not swapping preA and preB, you're just assigning preA to preB. That makes them both equal. Not a good idea in a linked list.

**Axel** · 10-15-2006

ok so you mean i should also run the swap method on the precedent nodes as well?

i.e.:

Code:

swap(&preA->next,&preB->next, start);

because now the list is just empty.

**Axel** · 10-15-2006

well i've tried doing things on paper and it makes sense. but when i apply it like below:

Code:

 temp = *a;
  *a = *b;
  temp2 = *b;
  *b = temp;
  (*b)->next->next = temp2;

it doesn't. the last node is *still empty*

**Happy_Reaper** · 10-15-2006

No. You see how you have a temp variable there when you swap a and b ? What is that temp node for ?

Now do the same thing for preA.next and preB.next.