Thread: cannot figure out problem: selection sort in linked list

hi, i have this code over here which i cant figure out what's going on.

Code:

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
   int data;
   struct node *next;
} Node;

Node *addNode(Node *head, int value); 
void  printList(Node *head);          
void  selsort(Node *head);            
int main(int argc, char **argv) {
   Node *head = NULL;

   int i;
   int number;

   for  (i = 0; i < argc; i++) {
      if (atoi(argv[i]) != 0) {
         number = atoi(argv[i]);
         head = addNode(head, number);
      }
      else {
      printf ("Bad data %s, ignoring\n", argv[i]);
      }
   }
   
   

   selsort(head);     


   printf("Sorted numbers:");
   printList(head);                   
   return EXIT_SUCCESS;
}

void  printList(Node *head) {
   Node *cur;
   cur=head;
   while (cur->next != NULL) {
      printf ("%d ", cur->data);
      cur = cur-> next;
   }
   printf ("%d\n", cur->data);
}


Node *addNode(Node *head, int value) {

   Node *new;
   Node *cur;
   new = malloc(sizeof(Node));
   if (new == NULL) {
      fprintf (stderr, "create: no memory, aborting\n");
      exit(1);
   }
   new->data = value;
   new->next = NULL;

   if (head == NULL) {
      head = new;
   }
   
   else {
      cur = head;
      while (cur->next != NULL) {
         cur = cur->next;
      }
      cur->next = new;
   } 
   return head;
}

void selsort(Node *head) { 
   Node *cur;
   Node *i;                               
   Node *min;                             
   for (cur = head; cur->next != NULL ; cur = cur->next) {
      min = cur;                    
      for (i = cur->next; cur->next != NULL ; i = cur->next) {
         if (i->data < cur->data)
            min = i;                   
      }
      Node *tmp;
      tmp = cur;
      cur = min;       
      min = tmp;
   }
   return;
}

it seems that if i enter more than 1 number in the stdin, the program will not run successfully. After trying to debug it for a long time, I located the problem to the first for loop. However, I dont see anything wrong with it can anyone help me with it? Thanks in advance!

Start the first loop at 1 not 0 ... In C arrays are always 0 based, but when your program starts up the command line arguments are placed into the argv array so that argv[0] is the path to the program itself, your first command line variable is argv[1].

Also ... head = addNode(head, number); ... is continuously replacing the entire list with your newest entry instead of adding it to the end of your list. Not only does this not build a linked list, it leaks memory from the lost nodes.

Thank you for your reply. I managed to solve the problem already. Like you say, I do agree that head = addnode (head, number) is not a very nice line, but my lecturer wants me to create a function with that line =/ so i cant change that.

Cheers!

There's nothing wrong with addNode(). Data is appended to the end of the list, and each time the head of that list is returned.

The problem is in selsort(). You're attempting to swap nodes in the list using:

Code:

Node *tmp;
tmp = cur;
cur = min;
min = tmp;

You can't swap nodes in a linked list like that. When you're doing a selection sort on a linked list, you have to explicitly unlink the node and relink it where it's supposed to go.

A better way to sort linked lists is merge sort, but if you're just doing this to learn selection sort, that's fine.

uh huh.. instead of Node *tmp, I should have used int tmp and saved alot of trouble. Moving nodes in linked list is a nightmare!