Hash表是计算机里面最重要的一种表。
常见有链地址法 List [ N ] 和 开放地址法 Pair<key, value> [N].
简单实现 原文：http://blog.csdn.net/zhangjieting/article/details/5647033
1、开放地址法
- #include <stdio.h>
- #define N 4
- typedef int datatype;
- typedef struct
- {
- datatype key;
- }Hretype;
- int LHashsearch(Hretype HT[N], datatype k)
- {
- int addr,i=0;
- addr = k % N;
- while(i<N && HT[addr].key != -1 && HT[addr].key != k)
- {
- i++;
- addr = (addr+1)%N;
- }
- if(i == N)
- return -1; //表溢出
- else
- return addr;
- }
- int LHinsert(Hretype HT[N], Hretype R)
- {
- int addr;
- addr = LHashsearch(HT, R.key);
- if(addr==-1 || HT[addr].key == R.key)
- {
- return 1;
- }
- else
- {
- HT[addr] = R;
- return 0;
- }
- }
- int main()
- {
- Hretype R[6];
- Hretype HT[N];
- for(int i=0;i<N;i++)
- HT[i].key = -1;
- for(i=0;i<6;i++)
- R[i].key = i;
- for(i=0;i<6;i++)
- {
- int value = LHinsert(HT,R[i]);
- if(value)
- printf("表溢出或记录已存在!/n");
- else
- {
- printf("插入成功!/n");
- }
- }
- return 0;
- }
2、用链表 链地址法
- #include <stdio.h>
- #include <stdlib.h>
- #define N 4
- typedef int datatype;
- typedef struct node
- {
- datatype key;
- struct node *next;
- }Renode;
- Renode *LinkHsearch(Renode *HT[N], datatype k)
- {
- Renode *p;
- int addr = k % N;
- p = HT[addr];
- while(p && p->key !=k)
- p = p->next;
- return p;
- }
- void LinkHinsert(Renode *HT[N], Renode *S)
- {
- int addr;
- Renode *p;
- p = LinkHsearch(HT,S->key);
- if(p)
- {
- printf("记录已存在/n");
- free(S);
- }
- else
- {
- addr = S->key % N;
- S->next = HT[addr];
- HT[addr] = S;
- printf("已插入/n");
- }
- }
- int main()
- {
- Renode *HT[N];
- //指针数组初始化
- for(int i=0;i<N;i++)
- HT[i] = NULL;
- for(i=0;i<6;i++)
- {
- Renode *S = (Renode*)malloc(sizeof(Renode));
- S->key = i;
- LinkHinsert(HT,S);
- }
- for(i=0;i<6;i++)
- {
- Renode *S = (Renode*)malloc(sizeof(Renode));
- S->key = i;
- LinkHinsert(HT,S); //注意指针数组实参
- }
- return 0;
- }