从下图受到启发，我们编写如下栗子：
/************************************************************************* > File Name: hash_table.c > Author: XXDK > Email: v.manstein@qq.com > Created Time: Thu 09 Mar 2017 02:56:15 AM PST ************************************************************************/ #include <stdio.h> #include <stdlib.h> #define MAX 10 // 创建链表节点 // 定义链表指针数组,包含10个成员; // [存放struct node*]...... struct node { int data; struct node *next; }*global_arry[MAX]; /********************************************* * 有序插入 * 用取余法，设定哈希函数 * [0] 里面的链表指向 包含余数为0的data的链表 * [1] 里面的链表指向 包含余数为1的data的链表 * [2] 里面的链表指向 包含余数为2的data的链表 * [3] 里面的链表指向 包含余数为3的data的链表 * [4] 里面的链表指向 包含余数为4的data的链表 * [5] 里面的链表指向 包含余数为5的data的链表 * [6] 里面的链表指向 包含余数为6的data的链表 * [7] 里面的链表指向 包含余数为7的data的链表 * [8] 里面的链表指向 包含余数为8的data的链表 * [9] 里面的链表指向 包含余数为9的data的链表 * * 这里将冲突（余数相同）的数据存放在同一个链上 * 从而解决了冲突问题 * 如此，整个哈希表构建完成 *********************************************/ int insert_hash_table(int data) { int Index; struct node *temp; struct node **p; // 设置hash转化规则求余法 // 01 % 10 1 // 03 % 10 3 // 13 % 10 3 // ...... Index = data % MAX; // data index // 01 1 // 03 3 // 13 3 // ...... /** * 第一次执行，p = &global_arry[1], 此时（*p）取数组中的元素也就是下标[1]的struct node* 指针 * (*p)->data, 访问struct node* 指向的链表结点的数据域，第一次所以时0,而0 < 1, 判断*p 其实是0 * 故而for退出。程序到B处执行 * **/ // A. for(p = &global_arry[Index]; *p ; p = &( (*p)->next ) ) { if((*p)->data > data) break; } // B.创建一个新结点，填数据 temp = (struct node *)malloc(sizeof(struct node)); temp->data = data; // C. 数据的next指针指向 之前按照index取出来的struct node* temp->next = *p; // D. 保存temp新结点指针（其中数据域包含要处理的数据）到*p(struct node*)里面 *p = temp; // 保存temp地址(node类型的指针)到global_arry[Index] 中 return 0; } int printf_hash_table() { int i = 0; struct node **p; for(i = 0;i < MAX;i ++) { printf("[Index[%d]] : ",i); // 对数组的每个元素（链表指针），取里面的数据对链表指针解引用，然后访问数据域 for(p = &global_arry[i]; *p ; p = & ( (*p)->next )) { printf("%d ",(*p)->data); } printf("\n"); } return 0; } /************************************************************ * 哈希表的查找 * 思路： * 因为我们已经按照我们设定的哈希函数映射建立了哈希表 * 查找自然容易很多: * 1. 将待查数据按照哈希函数映射找到其在哈希表的位置 * （这里是下标匹配） * 2. 以该下标为索引，拿出表中的存放的链表指针 * 3. 根据该指针的数据域匹配遍历该链表，直到找到或者 * 为空返回 ************************************************************/ int search_hash_table(int target) { int index = 0; struct node *p; // 1. index = target % MAX; // 2. p = global_arry[index]; // 3. while(p) { if(p->data == target) { printf("Get target.\n"); return p->data; } p = p->next; } printf("Target not find.\n"); return -1; } int main(int argc, const char *argv[]) { int i = 0; int a[] = {1,3,13,73,4,5,11, 6, 42, 30, 17, 88, 59}; for(i = 0;i < sizeof(a)/sizeof(a[0]);i ++) { insert_hash_table(a[i]); } printf_hash_table(); printf("Target: %d\n", search_hash_table(88)); return 0; }gcc编译输出：
---------------------------------------------------------
[Index[0]] : 30 [Index[1]] : 1 11 [Index[2]] : 42 [Index[3]] : 3 13 73 [Index[4]] : 4 [Index[5]] : 5 [Index[6]] : 6 [Index[7]] : 17 [Index[8]] : 88 [Index[9]] : 59 Get target. Target: 88
----------------------------------------------------------
