help with sorting a list :(

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

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.

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

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);

}

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..:/

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

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");

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;
}

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

start = sort(start);

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?

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

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;
}

ok, try again, i've modified the code above

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.