/* test_hash.h */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int prime_array[] = {
17, /* 0 */
37, /* 1 */
79, /* 2 */
163, /* 3 */
331, /* 4 */
673, /* 5 */
1361, /* 6 */
2729, /* 7 */
5471, /* 8 */
10949, /* 9 */
21911, /* 10 */
43853, /* 11 */
87719, /* 12 */
175447, /* 13 */
350899, /* 14 */
701819, /* 15 */
}; /*这里没有用*/
typedef struct _node{
char *name;
char *desc;
struct _node *next;
}node;
/*1.初始化init_hash()*/
void init_hash(node **hashtab,int SIZE){
int i;
for(i=0;i<SIZE;i++)
hashtab[i]=NULL;
}
/*2.哈希随机数hash(char *)*/
/*
unsigned int hashkey(char *key,int SIZE){
unsigned int h=0;
while (*key)
h = (h<<5) + h + *key++;
return h%SIZE;
}
*/
/*3.查找函数find(char *n)*/
node* find(node **hashtab,int SIZE,char *n){
unsigned int hi=0;
while(*n)
hi=(hi<<5)+hi+*n++;
hi%=SIZE;
/*hashkey(hi,n,SIZE);*/
node* np=hashtab[hi];
for(;np!=NULL;np=np->next){
if(!strcmp(np->name,n))
return np;
}
return NULL;
}
/*4.重复n个字符strndup(char *o)*/
char* strndup(char *o){
int l=strlen(o)+1;
char *ns=(char*)malloc(l*sizeof(char));
strcpy(ns,o);
if(ns==NULL)
return NULL;
else
return ns;
}
/*5.从hashtable取值*/
char* get_hash(node **hashtab,int SIZE,char* name){
node* n=find(hashtab,SIZE,name);
if(n==NULL)
return NULL;
else
return n->desc;
}
/*6.数据输入hashtable*/
int set_hash(node **hashtab,int SIZE,char* name,char* desc){
unsigned int hi=0;
node* np;
if((np=find(hashtab,SIZE,name))==NULL){
/*hi=hashkey(hi,name,SIZE);*/
while(*name)
hi=(hi<<5)+hi+*name++;
hi%=SIZE;
np=(node*)malloc(sizeof(node));
if(np==NULL)
return 0;
np->name=strndup(name);
if(np->name==NULL) return 0;
np->next=hashtab[hi];
hashtab[hi]=np;
}
else
free(np->desc);
np->desc=strndup(desc);
if(np->desc==NULL) return 0;
return 1;
}
/*7.打印hashtable表的值*/
void printhashtable(node **hashtab,int SIZE){
int i;
node *t;
for(i=0;i<SIZE;i++){
if(hashtab[i]==NULL)
printf("[]\n");
else
{
t=hashtab[i];
for(;t!=NULL;t=t->next) printf("[%s.%s]\n",t->name,t->desc);
}
}
}
/*7.清除hashtable表*/
void del_hash(node **hashtab,int SIZE){
int i;
node *np,*t;
for(i=0;i<SIZE;i++){
if(hashtab[i]!=NULL){
np=hashtab[i];
while(np!=NULL){
t=np->next;
free(np->name);
free(np->desc);
free(np);
np=t;
}
}
}
}
/* test_hash.c */
#include "test_hash.h"
int main(){
int i;
char* key[]={"name","address","phone","door","city"};
char* value[]={"netboy","china","263788","110#","guangzhou"};
int SIZE=100;
node *hashtab[SIZE];
init_hash(hashtab,SIZE);
for(i=0;i<5;i++) { set_hash(hashtab,SIZE,key[i],value[i]);}
printf("测试开始...\n");
printf("phone=%s\n",get_hash(hashtab,SIZE,"phone"));
/*修改键值对为"phone","020-69854124";*/
set_hash(hashtab,SIZE,"phone","020-69854124");
printf("phone=%s\n",get_hash(hashtab,SIZE,"phone"));
printf("city=%s\n",get_hash(hashtab,SIZE,"city"));
puts("\n");
/*print_hash();*/
del_hash(hashtab,SIZE);
init_hash(hashtab,SIZE);
system("pause");
system("cls");
set_hash(hashtab,SIZE,"skybyte","goodman");
printf("%s",get_hash(hashtab,SIZE,"skybyte"));
del_hash(hashtab,SIZE);
system("pause");
return 0;
}
阅读(1026) | 评论(0) | 转发(0) |