我应该在ANSI C中使用什么来创建链接列表



在Java中,我使用了LinkedList<T>

有没有任何标准,或者其他一些库,可以在C中创建LinkedLists?

不,C没有这样的东西。如果你能使用C++,就有std::list

您必须自己用C.编写结构

正如其他人所说,C中没有对链表的标准库支持。这意味着你要么可以自己滚动(就像大多数人在C编码生涯中曾经做过的那样),要么可以向其他库寻求支持。

对于大多数用途,您会发现"侵入式"实现是合适的。您可以修改现有结构,使其包含指向列表中下一项的指针(如果您正在执行双链接列表,则包括上一项)。

typedef struct TheStruct TheStruct;
struct TheStruct
{
    ...the real data...
    TheStruct *next;
  //TheStruct *prev;
};

您的列表现在由一个指向标题项目的简单指针组成:

TheStruct *head = 0;
TheStruct *allocated_node = new_TheStruct(value1, value2, ...);
assert(allocated_node->next == 0);
// Insert new allocated node at head of list
allocated_node->next;
head = allocated_node;

如果让线程访问相同的列表,那么您必须担心线程问题,以此类推。

因为这段代码非常简单,所以处理它的频率最高。从列表中删除节点比较棘手,但您可以编写一个函数来完成

人们用不同复杂度的宏来修饰这个基本方案,这样处理不同类型列表的代码就可以使用相同的宏。Linux内核使用一组基于宏的链表来管理其链表数据结构。

"侵入式"实现的另一种选择(之所以称为"插入式"实现,是因为它需要更改结构以包括列表指针)是具有一些通用的列表机制:

typedef struct GenericList GenericList;
struct GenericList
{
    void        *data;
    GenericList *next;
  //GenericList *prev;
};

现在,您可以将未修改结构的指针放入列表中。你失去了某种类型的安全性;没有什么可以阻止您将随机的不同结构类型添加到应该是同构的列表中。您还必须为GenericList结构与指向的数据分开分配内存。

  • 这样做的一个优点是,单个数据项可以同时位于多个单独的列表上。*这样做的一个缺点是,单个数据项可能会意外地出现在多个列表上,或者同时出现在单个列表中多次

您还必须确保了解数据的所有权属性,以便正确释放数据(不泄漏、不多次释放、释放后不访问)。相比之下,管理列表本身的内存就是孩子的游戏。

使用GenericList机制,您可能会有一个函数库来管理列表操作。同样,搜索应该显示这样的列表的实现。

C(目前)还没有提供任何标准的容器结构。你必须自己滚。

标准C库中没有Lists。你可以使用的一个非常好的C库是PBL-这里的程序库。它的接口类似Java。您可以从这里下载

默认情况下它不存在,但制作起来很容易。

基本上,链表是指向第一个元素的头指针,以及指向null的结束文件。

元素实际上是节点,包含对象和指向下一个节点的指针。

因此,制作一个基本的类是非常容易的,尽管在C语言中可能会很痛苦,因为没有类,只有结构。

相关内容

  • 没有找到相关文章

最新更新