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; that sounds rite to me ... you are copying the address of the pointer, not the actual string try this ...

  1. #16
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    that sounds rite to me ... you are copying the address of the pointer, not the actual string

    try this
    Code:
    while (current != NULL) {// keep looping till the end.... 
       printf("%p %p %p %p\n, prev, current, temp, start); //  <--- add this
                if ( strcmp(current->petName, prev->petName) <0)  /* IF Androd is smaller than Dog == TRUE */
                {
                   prev->next = current->next;     /* this is just saying  Androd = Androd  */
                   temp = prev;     /* place "prev" i.e.  Dog in a temporary variable */
                   prev = current;      /* place current (Androd) to prev (Dog) so we have Androd, Dog
                   //  um, you are not using the temp? 
                                         
                }
             
                else
                   prev = current; // keep track of the previous item
                   current = current->next; // move current after prev
             }
    and tell me what's get printed
    Last edited by yxunomei; 10-15-2006 at 09:58 AM.

  2. #17
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Ok, before you can sort, you're going to have to be able to swap the elements of your list correctly. And as of now, you're just not doing that.

    To swap two elements, you need to swap their next pointers, you seem to be doing that much. BUT, you must ALSO swap the next pointers of their respective successors. If you don't do that, you'll end up with loads aof garbage any time you switch things around. Now I'm not sure if that's the exact cause of your infinite loop, but it wouldn't surprise me.

    Anyhow, first getting swapping to work right. Then think about sorting.
    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

  3. #18
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    is there an example somewhere? with just a simple * swap* ?

    i have tried following... but the list remains unsorted :|

    http://www.experts-exchange.com/Prog..._20914849.html

    Code:
    charNode *sort(charNode *start)
    {
       charNode *ptr1, *ptr2 = start;
      
             while (ptr1 != NULL)
             {
             	ptr2 = ptr1;
             	while (ptr2 != NULL)
             	{
                	if ( strcmp(ptr1->petName, ptr2->petName) <0)
                	{
                		ptr2 = ptr2->next;
                	}
             	}
             ptr1 = ptr1->next;
             }
             
          
       
       return start;
    }
    also...re: to your q

    003D2C90 003D2C60 00000000 003D2C60
    003D2C60 003D2C78 00000000 003D2C60
    003D2C78 003D2C90 003D2C60 003D2C60
    Last edited by Axel; 10-15-2006 at 10:03 AM.

  4. #19
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    simple int swap
    Code:
    #include <stdio.h>
    
    void swap(int *a, int *b) {
      int temp;
    
      temp = *a;
      *a = *b;
      *b = temp;
    }
    
    int main() {
      int a = 3 , b = 5;
    
      swap(&a, &b);
    
      printf("%d %d\n", a, b);
    
    }

  5. #20
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    thanks but swapping ints in its self is easy (basically you're just passing the addresses to swap deref that address and get its value, assigning it to temp and swapping the values around). But in a list its much more difficult..:/
    Last edited by Axel; 10-15-2006 at 10:11 AM.

  6. #21
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    Code:
    while (current != NULL) 
             {
                if ( strcmp(current->petName, prev->petName) <0)
                {
                   prev->next = current->next;     
                   temp = prev;     
                   prev = current;      
                                         
                }
             
                else
                   prev = current; 
                   current = current->next;
             }
    Code:
    previous current  temp     start
    003D2C90 003D2C60 00000000 003D2C60 // zwha??? :O ... I thought previous == current??
    003D2C60 003D2C78 00000000 003D2C60
    003D2C78 003D2C90 003D2C60 003D2C60
    this is sort of unexpected ?? can you post your newest code with this?

    as to your code up there, I wouldn't wonder... there's no swapping at all... it just basically go thru the list
    Last edited by yxunomei; 10-15-2006 at 10:18 AM.

  7. #22
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    i have modified your swap method:

    Code:
    void swap(charNode **a, charNode **b) {
      charNode *temp;
    
      temp = *a;
      *a = *b;
      *b = temp;
    }
    by running: swap(&start, &start->next);

    the problem is it prints


    Androd
    Bat

    no last node??

    original list:

    addElement(&start, "Dog");
    addElement(&start, "Androd");
    addElement(&start, "Bat");

  8. #23
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    Quote Originally Posted by yxunomei
    this is sort of unexpected ?? can you post your newest code with this?

    as to your code up there, I wouldn't wonder... there's no swapping at all... it just basically go thru the list
    Code:
    charNode *sort(charNode *start)
    {
       charNode *prev, *temp = NULL;
       charNode *current = start;
      
         while (current != NULL) {// keep looping till the end.... 
          printf("%p %p %p %p\n", prev, current, temp, start); //
                if ( strcmp(current->petName, prev->petName) <0)  
                {
                   prev->next = current->next;    
                   *temp = *prev;     
                   *prev = *current;    
                                         
                }
             
                else
                   prev = current; // keep track of the previous item
                   current = current->next; // move current after prev
             }
             
          
       
       return start;
    }

  9. #24
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    T_T_T_T_T_T ....

    OK... I need you to do the following...

    1. compile your newest code with the print thing I gave you earlier...
    2. copy paste the exact result
    Last edited by yxunomei; 10-15-2006 at 10:24 AM.

  10. #25
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    start = sort(start);

  11. #26
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    ok:

    Code:
    charNode *sort(charNode *start)
    {
       charNode *prev, *temp = NULL;
       charNode *current = start;
      
         while (current != NULL)
          
             {
             	printf("%p %p %p %p\n", prev, current, temp, start);
                if ( strcmp(current->petName, prev->petName) <0)
                {
                   prev->next = current->next;     
                   temp = prev;     
                   prev = current;      
                                         
                }
             
                else
                   prev = current; 
                   current = current->next;
             }
             
          
       
       return start;
    }
    result:

    003D2C90 003D2C60 00000000 003D2C60
    003D2C60 003D2C78 00000000 003D2C60
    003D2C78 003D2C90 003D2C60 003D2C60


    Dog
    Bat


    and this is the complete code for the swap function earlier (i can't get it to work properly...the end node is missing??)

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct charNode
    {
       char petName[12];
    
       struct charNode *next;
    };
    
    typedef struct charNode charNode;
    
    void addElement(charNode **start, char *petName);
    void printList(charNode *start);
    charNode* newNode(char *petName);
    void getString(charNode *start);
    void swap(charNode **a, charNode **b);
    
    int main()
    {
       charNode *start = NULL;
    
       getString(start);
      
       return 0;
    }
    
    
    void getString(charNode *start)
    {
    
    	addElement(&start, "Dog");
         addElement(&start, "Androd");
         addElement(&start, "Bat");
         
         swap(&start, &start->next); 
         printList(start);
    
    }
    
    void addElement(charNode **start, char *petName)
    {
    
       charNode *temp,*prev, *loc;
       int i;
    
       temp = newNode(petName);
    
    
       if (*start == NULL)
       {
          *start = temp;
       }
    
       else
       {
          loc = *start;
          prev = NULL;
    
           for (i=0; loc != NULL; i++)
           {
       
               	prev = loc;
    			loc = loc->next;
            }
    	      if (prev == NULL)
             {     
                *start = temp;
             }
             else
             {
                prev->next = temp;  
             }
       }
      
    
    }
    
    charNode* newNode(char *petName)
    {
    
       charNode *temp;
    
       temp = (charNode *) malloc(sizeof(charNode));
       if (temp == NULL)
       {
          printf("WARNING - Memory allocation error\n");
          exit(EXIT_FAILURE);
       }
    
    
      strcpy(temp->petName, petName);
    
    
       temp->next = NULL;
    
       return temp;
    }
    
    
    void printList(charNode *start)
    {
    
       while (start != NULL)
       {
    
          printf("%s\n", start->petName);
          start = start->next;
       }
    }
    
    void swap(charNode **a, charNode **b) {
      charNode *temp;
    
      temp = *a;
      *a = *b;
      *b = temp;
    }
    any idaes?
    Last edited by Axel; 10-15-2006 at 10:44 AM.

  12. #27
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    your prev isn't initialized
    Code:
    charNode *prev, *temp = NULL;
    try this

    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;
    }
    compile, run, copy paste the exact stuff
    Last edited by yxunomei; 10-15-2006 at 11:12 AM.

  13. #28
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    noooooooo

    00000000 003D2C78 00000000 003D2C60

    and then crashes

    i had to change:

    swap(current->petName, prev->petName); // I'm not sure about this, try it

    to

    swap(&current, &prev); // I'm not sure about this, try it

    otherwise it wouldn't compile...

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct charNode
    {
       char petName[12];
    
       struct charNode *next;
    };
    
    typedef struct charNode charNode;
    
    void addElement(charNode **start, char *petName);
    void printList(charNode *start);
    charNode* newNode(char *petName);
    void getString(charNode *start);
    void swap(charNode **a, charNode **b);
    charNode *sort(charNode *start);
    
    int main()
    {
       charNode *start = NULL;
    
       getString(start);
      
       return 0;
    }
    
    
    void getString(charNode *start)
    {
    
    	addElement(&start, "Dog");
         addElement(&start, "Androd");
         addElement(&start, "Bat");
         
         sort(start); 
         printList(start);
    
    }
    
    void addElement(charNode **start, char *petName)
    {
    
       charNode *temp,*prev, *loc;
       int i;
    
       temp = newNode(petName);
    
    
       if (*start == NULL)
       {
          *start = temp;
       }
    
       else
       {
          loc = *start;
          prev = NULL;
    
           for (i=0; loc != NULL; i++)
           {
       
               	prev = loc;
    			loc = loc->next;
            }
    	      if (prev == NULL)
             {     
                *start = temp;
             }
             else
             {
                prev->next = temp;  
             }
       }
      
    
    }
    
    charNode* newNode(char *petName)
    {
    
       charNode *temp;
    
       temp = (charNode *) malloc(sizeof(charNode));
       if (temp == NULL)
       {
          printf("WARNING - Memory allocation error\n");
          exit(EXIT_FAILURE);
       }
    
    
      strcpy(temp->petName, petName);
    
    
       temp->next = NULL;
    
       return temp;
    }
    
    
    void printList(charNode *start)
    {
    
       while (start != NULL)
       {
    
          printf("%s\n", start->petName);
          start = start->next;
       }
    }
    
    void swap(charNode **a, charNode **b) {
      charNode *temp;
    
      temp = *a;
      *a = *b;
      *b = temp;
    }
    
    charNode *sort(charNode *start)
    {
       charNode *prev = NULL, *temp = NULL;
       charNode *current = NULL;
       
       if(start == NULL || start->next == NULL) { // have you tried this?? 
          return start;
       } 
    
       prev = current;
       current = start->next;
    
       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;
    }

  14. #29
    The C eater *munch*
    Join Date
    Oct 2006
    Posts
    101
    ok, try again, i've modified the code above

  15. #30
    Learner Axel's Avatar
    Join Date
    Aug 2005
    Posts
    335
    yes it works but its still unsorted:

    Dog
    Androd
    Bat

    i used the same exact code except for:

    swap(&current, &prev); // I'm not sure about this, try it


    even afte i modified:

    start = sort(start);
    printList(start);

    so the i get a reference to the new list after its sorted.

Page 2 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, 11:10 AM
  2. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  3. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  4. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 10:16 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

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