CでPythonセットを実装する方法

Question

私はCでPythonスタイルの 'Set'を実装する方法について質問があります。私はフラッドフィルアルゴリズムを書いていますし、スタックのようなリストを使ってピクセルが着色されるのを待っています。関数は、ピクセルが色付けされている順序を返すようにしたい（私は、アルゴリズムを使って開始点から丸い線をトレースしていますが、ピクセルを見逃すことはありません。この挙動は、従来のスタックまたは再帰的な埋め込み関数のいずれかで発生します）。

偶然（プロトタイプコード）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; 

あなたはその後、実装しハッシュテーブルはnext_in_bucketとprevious_in_bucketポインタを使用してリンクリストとしてバケットを作成すると同時に、next_in_queueとprevious_in_queueポインタを使用してキューの順序でノードを接続します。

Answer 2

あなた自身で実装する必要があるかどうか、またはキュー（FIFO）を含む基本的なデータ構造を実装するCollections-Cのようなライブラリを単純に使用できるかどうかはわかりません。

あなたが自分でそれを実装する必要がある場合、私はあなたに短いコード例を与えるだろう...