Hash表

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

#define MAX 16

#define SZ_SIZE 128

typedef char STRING[SZ_SIZE];

/*哈希结点*/
typedef struct hashnode
{
    int key; //初始化为0：表示没有数据
    STRING value; //结点的数据域
    int flag; //有无数据的标志
    int len; //单链表的长度
    struct hashnode * next;
}HashNode;

typedef HashNode * HashNodePtr;

typedef HashNode HASHTABLE[MAX];

void InitHashTable(HASHTABLE list);
int CreateHashTable(HASHTABLE list, int data[], int len);
int Hash(int key);
int CreateHashTable(HASHTABLE list, int data[], int len);
void PrintHashTable(HASHTABLE list);

void AdjustHashTable(HASHTABLE list);
int SortHashNode(HashNodePtr hashheadptr);
int GetHashNode(HashNodePtr hashheadptr, int num, HashNodePtr * hashnodeptr);

int SearchHashTable(HASHTABLE list, int key, HashNodePtr * hashnodeptr);
int InsertHashTable(HASHTABLE list, int key, STRING value);
int DeleteHashTable(HASHTABLE list, int key);

int main(int argc, char * * argv)
{
    printf("链地址哈希表的存储结构！\n");
    HASHTABLE list;

    /*关键字序列如下：*/
    int data[12]={19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79};

    CreateHashTable(list, data, 12); /*创建哈希表*/

    PrintHashTable(list); /*打印哈希表*/

    int key;
    HashNodePtr hashnodeptr = NULL;

    key = 23;
    SearchHashTable(list, key, &hashnodeptr);
    if(hashnodeptr != NULL)
        printf("key=[%d], value=[%s]\n", key, hashnodeptr->value);
    else
        printf("key=[%d]的元素不存在！", key);

    key = 78;
    SearchHashTable(list, key, &hashnodeptr);
    if(hashnodeptr != NULL)
        printf("key=[%d], value=[%s]\n", key, hashnodeptr->value);
    else
        printf("key=[%d]的元素不存在！\n", key);

    InsertHashTable(list, key, "key=78");
    key = 92;
    InsertHashTable(list, key, "key=92");
    AdjustHashTable(list); /*调整哈希表*/
    PrintHashTable(list); /*打印哈希表*/

    SearchHashTable(list, key, &hashnodeptr);
    if(hashnodeptr != NULL)
        printf("key=[%d], value=[%s]\n", key, hashnodeptr->value);
    else
        printf("key=[%d]的元素不存在！\n", key);

    key = 27;
    DeleteHashTable(list, key);
    AdjustHashTable(list); /*调整哈希表*/
    PrintHashTable(list); /*打印哈希表*/

    return 0;
}

/**************************************************************
 *函数名：
 *函数功能：
 *
***************************************************************/

/**************************************************************
 *函数名：DeleteHashTable()
 *函数功能：哈希表中删除一个元素
 *输入参数：
 * list : 哈希表
 * key : 待删除元素的关键字
 *返回值：
***************************************************************/
int DeleteHashTable(HASHTABLE list, int key)
{
    int flag = -1;

    /*元素存在：才需要删除*/
    int index = -1;
    index = Hash(key);
    HashNodePtr p = NULL;
    HashNodePtr t = NULL;

    p = &(list[index]); //相当于是表头结点:为空
    while(p->next != NULL)
    {
        if(p->next->key == key) /*找到要删除的结点*/
        {
            t = p->next;
            p->next = t->next; /*删除结点*/
            free(t);
            t = NULL;
            list[index].len--; //链表长度减1
            flag = 1; //待删除的结点存在
            printf("成功删除一个结点：key=[%d]\n", key);
            return 0;
        }
        p = p->next;
    }
    if(flag != 1) //待删除的结点不存在
        printf("key=[%d]结点不存在，不需要删除！\n",key);

    return 0;
}

