C中的通用列表操作函数？
什么是C中的通用列表操作函数？ （当我浏览一些材料时，我看到了这一点。）
这个函数和一个可以接受任何元素的函数有什么区别？
它们是一样的吗？ 如果它们不相同，我们如何单独实施？
通用列表可能是单链接的，并且可能假设列表中的项具有如下结构：
typedef struct list_item list_item; struct list_item { list_item *next; ...data for node... }; 使用此布局，您可以编写函数来仅使用下一个指针来操作列表。
有时，’ ...data for node... ‘将是一个简单的’ void * ‘; 也就是说，列表项将包含指向列表中下一个节点的指针（如果没有下一个节点，则为NULL）和指向数据的指针。
typedef struct list list; struct list { list *next; void *data; };
由于您可以将任何指针转换为’ void * ‘，因此您可以在列表中添加任何数据类型 – 但您的代码必须知道如何处理它们。
你问的是’a’通用列表函数，但可能没有一个单function – 全部设计，当然也不是一个简单的设计。 有许多可能的函数集可以创建通用列表函数。 一套灵感来自Lisp，包括：
void *car(list *lp); // Return the data for the first item on the list list *cdr(list *lp); // Return the tail of the list list *cons(list *lp1, list *lp2); // Construct a list from lists lp1 and lp2 list *cond(list *lp, void *data); // Append data item to list
您可能希望提供测试列表是否为空以及其他一些项目的function。
在Koenig的“ Ruminations on C ++ ”中可以找到一个很好的阐述， 无论是在C ++中 。 这些想法很容易适应C – 它并不难（尽管C中的存储管理比C ++更难）。
C没有“通用”指针或对象的概念 – 你可以得到的最接近的是使用void*指针。 如果您希望一段代码能够处理任何数据类型，那么您几乎必须使用void*指针。 对于大小不大于指针的数据类型，可以在类型和void*之间进行转换; 对于较大的数据类型，您必须使用动态内存并使void*成员指向动态内存。 请注意内存泄漏！
typedef struct list_node { struct list_node *next; void *data; } list_node; void list_insert(list_node *node, void *data) { // ... }
另一方面，如果要为每种可能的数据类型生成代码，则必须使用宏，然后为可能使用的每种数据类型实例化宏。 例如：
#define DEFINE_LIST(type) \ typedef struct list_node_##type { \ struct list_node_##type *next; \ type data; \ } #define IMPLEMENT_LIST_INSERT(type) \ void list_##type##_insert(list_node_##type *node, type data) { \ ... \ } DEFINE_LIST(int); // defines struct list_node_int DEFINE_LIST(double); // defines struct list_node_double IMPLEMENT_LIST_INSERT(int); // defines list_int_insert IMPLEMENT_LIST_INSERT(double); // defines list_double_insert
Linux内核在其linux / list.h头文件中的C中有一个有趣的通用链表实现。 它是一个带有头节点的双向链表，如下所示：
struct mystruct { ... /* Contains the next and prev pointers */ struct list_head mylist; ... /* A single struct can be in several lists */ struct list_head another_list; ... }; struct list_head mylist_head; struct list_head another_list_head;
这个小例子中有些有趣的事情：
- 列表节点嵌入在目标结构中，不需要数据指针。
- 列表节点不必位于目标结构的开头。
- 单个结构可以同时位于多个链接列表中。
- 列表中的next和prev指针指向
struct list_head，而不指向目标结构（在上面的示例中，它们指向第一个列表的&(foo->mylist)和第二个列表的&(foo->another_list)列表）。
所有列表操作函数都指向struct list_head （并且大多数都不关心它是单独的头节点还是其中一个嵌入节点）。 要从struct list_head获取到目标结构，可以使用list_entry宏（与linux / kernel.h头中的containter_of宏相同），它将扩展为简单的指针减法。
由于它是带有头节点的双向链表，因此可以在O(1) ：
- 检查列表是否为空，或者节点是否在任何列表中。
- 获取任何其他节点之后或之前的节点（如果节点是头部，则获取列表的第一个或最后一个元素）。
- 在任何其他节点之前或之前插入节点（如果节点是头部，则在列表的开头或末尾插入）。
- 从列表中删除节点（您只需要指向节点本身的指针即可）。
- 其他几项行动。
根据我的教导，我开始开发这个“通用”列表模块，可能是linux内核的简化版本，包含额外但未发现的bug，并且使用gcc扩展…欢迎任何评论！
#ifndef _LISTE #define _LISTE #include typedef struct liste_s { struct liste_s * suivant ; } * liste ; #define newl(t) ( (liste) malloc ( sizeof ( struct liste_s ) + sizeof ( t ) ) ) #define elt(l,t) ( * ( ( t * ) ( l + 1 ) ) ) #define liste_vide NULL #define videp(l) ( l == liste_vide ) #define lvide() liste_vide #define cons(e,l) \ ({ liste res = newl(typeof(e)) ; \ res->suivant = l ; \ elt(res,typeof(e)) = e ; \ res ; }) #define hd(l,t) ({ liste res = l ; if ( videp(res) ) exit ( EXIT_FAILURE ) ; elt(res,t) ; }) #define tl(l) ({ liste res = l ; if ( videp(res) ) exit ( EXIT_FAILURE ) ; res->suivant ;}) #endif
C及其标准库不提供任何列表特定function。
但是有些库有许多有用的C函数，它们支持其他编程语言中已知的数据类型： http ： //library.gnome.org/devel/glib/2.18/glib-data-types.html
如上所述，我尝试使用MACROS方法来创建列表操作函数。 它很容易创建INSERT操作例程但很难创建删除和遍历操作。 在它之后是列表结构和INSERT例程签名：
#define LIST_DEFINE(type) \ struct list_node_##type \ { \ type *data; \` struct list_node_##type *next; \ }; LIST_INSERT(&ListHead,&Data, DataType);
哪里：
ListHead – 链表的负责人
Data – 将为其创建新节点并在节点中插入数据的数据DataType – 是否传递了数据的数据类型
仅供参考，我在函数中分配内存并复制新创建的节点中传递的所有数据，并将节点附加到链表中。
现在，当创建LIST_DELETE例程时，将使用数据中的唯一标识符来标识需要删除的节点。 该标识符也在MACRO例程中作为密钥传递，该密钥将在MACRO扩展中被替换。 例行签名可以是：
LIST_DELETE(&ListHead, DataType, myvar->data->str, char*);
哪里：
ListHead – 链表的负责人
DataType – 是数据的数据类型
myvar->data->str – 唯一键
char* – 密钥类型
现在，当扩展密钥时，相同的密钥不能用于比较，就像我们写的那样
if((keytype)ListHead->data->key == (keytype)key)
它扩展到
ListHead->data->myvar->data->str == myvar->data->str
这里没有变量，如： ListHead->data->myvar->data->str
因此，这种方法无法编写删除例程，并且由于遍历和搜索例程也使用唯一键，因此它们也将面临同样的问题。
而且，在一个不相关的说明中，如何确定唯一键的匹配逻辑，因为唯一键可以是任何东西。
我一直在尝试不同的东西。 这是如何解决问题的另一个视角
如果我们有以下结构：
typedef struct token { int id; char *name; struct token *next; } Token;
我们需要创建一个返回链表尾部的函数，但该函数对任何链表都应该是通用的，所以：
void* tail(void* list, void* (*f)(void *)) { void *head = list; while(f(head) != NULL) { head = f(head); } return head; }
现在将需要创建一个函数来负责在我们的自定义结构与尾函数中的通用可用性之间建立桥梁。 通过这种方式，我们有：
void* nextToken(void *a) { Token *t = (Token *) t; return (void *) (a->next); }
最后我们可以简单地使用：
Token *listTokens; (...) Token *lastToken = tail(listTokens, nextToken);