在用C編寫(xiě)程序時(shí)，我想念的一件事就是字典數(shù)據(jù)結(jié)構(gòu)。用C實(shí)現(xiàn)一個(gè)最方便的方法是什么？我不是在尋找性能，而是希望從頭開(kāi)始編寫(xiě)它。我也不希望它是通用的-像string-> int這樣的東西。但是我確實(shí)希望它能夠存儲(chǔ)任意數(shù)量的項(xiàng)目。這更多地是作為練習(xí)。我知道有一個(gè)第三方庫(kù)可供使用。但是請(qǐng)考慮一下，它們不存在。在這種情況下，實(shí)現(xiàn)滿足以上要求的字典的最快方法是什么。
3 回答
楊魅力
TA貢獻(xiàn)1811條經(jīng)驗(yàn) 獲得超6個(gè)贊
為了易于實(shí)現(xiàn)，很難天真地搜索數(shù)組。除了一些錯(cuò)誤檢查之外，這是一個(gè)完整的實(shí)現(xiàn)（未經(jīng)測(cè)試）。
typedef struct dict_entry_s {
const char *key;
int value;
} dict_entry_s;
typedef struct dict_s {
int len;
int cap;
dict_entry_s *entry;
} dict_s, *dict_t;
int dict_find_index(dict_t dict, const char *key) {
for (int i = 0; i < dict->len; i++) {
if (!strcmp(dict->entry[i], key)) {
return i;
}
}
return -1;
}
int dict_find(dict_t dict, const char *key, int def) {
int idx = dict_find_index(dict, key);
return idx == -1 ? def : dict->entry[idx].value;
}
void dict_add(dict_t dict, const char *key, int value) {
int idx = dict_find_index(dict, key);
if (idx != -1) {
dict->entry[idx].value = value;
return;
}
if (dict->len == dict->cap) {
dict->cap *= 2;
dict->entry = realloc(dict->entry, dict->cap * sizeof(dict_entry_s));
}
dict->entry[dict->len].key = strdup(key);
dict->entry[dict->len].value = value;
dict->len++;
}
dict_t dict_new(void) {
dict_s proto = {0, 10, malloc(10 * sizeof(dict_entry_s))};
dict_t d = malloc(sizeof(dict_s));
*d = proto;
return d;
}
void dict_free(dict_t dict) {
for (int i = 0; i < dict->len; i++) {
free(dict->entry[i].key);
}
free(dict->entry);
free(dict);
}
- 3 回答
- 0 關(guān)注
- 1203 瀏覽
添加回答
舉報(bào)
0/150
提交
取消