我不明白出了什么问题。我使用橡皮鸭技术多次完成该程序。请问有什么问题吗?
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
enum state {legitimate, empty, deleted};
typedef struct
{
enum state info;
char *key;
char *value;
}cell;
typedef struct
{
cell *cells;
unsigned int size;
}hash_table;
unsigned int
hash1(const char *key, unsigned int size)
{
unsigned int hash = 0;
for(unsigned int i = 0; key[i]; i++)
{
hash = (hash << 5) + key[i];
}
return (hash%size);
}
unsigned int
hash2(const char *key)
{
unsigned int hash = 0;
unsigned int prime = 3;
for(unsigned int i = 0; key[i]; i++)
{
hash = prime - (key[i] % prime);
}
return (hash);
}
hash_table*
initialize(unsigned int size)
{
hash_table *H = malloc(sizeof(*H));
H->cells = malloc(sizeof(*H->cells)*size);
for(unsigned int i = 0; i<size; i++)
{
H->cells[i].info = empty;
}
return H;
}
unsigned int
find(hash_table *H, const char *key)
{
unsigned int index = hash1(key, H->size);
unsigned int hash = hash2(key);
unsigned max = index;
while(H->cells[index].key!=key && H->cells[index].info!=empty)
{
index = (index+hash)%H->size;
if(index==max){printf("Not found!"); return -1;}
if(index>=H->size){index-=H->size;}
}
return index;
}
void
insert(hash_table *H, const char *key, const char *value)
{
unsigned int index = find(H, key);
if(H->cells[index].info!=legitimate)
{
H->cells[index].key= malloc(strlen(key)+1);
H->cells[index].value = malloc(strlen(value)+1);
strcpy(H->cells[index].key,key);
strcpy(H->cells[index].value,value);
H->cells[index].info = legitimate;
}
}
void
dump(hash_table *H)
{
for(unsigned int i = 0; i<H->size; i++)
{
if(H->cells[i].info!=legitimate){continue;}
printf("Index[%d]: %s\n", i, H->cells[i].value);
}
}
int main()
{
hash_table *H = initialize(10);
insert(H,"name1","David");
insert(H, "name2", "Radka");
dump(H);
return 0;
}
输出:
NO OUTPUT
我检查了 hash1()、hash2() 和 find() 函数是否正常工作,它们确实有效,检查了多个输入,一切似乎都正常工作。我不确定缺少什么或我做错了什么。请帮忙。