C语言中的通用列表操作函数是什么？ （我在查阅一些资料时看到了这个。）
这个函数和一个可以接受任何类型元素的函数有什么区别？
它们相同吗...？如果它们不同，我们如何分别实现它们？
7个回答
7
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
- Adam Rosenfield
5
通用列表可能是单向链表，并且可能假定列表中的项具有以下结构:
typedef struct list_item list_item;
struct list_item
{
list_item *next;
...data for node...
};
使用这种布局，您可以编写函数来仅使用下一个指针操作列表。
有时，“...节点数据...”将是一个简单的“void *”;也就是说，列表项将包含指向列表中下一个节点（如果没有下一个节点，则为NULL）和指向数据的指针。
typedef struct list list;
struct list
{
list *next;
void *data;
};
由于您可以将任何指针转换为'void *'，因此列表中可以有任何混合数据类型 - 但是您的代码必须知道如何处理它们。
您询问'一个'通用列表函数，但可能不存在单个功能可做所有设计，而且肯定不会是简单的。有许多可能的一组函数可以制作通用列表函数。其中一组受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
你可能希望提供测试列表是否为空的能力，以及其他几个项目。
一篇很好的阐述，虽然是关于C++的，可以在Koenig的 "Ruminations on C++"中找到。这些想法可以很容易地适应到C中-它并不可怕难（尽管C中的存储管理比C ++中更难）。
- Jonathan Leffler
3
Linux内核在其linux/list.h头文件中实现了一个有趣的通用双向链表。它是一个带有头节点的双向链表，使用方法如下：
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)时间内执行以下操作：
- 检查列表是否为空，或者节点是否不在任何列表中。
- 获取任何其他节点之后或之前的节点（如果节点是头节点，则获取列表的第一个或最后一个元素）。
- 在任何其他节点之后或之前插入节点（如果节点是头节点，则在列表的开头或结尾插入）。
- 从列表中删除节点（您只需要指向节点本身的指针即可完成此操作）。
- 其他几个操作。
- CesarB
2
为了我的教学，我开发了这个“通用”列表模块，可能是Linux内核版本的简化版，包含额外的、尚未发现的错误，并使用gcc扩展...
欢迎提出任何意见！
#ifndef _LISTE
#define _LISTE
#include <stdlib.h>
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
- user1251840
1
C语言及其标准库并没有提供任何针对列表的特定函数。
但是有一些库为C语言提供了许多有用的函数，支持其他编程语言中已知的数据类型：http://library.gnome.org/devel/glib/2.18/glib-data-types.html
- stesch
0
如上所述，我尝试使用宏的方法来创建列表操作函数。 创建插入操作例程很容易，但是创建删除和遍历操作却很困难。以下是列表结构和插入例程的签名：
#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
因此，这种方法无法用于编写删除例程，而遍历和搜索例程也使用唯一键，同样会面临相同的问题。
另外，如何确定唯一键的匹配逻辑，因为唯一键可以是任何东西。
- pistonhead1
0
我一直在尝试不同的东西。这是另一种解决问题的视角。
如果我们有以下结构：
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);
- mmcorrelo
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接