哈希表(Hash Table)

哈希表是将关键字映射到另一个数组中成为下标，以空间换时间的一种数据结构。

#include<stdio.h>
#include<malloc.h>

#define MAXSIZE 10
#define NULLKEY -1

typedef int ElemType;
typedef struct{
    ElemType *elem;
    int size;
}Hash, *hash_tab;

void init(hash_tab t){
    t->elem = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));
    t->size = MAXSIZE;
    int i=0;
    ElemType *p = t->elem;
    while(i<t->size){
        *p = NULLKEY;
        i++;
        p++;
    }
}

int hash(hash_tab t,ElemType m){
    return m % t->size;
}

void create_hash(ElemType arr[],hash_tab t){
    int i = 0;
    int j;
    while(i<t->size){
        j = hash(t,arr[i]);
        while(t->elem[j] != NULLKEY)
            j = (j+1)%t->size;
        t->elem[j] = arr[i];
        i++;
    }
}


int search(hash_tab t, ElemType m){
    int outcome = 0;
    int i = hash(t,m);
    if(m == t->elem[i]){
        outcome = 1;
    }
    int p = (i+1)%t->size;
    while(p!=i){
        if(m == t->elem[p]){
            outcome = 1;
        }
        p = (p+1)%t->size;
    }
    return outcome;
}

void show(hash_tab t){
    for(int i=0;i<t->size; ++i){
        printf("%3d",t->elem[i]);
    }
    printf("\n");
}


int main(){
    Hash hash;
    ElemType a[] = {11,14,21,13,8,41,25,7,31,20};
    init(&hash);
    create_hash(a,&hash);
    show(&hash);
    ElemType e1 = search(&hash,33);
    ElemType e2 = search(&hash,31);
    printf("%2d %2d\n",e1,e2);
    return 0;
}