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
通用列表可能是单向链表,并且可能假定列表中的项具有以下结构:
typedef struct list_item list_item;
struct list_item
{
list_item *next;
...data for node...
};
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
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;
这个小例子中有一些有趣的事情:
struct list_head
,而不是目标结构体(在上面的示例中,它们分别指向第一个列表的&(foo->mylist)
和第二个列表的&(foo->another_list)
)。所有的列表操作函数都接受struct list_head
的指针(大多数函数根本不关心它是单独的头节点还是嵌入节点之一)。要从struct list_head
到目标结构体,请使用list_entry
宏(与linux/kernel.h头文件中的containter_of
宏相同),它会扩展为简单的指针减法。
由于它是带有头结点的双向链表,您可以在O(1)
时间内执行以下操作:
为了我的教学,我开发了这个“通用”列表模块,可能是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
C语言及其标准库并没有提供任何针对列表的特定函数。
但是有一些库为C语言提供了许多有用的函数,支持其他编程语言中已知的数据类型:http://library.gnome.org/devel/glib/2.18/glib-data-types.html
如上所述,我尝试使用宏的方法来创建列表操作函数。 创建插入操作例程很容易,但是创建删除和遍历操作却很困难。以下是列表结构和插入例程的签名:
#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);