Как реализовать набор Python в C

Question

У меня вопрос о том, как реализовать стиль Python «Установить» в C. Я пишу алгоритм заполнения заливки, и он должен использовать список, подобный стеку, чтобы отслеживать, какие пиксели ждут цвета. Я хочу, чтобы функция возвращала порядок, в котором пиксели окрашены (я использую алгоритм для трассировки круглых линий из начальной точки, и я не хочу, чтобы он пропускал пиксели по мере того, как он идет, по которому нужно поднять вверх по конец - это поведение происходит либо с помощью обычного стека, либо с помощью функции рекурсивного заполнения).

Случайно (прототипирующий код) Я обнаружил, что использование Python 'Set' в виде стека дает правильный стиль заполнения, который я ищу. Эти две характеристики этого множества, которые, кажется, ответственны за это, являются:

• поведение FIFO
• Когда пиксель добавил, что уже в наборе множество не меняется (это не на самом деле, кажется, быть требованием, но приятно иметь - я думаю, это зависит от того, увеличение числа вызовов перевешивают над головой поиска множества дубликатов)

я могу добавить пиксели как линейные индексы, так что я могу держать если это помогает. Любые идеи, которые не требуют много циклов?

Answer 1

Так что вы хотите это «уникальные очереди» - может быть, вы могли бы перефразировать название вашего вопроса лучше отражают это.

Вы можете реализовать уникальную очередь, объединив 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; 

Вы бы тогда реализовать таблицы хеш-таблицы в виде связанных списков с помощью указателейи previous_in_bucket, в то же время подключая узлы в порядке очереди с помощью указателей next_in_queue и .

Answer 2

Я не уверен, что вам нужно реализовать один самостоятельно, или если вы можете просто использовать библиотеку, такую ​​как Collections-C, которая реализует некоторые основные структуры данных, включая очередь (FIFO).

Если вам нужно реализовать его самостоятельно, я дам вам краткий пример код ...