算法导论 哈希表

哈希表的灵魂在于哈希函数；

这么简单的哈希表（散列表），我半天没有理解，虽然网上的资料很多，但是我还想再阐述以下

ps，我领导说我的sop做的不好，好的sop是白痴站在面前都能看懂！！！

拉链式的散列表，将输入元素通过转换（哈希函数）后的关键字，来决定放到哪个桶里面，桶可以是一个线性链表，（网上叫拉链，解决多个元素对应一个关键字的冲突）

灵机一动，利用字典取首字母查询单词的逻辑，写出数组的哈希表；

源码走起

-----------------------------------------------------------------------------------------------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
#define N 10000
#define K 1000
typedef struct link S_L;
struct link {
    int n;
    S_L* p;
};
void happen_rand(int* p, int n);//生成随机数
void hash(int* p , int n);//生成散列表
int F(int x);//hash函数
S_L* hash_table[100] = { NULL };//哈希表
S_L tmp;
int main() {
    int array[N] = { 0 };
    happen_rand(array,N);
    for (int i = 0; i < N; i++) {//插入元素到哈希表中
        hash(array, array[i]);
    }
    ;
}

void happen_rand(int* p, int n)
{

    for (int i = 0; i < N; i++) {
        p[i] = rand() % K;

    }
}

int F(int x) {
    if (x < 10) return 0;
    else
    {
        while (x > 99)
            x /= 10;
    }
    return x;
}

void hash(int* p, int n) {
    S_L * ptmp ;
    int y = F(n);
    if (hash_table[y] == NULL) {
        hash_table[y] = (S_L*)malloc(sizeof(S_L));
        hash_table[y]->n = n;
        hash_table[y]->p = NULL;
        return;
    }
    else  
        ptmp= hash_table[y];
    while ((ptmp)->p != NULL) ptmp = (ptmp)->p;
    ptmp->p = (S_L*)malloc(sizeof(S_L));
    (ptmp)->p->n = n;
    (ptmp)->p->p = NULL;

}