[Data structures]Hash table
#include <stdio.h> #include <stdlib.h> #define NULLKEY -1 int hashsize[] = {10, 20, 40, 100, 1024}; typedef struct _HashTable{ int *elem; int count; // count of the elements of the table now; int sizeIndex; // hashsize[sizeIndex] is the size of the table now; }HashTable; int Hash(int key, int size) { return key%size; } int Collision(int *p, int *c, int size) { *p = (*p + *c)/size; return *p; } int RecreateHash(HashTable *H) { int *p = NULL; int n = sizeof(hashsize)/sizeof(int); int i; if(H->sizeIndex < n){ H->sizeIndex++; p = (int *)malloc(sizeof(int)*sizeof(hashsize[H->sizeIndex])); for(i=0; i< hashsize[H->sizeIndex]; i++){ p[i] = NULLKEY; } free(H->elem); H->elem = p; return 1; }else{ return 0; } } int SearchHash(HashTable *H, int key, int *p, int *c) { *p = Hash(key, hashsize[H->sizeIndex]); while(H->elem[*p] != NULLKEY && H->elem[*p] != key){ ++(*c); Collision(p, c, hashsize[H->sizeIndex]); if(*c > 10){ break; } } if(H->elem[*p] == key){ return 1; }else{ return 0; } } int InsertHash(HashTable *H, int key) { int c = 0; int p = 0; if( SearchHash(H, key, &p, &c) ){ return 0; }else if( c < hashsize[H->sizeIndex]/2 ){ H->elem[p] = key, ++H->count; return 1; }else{ RecreateHash(H); return -1; } } void main() { int data[] = {1,3,4,5,8,10,11,22,44,55,66,22,99,32,41}; //int data[] = {3,4,5,8,10,11}; int n = sizeof(data)/sizeof(int); int i; int p; int c=0; HashTable H; H.count = 0; H.sizeIndex = 0; H.elem = (int *)malloc(sizeof(int) * hashsize[H.sizeIndex]); for(i=0;i<hashsize[H.sizeIndex];i++){ H.elem[i] = NULLKEY; } printf("log.anycle.com\n\n"); printf("Original data:\n"); for(i=0;i<n; i++){ printf(" %d", data[i]); } printf("\n"); printf("Insert hash table:\n"); i=0; while(i<n){ for(i=0;i<n;i++){ if(InsertHash(&H, data[i]) < 0){ break; } } } printf("Print the hash table:\n"); for(i=0;i<hashsize[H.sizeIndex];i++){ printf(" %2d", H.elem[i]); } printf("\n"); }
日历
最新微语
- 有的时候,会站在分叉路口,不知道向左还是右
2023-12-26 15:34
- 繁花乱开,鸟雀逐风。心自宁静,纷扰不闻。
2023-03-14 09:56
- 对于不可控的事,我们保持乐观,对于可控的事情,我们保持谨慎。
2023-02-09 11:03
- 小时候,
暑假意味着无忧无虑地玩很长一段时间,
节假意味着好吃好喝还有很多长期不见的小朋友来玩...
长大后,
这是女儿第一个暑假,
一个半月...
2022-07-11 08:54
- Watching the autumn leaves falling as you grow older together
2018-10-25 09:45
分类
最新评论
- Goonog
i get it now :) - 萧
@Fluzak:The web host... - Fluzak
Nice blog here! Also... - Albertarive
In my opinion you co... - ChesterHep
What does it plan? - ChesterHep
No, opposite. - mojoheadz
Everything is OK!... - Josephmaigh
I just want to say t... - ChesterHep
What good topic - AnthonyBub
Certainly, never it ...
发表评论: