Общий связанный список?

Question

Мне было интересно, возможно ли использовать обобщенную функцию для связанных списков в C, (я не хочу делать это в C ++, но в C), например:

struct first_struct
{
    struct first_struct *next;
    int a;
    int b;
};
struct second_struct
{
     struct second_struct *next;
     int a;
     int b;
     int c; // just one more variable than first-struct
};

заставляю ли я каждый раз создавать функцию для двух списков:

add_node(struct first_struct *mystruct)// doesn't matter the function here juste let's assume they add correctly a node
add_node1(struct second_struct *mystruct)
//and so on each time i want to make some others function always make them twice

или есть лучший способ сделать это?

Answer 1

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

Последнее (указатели функций) не имеет решающего значения для построения связанного списка, но важно, если вы хотите сделать что-то полезное с данными связанного списка, например печать.

Вот полный рабочий пример:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct node {
    void *data;
    struct node *next;
} node;


int lst_nodeAdd(
    node **head,
    node **tail,
    const void *data,
    size_t szData);

void lst_nodePrint(
    node *head,
    void(*print)(const void *));

void lst_nodeFree(node *head);

/* PRINTING FUNCTIONS */
void print_int(const void *a);
void print_string(const void *str);


int main(void)
{
    const char *str[] = {
        "0x0001",
        "0x0002",
        "0x0003",
    };

    // head & tail
    node *head = NULL; 
    node *tail = NULL;

    // List of strings
    lst_nodeAdd(&head, &tail, str[0], strlen(str[0]) + 1);
    lst_nodeAdd(&head, &tail, str[1], strlen(str[1]) + 1);
    lst_nodeAdd(&head, &tail, str[2], strlen(str[2]) + 1);

    lst_nodePrint(head, print_string);
    lst_nodeFree(head);
    head = NULL;
    tail = NULL;
    //....................................................

    // List of ints
    int int_array[] = {
        0,
        1,
        2,
    };
    lst_nodeAdd(&head, &tail, &int_array[0], sizeof(int));
    lst_nodeAdd(&head, &tail, &int_array[1], sizeof(int));
    lst_nodeAdd(&head, &tail, &int_array[2], sizeof(int));

    lst_nodePrint(head, print_int);
    lst_nodeFree(head);
    head = NULL;
    tail = NULL;


    system("PAUSE");
    return 0;
}


int lst_nodeAdd(
    node **head,
    node **tail,
    const void *data,
    size_t szData)
{
    void *tmp;
    tmp = malloc(sizeof(node));

    if (!tmp)
    {
        return 0;
    }

    ((node *)tmp)->next = NULL;
    ((node *)tmp)->data = malloc(szData);

    if (!((node *)tmp)->data)
    {
        free(tmp);
        return 0;
    }

    memcpy(((node *)tmp)->data, data, szData);

    if (!*head)
    {
        *head = (node *)tmp;
    }
    else
    {
        (*tail)->next = (node *)tmp;
    }
    *tail = (node *)tmp;
    return 1;
}

void lst_nodePrint(
    node *head,
    void(*print)(const void *))
{
    while (head)
    {
        print(head->data);
        head = head->next;
    }
}

void lst_nodeFree(node *head)
{
    node *tmp = head;
    while (head)
    {
        head = head->next;
        free(tmp->data);
        free(tmp);
        tmp = head;
    }
}

void print_int(const void *a)
{
    printf("%d\n", *(const int *)a);
}

void print_string(const void *str)
{
    puts((const char *)str);
}

Answer 2

Лично я реализовал общий связанный список: он работает, предоставляя функцию для сравнения двух узлов и дополнительную функцию для уничтожения узла (свободная строка, закрытие файла и т. Д.).

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

typedef struct link {
    void        *data;
    struct link *previous;
    struct link *next;
} link_s;

typedef struct list {
    link_s *head;
    link_s *tail;
    size_t nbLink;

    /* function pointer */
    int    (*Data_Compare)(const void *data1, const void *data2);
    void   (*Data_Destructor)(void *data);
} list_s;

#define LIST_CONSTRUCTOR(f_compar, f_destructor) {.head = NULL, \
                                                  .tail = NULL, \
                                                  .nbLink = 0, \
                                                  .Data_Compare = f_compar, \
                                                  .Data_Destructor = f_destructor}

void List_Constructor(list_s *self, int (*Data_Compare)(const void *data1, const void *data2), void (*Data_Destructor)(void *data));
void List_Destructor(list_s *self);

bool List_Add(list_s *self, void *data);

void *List_RemoveByLink(list_s *self, link_s *link);
void *List_RemoveByData(list_s *self, void *data);
void *List_RemoveByCondition(list_s *self, bool (*Data_Condition)(const void *data));

void List_DestroyByLink(list_s *self, link_s *link);
void List_DestroyByData(list_s *self, void *data);

void List_DestroyByCondition(list_s *self, bool (*Data_Condition)(const void *data));

void List_Sort(list_s *self);
void List_Merge(list_s *to, list_s *from);
void List_Reverse(list_s *self);

