如何将值插入哈希表上的链表成员

Question

我有一个联系人结构插入到哈希表中的链表中。我不知道我是否正确定义了所有结构。我基本上想在给出命令 'a' 时通过输入添加一个联系人（命令是这样的：一个名字邮件 phone）。如果联系人已经存在，我将无法添加。

我试过用链接列表创建哈希表的必要结构，但我只是不明白如何使用它。所以这个函数对我理解这个概念有很大帮助。

这是我试过的结构

#define NOME_SIZE 1023
#define MAIL_SIZE 511
#define TELEFONE_SIZE 63
#define HASH_SIZE 1000

typedef struct contacts{
    char name[NOME_SIZE];
    char mail[MAIL_SIZE];
    char phone[TELEFONE_SIZE];
    struct contacts *next;
}HashList;


typedef struct hash_bucket{
    HashList *head, *tail; 
    int n_elements; 
}HashBucket;

HashBucket hashtable[HASH_SIZE];

如果我可以成功添加联系人，我不希望有任何输出。如果它已经存在它应该 return 一个错误说联系人已经存在

Answer 1

根据你的代码和我的评论提出的建议。我删除了 n_elements 因为对我来说它没用。我让 tail 但不确定它是否有用，因为您的列表只有 next 和 previous。我让 name、phone 和 mail 的数组，但我认为最好使用 char *

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NOME_SIZE 1023
#define MAIL_SIZE 511
#define TELEFONE_SIZE 63
#define HASH_SIZE 1000

typedef struct contacts{
    char name[NOME_SIZE];
    char mail[MAIL_SIZE];
    char phone[TELEFONE_SIZE];
    struct contacts *next;
}HashList;


typedef struct hash_bucket{
    HashList *head, *tail; 
    /* int n_elements; * I removed that field, it is useless */
}HashBucket;

HashBucket hashtable[HASH_SIZE]; 

// from 
size_t hash(char * str)
{
  size_t hash = 5381;
  unsigned char c;

  while ((c = (unsigned char) *str++) != 0)
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

  return hash;
}

HashList * createElt(char * n, char * m, char * p)
{
  HashList * e = malloc(sizeof(HashList));

  strncpy(e->name, n, NOME_SIZE - 1);
  e->name[NOME_SIZE - 1] = 0;

  strncpy(e->mail, m, MAIL_SIZE - 1);
  e->name[MAIL_SIZE - 1] = 0;

  strncpy(e->phone, p, TELEFONE_SIZE - 1);
  e->name[TELEFONE_SIZE - 1] = 0;

  e->next = NULL;

  return e;
}

// add or replace an element, the key is the name
// return 0 if the entry is added, else a non null value if the entry is (probably) modified
int insertElt(char * n, char * m, char * p)
{
  // suppose list sort on the name
  HashBucket * hb = &hashtable[hash(n) % HASH_SIZE];
  HashList ** hl = &hb->head;

  for (;;) {
    if (*hl == NULL) {
      /* last (and may be first) element */
      *hl = createElt(n, m, p);
      hb->tail = *hl;
      return 0;
    }

    int cmp = strcmp((*hl)->name, n);

    if (cmp == 0) {
      /* replace */
      strncpy((*hl)->mail, m, MAIL_SIZE - 1);
      (*hl)->name[MAIL_SIZE - 1] = 0;

      strncpy((*hl)->phone, p, TELEFONE_SIZE - 1);
      (*hl)->name[TELEFONE_SIZE - 1] = 0;

      return 1;
    }

    if (cmp > 0) {
      /* insert before */
      HashList * e = createElt(n, m, p);

      e->next = *hl;
      *hl = e;

      return 0;
    }

    hl = &(*hl)->next;
  }
}

void pr()
{
  for (size_t i = 0; i != HASH_SIZE; ++i)
    for (HashList * hl = hashtable[i].head; hl != NULL; hl = hl->next)
      printf("%s %s %s\n", hl->name, hl->mail, hl->phone);
}

int main()
{
  printf("%d\n", insertElt("n1", "m1", "p1"));
  printf("%d\n", insertElt("n2", "m2", "p2"));
  pr();
  printf("%d\n", insertElt("n1", "mm1", "pp1"));
  pr();

  return 0;
}

编译与执行：

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra -Wall hm.c
pi@raspberrypi:/tmp $ ./a.out
0
0
n1 m1 p1
n2 m2 p2
1
n1 mm1 pp1
n2 m2 p2

如何将值插入哈希表上的链表成员

How to insert values into linked list members on an hashtable

c

hashtable

linked-list