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;
	}
}

>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;
}

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

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 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");
    }
}

>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.

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.

>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.

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;
	}
}

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...

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.

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

>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.