哈希表

1、哈希表的创建

#define MAX 10
#define NULL_KEY -1
typedef int data_type;
typedef struct{
    data_type *ele;
    int n;
​
}hash_table;
​
hash_table *create_hash_table(){
hash_table * ht=(hash_table *)malloc(sizeof(hash_table));
ht->n=0;
ht->ele=(data_type *)malloc(sizeof(data_type)*MAX);
for(int i=0;i<MAX;i++){
    ht->ele[i]=NULL_KEY;
}
return ht;
}

2、判满

int is_full(hash_table *ht){
    return ht->n==MAX?1:0;
}
​

3、使用开放地址法解决冲突

void insert_hash_table(hash_table *ht,data_type key){
    if(is_full(ht)){
    printf("hash is full\n");
        return;
    }
    int index=key%MAX;
    while(ht->ele[index]!=NULL_KEY){
        index=(index+1)%MAX;
    }
    ht->ele[index]=key;
    ht->n++;
    return;
}

4、查找key

int search_hash_key(hash_table *ht,data_type key){
int index=key%MAX;
while(ht->ele[index]!=key){
    index=(index+1)%10;
    //找了一圈没找到，或者找到-1了
    if(index==key%MAX||ht->ele[index]==NULL_KEY){
        return -1;
    }
}
return index;
​
}

5、遍历哈希表

void print_hash(hash_table *ht){
    for(int i=0;i<MAX;i++){
        printf("%d ",ht->ele[i]);
    }
    return;
}
​

6、使用链地址法

#define MAX 7
typedef int data_type;
​
typedef struct node{
     struct node *next;
     data_type data;
}hash_node;
//二重指针是用来存放指针的地址
//使用指针数组（二重指针）保存
hash_node **create_hash_table(){
    hash_node **ht=(hash_node **)malloc(sizeof(hash_node *)*MAX);
    memset(ht,0,sizeof(hash_node *)*MAX);
    for(int i=0;i<MAX;i++){
        ht[i]=NULL;
    }
    return ht;
}
//插入数据
void insert_hash_data(hash_node **h,data_type key){
    int index=key%MAX;
    hash_node **p=NULL;
    hash_node *temp=NULL;
   for(p=&h[index];*p !=NULL;p=&((*p)->next)){
      if((*p)->data>key){
        break;
        }
    }
    temp=(hash_node *)malloc(sizeof(hash_node));
    temp->data=key;
    //*p是前一个节点的next里面存放的地址
    temp->next=*p;
    *p=temp;
   return;
​
}
​
void printf_hash_table(hash_node **h){
    int i=0;
    hash_node **p=NULL;
    for(int i=0;i<MAX;i++){
        printf("index=%d ：",i);
        for(p=&h[i];*p!=NULL;p=&((*p)->next)){
            printf("%d ",(*p)->data);
        }
        putchar('\n');
    }
    return;
}