/**************************************************************
 *函数名：InsertHashTable()
 *函数功能：哈希表中新插入一个元素
 *输入参数：
 * list : 哈希表
 * key : 新结点元素关键字
 * value : 新结点数据域
 *返回值：
 *注意：
 * 其实也可以由这个插入算法来实现哈希表的创建
***************************************************************/
int InsertHashTable(HASHTABLE list, int key, STRING value)
{
    int ret = -1;
    HashNodePtr hashnodeptr = NULL;
    ret = SearchHashTable(list, key, &hashnodeptr);
    if(ret == 0)
    {
        printf("key=[%d]的元素存在，不必要插入！\n", key);
        return -1;
    }

    /*元素存在：才需要插入*/
    int index = -1;
    index = Hash(key);

    HashNodePtr p = NULL;
    p = (HashNode*)malloc(sizeof(HashNode));
    p->key = key;
    strcpy(p->value, value);
    p->next = list[index].next; /*插在单链表表头后的第1个位置*/
    list[index].next = p;

    list[index].flag = 1;
    list[index].len++; /*单链表长度+1*/

    return 0;
}

/**************************************************************
 *函数名：SearchHashTable()
 *函数功能：哈希表的查找(根据给定的关键字查找元素)
 *输入参数：
 * list : 哈希表
 * key : 关键字
 *输出参数：
 * hashnodeptr : 查找到的哈希结点指针
 *返回值：
 * 0 : 查找成功， -1 : 查找失败
***************************************************************/
int SearchHashTable(HASHTABLE list, int key, HashNodePtr * hashnodeptr)
{
    int index = -1;
    index = Hash(key);
    //则结点一定在哈希表的第[index]个位置:但是还不知道是单链表中哪个？
    HashNodePtr p = NULL;
    p = list[index].next;
    while(p != NULL)
    {
        if(p->key == key)
        {
            *hashnodeptr = p;
            return 0;
        }
        p = p->next;
    }
    *hashnodeptr = NULL;
    return -1;
}

/**************************************************************
 *函数名：AdjustHashTable()
 *函数功能：调整哈希表：让单链表中的所有元素递增有序
 *函数参数：
 * list ：哈希表
***************************************************************/
void AdjustHashTable(HASHTABLE list)
{
    int i = -1;
    for(i=0; i<MAX; i++)
    {
        if(list[i].flag == 1) /*有元素才需要调整*/
        {
            SortHashNode(&(list[i])); /*数组中的元素是单链表表头，均为空*/
        }
    }
}

/***************************************************************
 *函数名：SortHashNode()
 *函数功能：按照数据域中某个数据成员的值(key)对单链表的元素进行递增排序
 *函数参数：
 * hashheadptr : 单链表表头指针
 ***************************************************************/
int SortHashNode(HashNodePtr hashheadptr)
{
    int i, j, len;
    HashNodePtr P0 = NULL;
    HashNodePtr P1 = NULL;
    HashNodePtr P2 = NULL;

    //printf("对单链表排序如下：\n");
    len = hashheadptr->len;
    /*只能用冒泡法排序：相邻两数比较，对链表来说，交换相邻两数要相对容易的多*/
    for(i=0; i<len-1; i++)
    {
        for(j=0; j<len-1-i; j++)
        {
            GetHashNode(hashheadptr, j, &P0); /*j=0，则P0是头指针*/
            P1 = P0->next;
            P2 = P0->next->next;
            /*P1，P2是要交换的2个节点的指针，P0是这2个节点之前的节点指针*/
            /*3个节点的指针都已经保存，所以就不需要另外定义临时节点指针了*/
            if(P1->key > P2->key)
            {
                P1->next = P2->next;
                P2->next = P1;
                P0->next = P2;
            }
        }
    }
    return 0;
}

