C中的通用列表操作函数？

Question

什么是C中的通用列表操作函数？(当我浏览一些材料时,我看到了这一点.)

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

它们一样......？如果它们不相同,我们如何单独实施它们？

Answer 1

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

Answer 2

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

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'通用列表函数,但可能没有一个单功能全部设计,当然也不是一个简单的设计.有许多可能的函数集可以创建通用列表函数.一套灵感来自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++更难).