Таким образом, вы можете добавить в список все, что захотите. Просто будьте осторожны, чтобы иметь функцию сравнения propre и уничтожить функцию.

Answer 3

Вы можете довольно просто реализовать общий связанный список, используя указатель void в своей структуре.

Вот пример такого списка, созданного мной:

list.c

#include <stdlib.h>
#include "list.h"
#include <malloc.h>
#include <stdio.h>
#include <string.h>

void listNew(list* list, unsigned int elementSize, freeMemory freeFn,        
printList print) {

    list->numOfElem = 0;
    list->freeFn = freeFn;
    list->pr = print;
    list->head = NULL;
    list->sizeOfElem = elementSize;
}

node * listPushFront(list *list, void* data) {

    node *listNode = (node*)malloc(sizeof(node));

    if (listNode == NULL) {

        return NULL;
    }

    listNode->object = malloc(sizeof(list->sizeOfElem));

    if (listNode->object == NULL) {

        return NULL;
    }

    memcpy(listNode->object, data, list->sizeOfElem);

    listNode->pNext = list->head;
    list->head = listNode;

    list->numOfElem++;

    return listNode;
}

void listDestroy(list *list)
{
    node *current;

    while (list->head != NULL) {
        current = list->head;
        list->head = current->pNext;

        if (list->freeFn) {
            list->freeFn(current->object);
        }

        free(current->object);
        free(current);
    }
}

void listPrint(list *l) {

    node* temp = l->head;
    int i = 0;

    if (temp == NULL) {

        printf("\nEmpty list.");
        return;
    }

    while (temp) {

        printf("\nPrint element %d", i);

        l->pr(temp->object);
        temp = temp->pNext;

        i++;
    }
}

list.h

#ifndef __LIST_H
#define __LIST_H

typedef void(*freeMemory)(void*);
typedef void(*printList)(void*);

typedef struct _node {

    void* object;
    struct _node* pNext;

}node;

typedef struct _list {

    unsigned int sizeOfElem;
    unsigned int numOfElem;
    node* head;
    freeMemory freeFn;
    printList pr;

}list;

void listNew(list* list, unsigned int elementSize, freeMemory freeFn,             
printList print);
node * listPushFront(list *list, void* data);
void listDestroy(list *list);
void listPrint(list *l);

#endif

main.c

#include <stdlib.h>
#include "list.h"
#include <stdio.h>
#include <string.h>

typedef struct _TLV {

    unsigned int tag;
    unsigned int length;
    unsigned char* value;

}TLV;


void listFree(void* data) {

    TLV** ptr = (TLV**)data;

    free((*ptr)->value);
}

void Print(void* data) {

    TLV** ptr = (TLV**)data;

    printf("\nTag = %d", (*ptr)->tag);
    printf("\nLength = %d", (*ptr)->length);
    printf("\nValue = ");

    for (int i = 0; i < (*ptr)->length; i++) {

        printf("%d", (*ptr)->value[i]);
    }
}

TLV* allocateTLV(unsigned int tag, unsigned int length, unsigned char* 
value) {

    TLV* elem = (TLV*)malloc(sizeof(TLV));

    if (elem == NULL) {

        return NULL;
    }

    elem->tag = tag;
    elem->length = length;
    elem->value = (unsigned char*)malloc(length);

    if (value == NULL) {

        return NULL;
    }

    memcpy(elem->value, value, length);

    return elem;
}

int main()
{
    list l;
    TLV* tag;

    unsigned char test2[2] = { 1,2 };
    unsigned char test3[3] = { 1,2,3 };
    unsigned char test4[4] = { 1,2,3,4};

    listNew(&l, sizeof(TLV*), listFree, Print);

    tag = allocateTLV(2, sizeof(test2), test2);
    if (tag != NULL) {

        listPushFront(&l, &tag);
    }

    tag = allocateTLV(3, sizeof(test3), test3);
    if (tag != NULL) {

        listPushFront(&l, &tag);
    }

    tag = allocateTLV(4, sizeof(test4), test4);
    if (tag != NULL) {

        listPushFront(&l, &tag);
    }

    listPrint(&l);

    listDestroy(&l);

    return 0;
}

main.c является примером создания списка указателей на структуру TLV.

Answer 4

Лучший способ состоит в том, чтобы абстрагироваться от обработки ссылки (что превращает структуру в узел списка), а затем повторно использовать ее, запуская каждую структуру с возможностью отображения со структурой узла.

Вроде так:

struct list_node {
  struct list_node *next;
};


struct first_struct {
  struct list_node list_node;
  int a;
  int b;
};


struct second_struct {
  struct list_node list_node;
  int a;
  int b;
  int c;
};

Затем создайте список функций, которые имеют дело с (указателями) struct list_node.

Это обычно называют «навязчивыми списками», поскольку для этого требуется, чтобы структура данных уровня приложения «знала», что ее можно поместить в список. Это также означает, что экземпляр структуры может быть только в одном списке одновременно.

Другой способ - создать библиотеку списков, которая работает только с указателями на данные (void *), которая снимает ограничение, но вместо этого приносит другие (большее выделение кучи, раздражает, когда данных мало).