/*
    主函数
*/

#include "head.h"

int main(void){
    int i,j,p,c;
    HashTable H;
    ElemType e;
    H.elem=(ElemType *)malloc(50*sizeof(ElemType));
    for(i=0;i<50;i++){
        H.elem[i].key=NULLKEY;
    }
    for(i=0;i<50;i++){
        e.key=rand()%500;
        if(i==41){
            e.key=e.key;
        }
        j=InsertHash(H,e);
        if(j==OK)printf("Insert %3d V , ",e.key);
        else printf("Insert %3d X , ",e.key);
        if(!((i+1)%4))printf("\n");
    }
    printf("\n\n");
    for(i=0;i<50;i++){
        printf("%3d ",H.elem[i]);
    }
    printf("\n\n");
    for(i=0;i<50;i++){
        j=rand()%500;
        if(SearchHash(H,j,p,c))printf("Search %3d V , ",j);
        else printf("Search %3d X , ",j);
        if(!((i+1)%4))printf("\n");
    }
    printf("\nResult End!\n");
    system("pause");
    return 0;
}

/*
   
    哈希搜索

*/

#include"head.h"

int Hash(KeyType k){
    //求哈希值
    return k%50;

}

void colloision(int &p,int &c){
    //求哈希值冲突时的下一个地址
    p++;
    if(p>49)p-=49;
}

Status SearchHash(HashTable H,KeyType K,int &p,int &c){
    //在开放定址哈希表H中查找关键码为K的元素，若成功，以p指示待查数据在表中位置，并返回SUCCESS
    //否则，p指示插入位置，返回UNSUCCESS，c用来计数冲突次数，其初始值为零，供建表时插入参考
    p=Hash(K);
    while(H.elem[p].key!=NULLKEY && !EQ(K,H.elem[p].key) )
        colloision(p,++c);

    if(EQ(K,H.elem[p].key))return SUCCESS;//查找成功p返回带查数据元素位置
    else return UNSUCCESS;//不成功，返回插入位置 H.elem[p].key==NULLKEY
}

Status InsertHash(HashTable &H,ElemType e){
    //若查找不成功时插入数据元素e到开放地址哈希表H中，并返回OK；若冲突次数过大，则重建hash表
    int c=0,p=0;
    if(SearchHash(H,e.key,p,c))return DUPLICATE;
    H.elem[p]=e;
    ++H.count;
    return OK;
}