Chinaunix首页 | 论坛 | 博客
  • 博客访问: 315373
  • 博文数量: 113
  • 博客积分: 446
  • 博客等级: 下士
  • 技术积分: 1229
  • 用 户 组: 普通用户
  • 注册时间: 2012-12-09 16:01
个人简介

Let's go!!!!!

文章分类

全部博文(113)

文章存档

2019年(5)

2018年(4)

2017年(9)

2016年(5)

2015年(39)

2014年(6)

2013年(28)

2012年(17)

分类: LINUX

2015-03-08 22:24:55

#include
#include
#include
#include

#define BUCKETS 200

typedef struct ListElmt_{
   char data[15];
   struct ListElmt_ *next;
}ListElmt;

typedef struct List_{
   int size;
   ListElmt *head;
}List;

typedef struct CHTBL_{
   int buckets;
   unsigned int (*h)(const char *key);
   int size;
   List *table;
}CHTBL;

unsigned int hashpjw(const char *key)
{
   const char *ptr = key;
   unsigned int val = 0;
   while(*ptr)
   {
       val = val * 131 + *ptr;
       ptr++;
   }
   return val%BUCKETS;
}

void list_init(List *list)
{
   ListElmt  *tmp = (ListElmt *)malloc(sizeof(ListElmt));
   list->size = 0;
   list->head = tmp;
   return;
}

void list_destroy(List *list)
{
   ListElmt *tmp1 = list->head;
   ListElmt *tmp2 = tmp1->next;
   while(tmp2)
   {
       tmp1 = tmp2->next;
       free(tmp2);
       tmp2 = tmp1;  
   }
   list->size = 0;
}

int chtbl_init(CHTBL *chtbl,int buckets,unsigned int (*h)(const char *key))
{
   int i = 0;
   chtbl->table = (List *)malloc(buckets * sizeof(List));
   if(!chtbl->table)
       return -1;
   chtbl->buckets = buckets;
   for(i=0;ibuckets;i++)
       list_init(&chtbl->table[i]);
   chtbl->h = h;
   chtbl->size = 0;
   return 0;
}

void chtbl_destroy(CHTBL *chtbl)
{
   int i;
   for(i=0;ibuckets;i++)
   {
       list_destroy(&chtbl->table[i]);
   }
   free(chtbl->table);
   return;
}

int chtbl_lookup(CHTBL *chtbl,char *data)
{
   List *list;
   ListElmt *tmp;
   int bucket;

   bucket = chtbl->h(data)%chtbl->buckets;
   list = &chtbl->table[bucket];
   tmp = list->head;
   tmp = tmp->next;
   while(tmp)
   {
       if(strcmp(tmp->data,data))
           return 0;
       tmp = tmp->next;
   }
   return 1;
}

int chtbl_insert(CHTBL *chtbl,char *data)
{
   List *list;
   ListElmt *tmp,*node;
   int bucket,retval;


   if(chtbl_lookup(chtbl,data)==0)
       return 1;
   bucket = chtbl->h(data)%chtbl->buckets;
   printf("bucket : %d\n",bucket);
   list = &chtbl->table[bucket];
   tmp = list->head;
   node = (ListElmt *)malloc(sizeof(ListElmt));
   strcpy(node->data,data);
   node->next = tmp->next;
   tmp->next = node;
   list->size++;
   return 0;
}

int main()
{
   CHTBL test;
   char string[15];
   chtbl_init(&test,BUCKETS,hashpjw);
   strcpy(string,"abc");
   chtbl_insert(&test,string);
   strcpy(string,"ccc");
   chtbl_insert(&test,string);
   strcpy(string,"fsdfdsfgsdg");
   chtbl_insert(&test,string);
   return 0;
}
阅读(512) | 评论(0) | 转发(0) |
0

上一篇:集合

下一篇:pthread_mutex_t

给主人留下些什么吧!~~