C: Передача по ссылке между несколькими функциями?

Question

Я пытаюсь передать по ссылке (точнее, указателем) между несколькими функциями. Я понимаю основы прохождения по ссылке и успешно справился с этим для отдельных функций. Кажется, я не понимаю, как передать одну переменную по ссылке по нескольким функциям.

int main(int argc, char const *argv[]) 
{ 
    int* quicksort(int*, int, int, long long int*); 
    int *sortedList = malloc(MAX_LENGTH * sizeof(int)); 
    long long int compCount=0; 
    sortedList = quicksort(LIST, 0, MAX_LENGTH-1, &compCount); 
    printf("%lld", compCount); 
    return 0; 
} 

int* quicksort(int* A, int l, int r, long long int* compCount) { 
    int partition(int*, int, int, long long int*); 
    int p; 
    if (!(l < r)) { 
     return A; 
    } 
    else { 
     p = partition(A, l, r, compCount); 
     quicksort(A, l, p-1, compCount); 
     quicksort(A, p+1, r, compCount); 
    } 
    return A; 
} 

int partition(int *A, int l, int r, long long int* compCount) { 
    int i, j, p, tmp; 
    i = l + 1; 
    p = l; 

    for (j = l + 1; j <= r; j++) { 
     if (A[j] < A[p]) { 
      tmp = A[i]; 
      A[i] = A[j]; 
      A[j] = tmp; 
      i = i+1; 
     } 
    } 
    compCount += r-l; 
    tmp = A[l]; 
    A[l] = A[i-1]; 
    A[i-1] = A[l]; 
    return i-1; 
} 

Получаю значение compCount = 0 в конце этого. Я знаю, что могу решить эту проблему, используя глобальную переменную, но я бы предпочел не использовать глобальную.

Как я неправильно использую свои указатели?

Answer 1

Вы правильно передаете указатели между функциями. Проблема в том, что вы обновляете указатель вместо того, на что он указывает.

compCount += r-l; 

должно быть:

*compCount += r-l; 

Unrelated к этому вопросу, сортировка производится на месте, так sortedList будет назначен тот же указатель в качестве исходного списка, и ваш malloc является ненужным и будет просочиться.

Answer 2

Что вы называете ссылкой, вы фактически передаете указатель по значению. Когда вы передаете указатель, содержание указателя может быть изменен путем разыменования, так что вы должны сделать:

*compCount += r-l; 

Answer 3

Обратите внимание, что результат quicksort (int *) бесполезно. Подпись сбивает с толку: можно было подумать, что quicksort принимает массив A и возвращает отсортированную копию A (A не изменяется). Ясно, что A изменен на месте. Итак, какова заинтересованность в возвращении A? Заметим, что 2 рекурсивных обращения к quicksort просто игнорируют возвращаемые значения. Это возвращаемое значение бесполезно. Кстати: LIST в основном (не объявлен)? Разве это не должно быть SortedList?

Эта подпись вашей функции должна быть:

void quicksort(int* A, int l, int r, long long int* compCount); 

Теперь вы можете использовать возвращаемое значение для возврата числа сравнений (кстати long достаточно):

long quicksort(int* A, int l, int r) { 
    int partition(int*, int, int, long*); 
    int p; 
    if (!(l < r)) { 
     return 0; 
    } else { 
     long compCount = 0; 
     p = partition(A, l, r, &compCount); 
     compCount += quicksort(A, l, p-1); 
     compCount += quicksort(A, p+1, r); 
    } 

    return compCount; 
} 

Дополнительное замечание: partition может быть упрощен, так как теперь он всегда принимает compCount = 0 таким образом:

*compCount += r-l; 

становится

*compCount = r-l; 

и, таким образом, больше нет необходимости инициализировать compCount в quicksort:

long quicksort(int* A, int l, int r) { 
    int partition(int*, int, int, long*); 
    int p; 
    long compCount; 

    if (!(l < r)) { 
     return 0; 
    } 

    p = partition(A, l, r, &compCount); 
    return compCount + quicksort(A, l, p-1) + quicksort(A, p+1, r); 
}