不晓得哪个

  1 /*
  2  *一个简单的字符串HASH表，哈希函数是用的PHP中的DJB_Hash
  3  *冲突是用的简单的连接法解决
  4  *
  5  *代码不是一般的烂。。。。。。
  6  */
  7 #include<stdio.h>
  8 #include<stdlib.h>
  9 #include<string.h>
 10 
 11 struct table_node{
 12     void *value;
 13     struct table_node *prev,*next;
 14 };
 15 struct hashtable{
 16     struct table_node *head,*tail;
 17 };
 18 struct hashtable_head{
 19     unsigned int table_size;
 20     unsigned int end_iterator;
 21     struct hashtable *buckets;
 22 };
 23 /*******************************************
 24  *
 25  *查创建HASH_TABLE
 26  *
 27  */
 28 struct hashtable_head * hashtable_init(unsigned int size)
 29 {
 30     struct hashtable_head *ptr;
 31 
 32     if (0 == size)
 33         return NULL;
 34     ptr = (struct hashtable_head *)calloc(1,sizeof(struct hashtable_head));
 35     if(!ptr)
 36         return NULL;
 37     ptr->table_size = size;
 38     ptr->buckets = (struct hashtable *)calloc(size,sizeof(struct hashtable));
 39     if(!ptr->buckets){
 40         free (ptr);
 41         return NULL;
 42     }
 43     ptr->end_iterator = 0;
 44     return ptr;
 45 }
 46 /*******************************************
 47  *
 48  *hash函数，
 49  *
 50  */
 51 unsigned int DJB_Hash(char *str,int len)
 52 {
 53     int i;
 54     unsigned hash = 0;
 55     for (i = 0;i <len;i++)
 56      {
 57         hash += (hash << 5 )+ str[i];
 58 
 59     }
 60     return hash % 47;
 61 }
 62 /********************************
 63  *
 64  *把value插入表中
 65  */
 66 struct hashtable_head *hashtable_insert(struct hashtable_head *ptr,char *value,int len)
 67 {
 68     int hash_id;
 69     struct table_node *node;
 70        if(!value)
 71            return NULL;
 72     hash_id=DJB_Hash(value,len);
 73     node = (struct table_node *)malloc(sizeof(struct table_node));
 74         if (!node) {
 75         return NULL;
 76     }
 77     node->value=value;
 78     node->next=NULL;
 79     if(ptr->buckets[hash_id].head==NULL)
 80     {
 81         ptr->buckets[hash_id].head=node;
 82         node->prev=NULL;
 83     }
 84     if(ptr->buckets[hash_id].tail){
 85         ptr->buckets[hash_id].tail->next=node;
 86         node->prev=ptr->buckets[hash_id].tail;
 87     }
 88     ptr->buckets[hash_id].tail=node;
 89     ptr->end_iterator+=1;
 90     return 0;
 91 }
 92 /*******************************************************************
 93  *
 94  *查询HASH_TABLE中value在BUCKETS[]中的哪一个，通过计算KEY确定下标
 95  *
 96  */
 97 int hashtable_find_buckets(struct hashtable_head * ptr,char *value,int len)
 98 {
 99     int key=0;
100     struct table_node *temp;
101     if(ptr==NULL||value==NULL)
102         return 0;
103 
104     key=DJB_Hash(value,len);
105     if(key<0)
106     {
107         return -1;
108     }
109     temp=ptr->buckets[key].head;
110     while(temp!=NULL){
111         if(!strcmp((const char *)(temp->value),value)){
112             return key;
113         }
114         else{
115             temp=temp->next;
116         }
117         
118     }    
119     return -1;
120 }
121 /*******************************************************************
122  *
123  *查询HASH_TABLE中value在BUCKETS[key]中的具体位置
124  *
125  */
126 int hashtalbe_find_node(struct hashtable_head *ptr,char * value,int len)
127 {
128     int key=0;
129     int node=1;
130     struct table_node *temp;
131     if(ptr==NULL||value==NULL)
132         return 0;
133 
134     key=DJB_Hash(value,len);
135     if(key<0)
136     {
137         return -1;
138     }
139     temp=ptr->buckets[key].head;
140     while(temp!=NULL){
141         if(!strcmp((const char *)(temp->value),value)){
142             return node;
143         }
144         else{
145             node+=1;
146             temp=temp->next;
147         }
148         
149     }
150 }
151 /*******************************************************************
152  *
153  *显示HASH_TABLE里所有数据
154  *
155  */
156 int hashtable_display(struct hashtable_head *ptr)
157 {
158     unsigned int i;
159     struct table_node * node;
160     if (ptr==NULL){
161         printf("the table is null");
162         return 0;
163     }
164     for(i=0;i<ptr->table_size;i++){
165         node=ptr->buckets[i].head;
166         if(node==NULL)
167             printf("buckets[%d]=null\n",i);
168         else{
169             while(node){
170                 printf("buckets[%d]=%s\t",i,node->value);
171                 node=node->next;
172             }
173             printf("\n");
174         }
175     }
176     return 1;
177 }
178 /*******************************************************************
179  *
180  *删除一指定值
181  *
182  */
183 int hashtable_del(struct hashtable_head *ptr,char * value,int len)
184 {
185     int key=0;
186     struct table_node *temp;
187     if(ptr==NULL||value==NULL)
188         return 0;
189     key=DJB_Hash(value,len);
190     if(key<0){
191         return NULL;
192     }
193     temp=ptr->buckets[key].head;
194     if(!temp){
195         printf("NO %s FOUND\n",value);
196         return NULL;
197     }
198     while(temp!=NULL){
199         if(!strcmp((const char *)(temp->value),value)){
200             if(!temp->next){
201                 if(ptr->buckets[key].head==temp){
202                     ptr->buckets[key].head=NULL;
203                     ptr->buckets[key].tail=NULL;
204                 }
205                 else{
206                     temp->prev->next=NULL;
207                     ptr->buckets[key].tail=temp->prev;
208                 }
209             }
210             else{
211                 if(ptr->buckets[key].head==temp){
212                     ptr->buckets[key].head=temp->next;
213                     ptr->buckets[key].tail=temp->next;
214                 }
215                 else{
216                 temp->prev->next=temp->next;
217                 temp->next->prev=temp->prev;
218                 }
219             }
220             ptr->end_iterator-=1;
221             return 1;
222         }
223         temp=temp->next;
224     }
225 }
226 /*****************************************
227  *
228  *删除整个HASH_TABLE,释放内存
229  *
230  */
231 
232 int hashtable_remove(struct hashtable_head *ptr)
233 {
234         unsigned int i,j;
235         struct table_node * node;
236         if (ptr == NULL)
237                 return -1;
238         for (i = 0; i < ptr->table_size; i++) {
239             if (ptr->buckets[i].head != NULL) {
240                 node=ptr->buckets[i].tail;
241                 while (node){
242                     free(node->value);
243                     free(node);
244                }
245             }
246         }
247         free(ptr->buckets);
248         free(ptr);
249         return 0;
250 }
251 
252 /*******************************************************************
253  *
254  *A test 
255  *
256  */
257 int main()
258 {
259     struct hashtable_head *ptr=NULL;
260     int key,node,i=0;
261     char *name1[]={
262     "hippies","min","linyun","chenyu","wenli","zhaoyuanyuan","huangjingxing",
263     "lishaojie","laoma","xiaoyu","chentao","guojunjie","xiaobanzhang","caizhongyuan",
264     "heqiang","wangpai","wangzhitong","yixia","huangxuehong","bodong","liyong",
265     "liujinling","liuyuezhong",    "meilijia","wangyinqi","zhangbo","zhangwen","zouyinghua",NULL
266     };
267     ptr=hashtable_init(50);
268     if(!ptr)
269         printf("error\n");
270     for(i=0;name1[i]!=NULL;i++){
271         //printf("%s is %d\n",name1[i],strlen(name1[i]));
272         hashtable_insert(ptr,name1[i],strlen(name1[i]));
273     }
274     hashtable_display(ptr);
275     char *name=name1[2];
276     int len=strlen(name);
277     if((key=hashtable_find_buckets(ptr,name,len))>=0)
278         printf("the %s is in buckets of %d\n",name,key);
279     else printf("\nthe %s not found in the hashtable \n",name);
280     if((node=hashtalbe_find_node(ptr,name,len))>=0)
281         printf("the %s is in node of %d \n",name,node);
282     else printf("\nthe %s not found in the hashtable \n",name);
283     hashtable_del(ptr,name,len);
284     hashtable_display(ptr);
285     return 0;
286 }
287