比较函数作为稍后使用的参数

Question

我正在研究通用二叉搜索树，但我很难理解 parameter/argument 传递函数在 C 中的工作原理。我想告诉我的通用 BST，它必须在需要比较时使用 compare_doubles()。

当我在 createBST() 中创建空 BST 时，如何在代码中的某处实例化函数指针？

鉴于此 BST.h :

#include <stddef.h>
#include <stdbool.h>

typedef struct tree_t BinarySearchTree;

/* ------------------------------------------------------------------------- *
 * Creates an empty BST.
 * ARGUMENT
 * comparison_fn_t      A comparison function
 * BinarySearchTree bst = newBST(&compare_doubles);
 * ------------------------------------------------------------------------- */

BinarySearchTree* createBST(int comparison_fn_t(const void *, const void *));
bool insertInBST(BinarySearchTree* bst, const void* key, const void* value);

BST.c :

#include <stddef.h>
#include <stdlib.h>
#include "BinarySearchTree.h"

struct tree_t {
    const void *key;
    const void *value;
    const void *leftChild;
    const void *rightChild;
    //const void *comparison_fn_t; //try to have it as an argument 1st try
};

//int (*compare) (const void *, const void *); //try to save it for later 2nd try

BinarySearchTree* newBST(int comparison_fn_t(const void*, const void*)) {
    BinarySearchTree *binarySearchTree = malloc(sizeof(BinarySearchTree));
    if (!binarySearchTree)
        return NULL;
    binarySearchTree->value = NULL;
    binarySearchTree->key = NULL;
    binarySearchTree->leftChild = NULL;
    binarySearchTree->rightChild = NULL;
    compare = &comparison_fn_t; //1st try
    //binarySearchTree->comparison_fn_t = comparison_fn_t //2nd try
    return binarySearchTree;
}
bool insertInBST(BinarySearchTree* bst, const void* key, const void* value) {
    //other code
    int val = (*compare) (key, bst->key); //1st try
    int val = bst->comparison_fn_t... //2nd try
}

在我的 Main.c 中：

int compare_doubles(const void *a, const void *b) {
    const double *a_ = (const double*) a;
    const double *b_ = (const double*) b;
    return (*a_ > *b_) - (*a_ < *b_);
}

BinarySearchTree *searchTree= createBST(&compare_doubles);
insertInBST(searchTree, key, value);

Answer 1

只需在结构中使用相同的函数指针定义：

struct tree_t {
    const void *key;
    const void *value;
    const void *leftChild;
    const void *rightChild;
    int (*comparison_fn)(const void*, const void*);
};

BinarySearchTree* newBST(int (*comparison_fn)(const void*, const void*)) {
    
    ...
    // assign the fn pointer here
    binarySearchTree->comparison_fn = comparison_fn;
    return binarySearchTree;
}

为了使语法更简单，您可以使用 typedef：

typedef int (*BinaryComparison)(const void*, const void*); 

struct tree_t {
    const void *key;
    const void *value;
    const void *leftChild;
    const void *rightChild;
    BinaryComparison comparison_fn;
};

BinarySearchTree* newBST(BinaryComparison comparison_fn) {
    BinarySearchTree* binarySearchTree = malloc(sizeof *binarySearchTree);
    binarySearchTree->comparison_fn = comparison_fn;
    return binarySearchTree;
}

Answer 2

对于初学者来说，不清楚为什么数据成员 leftChild 和 rightChild 具有类型 const void * 而不是类型 struct tree_t *.

struct tree_t {
    const void *key;
    const void *value;
    const void *leftChild;
    const void *rightChild;
    //const void *comparison_fn_t; //try to have it as an argument 1st try
};

此外，将指向函数的指针存储为该结构的数据成员也没有什么意义，因为在这种情况下，该数据成员将在二叉树的每个节点中重复。

您可以再声明一个结构，例如

struct node_t {
    const void *key;
    void *value;
    struct node_t *leftChild;
    struct Node_t *rightChild;
};

和

struct tree_t {
    struct node_t *head;
    int ( *comparison )( const void *, const void * );
};

typedef struct tree_t BinarySearchTree;

在这种情况下，您可以通过以下方式创建 struct tree_t 类型的对象

BinarySearchTree * createBST( int comparison( const void *, const void * ) )    
{
    BinarySearchTree *tree = malloc( sizeof( *tree ) );

    if ( tree != NULL )
    {
        tree->head = NULL;
        tree->comparison = comparison;
    }

    return tree;
}

int compare_doubles(const void *a, const void *b) {
    const double *a_ = (const double*) a;
    const double *b_ = (const double*) b;
    return (*a_ > *b_) - (*a_ < *b_);
}


int main( void )
{
    BinarySearchTree *tree = createBST( compare_doubles );
    //...
}

比较函数作为稍后使用的参数

Comparison function as argument to use later on

c

function

binary-tree

generic-programming