如何在C中实现Python集

Question

我有一个关于如何在 C 中实现 Python 风格 'Set' 的问题。我正在编写一个洪水填充算法，它必须使用一个类似堆栈的列表来跟踪哪些像素正在等待着色。我希望该函数 return 像素着色的顺序（我正在使用该算法从起点追踪圆线，我不希望它在运行时错过像素，这必须最后被吸走 - 这种行为发生在传统堆栈或递归填充函数中）。

偶然（原型代码）我发现使用 Python 'Set' 作为堆栈可以提供我正在寻找的正确填充样式。这个集合的两个特征似乎是造成这种情况的原因：

先进先出行为
当添加一个已经在集合中的像素时，集合不会改变（这实际上似乎不是必需的，但很高兴拥有 - 我想这取决于是否增加了调用超过了在集合中搜索重复项的开销）

我可以将像素添加为线性索引，这样我就可以保持基于整数的队列（如果有帮助的话）。任何不涉及大量循环的想法？

Answer 1

我不确定你是否需要自己实现一个，或者你是否可以简单地使用像 Collections-C 这样的库来实现一些基本的数据结构，包括队列 (FIFO)。

如果你需要自己实现，我给你一个简短的示例代码...

Answer 2

所以您想要的是 "unique queue" - 也许您可以改写问题的标题以更好地反映这一点。

您可以通过组合 hash table, which has set-like behaviour with O(1) performance, and a doubly linked list 来实现独特的 queue，它可以像 queue 一样使用。

typedef struct {
    hashtable *set;
    linkedlist *queue;
} unique;

添加到 queue 时，您首先检查该项目是否已在哈希 table 中，只有当它不存在时才将其添加到哈希 table和链表。您可以 return NULL 成功添加，或者现有项目（如果它已经存在）以便调用者知道发生了什么：

void *unique_add(unique *uniq, void *data)
{
    void *existing = hashtable_find(uniq->set, data);
    if (!existing) {
        hashtable_add(uniq->set, data);
        linkedlist_add_tail(uniq->queue, data);
    }
    return existing;
}

从 queue 中删除时，您从链表和散列 table 中删除项目，如下所示：

void *unique_remove(unique *uniq)
{
    void *data = linkedlist_remove_head(uniq->queue);
    if (data) {
        hashtable_remove(uniq->set, data);
    }
    return data;
}

我写了一个 hash table in C and a linked list in C，欢迎您使用它们来获得灵感。

您可以更进一步，通过使用具有 4 个指针的链表节点来创建哈希 [=43=] 和链表 queue 的混合数据结构，如下所示：

struct unique_node {
    struct unique_node *next_in_queue;
    struct unique_node *next_in_bucket;
    struct unique_node *previous_in_queue;
    struct unique_node *previous_in_bucket;
};
typedef struct unique_node unique_node;

然后，您将使用 next_in_bucket 和 previous_in_bucket 指针将散列 table 存储桶实现为链表，同时按 queue 顺序连接节点使用 next_in_queue 和 previous_in_queue 指针。

如何在C中实现Python集

How to implement Python Set in C

c

python

stack

flood-fill