通用链接列表？

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

更好的方法是提取链接处理(是什么使结构成为一个列表节点)，然后通过从节点结构开始每个可列表结构来重用它。

就像这样：

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 *)，它消除了限制，但带来了其他限制(更多的堆分配，当数据很小时很烦人)。

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);

这样，您可以在列表中添加任何您想要的内容。只是小心地有一个比较功能和破坏功能。

Answer 3

使用结构中的空指针，可以很容易地实现泛型链接列表。

下面是我创建的这样一个列表的一个例子：

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;
}

C是创建指向struct的指针列表的示例。