4

二分探索木を実装しましたが、それを一般的なものにしたいと考えています。コードは次のとおりです。

typedef struct treeNode {
  int data;
  struct treeNode *left;
  struct treeNode *right;
} treeNode;

および関数:

treeNode* FindMin(treeNode *node) {
  if(node==NULL) {
    /* There is no element in the tree */
    return NULL;
  }
  if(node->left) /* Go to the left sub tree to find the min element */
    return FindMin(node->left);
  else 
    return node;
}

treeNode * Insert(treeNode *node,int data) {
  if(node==NULL) {
    treeNode *temp;
    temp = (treeNode *)malloc(sizeof(treeNode));
    temp -> data = data;
    temp -> left = temp -> right = NULL;
    return temp;
  }

  if(data > (node->data)) {
    node->right = Insert(node->right,data);
  }
  else if(data <= (node->data)) {
    node->left = Insert(node->left,data);
  }
/* Else there is nothing to do as the data is already in the tree. */
  return node;
}

treeNode * Delete(treeNode *node, int data) {
  treeNode *temp;
  if(node==NULL) {
    printf("Element Not Found");
  }
  else if(data < node->data) {
    node->left = Delete(node->left, data);
  }
  else if(data > node->data) {
    node->right = Delete(node->right, data);
  }
  else {
    /* Now We can delete this node and replace with either minimum element 
       in the right sub tree or maximum element in the left subtree */
    if(node->right && node->left) {
        /* Here we will replace with minimum element in the right sub tree */
        temp = FindMin(node->right);
        node -> data = temp->data; 
        /* As we replaced it with some other node, we have to delete that node */
        node -> right = Delete(node->right,temp->data);
    }
    else {
        /* If there is only one or zero children then we can directly 
            remove it from the tree and connect its parent to its child */
        temp = node;
        if(node->left == NULL)
            node = node->right;
        else if(node->right == NULL)
            node = node->left;
        free(temp); /* temp is longer required */ 
    }
}
  return node;

}

void PrintInorder(treeNode *node) {
  if (node != NULL) {
    PrintInorder(node->left);
    printf("%d ",node->data);
    PrintInorder(node->right);
  }
}

まず、構造体を変更します

int data;

に

void *data;

より多くのコードで編集:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct treeNode {
  void *data;
  struct treeNode *left;
  struct treeNode *right;
}treeNode;

treeNode * Insert(treeNode *node, void *data, int sizeOfType, int (*compare) (void *arg1, void *arg2)) { 
  if(node==NULL) {
    treeNode *temp;
    temp = malloc(sizeof(*temp));
    temp->data = malloc(sizeOfType);
    memcpy(temp->data, data, sizeOfType);
    temp -> left = temp -> right = NULL;
    return temp;
  }

  if(compare(data, node->data) == 1) {
    node->right = Insert(node->right, data, sizeof(int), compare(data, node->data));
  }
  else if(compare(data, node->data) == -1 || compare(data, node->data) == 0) {
    node->left = Insert(node->left, data, sizeof(int), compare(data, node->data));
  }
  return node;
}

void print(void* a) { 
printf("%d ",*(int*)a); 
}

void InorderGeneric(treeNode *node, void(*p)(void *)) { 
  if (node != NULL) {                                
    InorderGeneric(node->left, p);
    p(node->data);  
    InorderGeneric(node->right, p); 
  }
}

int int_sorter( void *first_arg, void *second_arg ) {
  int first = *(int*)first_arg;
  int second = *(int*)second_arg;
  if ( first < second ) {
    return -1;
  }
  else if ( first == second ) {
    return 0;
  }
  else {
    return 1;
  }
}

int main(void) {
  treeNode *root = NULL;
  int item;
  void *v;

  printf("Add nodes in binary tree:\n");
  while (scanf("%d ", &item) == 1) {
    v = &item;
    root = Insert(root, v, sizeof(int), int_sorter);
  }

  printf("\n---Initial tree---\n");
  printf("IN-order walk of tree:\n");
  InorderGeneric(root, print);
  printf("\n");

  return 0;
 }
4

3 に答える 3

7

使用するデータ型ごとに比較関数を作成し、2つのデータが互いに等しいか大きいか小さいかを知る必要がある各関数に関数ポインターを渡す必要があります。この関数のみが内部データ型を知っている必要があります。

この関数は次のようになります。

int compare_X(const void *d1, const void *d2)

