构造哈希表存储电话号码，用再哈希法处理冲突？要c语言程序代码

Question

如题所述

Answer 1

给你个hash表的接口和实现
你根据需求该下吧
#ifndef _Hash_H_
#define _Hash_H_
/*
* 查找算法时间是 O(1)
* 优点:查找迅速
* 缺点:比较占用内存
*/

/*
*
* hash原子结构体
*
*
*/
typedef struct hash_table_pair_s{
/*hash表长*/
int length;
/*hash key*/
char *key;
/*储存的值,可以是地址*/
int value;
struct hash_table_pair_s *next;
}hash_table;

/*
* function: hash_insert
* --------------------------------------
* 往hash表中增加一个元素
* Usage:
*
* #include "corelib/hash.h"
* void run(hash_table*hash){
* int i, status, value;
* status = hash_get(hash,"hawk", &value);
* if(status!=-1){
* printf("find,%d",value);
* }else{
* printf("not find");
* }
* }
* void main(){
* hash_table* hash= hash_create(10);//创建一个表长是10的hash表
* hash_insert(hash,"robin", 0);
* hash_insert(hash,"sparrow", 1);
* hash_insert(hash,"hawk", 2);
* hash_insert(hash,"jack", 3);
* hash_insert(hash,"seagull", 4);
* run(hash);
* }
*
*/
void hash_insert(hash_table *hash,const char *key, int value);

/*
* function: hash_get
* --------------------------------------
* 根据key值在hash表中获取一个元素对象
*
*
*/
int hash_get(hash_table *hash,const char* key, int *value);

/*
* function: hash_create
* 创建一个hash表
*
*/
hash_table* hash_create(int size);

#include "corelib/hash.c"
#endif
//-----------------------------------------------------------------------------------------------
#include <default.c>
#include <stdio.h>
/*
*一个key字符串占用的字节数
*/
#define KEY_SIZE 64

/*
*
*hash函数
*
*/
int ELFhash(const char *key){
unsigned long h = 0;
unsigned long g;
while( *key )
{
h =( h<< 4) + *key++;
g = h & 0xf0000000L;
if( g ) h ^= g >> 24;
h &= ~g;
}
return h;
}
void hash_insert(hash_table *hash,const char *key, int value){
char keystr[KEY_SIZE];
memset(keystr,0,KEY_SIZE);
memcpy(keystr,key,strlen(key));

int pos;
hash_table *new_pair;
char *new_str;
pos = ELFhash(key) % hash[0].length;

if (hash[pos].key != NULL) {
/*发生冲突*/
char log[512];
memset(log,0,512);
int j=0;
j+=sprintf(log+j,"冲突: %s and %s\n", keystr, hash[pos].key);
new_pair = (hash_table *)malloc(sizeof(hash_table));
new_str = (char *)malloc(sizeof(char) * (strlen(keystr) + 1));
strcpy(new_str, keystr);
new_pair->key = new_str;
new_pair->value = value;
new_pair->next = hash[pos].next;
hash[pos].next = new_pair;
// printf("%s",log);
}else{
int len = sizeof(char) * (strlen(keystr) + 1);
new_str = (char *)malloc(len);
memset(new_str,0,len);
strcpy(new_str, keystr);
hash[pos].key = new_str;
hash[pos].value = value;
hash[pos].next = NULL;
}
}
int hash_get(hash_table *hash,const char* key, int *value){
int pos;
hash_table *p;

char keystr[KEY_SIZE];
memset(keystr,0,KEY_SIZE);
memcpy(keystr,key,strlen(key));
pos = ELFhash(key) % hash[0].length;
for (p = &(hash[pos]); p != NULL; p = p->next) {
if (!strcmp(p->key, keystr)) {
*value = p->value;
return 0;
}
}
return -1;
}
hash_table* hash_create(int size){
int i;
hash_table *hash = (hash_table *)malloc(size * sizeof(hash_table));
hash[0].length = size;

for (i = 0; i < size; i++) {
hash[i].key = NULL;
hash[i].next = NULL;
hash[i].value = 0;
}
return hash;
}

#undef KEY_SIZE