해시 작업 의 기본 루틴 (1)

요약: 해시 표 는 매우 유용 한 데이터 구조 로 특히 Find 작업 에 상수 시간 만 필요 합 니 다. 본 논문 의 해시 표 는 공간 을 이용 하여 충돌 을 피하 고 이 용 률 이 높 습 니 다. (1) 해시 의 기본 데이터 구 조 는 하나의 크기 변수 와 하나의 포인터 배열 (포인터 가 하나의 링크 를 가리 키 는 것) 로 구성 되 어 있 습 니 다.

#define Num 100
#define MinTableSize 5
typedef struct Hashtbl *HashTable;
typedef struct ListNode * List;
struct ListNode
{
    int Element;
    List Next;
};
struct Hashtbl
{
    int TableSize;
    List*  TheLists;
};

(2) 시계 초기 화 에 주의 하 십시오. 주요 구 조 는 포인터 배열 입 니 다. 모든 지침 은 야생 지침 이 므 로 모든 지침 에 해당 하 는 메모리 공간 을 지정 해 야 합 니 다.

HashTable Initialize(int TableSize)
{
    HashTable H ;
    if (TableSize < MinTableSize)
    {
        puts("the tablesize is too small");
        return NULL;
    }
    H = (HashTable)malloc(sizeof(Hashtbl));
    H->TableSize = TableSize;
    H->TheLists = (List*)malloc(sizeof(List)*TableSize);
    for(int i = 0;i<=TableSize-1;i++)
    {
        H->TheLists[i] = (List)malloc(sizeof(ListNode));
        if(H->TheLists[i] == NULL)
        {
            puts("out of space");
            return NULL;
        }
        else
            H->TheLists[i]->Next=NULL;
    }
    return H;
}

(3) 가장 간단 한 hash 값 함수: 나머지 를 취하 고 기본 적 인 검색 방식 을 사용 합 니 다. hash 값 에 대응 하 는 요 소 는 찾 으 려 는 요소 가 아니 라 찾 을 때 까지 앞으로 옮 겨 다 닙 니 다.

int Hash(int key,int TableSize)
{
    return key%TableSize;
}
List Find(int key,HashTable H)
{
    List P;
    P = H->TheLists[Hash(key,H->TableSize)];    
    P = P->Next;//   
    while(P!=NULL&&P->Element!=key)
        P = P->Next;
        return P;
}

(4) 삽입 루틴: Find 를 이용 하여 사용 가능 한 공간 을 찾 습 니 다.

void Insert(int key,HashTable H)
{
    List L, P,NewCell;
    P = Find(key,H);
    if(P==NULL)
    {
        NewCell = (List)malloc(sizeof(ListNode));
        L = H->TheLists[Hash(key,H->TableSize)];
        NewCell->Next = L->Next;
        L->Next = NewCell;
        NewCell->Element = key;
    }
}

(5) 삭제 루틴

void Delete(int key,HashTable H)
{
    List P,L,temp;
    P = Find(key,H);
    if(P!=NULL)
    {
        L = H->TheLists[Hash(key,H->TableSize)];
        //  P      temp
        temp = L;
        while(temp->Next!=P)
            temp = temp->Next;
            temp->Next = P->Next;
            free(P);
    }
}

(6) 전체 hash 표 인쇄

void PrintHashTable(HashTable H)
{
    List P;
    for(int i = 0;i<= H->TableSize-1;i++)
    {
        P = H->TheLists[i];
        P = P->Next;
        while(P!=NULL)
        {
            printf("%d: ",P->Element);
            P = P->Next;
        }
            putchar('
');
    }
}