Thread: Sorting a string linked list

  1. #1
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62

    Sorting a string linked list

    I want to print out a sorted string linked list but my codes sort in the order of entry.
    such as :
    Code:
    Input : e a g c
    Outout : e a g c
    How can I convert my codes to insert the inputs in actual alphabetic sorted order. Could you help me please?

    Code:
    void insert_in_order(char *n, node_ptr list)
    {
    	node_ptr before = list;
    	node_ptr new_node = (node_ptr)malloc(sizeof(struct node));
    	new_node->name = n;
    
    	while(before->next && (before->next->name < n))
    	{
    		before = before->next;
    	}
    	new_node->next = before->next;
    	before->next = new_node;
    }
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  2. #2
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    1. Shouldn't you be comparing n with before->name instead of before->next->name ?
    2. Use strcmp()

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    In order to sort the list, you need to do comparisons, yeah? Unless your names are going to have just one letter, you'll want to use a library function like strcmp(), to take care of the letter by letter comparisons involved.

    Why don't you start with a simple Bubble sort (you can get the algo from Wiki or zillions of web sites), and study it, see what it's all about.

    Then make the adjustments in that code that need to be made so it will work with a linked list, instead of the usual, array.

    Sorting is one of the most common activities for all kinds of programs to do. Learn all you can about it, including why Bubble sort is not a good sorter if you have a good deal of data that needs to be sorted.

    Adak
    Last edited by Adak; 04-28-2007 at 01:44 AM.

  4. #4
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    Thanks for the replies.At this point I need bit more effective. Am I on the right right track, if I am not can you put me on the right track?

    I am getting
    Code:
    list.c:59: warning: passing arg 2 of `__builtin_strcmp' from incompatible pointer type
    list.c:59
    Code:
    while(strcmp(previous, new_node ) > 0 && strcmp(current, new_node) < 0)
    Rest of the codes:
    Code:
    void insert_in_order(char *n, node_ptr list)
    {
    	node_ptr previous = list;
    	node_ptr current = list->next;
    	node_ptr new_node = (node_ptr)malloc(sizeof(struct node));
    	new_node->name = n;
    	
    	if(current == NULL)
    	{
    		new_node->next = list->next;
    		list->next = new_node;
    		
    	}
    	while (current != NULL)
    	{
    		while(strcmp(previous, new_node ) > 0 && strcmp(current, new_node) < 0)
    		{
    			previous->next = new_node;
    			new_node->next = current;
    			break;	
    		}
    		previous = current;
    		current = current->next;
    	}
    }
    Last edited by BoneXXX; 04-29-2007 at 01:11 AM.
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  5. #5
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    strcmp() compares strings, its two parameters need to be of type char* and not of type node_ptr

  6. #6
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    Thanks for the reply. The compiling problem is fixed.

    Unfortunately it didn't sorted in the way that I wanted which is in an alphabetic way.

    My input was : a b z c
    the output : c z b a
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  7. #7
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    your internal while is executes 0 or 1 time - use if instead

    What if the new_node should be insearted after the last one? Where do you do it?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  8. #8
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    but whit the while loop I wanted to compare the previous and the current nodes find the right place. Such as 1 2 4 5 - 3 is going to be inserted between 2 and 4. I was trying to do this.
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  9. #9
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    I sorted out now, it compiles in the right alphabetic order but it can take the same input more than once. Is there any idea?

    Code:
    void insert_in_order(char *n, node_ptr list)
    {
        node_ptr before = list;
        node_ptr new_node = (node_ptr) malloc(sizeof(struct node));
        new_node->name = n;
    
        /* Move along list until right place is found, looking for node after
           which new node should go */
        while(before->next && (strcmp(before->next->name, new_node->name) < 0))
        {
            before = before->next;
        }
    
        new_node->next = before->next;
        before->next = new_node;
    }
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Change it to <= instead of just < and it will then match identical strings also.


    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    I tried it with && (strcmp(before->next->name, new_node->name) == 0) but I will try your suggestion and let you know. Thanks.
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  12. #12
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    Quote Originally Posted by quzah View Post
    Change it to <= instead of just < and it will then match identical strings also.


    Quzah.
    it didn't work Can it be related to my main program.
    Code:
    			printf("Enter a name:\n");
    			scanf("&#37;s",buffer);
    			n=(char*)malloc(strlen(buffer));
    			strcpy(n,buffer);
    			delete_it(n,the_list);
    Last edited by BoneXXX; 04-30-2007 at 05:12 AM.
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  13. #13
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    It is fixed. I have another question now. When I want to delete a name from the list I get a segmentation fault. At least could you help me on this?

    calling the function:
    Code:
    	printf("Enter an unit name but not more than 100 characters:\n");
    	scanf("&#37;s",buffer);
    	n=(char*)malloc(strlen(buffer)+1);
    	strcpy(n,buffer);
    	delete_it(n,the_list);
    The Function:
    Code:
    /*Function to delete  unit from the list*/
    void delete_it(char *n, node_ptr list)
    {
    	node_ptr before = list;
    	node_ptr current = list->next;
    	node_ptr new_node = (node_ptr) malloc(sizeof(struct node));
    	
    	while(current != NULL)
    	{
    		if(strcmp(before->next->name, new_node->name) == 0)
    		{
    			before->next = current->next;
    			free(current);
    		}
    		else
    		{
    			before = current;
    			current = current->next;
    		}
    	}
    	return;
    }
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

  14. #14
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    No need to cast malloc,

    Me thinks first bit of code should be:

    Code:
    char buffer[128];
    /*
    ...
    */
    
    printf("Enter an unit name but not more than 100 characters:\n");
    puts("Enter an unit name");
    fgets(buffer, sizeof(buffer), stdin);
    delete_it(buffer, the_list);
    /* um, why were you moving buffer from the stack to the heap ? */

  15. #15
    Brak BoneXXX's Avatar
    Join Date
    Mar 2007
    Location
    Bangkok
    Posts
    62
    Thanks for the reply but in your codes nothing goes into the function. In my codes everything is fine until "delete_it(n,the_list);", when it comes to this point I get a segmentation fault.
    “Example isn't another way to teach, it is the only way to teach” Albert Einstein

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Concatenating in linked list
    By drater in forum C Programming
    Replies: 12
    Last Post: 05-02-2008, 11:10 PM
  2. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  3. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  4. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 10:33 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM