Incompatible Pointer Type passing Argument in C?

Question

I'm trying to implement a merge sort on a linked list. Running into a problem which yields the following errors:

student@wheezyupsec:~/CS305/HW4$ make
gcc -c sort.c
sort.c: In function ‘mergeSortHelper’:
sort.c:70:2: warning: passing argument 1 of ‘mergeSort’ from incompatible pointer type [enabled 
by default]
sort.c:34:6: note: expected ‘struct listNode **’ but argument is of type ‘struct listNode *’
sort.c:70:2: warning: passing argument 1 of ‘mergeSort’ from incompatible pointer type [enabled  
by default]
sort.c:34:6: note: expected ‘struct listNode **’ but argument is of type ‘struct listNode *’
sort.c:70:2: error: invalid use of void expression
sort.c:70:2: error: invalid use of void expression
make: *** [sort.o] Error 1

Can anyone see my error. It has something to do with the mergeSortHelper where I make a recursive statement. It wants a double pointer rather than a single pointer that is given. Not sure how to do it otherwise however. I have put my sort.c code below. Thanks for the help.

 /* 
 * sort.c
 * 
 * Author: CS305 STUDENT ADD YOUR NAME HERE.
 * 
 * Description: Contains sorting functions that operate on the linked
 * list implementation for the company entry node found in
 * list.[c,h].
 *
 */

 #include <stdio.h>
 #include <stddef.h>
 #include <stdlib.h>
 #include <string.h>
 #include <math.h>

 #include "list.h"
 #include "sort.h"


 // Function prototypes for helper functions used only within this
 // file.  They are declared as static since they should be global
 // function declarations available only to this file.
 static listNode * mergeSortHelper(listNode * head, listNodeCompareFcn compare);
 static listNode * merge(listNode * l1, listNode * l2, listNodeCompareFcn compare);


/* mergeSort()
 *
 * CS305 students should *not* alter this function for HW4.  Nope
 * Don't do it.
 */
void mergeSort(listNode ** listPtr, listNodeCompareFcn compare)
{
// mergeSort() calls mergeSortHelper which performs the actual
// merge sort algorithm.  This function simply points the head
// of the list at the result of the sorting.
*listPtr = mergeSortHelper(*listPtr, compare);
}

// CS305 Students must implement the function stubs below.  To maximize points earned
// on the homework, students should also supply function comment headers as well as
// document the function bodies with useful comments.


/* mergeSortHelper()
*
* CS305 students must implement this function for HW4.
*/
listNode * mergeSortHelper(listNode * head, listNodeCompareFcn compare)
{
listNode * chop = head;
listNode * other = head->next;
int n = count(head);
int i = 0;
while (i<((n/2) - 1))
{
    //advance chop and other
    chop = chop->next;
    other = other->next;
    i++;
}
chop->next = NULL;

//return head;

//return merge(mergesort(head, compare), mergesort(other, compare), compare);

return merge(mergeSort(head, compare), mergeSort(other, compare), compare);

}

/* merge()
* Parameters: 1. l1: the first linked list to be merged.
*             2. l2: the second linked list to be merged.
*
* Description: Merge two sorted linked lists and return the merged
*              list.
*
* CS305 students must implement this function for HW4.
*
*/
listNode * merge(listNode * l1, listNode * l2, listNodeCompareFcn compare)
{
listNode * head;
//Base Case
if(l1 == NULL)
{
    return l2;
}
if(l2 == NULL)
{
    return l1;
}
//recursive case
if(compare(l1, l2))
{
    head = l1;
    head->next=merge(l1->next, l2, compare);
}
else
{
    head = l2;
    head->next = merge(l1, l2->next, compare);
}

return head;

}

