Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2279756
  • 博文数量: 668
  • 博客积分: 10016
  • 博客等级: 上将
  • 技术积分: 8588
  • 用 户 组: 普通用户
  • 注册时间: 2008-05-29 19:22
文章分类

全部博文(668)

文章存档

2011年(1)

2010年(2)

2009年(273)

2008年(392)

分类:

2009-01-06 21:27:18

/* 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) |
给主人留下些什么吧!~~