时间戳

首页 > 解决方案 > 如何在c中实现通用链表

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

问题描述

我想在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;

}

标签： cgenericsstructlinked-listadt

解决方案

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

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

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

有几种方法可以解决这个问题。

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

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

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

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

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

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

    #define VALUE_T MyType #define LISTOF(type) type ## list LISTOF(VALUE_T) add_node(LISTOF(VALUE_T) l, VALUE_T v) { /* alloc(sizeof(VALUE_T)),copy from &v, link into l */ }

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

推荐阅读