Translating Java to C. Mergesorting linked list.

This is a discussion on Translating Java to C. Mergesorting linked list. within the C Programming forums, part of the General Programming Boards category; I am having some trouble translating this java code in to C. There is something wrong with my merge sort ...

  1. #1
    Registered User
    Join Date
    Feb 2002
    Posts
    37

    Translating Java to C. Mergesorting linked list.

    I am having some trouble translating this java code in to C. There is something wrong with my merge sort in C. Don't know what since I get error at runtime.

    Compiler: Dev-cpp 4.8.8.0
    OS: Windows 2000 sp4

    "Java"

    Code:
    public static IntNode MergeSort(IntNode list1)
    {
        if ((list1 == null) || (list1.getLink() == null)
             return list1;
    
        IntNode list2 = split(list1);
        list1 = MergeSort(list1);
        list2 = MergeSort(list2);
    
        return merge(list1, list2);
    }
    
    private static IntNode split(IntNode list1)
    {
        if ((list1 == null) || (list1.getLink() == null)
             return null;
    
        IntNode.list2 = list1.getLink();
        list1.setLink(list2.getLink());
        list2.setLink(split(list2.getLink()));
    
        return list2;
    }
    
    private static IntNode merge(IntNode list1, IntNode list2)
    {
        if (list1 == null)
             return list2;
        if (list2 == null)
             return list1;
        if (list1.getData() < list2.getData())
        {
             list1.setLink(merge(list1.getLink(), list2));
             return list1;
        }
        else
        {
             list2.setLink(merge(list1, list2.getLink()));
             return list2;
        }
    }
    This is what I have done in C.

    INTLINKEDLIST.H
    Code:
    #ifndef _INTLINKEDLIST_H_
    #define _INTLINKEDLIST_H_
    
    struct Node
    {
        int element;
        struct Node * Next;
    };
    
    void Insert(int x, struct Node * l);
    struct Node * MergeSort(struct Node * list1);
    struct Node * split(struct Node * list1);
    struct Node * merge(struct Node * list1, struct Node * list2);
    
    #endif
    Code:
    #include "IntLinkedList.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    void insert(int X, struct Node * l)
    {
        struct Node * temp = malloc(sizeof(struct Node));
    
        if (temp == NULL)
            fprintf(stderr, "Error in memory allocation.\n");
    
        temp->element = X;
        temp->Next = l->Next;
        l->Next = temp;
    }
    
    struct Node * MergeSort(struct Node * list1)
    {
    	struct Node * list2;
    
    	if ((list1 == NULL) || (list1->Next == NULL))
    		return list1;
    
    	list2 = split(list1);
    
    	list1 = MergeSort(list1);
    	list2 = MergeSort(list2);
    
    	return merge(list1, list2);
    }
    
    struct Node * split(struct Node * list1)
    {
    	struct Node * list2;
    
    	if ((list1 == NULL) || (list2->Next == NULL))
    		return NULL;
    
            list2 = list1->Next;
    	list1->Next = list2->Next;
    	list2->Next = split(list2->Next);
    
    	return list2;
    }
    
    struct Node * merge(struct Node * list1, struct Node * list2)
    {
    	if (list1 == NULL)
    		return list2;
    	if (list2 == NULL)
    		return list1;
    	if (list1->element < list2->element)
    	{
    		list1->Next = merge(list1->Next, list2);
    		return list1;
    	}
    	else
    	{
    		list2->Next = merge(list1, list2->Next);
    		return list2;
    	}
    }

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >There is something wrong with my merge sort in C.
    There's only one small thing wrong with the merge sort. In split you have this:
    Code:
    if ((list1 == NULL) || (list2->Next == NULL))
    The second test should be on list1 instead of list2 because list2 is indeterminate at this point.

    The real problem is your linked list insertion function. You don't send the changes back to the original list. To do so you would need to either pass a pointer to the pointer or return the new head of the list:
    Code:
    struct Node * Insert(int X, struct Node * l)
    {
      struct Node * temp = malloc(sizeof(struct Node));
    
      if (temp == NULL)
        fprintf(stderr, "Error in memory allocation.\n");
      temp->element = X;
      temp->Next = l;
    
      return temp;
    }
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Feb 2002
    Posts
    37
    I have made the changes but when I insert for example the following numbers 5, 7, 4, 6 and then using the mergesort. I get the result 5, 6, 7, 4138088 instead of 4, 5, 6, 7

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    My test driver works just fine on multiple compilers and through a debug trace. Show me the driver you're using that gives you that output. Chances are you're building the list improperly.
    My best code is written with the delete key.

  5. #5
    Registered User
    Join Date
    Feb 2002
    Posts
    37
    My printlist function.

    Code:
    void PrintList(struct Node * L)
    {
        struct Node * P = L;
    
        if (L == NULL)
            printf("Empty list\n");
        else
        {
            do
            {
                P = P->Next;
                printf( "%d ", P->element);
            } while(P->Next != NULL);
            printf("\n");
        }
    }

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >My printlist function.
    Okay...Tell me, does your call to MergeSort look something like this?
    Code:
    list = MergeSort(list);
    Where list is the dummy node for your list? If so, it should be:
    Code:
    list->Next = MergeSort(list->Next);
    That way the dummy node isn't sorted along with the rest of the list.

    Also, I didn't notice that you were using a dummy head, so my comments about the Insert function were incorrect.
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Hum, you're wondering why you have 5, 6, 7, 4138088 instead of 4, 5, 6, 7 as output.
    Its simple: in Java whenever a new variable is created, it is initialized by default with 0 value for primitive types, or null for pointers, which in C is the same stuff ( but not in Java ). For C, I think this happens only in gcc. Any other compiler you have to initialize variables

    Code:
    do{
        P = P->Next;
        printf( "%d ", P->element);
    }while(P->Next != NULL);
    If you look carefully to you're code, you should realize that you have no warranty that p->next is in fact null, because when you allocate memory to the new node, you don't clear the next field, therefore the cicle doesn't end and you're presented with a random value, from the next->element field, caused by the not initialized memory allocation. You can use calloc to allocate memory initialized with all bytes to 0, declared in stdlib.h. That way you don't need to worry with initialization, or calling ZeroMemory, or memset.
    I've been looking at your insert function... What happens when you create the very first node? The later nodes are inserted at the beginning, therefore you have to put the next field of the first node to NULL.
    Plus, in java you have
    Code:
    if ((list1 == null) || (list1.getLink() == null)
             return null;
    A Java feature that you don't have in C is a dynamic verification for boolean sentences that breaks the boolean test when the boolean value is know. Confused?? If list1 == null is true, the second boolean test isn't verified because "true || something" is always true. The same stuff with 'and' and false at the beginning. In C this doesn't happen, unless you have a good compiler with optimized code.
    Code:
    if ((list1 == NULL) || (list1->Next == NULL))
        return list1;
    Therefore if list1 is null the second test crashes the program, because you're trying to get an object pointed by null.
    Do this instead
    Code:
    if (list1 == NULL)
        return list1;
    if(list1->Next == NULL)
       return list1;
    This way if list1 is null, or list1->next is null, both ifs will work fine.
    Last edited by xErath; 06-21-2004 at 10:10 PM.

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >For C, I think this happens only in gcc.
    Any compiler is allowed to default initialize local memory with 0. IIRC, Borland compilers do this too. But it would be wise to assume your compiler does not so that your code will be more portable.

    >You can use calloc to allocate memory initialized with all bytes to 0
    Best avoided. calloc can catch the unaware off-guard because only integral values are guaranteed to be zero initialized correctly. The equivalent of 0 for floating-point and pointer values may not be all bits zero, which is what calloc does.

    >What happens when you create the very first node?
    The first node is a dummy header created elsewhere, probably manually in the calling function or with a make_list function:
    Code:
    struct Node *
    make_list(void)
    {
      struct Node *head = malloc(sizeof *head);
    
      if (!head) {
        return NULL;
      }
      head->Next = NULL;
    
      return head;
    }
    Notice how head->element is left uninitialized because it's not needed. The dummy header's purpose is to simplify list operations by eliminating a special case. Though this only works if the header is ignored by the processing code, which is what I think the OP failed to do in calling MergeSort. Thus, the header is sorted along with the other nodes and the uninitialized element is incorrectly printed.

    >Therefore if list1 is null the second test crashes the program
    No it doesn't. Logical AND and logical OR are short circuited in C, just like in Java. The test is correct and will not crash if list1 is null.
    My best code is written with the delete key.

  9. #9
    Registered User
    Join Date
    Feb 2002
    Posts
    37
    Think now the problem has been solved.

    IntLinkedList.h

    Code:
    #ifndef _INTLINKEDLIST_H_
    #define _INTLINKEDLIST_H_
    
    struct Node
    {
        int element;
        struct Node * Next;
    };
    
    struct Node * makeEmpty(struct Node * l);
    struct Node * merge(struct Node * list1, struct Node * list2);
    struct Node * mergeSort(struct Node * list1);
    struct Node * split(struct Node * list1);
    void destroyList(struct Node * l);
    void insert(int x, struct Node * l);
    void printList(struct Node * L);
    
    #endif
    IntLinkedList.c

    Code:
    #include "IntLinkedList.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    struct Node * makeEmpty(struct Node * l)
    {
        if (l != NULL)
            destroyList(l);
        
        l = malloc(sizeof(struct Node));
        
        if (l == NULL)
            fprintf(stderr, "Error in memory allocation.\n");
        
        l->Next = NULL;
    
        return l;
    }
    
    void insert(int x, struct Node * l)
    {
        struct Node * temp = malloc(sizeof(struct Node));
    
        if (temp == NULL)
            fprintf(stderr, "Error in memory allocation.\n");
    
        temp->element = x;
        temp->Next = l->Next;
        l->Next = temp;
    }
    
    void destroyList(struct Node * l)
    {
        struct Node * temp;
        struct Node * z = l->Next;
        
        l->Next = NULL;
    
        while (z != NULL)
        {
            temp = z->Next;
            free(z);
            z = temp;
        }
    }
    
    void printList(struct Node * l)
    {
        struct Node * z = l;
    
        if (l == NULL)
            printf("Empty list\n");
        else
        {
            do
            {
                z = z->Next;
                printf("%d ", z->element);
            } while (z->Next != NULL);
            printf("\n");
        }
    }
            
    struct Node * mergeSort(struct Node * list1)
    {
    	struct Node * list2;
    
    	if ((list1 == NULL) || (list1->Next == NULL))
    		return list1;
    
    	list2 = split(list1);
    
    	list1 = mergeSort(list1);
    	list2 = mergeSort(list2);
    
    	return merge(list1, list2);
    }
    
    struct Node * split(struct Node * list1)
    {
    	struct Node * list2;
    
    	if ((list1 == NULL) || (list1->Next == NULL))
    		return NULL;
    
        list2 = list1->Next;
    	list1->Next = list2->Next;
    	list2->Next = split(list2->Next);
    
    	return list2;
    }
    
    struct Node * merge(struct Node * list1, struct Node * list2)
    {
    	if (list1 == NULL)
    		return list2;
    	if (list2 == NULL)
    		return list1;
    	if (list1->element < list2->element)
    	{
    		list1->Next = merge(list1->Next, list2);
    		return list1;
    	}
    	else
    	{
    		list2->Next = merge(list1, list2->Next);
    		return list2;
    	}
    }

  10. #10
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Quote Originally Posted by Prelude
    >Therefore if list1 is null the second test crashes the program
    No it doesn't. Logical AND and logical OR are short circuited in C, just like in Java. The test is correct and will not crash if list1 is null.
    Gee it does?? Cool...
    Quote Originally Posted by Prelude
    Best avoided. calloc can catch the unaware off-guard because only integral values are guaranteed to be zero initialized correctly. The equivalent of 0 for floating-point and pointer values may not be all bits zero, which is what calloc does.
    Quote Originally Posted by xErath
    You can use calloc to allocate memory initialized with all bytes to 0
    Like I said, all bytes to zero, not exactly int or floats to zero

  11. #11
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Like I said, all bytes to zero, not exactly int or floats to zero
    The way I read your statement was in the context of a pointer, and all bits zero is not guaranteed to be the equivalent of a null pointer.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 11:03 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 09:04 PM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 11:01 AM
  4. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

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