21xrx.com
2025-03-22 05:43:02 Saturday
文章检索 我的文章 写文章
C语言实现字典数据结构
2023-06-17 21:08:14 深夜i     9     0
C语言 数据结构 字典

C语言作为一种广泛使用的编程语言，常用于实现各种数据结构。其中，字典数据结构也是很常见的一种。字典数据结构可以用于存储键值对数据，通过键（key）来快速查询对应的值（value）。本文章将介绍如何使用C语言实现字典数据结构。首先，我们需要定义一个结构体来表示键值对。

typedef struct {
  char *key;
  void *value;
} DictEntry;

在结构体中，我们定义了两个成员变量：key和value。key保存了键的值，value保存了对应的值。这里，key的类型为字符指针(char *)，value的类型为void指针(void *)。这是因为我们希望字典数据结构可以存储任意类型的值。同时，我们还定义了一个DictEntry类型的结构体，用于表示键值对数据。接下来，我们定义一个字典数据结构，以存储多个键值对。

typedef struct {
  int size;
  int capacity;
  DictEntry *entries;
} Dict;

在字典数据结构中，我们定义了三个成员变量：size、capacity和entries。size表示当前字典中存储的键值对数量；capacity表示字典中最多可以存储的键值对数量；entries是一个DictEntry类型的数组，用于保存所有的键值对数据。字典数据结构的初始化函数可以定义如下。

void dict_init(Dict *dict, int capacity) {
  dict->size = 0;
  dict->capacity = capacity;
  dict->entries = calloc(capacity, sizeof(DictEntry));
}

在初始化函数中，我们使用calloc函数来分配一块内存，用于保存字典中所有键值对。我们同时将字典的大小(size)设置为0，容量(capacity)设置为传入的capacity值。接下来，我们可以实现一个函数，用于向字典中添加一个键值对。

void dict_set(Dict *dict, char *key, void *value) {
  int i;
  // 查找键是否已经存在，若存在则更新value
  for (i = 0; i < dict->size; i++) {
    if (strcmp(dict->entries[i].key, key) == 0) {
      dict->entries[i].value = value;
      return;
    }
  }
  // 若字典已满，则扩容一倍
  if (dict->size == dict->capacity) {
    dict->capacity *= 2;
    dict->entries = realloc(dict->entries, dict->capacity * sizeof(DictEntry));
  }
  // 否则，在字典末尾添加新的键值对
  dict->entries[dict->size].key = strdup(key);
  dict->entries[dict->size].value = value;
  dict->size++;
}

在添加键值对时，我们首先查找字典中是否已经存在相同的键。如果存在，则更新对应的值；如果不存在，则添加新的键值对。同时，如果字典已经满了，则通过realloc函数将字典的容量扩大一倍。最后，我们还需要实现一个函数，用于通过键获取对应的值。

void *dict_get(Dict *dict, char *key) {
  int i;
  for (i = 0; i < dict->size; i++) {
    if (strcmp(dict->entries[i].key, key) == 0) {
      return dict->entries[i].value;
    }
  }
  return NULL;
}

通过遍历字典中所有的键值对，我们可以在字典中查询是否存在获得对应键的值。如果找到了对应的键，则返回对应的值；否则，返回NULL。至此，我们使用C语言实现了字典数据结构。该数据结构可以存储任意类型的键值对数据，并且可以通过键快速查询对应的值。

  
  

评论区