链式哈希表（Hash Table)--算法导论示例

In computer science, a hash table is an associative array data structure that associates keys with values. The primary operation it supports efficiently is a lookup, where it is given a key, an identifier for the information to be found such as a person's name, and asked to find the corresponding value. It works by transforming the key using a hash function into a hash, a number that the hash table uses to locate the desired value.
散列表（也叫哈希表），是根据关键码值直接进行访问的数据结构，也就是说，它通过把 关键码值映射 ... 称这个对应关系f为哈希(Hash)函数，按这个思想建立的表为哈希表。

以下是链式哈希表的实现程序，参考算法导论第226页

#include "stdio.h"
#include "stdlib.h"
#define HASHSIZE 5
struct Node
{
    int k;
    struct Node *next;
};

struct Node T[HASHSIZE];

//初始化哈希表
void InitHash()
{
    for(int i=0;i    {
        T[i].k=i;
        T[i].next=0;
    }
}

//打印
void PrintHash()
{
    for(int i=0;i     {   
        printf("%d:",T[i].k);
        struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
        newNode=&T[i];
        newNode=newNode->next;
        while(newNode!=NULL)
        {
            printf("-->%d",newNode->k);
            newNode=newNode->next;
        }
       
        printf(" ");
    }
}

//插入新值
void Insert()
{
    int value;
    printf("Please input the value you want to insert:");
    scanf("%d",&value);
    //Hash value
    int hash=value%HASHSIZE;
    struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
    newNode->k=value;
    newNode->next=T[hash].next;
    T[hash].next=newNode;
}
//删除值
void Delete()
{
    int value;
    printf("Please input the value you want to delete:");
    scanf("%d",&value);
    //Hash value
    int hash=value%HASHSIZE;
    struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
    struct Node *pointer=(struct Node*)malloc(sizeof(struct Node));
    newNode=&T[hash];
    pointer=newNode;
    newNode=newNode->next;

    while(newNode!=NULL)
    {
        if(newNode->k==value)
        {
            pointer->next=newNode->next;
            free(newNode);
            return;
        }
        pointer=newNode;
        newNode=newNode->next;
    }

    printf("Can't find this value! ");
}
//搜索哈希Key对应的哈希值
void Search()
{
    int value;
    printf("Please input the value you want to search:");
    scanf("%d",&value);
   
    if(value>=0&&value    {
        struct Node *pointer=(struct Node*)malloc(sizeof(struct Node));
        pointer=&T[value];
        pointer=pointer->next;
   
        while(pointer!=NULL)
        {
            printf("%d-->",pointer->k);
            pointer=pointer->next;
        }
    }
    else
        printf("输入的值不在哈希索引范围！");
    printf(" ");
}

int main()
{
    InitHash();
    int value=1;

    while(value)
    {
        printf("1:Insert ");
        printf("2:Delete ");
        printf("3:Search ");
        printf("0:Exit ");
        scanf("%d",&value);
        switch(value)
        {
        case 0:
            return 0;
        case 1:
            Insert();
            break;
        case 2:
            Delete();
            break;
        case 3:
            Search();
            break;
        default:
            break;
        }
        PrintHash();
    }
   
    return 0;
}