Модульная структура данных в C с динамическим типом данных

Question

Для моего предстоящего университетского проекта C меня просят иметь модульный код, поскольку C позволяет это. По сути, у меня будет файл .c и соответствующий файл .h для некоторой структуры данных, такой как связанный список, двоичное дерево, хеш-таблица, что угодно ...

Используя в качестве примера связанный список, у меня есть это:

typedef struct sLinkedList {
    int value;
    struct sLinkedList *next;
} List;

Но это заставляет value иметь тип int, и пользователь, использующий эту библиотеку связанного списка, будет вынужден напрямую изменить исходный код библиотеки. Я хочу избежать этого, я хочу избежать необходимости менять библиотеку, чтобы сделать код максимально модульным.

Мой проект, возможно, должен использовать связанный список для списка целых чисел или, может быть, список какой-то структуры. Но я не собираюсь дублировать библиотечные файлы / код и соответственно изменять код.

Как я могу решить это?

Answer 1

К сожалению, не существует простого способа решить эту проблему. Наиболее распространенный подход на чистом C к этому типу ситуаций заключается в использовании void* и копировании значения в выделенную вами память в указатель. Это делает использование сложным, и очень подвержено ошибкам.

Answer 2

Еще одна альтернатива, о которой еще никто не упомянул, можно найти в реализации обобщенного связанного списка list.h ядра Linux. Принцип таков:

/* generic definition */
struct list {
  strict list *next, *prev;
};

// some more code

/* specific version */
struct intlist {
  struct list list;
  int i;
};

Если вы создаете struct intlist* указатели, их можно безопасно приводить (в C) к struct list* указателям, что позволяет вам писать обобщенные функции, которые работают с struct list* и позволяют им работать независимо от типа данных.

Реализация list.h использует некоторый макрос-трюк для поддержки произвольного размещения struct list внутри вашего конкретного списка, но я предпочитаю полагаться на трюк struct cast-to-first-member. Это делает код вызова намного проще для чтения. Конечно, он отключает «множественное наследование» (если вы считаете, что это какое-то наследование), но next(mylist) выглядит лучше, чем next(mylist, list). Кроме того, если вы можете избежать хакерства offsetof, вы, вероятно, окажетесь в лучшей форме.

Answer 3

Вот пример утилит связанного списка в C:

struct Single_List_Node
{
    struct Single_List * p_next;
    void *               p_data;
};

struct Double_List_Node
{
    struct Double_List *    p_next;
    struct Double_List *    p_prev; // pointer to previous node
    void *                  p_data;
};

struct Single_List_Data_Type
{
    size_t                         size; // Number of elements in list
    struct Single_List_Node *      p_first_node;
    struct Single_List_Node *      p_last_node; // To make appending faster.
};

Некоторые общие функции:

void    Single_List_Create(struct Single_List_Data_Type * p_list)
{
    if (p_list)
    {
        p_list->size = 0;
        p_list->first_node = 0;
        p_list->last_node = p_list->first_node;
    }
    return;
}


void    Single_List_Append(struct Single_List_Data_Type *   p_list,
                           void *                           p_data)
{
    if (p_list)
    {
        struct Single_List_Node * p_new_node = malloc(sizeof(struct Single_List_Node));
        if (p_new_node)
        {
            p_new_node->p_data = p_data;
            p_new_node->p_next = 0;
            if (p_list->last_node)
            {
                p_list->last_node->p_next = p_new_node;
            }
            else
            {
                if (p_list->first_node == 0)
                {
                    p_list->first_node = p_new_node;
                    p_list->last_node = p_new_node;
                }
                else
                {
                    struct Single_List_Node * p_last_node = 0;
                    p_last_node = p_list->first_node;
                    while (p_last_node->p_next)
                    {
                        p_last_node = p_last_node->p_next;
                    }
                    p_list->last_node->p_next = p_new_node;
                    p_list->last_node = p_new_node;
                }
            }
            ++(p_list->size);
        }
    }
    return;
}

Вы можете поместить все эти функции в один исходный файл, а объявления функций в заголовочный файл. Это позволит вам использовать функции с другими программами и не придется перекомпилировать все время. void * для указателя на данные позволит вам использовать список с различными типами данных.

(Приведенный выше код поставляется "как есть" и не тестировался ни на одном компиляторе. Ответственность за исправление ошибок несет пользователь примеров.)

Answer 4

В отличие от C ++, где можно использовать template, void * является де-факто C-решением.

Кроме того, вы можете поместить элементы связанного списка в отдельную структуру, например:

typedef struct sLinkedListElem {
    int value; /* or "void * value" */
} ListElem;

typedef struct sLinkedList {
    ListElem data;
    struct sLinkedList *next;
} List;

так, чтобы элементы могли быть изменены без влияния на код ссылки.

Answer 5

Вы можете использовать Void * вместо int. Это позволяет данным быть любого типа. Но пользователь должен знать тип данных.

Для этого, при желании, у вас может быть другой член, представляющий тип. который имеет перечисление {INT, CHAR, float ...}

Answer 6

Именно из-за этой проблемы были разработаны шаблоны для C ++. Подход, который я использовал один или два раза в C, состоит в том, чтобы поле значения было пустым *, и приводило к нему значения при вставке и возвращало их при извлечении. Конечно, это далеко не типобезопасно. Для дополнительной модульности я мог бы написать функции insert_int (), get_mystruct () и т. Д. Для каждого типа, для которого вы это используете, и выполнить там приведение.

Answer 7

Вы можете избежать этого, определив значение как void* value;. Таким способом можно назначить указатель на любой тип данных, но код вызова требуется для приведения и разыменования указателя на правильный тип. Один из способов отслеживать это - добавить короткий char массив к struct, чтобы отметить имя типа.

Answer 8

Поскольку это университетский проект, мы не можем просто дать вам ответ. Вместо этого я бы предложил вам медитировать над двумя функциями C: указателем void (с которым вы, вероятно, сталкивались ранее) и оператором вставки токена (которого у вас может не быть).