在C中编写类模板通用代码的最佳方法是什么？

Question

我需要用C中的泛型类型编写AVL树.我知道的最好的方法是使用[void*]并编写一些用于创建,复制,赋值和销毁的函数.请告诉我一些更好的方法.

Answer 1

我将给您一个关于如何在 C 中实现泛型功能的示例。该示例位于链接列表中，但我确信您可以根据需要在 AVL 树上调整它。

首先，您需要定义列表元素的结构。一种可能的（最简单的实现）：

struct list_element_s {
    void *data;
    struct list_element_s *next;

};
typedef struct list_element_s list_element;

其中“数据”将充当您要保存信息的“容器”，“下一个”是对直接链接元素的引用。（注意：您的二叉树元素应包含对右/左子元素的引用）。

创建元素结构后，您将需要创建列表结构。一个好的做法是让一些成员指向函数：析构函数（需要释放“数据”所占用的内存）和比较器（以便能够比较两个列表元素）。

列表结构的实现可能如下所示：

struct list_s {
    void (*destructor)(void *data);    
    int (*cmp)(const void *e1, const void *e2);
    unsigned int size;
    list_element *head;
    list_element *tail;

};
typedef struct list_s list;

设计数据结构后，您应该设计数据结构接口。假设我们的列表将具有以下最简单的界面：

nmlist *list_alloc(void (*destructor)(void *data));
int list_free(list *l);
int list_insert_next(list *l, list_element *element, const void *data);
void *list_remove_next(list *l, list_element *element);

在哪里：

• list_alloc ：将为您的列表分配内存。
• list_free ：将释放为列表分配的内存，以及 list_element(s) 保存的所有“数据”。
• list_insert_next ：将在 'element' 旁边插入一个新元素。如果“element”为 NULL，则插入将在列表的头部进行。
• list_remove_next ：将删除并返回由 'element->next' 保存的 (void*)'data' 。如果'element'为NULL，它将执行“列表->头部删除”。

现在功能实现：

list *list_alloc(void (*destructor)(void *data))
{
    list *l = NULL;
    if ((l = calloc(1,sizeof(*l))) != NULL) {
        l->size = 0;
        l->destructor = destructor;
        l->head = NULL;
        l->tail = NULL;
    }
    return l;
}

int list_free(list *l)
{
    void *data;
    if(l == NULL || l->destructor == NULL){
        return (-1);
    }    
    while(l->size>0){    
        if((data = list_remove_next(l, NULL)) != NULL){
            list->destructor(data);
        }
    }
    free(l);
    return (0);
}

int list_insert_next(list *l, list_element *element, const void *data)
{
    list_element *new_e = NULL;
    new_e = calloc(1, sizeof(*new_e));
    if (l == NULL || new_e == NULL) {
        return (-1);
    }
    new_e->data = (void*) data;
    new_e->next = NULL;
    if (element == NULL) {
        if (l->size == 0) {
            l->tail = new_e;
        }
        new_e->next = l->head;
        l->head = new_e;
    } else {
        if (element->next == NULL) {
            l->tail = new_e;
        }
        new_e->next = element->next;
        element->next = new_e;
    }
    l->size++;
    return (0);
}

void *list_remove_next(list *l, list_element *element)
{
    void *data = NULL;
    list_element *old_e = NULL;
    if (l == NULL || l->size == 0) {
        return NULL;
    }
    if (element == NULL) {
        data = l->head->data;
        old_e = l->head;
        l->head = l->head->next;
        if (l->size == 1) {
            l->tail = NULL;
        }
    } else {
        if (element->next == NULL) {    
            return NULL;    
        }    
        data = element->next->data;
        old_e = element->next;
        element->next = old_e->next;
        if (element->next == NULL) {
            l->tail = element;
        }
    }
    free(old_e);
    l->size--;
    return data;
}

现在，如何使用简单的通用链表实现。在以下示例中，列表的作用类似于堆栈：

#include <stdlib.h>
#include <stdio.h>
#include "nmlist.h"

void simple_free(void *data){
    free(data);
}

int main(int argc, char *argv[]){
    list *l = NULL;
    int i, *j;

    l = list_alloc(simple_free);
    for(i = 0; i < 10; i++){
        j = calloc(1, sizeof(*j));
        if(j != NULL){
            *j = i;
            list_insert_next(l, NULL, (void*) j);
        }
    }

    for(i = 0; i < 10; i++){
        j = (int*) list_remove_next(l, NULL);
        if(j != NULL){
            printf("%d \n", *j);
        }
    }

    list_free(l);

    return (0);
}

请注意，您可以使用引用更复杂结构的指针来代替“int *j”。如果这样做，请不要忘记相应地修改“列表->析构函数”函数。