Алгоритм, который проверяет, является ли массив универсального типа MaxHeap

Question

Это мой код Я довольно новичок в c и указателях, так что, вероятно, ошибка в указателях.

#include<stdio.h>
#include <stdbool.h>

typedef int (*comparatorPtr)(void*, void*);
bool isMaxHeap(void **heap, int index, int length, comparatorPtr comparator);

/**
 * comparator with pointers (the mistake could be here)
 */
int comparator_integer(void* e1, void* e2) {
  int i1 = *(int *) e1;
  int i2 = *(int *) e2;

  //print 2 elements of array/heap
  printf("I1 heap: %d\n", i1);
  printf("I2 heap: %d\n", i2);
  printf("***************************\n");

  if (i1 == i2) return 0;
  else if (i1 > i2) return 1;
  else return -1;
}

/**
 * Function for check if the array is or isn't a maxHeap
 */
bool isMaxHeap(void **heap, int index, int length, comparatorPtr comparator) {
  if (index > length - 1) return true;

  printf("I'm calling comparator 1 \n%d value index1\n",index);
  if (length > index * 2 && comparator((heap + index), (heap + (index * 2))) < 0) return false;

  printf("I'm calling comparator 2 \n%d value index2\n",index);
  printf("Value lenght %d\n", length);
  if (length > index * 2 + 1 && comparator((heap + index), (heap + ((index * 2) + 1))) < 0) return false;

  printf("I'm calling comparator 3 \n");
  if (index == 0) return isMaxHeap(heap, 1, length, comparator) && isMaxHeap(heap, 2, length, comparator);

  else return isMaxHeap(heap, index * 2, length, comparator) && isMaxHeap(heap, index * 2 + 1, length, comparator);
}

int main() {
  int array[6] = {90, 15, 10, 7, 12, 2}; //maxHeap array
  int length = sizeof(array)/ sizeof(array[0]);
  int index = 0;

  printf("element in position 1: %d\n",*(array + (index*2)+1));
  printf("length %d\n", length);

  isMaxHeap((void **) &array, index, length, &comparator_integer) ? printf("Yes"): printf("No");
return 0;
}

массив является MaxHeap, но я не знаю, почему мой код возвращает № (printf здесь только для того, чтобы попытаться поймать ошибку)

Спасибо

Answer 1

Вы не должны приводить массив к void **, Это было бы уместно, если бы у вас был массив указателей, но у вас просто есть массив данных.

Вам нужно передать размер каждого элемента массива в функцию. Затем функция должна привести указатель массива к char * для доступа к элементам массива. Он должен умножить размер на индексы массива, чтобы получить ответвление элементов массива, которое он передает функции сравнения (это происходит автоматически при индексировании типизированных массивов, но вы должны эмулировать его в своей функции, потому что он работает на универсальный массив).

Вы также использовали неправильные индексы для дочерних узлов. Левый ребенок находится в index * 2 + 1Правильный ребенок находится на index * 2 + 2,

Там нет необходимости иметь специальный случай для index == 0 при совершении рекурсивных вызовов в конце.

Вам не нужно использовать &array при звонке isMaxHeap(), поскольку массивы автоматически распадаются на указатели при использовании в качестве аргументов функции.

#include<stdio.h>
#include <stdbool.h>

typedef int (*comparatorPtr)(void*, void*);
bool isMaxHeap(void *heap, int index, int length, size_t size, comparatorPtr comparator);

/**
 * comparator with pointers (the mistake could be here)
 */
int comparator_integer(void* e1, void* e2) {
    int i1 = *(int *) e1;
    int i2 = *(int *) e2;

    //print 2 elements of array/heap
    printf("I1 heap: %d\n", i1);
    printf("I2 heap: %d\n", i2);
    printf("***************************\n");

    if (i1 == i2) return 0;
    else if (i1 > i2) return 1;
    else return -1;
}

/**
 * Function for check if the array is or isn't a maxHeap
 */
bool isMaxHeap(void *heap, int index, int length, size_t size, comparatorPtr comparator) {
    char *heapbase = heap;
    if (index >= length) {
        return true;
    }

    printf("I'm calling comparator 1 \n%d value index1\n",index);
    if (length > index * 2 + 1 && comparator(heapbase + index * size, heapbase + (index * 2 + 1) * size) < 0) {
        return false;
    }

    printf("I'm calling comparator 2 \n%d value index2\n",index);
    printf("Value lenght %d\n", length);
    if (length > index * 2 + 2 && comparator(heapbase + index * size, heapbase + (index * 2 + 2) * size) < 0) {
        return false;
    }

    printf("I'm calling comparator 3 \n");
    return isMaxHeap(heap, index * 2 + 1, length, size, comparator) && isMaxHeap(heap, index * 2 + 2, length, size, comparator);
}

int main() {
    int array[6] = {90, 15, 10, 7, 12, 2}; //maxHeap array
    int length = sizeof(array)/ sizeof(array[0]);
    int index = 0;

    printf("element in position 1: %d\n",*(array + (index*2)+1));
    printf("length %d\n", length);

    isMaxHeap(array, index, length, sizeof array[0], comparator_integer) ? printf("Yes\n"): printf("No\n");
    return 0;
}