#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define true 1
#define false 0

typedef int elemtype;
typedef int status;

typedef struct HashNode{
    elemtype elem;
    struct HashNode *next;
}HashNode,*pNode;

//生成key
//公式：key = elem % 哈希表大小
int HashKey(elemtype elem){
    int key;
    key=elem%MAXSIZE;
    return key;
}

//创建哈希表
status CreateHash(pNode *hashmap,elemtype elem[],int size){
    int i=0;
    int key;
    for (i = 0; i < size; ++i)
    {
        //获得元素的key
        key=HashKey(elem[i]);
        //新建一个哈希表节点
        pNode temp = (pNode)malloc(sizeof(pNode));
        temp->elem=elem[i];
        //如果key对应的哈希表为空，则把节点加入哈希表之后;
        if(hashmap[key]==NULL){
            temp->next=hashmap[key];
            hashmap[key]=temp;
        }
        //如果不为空，直接赋值为新建的节点
        else{
            hashmap[key]=temp;
        }
    }
    return true;
}
//查找元素，并且输出元素
status FindHashElem(pNode *hashmap,elemtype elem){
    //获取元素的key
    int key=HashKey(elem);
    //获取哈希表中对应的key的节点
    pNode temp=hashmap[key];
    //当节点不为空的时候搜索
    while(temp!=NULL){
        //如果找到输出元素和他的key值
        if (temp->elem==elem)
        {
            printf("查找结果为：");
            printf("%d\n",temp->elem);
            printf("对应的key值为：");
            printf("%d",key);
            return true;
        }
        //如果不相等，指向下一个节点
        else{
            temp=temp->next;
        }
    }
    //没有搜索到这个元素
    printf("没有这个元素");
    return false;
}

int main(){
    int i,j;
    //数组
    elemtype num[100];
    //数组大小
    int size;
    pNode hashmap[MAXSIZE];
    //把哈希表全部赋值为空
    for (i = 0; i < MAXSIZE; ++i)
    {
        hashmap[i]=NULL;
    }
    printf("请输入数组大小：");
    scanf("%d",&size);
    for (j = 0; j < size; ++j)
    {
        printf("请输入数组元素：");
        scanf("%d",&num[j]);
    }
    //创建哈希表
    CreateHash(hashmap,num,size);
    //查找元素
    int findelem;
    printf("请输入要查找的元素：");
    scanf("%d",&findelem);
    FindHashElem(hashmap, findelem);
    return 0;
}