cannot figure out problem: selection sort in linked list

This is a discussion on cannot figure out problem: selection sort in linked list within the C Programming forums, part of the General Programming Boards category; hi, i have this code over here which i cant figure out what's going on. Code: #include <stdio.h> #include <stdlib.h> ...

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    6

    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!

  2. #2
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    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.

  3. #3
    Registered User
    Join Date
    May 2011
    Posts
    6
    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!

  4. #4
    cas
    cas is offline
    Registered User
    Join Date
    Sep 2007
    Posts
    957
    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.

  5. #5
    Registered User
    Join Date
    May 2011
    Posts
    6
    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!

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,269
    Quote Originally Posted by ghithong View Post
    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!
    Actually that would take you further away from your goal. Moving nodes in a linked list is not that hard, just draw yourself a few diagrams to help get the logic right. The thing is, none of your existing code is actually "moving nodes in a linked-list" at all.
    If you don't have to use selection sort, then insertion sort is the easiest to implement for a linked-list, well marginally easier.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Replies: 2
    Last Post: 01-17-2009, 09:48 PM
  3. Selection Sort Problem?
    By dcwang3 in forum C Programming
    Replies: 31
    Last Post: 11-07-2008, 12:25 PM
  4. Selection Sort problem #2
    By Twigstar in forum C++ Programming
    Replies: 7
    Last Post: 07-11-2005, 07:27 PM
  5. Selection sort problem
    By kippwinger in forum C++ Programming
    Replies: 1
    Last Post: 07-03-2003, 01:35 AM

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