Я приведу вам пример того, как вы можете добиться универсальности в 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.
- list_insert_next: вставит новый элемент рядом с 'element'. Если 'element' равен NULL, вставка будет сделана в начале списка.
- list_remove_next: удалит и вернет (void *) «данные», хранящиеся в «element-> next». Если 'element' имеет значение NULL, он будет выполнять "list-> удаление головы".
А теперь реализация функций:
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" вы можете использовать указатель, который ссылается на более сложные структуры. Если вы это сделаете, не забудьте соответствующим образом изменить функцию 'list-> destructor'.