5

什么是 C 中的通用列表操作函数？（我在浏览一些材料时看到了这一点。）

这个函数和可以接受任何类型元素的函数有什么区别？

他们是一样的吗……？如果它们不相同，我们如何单独实现它们？

4

7 回答 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
于 2008-11-28T17:06:55.723 回答
5

通用列表可能是单链接的，并且可能假设列表中的项目具有如下结构：

typedef struct list_item list_item;

struct list_item
{
    list_item *next;
    ...data for node...
};

使用这种布局，您可以编写函数来仅使用 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

您可能希望提供测试列表是否为空以及其他一些项目的能力。

在 Koenig 的“ Ruminations on C++ ”中可以找到一个很好的说明，诚然是在C++ 中。这些想法可以很容易地应用到 C 中——它并不难（尽管 C 中的存储管理比 C++ 中的更难）。

于 2008-11-28T16:53:54.547 回答
3

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到目标结构，请使用宏（与linux/kernel.h头文件中的宏list_entry相同），它扩展为简单的指针减法。containter_of

由于它是一个带有头节点的双向链表，您可以在O(1)：

  • 检查列表是否为空，或者节点是否不在任何列表中。
  • 获取任何其他节点之后或之前的节点（如果该节点是头部，则获取列表的第一个或最后一个元素）。
  • 在任何其他节点之后或之前插入一个节点（如果该节点是头部，则在列表的开头或结尾插入）。
  • 从列表中删除一个节点（您只需要指向节点本身的指针即可执行此操作）。
  • 其他几个操作。
于 2008-11-29T16:12:02.947 回答
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
于 2012-12-06T11:02:36.483 回答
1

C 及其标准库不提供任何特定于列表的函数。

但是有许多有用的 C 函数库支持从其他编程语言已知的数据类型：http: //library.gnome.org/devel/glib/2.18/glib-data-types.html

于 2008-11-30T03:32:20.437 回答
0

如上所述，我尝试使用 MACROS 方法来创建列表操作函数。创建 INSERT 操作例程很容易，但很难创建 Delete 和遍历操作。紧随其后的是列表结构和 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

因此，这种方法无法编写删除例程，并且由于遍历和搜索例程也使用唯一键，它们也会面临同样的问题。

并且，在不相关的说明中，如何确定唯一键的匹配逻辑，因为唯一键可以是任何东西。

于 2012-06-18T05:30:13.360 回答
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);
于 2015-10-28T04:00:36.557 回答