また、関数は、2つのオブジェクトが等しい場合は0を返し、d1が指すオブジェクトが小さい場合は0未満、それ以外の場合は0より大きい値を返す必要があります。特定のツリーに格納しているデータのタイプに応じて、、などcompare_intのさまざまな関数があります。compare_double


次に、2つのオブジェクトを比較する必要がある関数にこの引数を追加します。

int (*cpm_fptr)(const void *, const void *)


たとえば、でInsert、は次のif(data > (node->data))ようになります。

if (cmp_fptr(data, node->data) > 0) /* data > node->data */

また：

if (cmp_fptr(data, node->data) == 0) /* data == node->data */

if (cmp_fptr(data, node->data) < 0) /* data < node->data */


の署名は次のInsertようになります。

treeNode * Insert(treeNode *node, int data, 
                  int (*cpm_fptr)(const void *, const void *))

また、内部タイプがintの場合、次のように呼び出すことができます。

Insert(node, my_int, compare_int);


これは、あらゆるタイプのデータのように機能し、操作できるbsearch方法です。qsort

于 2012-11-05T01:58:08.170 に答える
3

を使用しunionて、いつでも共用体が表すタイプの情報とともに、保存したいデータを表すことができます。以下のようなもの：

typedef struct _generic_data {
    union {
        int         i;              /* Integer */
        long        l;              /* Long */
        float       f;              /* floating point */
        double      d;              /* double precision floating point */
        char        c;              /* char */
        char        *s;             /* c string */
        struct {
            void        *blob;      /* Arbitrary blog of binary data */
            int         size;       /* Size of this blob */
        }           b;              /* You may not really need it
                                     * So you can get rid of this struct
                                     * if you want.
                                     */
    } value;                        /* To access the above values */
    int type_id;                    /* To identify which data type is actually 
                                     * being stored in this generic data struct
                                     */
} generic_data;

もちろんunsigned、完全を期すために、上記の型に対応する型も必要です。type_id要素を明確に識別するために設定します。例えば：

const int char_type_id = 1;
const int long_type_id = 2;
....
const int blob_type_id = 10;
const int error_type_id = -42;

などなので、以下が成立します。generic_data gd;

  • の場合gd.type_id == char_type_id、 thengd.value.cが有効な値です。
  • 残りのタイプも同様です。

だから今、あなたNodeは次のようになります：

typedef struct treeNode {
  generic_data*   data;
  struct treeNode *left;
  struct treeNode *right;
} treeNode;

関数を次のように変更する必要があります

treeNode * Insert(treeNode *node, generic_data* data);
treeNode * Delete(treeNode *node, generic_data* data);

また、2 つの値を比較できる関数も必要generic_dataです。このようなもの：

long compare_generic(generic_data* lhs, generic_data* rhs) {
    if ( lhs == NULL || rhs == NULL ) {
        return error_type_id;
    }
    if ( lhs->type_id != rhs->type_id ) {
        /*
         * ERROR: Trying to compare two different types.
         * Do appropriate error handling here.
         * return some eror code.
         */
        return error_type_id;
    }
    switch( lhs->type_id ) {
        case char_type_id: return (long)(lhs->value.c - rhs.value.c); break;
        case int_type_id:  return (long)(lhs->value.i - rhs.value.i); break;
        /*
         * Something similarly logical for long, float, double.
         * The basic idea if this function returns 0 
         *
         * void *blob allows you to store arbitrary binary data. You 
         * may not need it, but if you do, there should be some way to
         * compare between the two.
         */
        default:
            /*
             * No type_id matches.
             * Handle this error case.
             * return some error code.
             */
            return error_type_id;
            break; /* Just a habbit to always have a break so that
                    * you don't have to deal with special cases.
                    */
    }
}

これは、以下のように既存のコードを置き換えるために使用されます。

  • if(data < node->data)これに：if ( compare_generic( data, node->data ) < 0 )
  • if(data > node->data)これに：if ( compare_generic( data, node->data ) > 0 )
  • if(data == node->data)これに：if ( compare_generic( data, node->data ) == 0 )

値にアクセスする際には、特に注意する必要があります。

于 2012-11-05T02:34:18.030 に答える
0

これを本当にCにしたい場合は、もう少し洗練されたアプローチが必要になります（ツリー内のデータの型を変数に格納し、必要に応じて型キャストを実行します）。

ただし、C ++で同じことを行う場合は、テンプレートを使用できます。Web上で利用可能なテンプレートに関する多数の例があります。

お役に立てれば！

于 2012-11-05T01:51:05.430 に答える