2017-05-06 7 views
1

これは私のコードです。私はCとポインタにはかなり新しいので、おそらくポインターに関する間違いです。ジェネリック型の配列がMaxHeapであるかどうかを調べるアルゴリズム

#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関数は単にエラーをキャッチしようとするためにここにいる)

おかげ

+2

'void **'はポインタの配列であり、要素の配列ではありません。 – Barmar

+0

'isMaxHeap'は、配列の各要素のサイズを知ってから、ポインタを' char * 'に変換し、インデックスにサイズを乗じて加算する必要があります。 – Barmar

答えて

1

を知りません配列をvoid **にキャストしてください。ポインタの配列を持っていても、データの配列だけがあればそれは適切でしょう。

各配列要素のサイズを関数に渡す必要があります。関数は配列要素にアクセスするために配列ポインタをchar *にキャストする必要があります。コンパイラ関数に渡す配列要素のオフセットを取得するには、配列のインデックスでサイズを掛ける必要があります(これは、型付きの配列をインデックスするときに自動的に行われますが、関数内で動作するため、関数でエミュレートする必要があります。ジェネリックアレイ)。

子ノードに間違ったインデックスも使用していました。左の子はindex * 2 + 1、右の子はindex * 2 + 2です。

最後に再帰呼び出しを行うときは、index == 0の特殊ケースを持つ必要はありません。

isMaxHeap()を呼び出すときに&arrayを使用する必要はありません。これは、配列が関数の引数として使用されたときに自動的にポインタに減衰するためです。

#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; 
} 
+0

この部分、*(int *)e1 - あまり明確ではありません。したがって、e1はvoidへのポインタとして入ってきます。それはmemアドレスです。 (int *)e1はこれをメモリアドレスの整数値に変換します。 *(int *)e1はそのメモリアドレスを逆参照しています。あれは正しいですか? –

+0

また、変数variableの目的は、配列がどのような型であってもかまいません。これは正しいです? –

+0

'(int *)e1'はvoidポインタを' int'へのポインタに変換します。次に、 '*'を使用してそれを逆参照して整数値を取得します。あなたは 'size'変数の目的について正しいです。 – Barmar

関連する問題