/*功能：求单链表中的第num个元素的节点指针*/
int GetHashNode(HashNodePtr hashheadptr, int num, HashNodePtr * hashnodeptr)
{
    HashNodePtr p = NULL;
    int count = 1;
    if(num < 0)
    {
        printf("num值不可小于0！\n");
        return -1;
    }
    if(num == 0)
    {
        *hashnodeptr = hashheadptr;
        return 0;
    }
    p = hashheadptr->next;
    while((p != NULL)&&(count < num))
    {
        p = p->next;
        count++;
    }
    if((p == NULL)||(count < num)) /*第num个元素不存在*/
    {
        printf("count = [%d]\n", count);
        printf("第[%d]个元素不存在！\n", num);
        return -1;
    }
    else if((p != NULL)&&(count == num)) /*第num个元素存在*/
        {
            *hashnodeptr = p;
            return 0;
        }
}

void PrintHashTable(HASHTABLE list)
{
    int i = -1;
    HashNode * p = NULL;
    for(i=0; i<MAX; i++)
    {
        if(list[i].flag == 0)
            printf("第[%d]个记录为空!\n", i);
        else
        {
            printf("第[%d]个记录有[%d]个元素:", i, list[i].len);
            fflush(stdout);
            p = list[i].next;
            while(p != NULL)
            {
                printf("->[%d]", p->key);
                p = p->next;
            }
            printf("\n");
        }
    }
}

void InitHashTable(HASHTABLE list)
{
    int i = -1;
    for(i=0; i<MAX; i++)
    {
        list[i].flag = 0; //初始化为0：表示没有数据
        memset(list[i].value, 0, sizeof(STRING));
        list[i].len = 0; //单链表的长度
        list[i].next = NULL; //
    }
}

/*******************************************************************
 *函数名：CreateHashTable()
 *函数功能：创建哈希表
 *输入参数：
 * data[] : 关键字序列存储数组
 * len : 数组长度
 *输出参数：
 * list : 哈希表(是个数组：其中每个元素都是单链表的表头结点)
 *返回值：
 * 0 : 成功， -1 : 失败
 *编程思想：
 * 关键字序列如下：int data[12]={19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79};
 * 选定的哈希函数：H(key) = key mod 13。
 * 具体：
 * 1，创建一个数组，数组的每个元素是哈希结点元素(可以做空表头，也可以实际存储一个结点元素)
 * 数组的长度是所有可能的哈希函数值的最大值。
 * 2，哈希函数：关键字key，与其对应存储地址之间的函数关系，哈希函数运算得到的即是哈希地址。
 * 3，如果关键字key不同，哈希地址相同：则将后来的元素以单链表的形式链接上去。
 * 4，这样：相同哈希地址的记录链成一个单链表，有的哈希地址可能一直为空，
 * 则有n个哈希地址的函数，最多有n个单链表。
 * 本例中：单链表表头数组为空：单链表是无序的，最后插入的结点是单链表的一个结点元素。
 *注意：
 * 也可以把单链表调整为有序表的操作放在这里
********************************************************************/
int CreateHashTable(HASHTABLE list, int data[], int len)
{
    InitHashTable(list); /*初始化哈希表*/

    int i = -1;
    int index = -1;
    HashNode * p = NULL;
    for(i=0; i<len; i++)
    {
        index = Hash(data[i]);
        //printf("data=[%d], 哈希函数值=[%d]\n", data[i], index);

        p = (HashNode*)malloc(sizeof(HashNode));
        p->key = data[i];
        sprintf(p->value, "%d%d%d", data[i], data[i], data[i]);
        p->next = list[index].next; /*插在单链表表头后的第1个位置*/
        list[index].next = p;

        list[index].flag = 1;
        list[index].len++; /*单链表长度+1*/
    }
    AdjustHashTable(list); /*调整哈希表*/
    return 0;
}

/*******************************************************************
 *函数名：Hash()
 *函数功能：哈希函数
********************************************************************/
int Hash(int key)
{
    int index = key % 13;
    return index;
}