swap elements in a linked list.

[Axel]

I want to sort a link last based on a few criterias. If a nodes x element is less than y then they should be swapped. I need to do this to all elements in the list till it is sorted from smallest to largest. The first step was i attempted to write a swap method as follows;

void swap(charNode **x, charNode **y)
{

   charNode*temp;
   temp = *x; // save x temporarly.
   x = y; // swap y and x position
   *y = temp; // place x after y

}

which miserably failed. I just tried modifying one of the swap methods that i use for an array. For some reason when i pass the address of the "start" node and start->next nodes after i print it; it does not reflect anything.. Any ideas?

[Axel]

my full code as follows...

#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 **x, charNode **y);

int main()
{
   charNode *start = NULL;

   getString(start);
  
   return 0;
}


void getString(charNode *start)
{

     addElement(&start, "(1)Cat");
     addElement(&start, "(2)Dog");
     addElement(&start, "(3)Horse");
     
     swap(&start->next, &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 **x, charNode **y)
{

   charNode *temp;
   temp = *x; // save x temporarly.
   x = y; // swap y and x position
   *y = temp; // place x after y

}

[Salem]

> x = y; // swap y and x position
Assuming everything else is OK, this would be
*x = *y; // swap y and x position

[zx-1]

Pass in two pointers to charNode, and do a byte-for-byte exchange of their information fields (i.e. char petName[12]).

The alternative approach is to mess around with pointers and actually change the logical sequence of the nodes, and that is not a pretty thing.

[Axel]

The alternative approach is to mess around with pointers and actually change the logical sequence of the nodes, and that is not a pretty thing.

this is what i'm trying to do now. I'm almost there but i have a few problems:

The following code will sort the animals in alphabetical order. The ONLY problem i'm having is if i have the last node come previously alphabetically then it does not order it i.e:

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

the result is :

Androd
Dog
Bat

charNode *swap(charNode *start)
{

   charNode *temp = NULL;
   charNode *prev = NULL;
   charNode *current = start;

   if (start!=NULL)
   {
      if (start->next != NULL)
      {
         prev = start;
         current = start;

         while (current != NULL)
         {
            if ( strcmp(current->petName, start->petName) <0)
            {
               prev->next = current->next;     
               temp = start;      
               start = current;      
               start->next = temp;   
                                    
            }
         
            else
               prev = current;
               current = current->next;
         }
      }
   }
   return start;
}

by the way the code above can be used with the code previously posted by replacing the swap function and by putting:

start = swap(start);

before the printList statement...

[Happy_Reaper]

You're not quite swapping correctly. To swap two elements in a linked list, you need to exchange their "next" pointer, but you also need to exchange their predecessor's "next" pointer. You seem to be understanding the former, but without the latter, your linked-list will quickly look like garbage.

[jafet]

Your sort algorithm is a little retarded. Read http://en.wikipedia.org/wiki/Sorting_algorithm for real sorting algorithms which do work. In any case, you probably want to do two passes in swap(), one going down the list and one back up, so small strings at the end can be swapped to the front as expected. You should really try out your algorithms on paper (with example strings) to see what-in-carnation are wrong with them before you actually write code. If you want a permanently sorted structure, it might also be more logical (and probably faster) to use a self-balancing binary tree for the job.