标签 python c stack flood-fill
<分区>
我有一个关于如何在 C 中实现 Python 风格的“Set”的问题。我正在编写一个填充算法，它必须使用一个类似堆栈的列表来跟踪哪些像素正在等待着色。我希望该函数返回像素着色的顺序(我正在使用该算法从起点跟踪圆线，并且我不希望它错过像素，因为它必须在最后 - 这种行为发生在传统堆栈或递归填充函数中)。
偶然(原型(prototype)代码)我发现使用 Python“Set”作为堆栈可以提供我正在寻找的正确填充样式。这个集合的两个特征似乎是造成这种情况的原因:
我可以添加像素作为线性索引，这样我就可以根据需要保持队列整数。任何不涉及大量循环的想法？
最佳答案
所以你想要的是一个“独特的队列”——也许你可以改写你的问题的标题以更好地反射(reflect)这一点。
您可以通过组合 hash table 来实现一个独特的队列，具有 O(1) 性能的类似集合的行为，以及 doubly linked list ，可以像队列一样使用。
typedef struct {
hashtable *set;
linkedlist *queue;
} unique;
添加到队列时，首先检查该项目是否已经在哈希表中，只有当它不存在时才将其添加到哈希表和链表中。您可以在成功添加时返回 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;
}
从队列中删除时，您从链表和哈希表中都删除了项目，如下所示:
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和一个 linked list in C ，因此欢迎您使用这些来获得灵感。
您可以更进一步，通过使用具有 4 个指针的链表节点来创建一个哈希表和链表队列混合的数据结构，如下所示:
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 指针将哈希表桶实现为链表，同时使用 按队列顺序连接节点>next_in_queue 和 previous_in_queue 指针。
关于python - 如何在 C 中实现 Python Set，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41897718/