1

アルゴリズムの知識をブラッシュアップしたかったので、次の本を使用しています:一言で言えばアルゴリズム

65 ページに、挿入ソートのアルゴリズムが掲載されています。アルゴリズムは非常に単純で、理解するのは簡単です。私の問題は、彼らがそれを実装した方法から来ています。私は主にマネージ言語 (C#/Java) で作業しているため、ポインタのカンフーはちょっとさびています。彼らが提供するコードサンプルは次のとおりです。

void sortPointers(void **ar, int n, int(*cmp)(const void *, const void *)) {
    int j;
    for(j = 1; j < n; j++) {
        int i = j - 1;
        void* value = ar[j];

        while(i >= 0 && cmp(ar[i], value) > 0) {
            ar[i+1] = ar[i];
            i--;
        }

        ar[i+1] = value;
    }
}

実際の例を得るために追加したものは次のとおりです。

int cmp(const void* t1, const void* t2) {
    if(t1 > t2) {
        return 1;
    }
    else if(t2 > t1) {
        return -1;
    }
    else {
        return 0;
    }
}

void main() {
    int values[] = { 51, 3, 5, 60, 9, 2, 7};

    sortPointers((void**)values, 7, cmp);

    for(int i = 0; i < 7; i++) {
        cout << values[i] <<  " ";
    }
}

これは機能しますが、理由と方法が完全にはわかりませんか? また、メイン関数で (void **) キャストが機能するのはなぜですか? ダブル ポインター インダイレクションを使用したのはなぜですか?

学校に戻ると、複数の間接参照を使用した唯一の場所は、多次元配列を動的に割り当てるときでした。私が知っている唯一の他の用途は、メソッドに渡すポインターが保持するアドレスを変更できる必要がある場合です。

さらに、コードを次のように変更したところ、問題なく動作しました。

void sortPointers2(int* arr, int n, int (*cmp)(int, int)) {
    int j;
    for(j = 1; j < n; j++) {
        int i = j - 1;
        int value = arr[j];

        while(i >= 0 && cmp(arr[i], value) > 0) { 
            arr[i+1] = arr[i];
            i--;
        }

        arr[i+1] = value;
    }
}

int cmp2(int t1, int t2) {
    if(t1 > t2) {
        return 1;
    }
    else if(t2 > t1) {
        return -1;
    }
    else {
        return 0;
    }
}

void main() {
    int values[] = { 51, 3, 5, 60, 9, 2, 7};

    sortPointers2(values, 7, cmp2);

    for(int i = 0; i < 7; i++) {
        cout << values[i] <<  " ";
    }
}

基本的で明白な何かが欠けていると確信しています。これを読んで、1つか2つのアイデアに参加してくれた人に感謝します. 追加の詳細が必要な場合、または用語を台無しにした場合はお知らせください。

編集: 最初の cmp 関数のタイプミスを修正

4

1 に答える 1

2

例に正しく従っている場合、void **実際には(void *)[];であるため、彼らは a を使用します。型指定されていないメモリの配列。比較関数には、型指定されていないメモリ ( ) への 2 つのポインターが与えられvoid *、データを比較するように求められます。

あなたが理解していないのは、最初の例では、配列は値の配列ではなく、ポインターの配列でなければならないということです。配列は次のようになります。

int *val0 = malloc(sizeof(int)); *val0 = 51;
int *val1 = malloc(sizeof(int)); *val1 = 3;
// ... for all values
int *values[] = { val0, val1, val2, ... };

次に、比較関数は、指定されたポインターではなく、値cmpに基づいて比較値を返す必要があります。コード：

int cmp(const void* t1, const void* t2) {
    if((const int)(*t1) > (const int)(*t2)) {
        return 1;
    }
    else if((const int)(*t2) > (const int)(*t1)) {
        return -1;
    }
    else {
        return 0;
    }
}

このように、型指定されていないメモリへのポインターを指定すると、比較関数はそれらのポインターで 2 つの整数を見つけ、それらの値を比較します。

関数が本のコードで機能した唯一の理由cmpは、並べ替え関数に、配列が型指定されていないメモリへのポインターでいっぱいであると伝えていたためです。実際には整数の配列でした。次に、比較関数にメモリへのポインターが与えられますが、これは実際には単なる整数であり、ポインターを値であるかのように比較します。この場合、そうでした。

本のアルゴリズムが a を使用する理由は、void **それが一般的であるためです。このsort関数は、任意のデータを保持する配列を取得し、汎用データを比較関数に渡すことができます。比較関数は、ポインターを逆参照し、それらのアドレスのデータを必要に応じて解釈できます。

于 2013-07-09T21:42:54.017 に答える