哈希表链式存储_数据结构哈希排序[通俗易懂]

#ifndef CHTBL_H
#define CHTBL_H

#include <stdlib.h>

#include "list.h"

/*为哈希表定义一个数据结构*/
typedef struct CHTbl_
{
    int buckets;                                       /*1、表中分配的“桶”的个数*/
    
    int (*h)(const void *key);                         /*2、指向哈希函数*/
    int (*match)(const void *key1, const void *key2);  /*3、指向match函数*/
    int (*destroy)(void *data);                        /*4、指向销毁函数*/
    
    int size;                                          /*5、表中元素的数量*/
    List *table;                                       /*6、存储“桶”的数组*/
}CHTbl;

/*公用接口*/
int chtbl_init(CHTbl *htbl, int buckets, int(*h)(void *key), int (*match)(const void *key1, const void *key2), 
               void(*destroy)(void *data));

int chtbl_destroy(CHTbl *htbl);

int chtbl_insert(CHTbl *htbl, const void *data);

int chtbl_remove(CHTbl *htbl,void **data);

int chtbl_lookup(const CHTbl *htbl,void **data);

#define chtbl_size(htbl)((htbl)->size)

#endif // CHTBL_H

#include <stdlib.h>
#include <string.h>

#include "list.h"
#include "chtbl.h"

/*chtbl_init  初始化链式哈希表*/
int chtbl_init(CHTbl *htbl, int buckets, int (*h)(const void *key),
               int (*match)(const void *key1,const void *key2),void (*destroy)(void *data))
               {
                   int i;
                   
                   /*首先，为“桶”分配空间*/
                   if((htbl->table = (List *)malloc(buckets*sizeof(List)))==NULL)
                    return -1;
                   
                   /*然后，调用list_init初始化这些桶*/
                   htbl->buckets = buckets;
                   for(i=0;i<htbl->buckets;i++)
                    list_init(&htbl->table[i],destroy);
                   
                   /*接着，封装h,match,destroy函数*/
                   htbl->h = h;
                   htbl->match = match;
                   htbl->destroy = destroy;
                   
                   /*最后，将size值设置为0*/
                   htbl->size = 0;
                   
                   return 0;
               }
               
/*chtbl_destroy  销毁链式哈希表*/
void chtbl_destroy(CHTbl *htbl)
{
    int i;
    
    /*首先，删除每个“桶”中的元素*/
    for(i=0;i<htbl->buckets;i++)
    {
        list_destroy(&htbl->table[i]);
    }
    
    /*然后，释放由chtbl_init分配的内存空间*/
    free(htbl->table);
    
    /*最后，哈希表不再允许任何操作，清除这一结构作为错误预防*/
    memset(htbl,0,sizeof(CHTbl));
    
    return ;
}

/*chtbl_insert  向链式哈希表中插入元素*/
int chtbl_insert(CHTbl *htbl,const void *data)
{
    void *temp;
    int bucket,retval;
    
    /*首先，调用chtbl_lookup检查哈希表中是否已经存有该元素*/
    temp = (void *)data;
    if(chtbl->lookup(htbl,&temp)==0)
        return 1;
    
    /*如果未存有该元素，接着将新元素的键散列*/
    bucket = htbl->h(data) % htbl->buckets;
    
    /*然后，根据哈希编码将新元素插入哈希表中相应位置的“桶”中*/
    if((retval = list_ins_next(&htbl->table[bucket],NULL,data))==0)
        htbl->size++;
    return retval;
}

/*chtbl_remove  删除表中的元素*/
int chtbl_remove(CHTbl *htbl,void **data)
{
    ListElmt *element,*prev;
    int bucket;

    /*首先，哈希(散列)元素的键*/
    bucket = htbl->h(*data)%htbl->buckets;
    
    /*接着，查找与元素的键相匹配的桶*/
    prev = NULL;
    for(element = list_head(&htbl->table[bucket]);element != NULL; element = list_next(element))
    {
        if(htbl->match(*data,list_data(element)))
        {
            /*然后，调用list_rem_next删除元素*/
            if(list_rem_next(&htbl->table[bucket],prev,data) == 0)
            {
                htbl->size--;
                return 0;
            }
            else
            {
                return -1;
            }
        }
        prev = element;
    }
    /*遍历结束后，没有找到元素，返回-1*/
    retrun -1;
}

/*chtbl_lookup  查找元素*/
int chtbl_lookup(const CHTbl *htbl,void **data)
{
    ListElmt *element;
    int bucket;

    /*首先，散列要查找元素的键*/
    bucket = htbl->h(*data) % htbl->buckets;
    
    /*接着，查找与元素相匹配的桶*/
    for(element = list_head(&htbl->table[bucket]; element != NULL; list_next(element))
    {
        if(htbl->match(*data,list_data(element))
        /*从表中返回该元素*/
        *data = list_data(element);
        return 0;
    }
    /*遍历结束后，没有找到元素，则返回-1*/
    return -1;
}