散列的C语言实现
/*复制散列操作，相当于创建了一个新的散列对象，而不是指针复制*/
Hashmap_handle_t copy_hashmap(Hashmap_handle_t hashmap)
{
Hashmap_handle_t newhashmap = NULL;
int i = 0;
if(hashmap == NULL)
return NULL;
/*采用动态分配的方式实现*/
if(!alloc_hashmap(&newhashmap,hashmap->capacity))
return NULL;
for(; i < hashmap->capacity ; ++ i)
{
if(hashmap->map[i].state == ACTIVE)
{
/*得到当前中的值实现插入操作*/
insert_hashnode(newhashmap,
hashmap->map[i].pair->key,
hashmap->map[i].pair->value);
}
else if(hashmap->map[i].state == DELETED)
{
newhashmap->map[i].state = DELETED;
}
}
return newhashmap;
}
测试函数：
#include "hashmap.h"
#include
#define CAPACITY 13
char *keys[] = {
"abcd",
"defh",
"abcd",
"12345",
"a1b2c3",
"12345",
"a1b2c3",
"23456",
"hijhk",
"test1",
"test1",
"789123",
"Input",
};
char *values[] = {
"abcd",
"defh",
"abcd",
"12345",
"a1b2c3",
"12345",
"a1b2c3",
"23456",
"hijhk",
"test1",
"test1",
"789123",
"Input",
};
int myhashFunc(const char *key, int Tabsize)
{
int hashVal = 0;
int i = 0;
int len = strlen(key);
for(; i < len ; ++ i )
hashVal += 37 *hashVal + key[i];
hashVal %= Tabsize;
if(hashVal < 0)
hashVal += Tabsize;
return hashVal;
}
int main()
{
int i = 0;
char str1[13];
char str2[13];
Hashmap_t mymap ;
Hashmap_handle_t map = NULL;
Hashmap_handle_t doubmap = NULL;
Pair_handle_t pair;
/*静态分配*/
srand((int)time(0));
printf("init and alloc test:");
if(!init_hashmap(&mymap,13))
{
return false;
}
/*动态分配*/
if(!alloc_hashmap(&map,13))
{
return false;
}
printf("Sucessed!");
/*插入测试*/
printf("insert test:");
for(i = 0; i < CAPACITY + 10; ++ i)
{
sprintf(str1,"%d%d",rand()%10+1,rand()%10+1);
sprintf(str2,"%d%d",rand()%10+1,rand()%10+1);
printf("%s->-f(%s)->%d->%s",str1,str1,
myhashFunc(str1,CAPACITY),str2);
// sprintf(str1,"%s",keys[i]);
// sprintf(str2,"%s",values[i]);
if(!insert_hashnode(&mymap,str1,str2))
{
printf("i = %d, insert to mymap failed", i);
break;
}
if(!insert_hashnode(map,str1,str2))
{
printf("i = %d, insert to map failed", i);
break;
}
}
printf("Sucessed!");
/*查找测试*/
printf("search test:");
if((pair = search_hashnode(&mymap,str1)) != NULL)
{
printf("%s->%s",key_pair(pair),value_pair(pair));
}
if((pair = search_hashnode(map,str1)) != NULL)
{
printf("%s->%s",key_pair(pair),value_pair(pair));
}
printf("Sucessed!");
/*delete*/
printf("delete test:");
if(delete_hashnode(&mymap,str1))
{
printf("Deleted success!!");
}
else
{
printf("Sorry, Failed!!");
}
if(delete_hashnode(map,str1))
{
printf("Deleted success!!");
}
else
{
printf("Sorry, Failed!!");
}
printf("Valid length : %d, Capacity : %d",
Length(&mymap),Capacity(&mymap));
printf("Valid length : %d, Capacity : %d",
Length(map),Capacity(map));
/*改变长度*/
printf("resize test:");
if(resize(&mymap))
printf("Sucessed!");
if(resize(map))
printf("Sucessed!");
/*长度*/
printf("Valid length : %d, Capacity : %d",
Length(&mymap),Capacity(&mymap));
printf("Valid length : %d, Capacity : %d",
Length(map),Capacity(map));
printf("Valid length : %d, Capacity : %d",
Length(&mymap),Capacity(&mymap));
printf("Valid length : %d, Capacity : %d",
Length(map),Capacity(map));
printf("copy test:");
doubmap = copy_hashmap(&mymap);
printf("Valid length : %d, Capacity : %d",
Length(doubmap),Capacity(doubmap));
printf("Sucessed!");
/*释放内存*/
printf("free test:");
delete_hashmap(&mymap);
free_hashmap(&map);
free_hashmap(&doubmap);
printf("Valid length : %d, Capacity : %d",
Length(&mymap),Capacity(&mymap));
printf("Sucessed!");
return 0;
}
测试结果：
[gong@Gong-Computer newversion]$ ./main
init and alloc test:
insert test:
48->-f(48)->4->49
108->-f(108)->5->910
78->-f(78)->1->98
87->-f(87)->12->73
36->-f(36)->3->109
59->-f(59)->4->98
32->-f(32)->12->48
210->-f(210)->10->91
105->-f(105)->2->22
41->-f(41)->10->82
1010->-f(1010)->11->69
19->-f(19)->8->64
25->-f(25)->3->45
28->-f(28)->6->104
16->-f(16)->5->83
44->-f(44)->0->86
85->-f(85)->10->72
51->-f(51)->9->27
54->-f(54)->12->57
107->-f(107)->4->210
73->-f(73)->9->27
1010->-f(1010)->11->61
63->-f(63)->10->63
search test:
63->63
63->63
delete test:
Deleted
Deleted
Valid length : 21, Capacity : 29
Valid length : 21, Capacity : 29
resize test:
Valid length : 21, Capacity : 59
Valid length : 21, Capacity : 59
Valid length : 21, Capacity : 59
Valid length : 21, Capacity : 59
copy test:
Valid length : 21, Capacity : 59
free test:
评论