C语言写一个散列表

C语言写一个散列表的完整攻略

什么是散列表？

散列表是一种数据结构，它将键映射到值。通过使用散列函数，散列表可以快速查找数据。散列表可以用于实现字典、哈希表、集合等数据结构。

散列表的实现

散列表的实现可以分为以下几步：

1. 定义散列表的结构体以及散列表元素的结构体；
2. 实现散列函数；
3. 实现插入元素方法；
4. 实现查找元素方法；
5. 实现删除元素方法；
6. 实现销毁散列表方法。

// 定义散列表元素的结构体
typedef struct node_s {
  char *key;
  void *value;
  struct node_s *next;
} node_t;

// 定义散列表的结构体
typedef struct hashtable_s {
  int size;
  node_t **table;
} hashtable_t;

// 计算散列值的函数
unsigned int hash_func(hashtable_t *hashtable, char *key) {
  unsigned int hashval = 0;
  for (; *key != '\0'; key++) {
    hashval = *key + (hashval << 5) - hashval;
  }
  return hashval % hashtable->size;
}

// 创建并初始化一个散列表
hashtable_t *create_hashtable(int size) {
  hashtable_t *hashtable;

  if (size < 1) {
    return NULL;
  }

  hashtable = (hashtable_t *)malloc(sizeof(hashtable_t));
  hashtable->table = (node_t **)malloc(sizeof(node_t *) * size);
  for (int i = 0; i < size; i++) {
    hashtable->table[i] = NULL;
  }
  hashtable->size = size;

  return hashtable;
}

// 插入一个元素到散列表
int hashtable_insert(hashtable_t *hashtable, char *key, void *value) {
  node_t *new_node;
  unsigned int hashval = hash_func(hashtable, key);
  node_t *current_node = hashtable->table[hashval];

  while (current_node != NULL && strcmp(current_node->key, key) != 0) {
    current_node = current_node->next;
  }

  if (current_node != NULL) {  // 更新值
    current_node->value = value;
  } else {  // 插入新元素
    new_node = (node_t *)malloc(sizeof(node_t));
    new_node->key = strdup(key);
    new_node->value = value;
    new_node->next = hashtable->table[hashval];
    hashtable->table[hashval] = new_node;
  }

  return 0;
}

// 从散列表中查找一个元素
void *hashtable_search(hashtable_t *hashtable, char *key) {
  unsigned int hashval = hash_func(hashtable, key);
  node_t *current_node = hashtable->table[hashval];
  while (current_node != NULL && strcmp(current_node->key, key) != 0) {
    current_node = current_node->next;
  }
  if (current_node == NULL) {
    return NULL;
  } else {
    return current_node->value;
  }
}

// 从散列表中删除一个元素
int hashtable_delete(hashtable_t *hashtable, char *key) {
  unsigned int hashval = hash_func(hashtable, key);
  node_t *current_node = hashtable->table[hashval];
  node_t *prev_node = NULL;

  while (current_node != NULL && strcmp(current_node->key, key) != 0) {
    prev_node = current_node;
    current_node = current_node->next;
  }

  if (current_node == NULL) {
    return -1;  // 没有找到元素
  } else {
    if (prev_node == NULL) {  // 需要删除的元素位于链表头部
      hashtable->table[hashval] = current_node->next;
    } else {
      prev_node->next = current_node->next;
    }
    free(current_node->key);
    free(current_node);
    return 0;
  }
}

// 销毁散列表
void hashtable_destroy(hashtable_t *hashtable) {
  node_t *current_node, *temp_node;
  for (int i = 0; i < hashtable->size; i++) {
    current_node = hashtable->table[i];
    while (current_node != NULL) {  // 释放散列表中每个元素的内存
      temp_node = current_node;
      current_node = current_node->next;
      free(temp_node->key);
      free(temp_node);
    }
  }
  free(hashtable->table);
  free(hashtable);
  return;
}

示例

示例1：实现一个电话簿

首先定义电话簿的结构体：

typedef struct phonebook_s {
  hashtable_t *hashtable;
} phonebook_t;

然后实现添加联系人的方法：

int phonebook_add_contact(phonebook_t *phonebook, char *name, char *phone) {
  contact_t *contact;
  contact = (contact_t *)malloc(sizeof(contact_t));
  contact->name = strdup(name);
  contact->phone = strdup(phone);

  hashtable_insert(phonebook->hashtable, name, contact);

  return 0;
}

实现查找联系人的方法：

contact_t *phonebook_search_contact(phonebook_t *phonebook, char *name) {
  return (contact_t *)hashtable_search(phonebook->hashtable, name);
}

实现删除联系人的方法：

int phonebook_delete_contact(phonebook_t *phonebook, char *name) {
  return hashtable_delete(phonebook->hashtable, name);
}

示例2：实现身份证号码的校验

身份证号码的前17位是数字，最后一位可能是数字或字母X。我们可以使用散列表存储身份证前17位的数字与其对应的权值（权值就是每一位数字所对应的权值，包括各种因子的加权和），并且使用所得到的总和进行校验。

定义存储身份证号码权值的结构体：

typedef struct idcard_value_s {
  char *num;
  int value;
} idcard_value_t;

定义身份证校验的方法：

int check_idcard(char *idcard) {
  int i, j;
  int sum = 0;

  // 计算身份证前17位数字的校验和
  idcard_value_t values[17] = {
    {"1", 7}, {"0", 9}, {"x", 10}, {"9", 0}, {"8", 1}, {"7", 3},
    {"6", 5}, {"5", 8}, {"4", 0}, {"3", 2}, {"2", 4}, {"1", 6},
    {"0", 8}, {"x", 11}, {"9", 3}, {"8", 5}, {"7", 9}
  };
  int value;
  for (i = 0; i < 17; i++) {
    value = 0;
    for (j = 0; j < 17-i; j++) {
      value += (idcard[j] - '0') * pow(2, 17-i-j-1);
    }
    sum += values[i].value * (value % 11);
  }

  // 校验最后一位数字或字母是否正确
  char last_char = tolower(idcard[17]);
  int last_num;
  if (last_char == 'x') {
    last_num = 10;
  } else if (last_char >= '0' && last_char <= '9') {
    last_num = last_char - '0';
  } else {
    return 0;
  }
  if ((sum + last_num) % 11 == 1) {
    return 1;
  } else {
    return 0;
  }
}

上述代码中使用了pwo()函数，需要包含math.h头文件：

#include <math.h>

更多用法示例可以参考散列表的应用场景。