/* alphabetCompare()
*
* Given two pointers to listNode, return 1 if the first one's
* companyName is lexicographically less than the second one.
* Otherwise, return 0.
* 
* For example, if l1->companyName is 'aaaa' and l2->companyName is
* 'aaab' then l1->companyName is less than l2->companyName.
* 
* CS305 students must implement this function for HW4.
* 
*/
int alphabetCompare(listNode * l1, listNode * l2)
{
if(strcmp(l1->entryPtr->companyName,l2->entryPtr->companyName)<0)
{
    return 1;
}
else
{
    return 0;
}
}

 /* distanceCompare()
 *
 * Given two pointers to listNode, return 1 if the first one's
 * latitude + longitude place it closer to the University of Portland
 * Bell Tower than the second one.  Otherwise, return 0.
 *
 * CS305 students must implement this function for HW4.
 *
 * For full points, the comparison should be made based on the
 * distance between two points on a sphere.  For 80% credit
 * a simple comparison can be made between two points on a plane.  
 *
 */
int distanceCompare(listNode * l1, listNode * l2)
{
//convert longitude and latitude of bell tower
//coordinates to radians
long upLonRadians = BELL_TOWER_LON/(180/PI);
long upLatRadians = BELL_TOWER_LAT/(180/PI);
//convert radians of bell tower coordinates 
//to spherical coordinates (x,y,z)
long upX = cos(upLatRadians) * cos(upLonRadians);
long upY = cos(upLatRadians) * sin(upLonRadians);
long upZ = sin(upLatRadians);
//convert longitude and latitude of company
//coordinates in l1 and l2 to radians
long comp1LonRadians = (l1->entryPtr->latitude)/(180/PI);
long comp1LatRadians = (l1->entryPtr->longitude)/(180/PI);
long comp2LonRadians = (l2->entryPtr->latitude)/(180/PI);
long comp2LatRadians = (l2->entryPtr->longitude)/(180/PI);
//convert radians of company coordinates 
//to spherical coordinates (x,y,z) for
//both companies
long comp1X = cos(comp1LatRadians) * cos(comp1LonRadians);
long comp1Y = cos(comp1LatRadians) * sin(comp1LonRadians);
long comp1Z = sin(comp1LatRadians);
long comp2X = cos(comp2LatRadians) * cos(comp2LonRadians);
long comp2Y = cos(comp2LatRadians) * sin(comp2LonRadians);
long comp2Z = sin(comp2LatRadians);
//find distance between bell tower and
//company 1 and distance between bell
//tower and company 2.
long dist1 = arccos((upX*comp1X)+(upY*comp1Y)+(upZ*comp1Z))*EARTH_RADIUS;
long dist2 = arccos((upX*comp2X)+(upY*comp2Y)+(upZ*comp2Z))*EARTH_RADIUS;
//compare distances between two companies.
//if company 1 distance is closer than
//company 2, return 1, otherwise return 0.
if(dist1<dist2)
{
    return 1;
}
else
{
    return 0;
}

}

Answer 1

In the line:

return merge(mergeSort(head, compare), mergeSort(other, compare), compare);

you are calling the external interface to mergeSort() which returns void. You are getting errors in part because mergeSort() takes a listNode ** and you are passing a listNode *, and in part because it doesn't return a value but you are trying to pass the non-existent value to another function.

You could fix the indirection problem with:

mergeSort(&head, compare);
mergeSort(&other, compare);
return merge(head, other, compare);

But it is probably simpler/better to use the internal interface, mergeSortHelper():

return merge(mergeSortHelper(head, compare), mergeSortHelper(other, compare), compare);

Answer 2

you can pass &header and &other to the mergesort function call.It will just avoids the compiler warnings but you need to look at the functionality of your sorting. Example you can call your function like this mergesort(&head,compare) or mergesort(&other,compare).

Answer 3

Signature of mergeSort()

void mergeSort(listNode ** listPtr, listNodeCompareFcn compare)

Signature of merge()

listNode * merge(listNode * l1, listNode * l2, listNodeCompareFcn compare)

That means, the first argument of merge() should be of type listNode *, whereas in your case,

return merge(mergeSort(head, compare), mergeSort(other, compare), compare);

its void.

Same for the second argument, incompatible.

Hint: try to display the line number corresponding your code and check the error/warning messages.