如何建立哈希表？C++题目

Question

从键盘输入任意长度的数组，为该数组建立哈希表，输出；并且根据该哈希表进行查找，显示查找结果，并计算该哈希表的平均查找长度。
要求：(1)使用除留余数法建立哈希表；
(2)p的选择：接近或等于该数组长度的质数；
(3)解决冲突的方法：线性探测法。

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//
#define LEN 6
#define INVIALD -1
#define INVAL 1

typedef struct node node_t;
struct node {
char ch[10];
int flag;
node_t* next;
};

typedef struct hash hash_t;
struct hash {
node_t* arr;
};

void inithash(hash_t* ha,int len){
ha->arr = (node_t*)calloc(len,sizeof(node_t));
int i;
for (i = 0; i < len; i++)
ha->arr[i].flag = INVIALD;
}

int func(const char* str){
int ret = 0;
while (0 != *str)
ret += *str++;
return ret % LEN;
}

void add(hash_t* ha,const char* str){
int position = func(str);
if (INVIALD == ha->arr[position].flag){
strcpy(ha->arr[position].ch,str);
ha->arr[position].flag = INVAL;
} else {
node_t* nd = (node_t*)malloc(sizeof(node_t));
strcpy(nd->ch,str);
nd->next = NULL;
node_t* index = &(ha->arr[position]);
nd->next = index->next;
index->next = nd;
ha->arr[position].flag = INVAL;
}
}

node_t* search(hash_t* ha,int len,const char* str){

int ret = func(str);
if (0 == strcmp(ha->arr[ret].ch,str))
return &(ha->arr[ret]);
node_t* index = &(ha->arr[ret]);
while (index){
if (0 == strcmp(index->ch,str))
return index;
index = index->next;
}
return NULL;
}

int main(){
hash_t* ha = (hash_t*)malloc(sizeof(hash_t));
ha->arr = NULL;
inithash(ha,LEN);
int i;
for (i = 0; i < LEN; i++){
char name[10] = {0};
sprintf(name,"haha%d",i+1);
add(ha,name);
}
add(ha,"ahah3");
node_t* nd = search(ha,LEN,"ahah3");
printf("%s %d\n",nd->ch,nd->flag);
return 0;
}本回答被提问者采纳