AVL を使用してバイナリ ツリーを構築した後、データが配列にパックされます。
typedef struct {
void **data;
int count;
} t_table;
比較関数は次のようになります。
int cmp(const void *pa, const void *pb)
{
int a = *(int *)pa;
int b = *(int *)pb;
if (a > b)
return +1;
else
if (b > a)
return -1;
else
return 0;
}
avl-tree に挿入し、K&R qsortを使用してポインタの配列を問題なくソートしています。
のサンダード関数を使用したいqsort
のです<stdlib.h>
が、新しい関数を使用するt_table
必要があります ( で必要なポインター変換のためqsort
)、次のようになります。
int cmp(const void *pa, const void *pb)
{
int a = *(int*)(*(void**)pa);
int b = *(int*)(*(void**)pb);
if (a > b)
return +1;
else
if (b > a)
return -1;
else
return 0;
}
関数を変更する必要がある理由を理解しています (C-FAQ を引用):
qsort 比較関数で興味深いポインター変換が必要な理由 (および qsort を呼び出すときに関数ポインターのキャストが役に立たない理由) を理解するには、qsort がどのように機能するかを考えると役に立ちます。qsort は、ソートされるデータの型や表現について何も知りません。メモリの小さなチャンクをシャッフルするだけです。(チャンクについて知っているのは、qsort の 3 番目の引数で指定したサイズだけです。) 2 つのチャンクを交換する必要があるかどうかを判断するために、qsort は比較関数を呼び出します。(それらを交換するには、memcpy と同等のものを使用します。)
stdlib qsort
しかし、2つの比較関数( avl 用と 用void **
)を維持する必要を避けるための代替手段( を使用)があるかどうか疑問に思います