C语言中用void*实现通用结构体函数、多态及通用BST的技术咨询

结论：完全可以，针对你给出的struct A和struct B，既可以通过简单方式直接访问key，也能通过额外参数明确控制类型转换逻辑。

一、直接访问共同首成员的极简方案 #

你的两个结构体中key都是第一个成员，根据C标准，结构体的起始地址与它的第一个成员的起始地址完全一致（无内存对齐偏移）。因此在func里可以直接这么写：

void func(void *ptr) {
    // 直接将void*转为int*访问key
    int key_val = *(int*)ptr;
    printf("Key value: %d\n", key_val);
}

调用时直接传入结构体指针即可：

struct A a = {10, 'a'};
struct B b = {20, 3.14f};
func(&a); // 输出10
func(&b); // 输出20

注意：这种方法仅适用于共同成员是结构体第一个成员的场景。

二、通过额外参数实现通用访问的三种方法 #

如果共同成员不在首位置，或需要更严谨的类型控制，可采用以下方式：

1. 传递成员偏移量 #

利用<stddef.h>中的offsetof宏获取key在结构体中的偏移量，通过指针运算定位成员：

#include <stddef.h>

void func(void *ptr, size_t key_offset) {
    // 结构体起始地址 + 偏移量 = key的地址
    int *key_ptr = (int*)((char*)ptr + key_offset);
    int key_val = *key_ptr;
    printf("Key value: %d\n", key_val);
}

调用时传入对应偏移量：

func(&a, offsetof(struct A, key));
func(&b, offsetof(struct B, key));

此方法不受成员位置限制，通用性极强。

2. 传递类型标签+分支转换 #

定义枚举标识结构体类型，在函数内根据类型转换指针：

typedef enum { TYPE_A, TYPE_B } StructType;

void func(void *ptr, StructType type) {
    int key_val;
    switch(type) {
        case TYPE_A:
            key_val = ((struct A*)ptr)->key;
            break;
        case TYPE_B:
            key_val = ((struct B*)ptr)->key;
            break;
        default:
            printf("Unknown type\n");
            return;
    }
    printf("Key value: %d\n", key_val);
}

调用时指定类型：

func(&a, TYPE_A);
func(&b, TYPE_B);

适合类型较少的场景，但新增类型时需修改函数内部的switch分支，扩展性一般。

3. 传递回调函数 #

定义获取key的回调函数，将其作为参数传入func，这是C语言模拟多态的常用方式：

// 回调函数类型：接收结构体指针，返回key值
typedef int (*GetKeyFunc)(void*);

int get_A_key(void *ptr) {
    return ((struct A*)ptr)->key;
}

int get_B_key(void *ptr) {
    return ((struct B*)ptr)->key;
}

void func(void *ptr, GetKeyFunc get_key) {
    int key_val = get_key(ptr);
    printf("Key value: %d\n", key_val);
}

调用时传入对应回调：

func(&a, get_A_key);
func(&b, get_B_key);

扩展性最优，新增结构体时只需编写对应的回调函数，无需修改func代码。

一、void*的用法 #

void*是C语言的通用指针，核心特性：

• 可指向任意类型数据，无需强制转换即可接收其他类型指针（如int*、struct A*直接赋值给void*）
• 不能直接解引用或做指针运算，必须先转换为具体类型指针（如(int*)ptr）
• 常用于实现通用函数（标准库的memcpy、qsort均使用void*作为参数）

二、结构体存储方式与成员偏移量 #

结构体成员按定义顺序布局，但受内存对齐规则影响：

1. 每个成员的起始地址必须是自身大小的整数倍（如int通常占4字节，起始地址需能被4整除）
2. 整个结构体的总大小必须是结构体中最大成员大小的整数倍
3. 第一个成员偏移量永远为0，后续成员偏移量 = 前一个成员偏移量 + 前一个成员大小 + 可能的填充字节

offsetof宏可准确获取成员相对于结构体起始地址的偏移量，其原理是利用空指针的地址运算：

#define offsetof(type, member) ((size_t)&((type*)0)->member)

将0地址强制转为type*，取member的地址数值即为该成员的偏移量。

三、C语言模拟多态的方式 #

C语言无原生多态，但可通过以下方式模拟：

• 通用指针+回调函数：如前面的GetKeyFunc，或标准库qsort通过比较函数实现多态排序
• 结构体内嵌函数指针：定义“基类”结构体存放函数指针，“子类”结构体将基类作为首成员，重写函数指针指向自身实现
• 类型标签+分支判断：通过枚举或整数标识类型，函数内根据类型执行不同逻辑（适合简单场景）

基于上述知识点，通用BST的核心是让节点存储任意类型数据，同时支持自定义key比较逻辑，具体步骤：

1. 定义通用结构体：

// BST节点：存储任意类型数据
typedef struct BSTNode {
    void *data;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode;

// BST控制结构体：存储比较逻辑
typedef struct BST {
    BSTNode *root;
    // 比较两个data的key：返回负数表示a<b，0表示相等，正数表示a>b
    int (*compare)(void *a, void *b);
} BST;

2. 实现核心BST操作：

// 递归插入节点
BSTNode* bst_insert(BSTNode *root, void *data, int (*compare)(void*, void*)) {
    if (root == NULL) {
        BSTNode *new_node = malloc(sizeof(BSTNode));
        new_node->data = data;
        new_node->left = new_node->right = NULL;
        return new_node;
    }
    int cmp = compare(data, root->data);
    if (cmp < 0) {
        root->left = bst_insert(root->left, data, compare);
    } else if (cmp > 0) {
        root->right = bst_insert(root->right, data, compare);
    }
    return root;
}

// 对外插入接口
void bst_insert_data(BST *tree, void *data) {
    tree->root = bst_insert(tree->root, data, tree->compare);
}

3. 为不同结构体实现比较函数：

// 比较struct A的key
int compare_A(void *a, void *b) {
    return ((struct A*)a)->key - ((struct A*)b)->key;
}

// 比较struct B的key
int compare_B(void *a, void *b) {
    return ((struct B*)a)->key - ((struct B*)b)->key;
}

4. 使用通用BST：

// 创建存储struct A的BST
BST a_bst = {NULL, compare_A};
struct A a1 = {5, 'x'}, a2 = {3, 'y'}, a3 = {7, 'z'};
bst_insert_data(&a_bst, &a1);
bst_insert_data(&a_bst, &a2);
bst_insert_data(&a_bst, &a3);

// 创建存储struct B的BST
BST b_bst = {NULL, compare_B};
struct B b1 = {10, 1.5f}, b2 = {8, 2.7f}, b3 = {12, 0.9f};
bst_insert_data(&b_bst, &b1);
bst_insert_data(&b_bst, &b2);
bst_insert_data(&b_bst, &b3);

此设计可让BST处理任意带key的结构体，新增类型只需实现对应的比较函数，完全满足通用化需求。

内容的提问来源于stack exchange，提问作者Jeff