help with sorting a list :(

This is a discussion on help with sorting a list :( within the C Programming forums, part of the General Programming Boards category; what happened when you used my exact original code?? compiler error? can you paste me the exact output and with ...

  1. #31
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    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;
    }
    Last edited by yxunomei; 10-15-2006 at 10:29 AM.

  2. #32
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    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

  3. #33
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    refer to my msg above (we should avoid posting more message , it's 3 pages already )

  4. #34
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    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.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  5. #35
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    Quote 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 ...

  6. #36
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Quote 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.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  7. #37
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    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)

  8. #38
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    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)
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  9. #39
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    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

  10. #40
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    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.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  11. #41
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    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.

  12. #42
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Quote 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.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

  13. #43
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    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.

  14. #44
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    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*

  15. #45
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    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.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

Page 3 of 4 FirstFirst 1234 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. Replies: 3
    Last Post: 03-04-2005, 01:46 PM
  3. Replies: 6
    Last Post: 03-02-2005, 01:45 AM
  4. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 09:16 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21