C에서 파이썬 세트 구현 방법

Question

C에서 파이썬 스타일 '설정'을 구현하는 방법에 대한 질문이 있습니다. 홍수 채우기 알고리즘을 작성 중이며 추적 할 수있는 스택과 같은 목록을 사용해야합니다 픽셀이 착색되기를 기다리고 있습니다. 함수는 픽셀이 채색되어있는 순서를 반환하기를 원합니다 (알고리즘을 사용하여 시작점에서 둥근 선을 추적하고 알고리즘을 사용하여 픽셀을 놓치고 싶지는 않습니다. 끝 -이 동작은 재래 적 스택 또는 재귀 적 채우기 함수에서 발생합니다.

우연히 (프로토 타입 작성 코드) 나는 파이썬 '세트'를 스택으로 사용하여 필자가 찾고자하는 정확한 스타일을 제공한다는 것을 발견했다. 이것에 대한 책임을 져야하는 것이 세트의 두 가지 특징은 다음과 같습니다

• FIFO 동작
픽셀가 (이 실제로하지 않는 것 세트가 변경되지 않습니다 세트에 이미 추가
• 요구 사항이지만 좋은 것입니다 - 전화 수가 증가하면 중복 세트를 검색하는 오버 헤드를 능가하는지에 따라 달라집니다)

픽셀을 선형 인덱스로 추가 할 수 있으므로 도움이된다면 정수를 기반으로 큐하십시오. 루핑이 많이 필요하지 않은 아이디어?

Answer 1

은 그래서 당신이 원하는 것은 "독특한 큐"입니다 - 아마도 당신은 더 나은 귀하의 질문의 제목을 바꾸어 말하다 수 이것을 반영하십시오.

O (1) 성능과 비슷한 동작을하는 hash table과 큐처럼 사용할 수있는 doubly linked list을 결합하여 고유 한 큐를 구현할 수 있습니다. 큐에 추가 할 때

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

, 당신은 첫 번째 항목이 이미 해시 테이블에없는 것을 확인하고, 그렇지 않은 경우에만 해시 테이블과 링크 된 목록에이 추가 않습니다.

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; 
} 

큐에서 제거, 링크 된 목록에서 해시 테이블에서 모두 항목을 제거 : 이미이 있다면 발신자가 무슨 일이 있었는지 알 수 있도록 당신은 성공 또한에 NULL을 반환하거나 기존 항목 수 다음과 같이

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과 같은 라이브러리를 사용할 수 있는지 확실하지 않습니다.

당신이 스스로를 구현해야하는 경우, 내가 당신에게 간단한 예제 코드를 제공합니다 ...