c - 如何在c中实现通用链表

Question

我想在 c 中创建一个通用链表，下面是我创建它的方式，但我不确定这是否是正确的方式，我在堆中为 struct uniqueOrderedList_t 分配了一个新内存，然后在堆中为元素分配一个新内存，因为我希望它是通用的，这是正确的方法吗？那么“下一个指针”呢，我是否也需要为它分配内存？

#the .h file contain:
typedef void* Element;
typedef struct uniqueOrderedList_t* UniqueOrderedList;
UniqueOrderedList uniqueOrderedListCreate(/*some parameters*/);

---

#the .c file:
struct uniqueOrderedList_t{
  Element element;
  struct uniqueOrderedList_t* next;  
};

uniqueOrderedList uniqueOrderedListCreate(/*some arguments*/){
   UniqueOrderedList newList = malloc(sizeof(*newList));
 if(!newList){
  return NULL;
 }
 newLust->element = malloc(sizeof(Element));
   if(!element){
     return NULL;
   }
 newList->next = NULL;

}

Answer 1

第一步是正确获取连接节点的所有繁琐细节。 @chux 在评论中有很好的建议 - 先用 int 或 float 类型实现它以确保它是正确的。

更大的问题是用什么代替/*some parameters*/，以使列表通用。具体来说，您应该为 add_node 函数的“value”参数使用什么类型。

唯一可以从任何其他类型来回自由转换的类型是 void*。您可以直接将指针的副本存储在节点中 - 但这意味着您需要确保它们指向的变量永远不会超出范围。您永远无法将堆栈局部变量的地址添加到列表中。

有几种解决方法。

1. 您可以跟踪项目大小并使用 malloc 和 memcpy 创建足以容纳数据的节点。

   一个。创建列表时声明项目大小。 list = makelist(sizeof(myType))。这最适合存储尺寸的独特头部类型。

   强制用户传递每个节点的大小:list = add_node(list, &item, sizeof(item)) 。

   策略 1b，但使用宏来传递大小:#define add_node(l,item) (add_node_impl(l, &item, sizeof(item))

这些策略的缺点是没有类型安全。编译器不会检测您是否将字符串传递给 float 列表。

1. 您可以使用宏为您的可列类型生成特定函数

   #define VALUE_T MyType
#define LISTOF(type) 类型##列表
LISTOF(VALUE_T) add_node(LISTOF(VALUE_T) l, VALUE_T v) {
/* alloc(sizeof(VALUE_T))，从 &v 复制，链接到 l */
}

这种策略更安全，但宏量很大，这使得它很难正确执行，也很难调试。它最终像更明确版本的 C++ 模板一样工作，您必须确保为您使用的每种不同类型生成的代码副本。