C中实现字典的快速方法 [英] Quick Way to Implement Dictionary in C

问题描述

在C中编写程序时我想念的一件事是字典数据结构。在C中实现一个最方便的方法是什么？我不是在寻找性能，而是从头开始编写代码。我不希望它是通用的，像string-> int会做的。但我确实希望能够存储任意数量的项目。

这是一个练习。我知道有可以使用的第三方图书馆。但考虑一下，他们不存在。在这种情况下，最简单的方式是实现满足上述要求的字典。

解决方案

C编程语言提供了一个简单的字典（散列表）数据结构。我不认为有用的字典实现可能比这更简单。为了方便起见，我在这里重现代码。

  struct nlist {/ *表项：* / 
 struct nlist * next; / *链中的下一个条目* / 
 char * name; / *定义名称* / 
 char * defn; / *替换文本* / 
}; 
 
 #define HASHSIZE 101 
 static struct nlist * hashtab [HASHSIZE]; / *指针表* / 
 
 / *哈希：字符串s * / 
的unsigned hash（char * s）的哈希值
 {
 unsigned hashval; 
 for（hashval = 0; * s！='\0'; s ++）
 hashval = * s + 31 * hashval; 
 return hashval％HASHSIZE; 
} 
 
 / *查找：在hashtab中查找s * / 
 struct nlist * lookup（char * s）
 {
 struct nlist * np ; 
 for（np = hashtab [hash（s）]; np！= NULL; np = np-> next）
 if（strcmp（s，np-> name）== 0）
 return np; / * found * / 
 return NULL; / * not found * / 
} 
 
 char * strdup（char *）; 
 / * install：put（name，defn）in hashtab * / 
 struct nlist * install（char * name，char * defn）
 {
 struct nlist * np; 
 unsigned hashval; 
 if（（np = lookup（name））== NULL）{/ * not found * / 
 np =（struct nlist *）malloc（sizeof（* np））; 
 if（np == NULL ||（np-> name = strdup（name））== NULL）
 return NULL; 
 hashval = hash（name）; 
 np-> next = hashtab [hashval]; 
 hashtab [hashval] = np; 
} else / * has there * / 
 free（（void *）np-> defn）; / * free以前的defn * / 
 if（（np-> defn = strdup（defn））== NULL）
 return NULL; 
 return np; 
} 
 
 char * strdup（char * s）/ *复制s * / 
 {
 char * p; 
 p =（char *）malloc（strlen（s）+1）; / * +1 for'\0'* / 
 if（p！= NULL）
 strcpy（p，s）; 
 return p; 
} 
  

请注意，如果两个字符串的散列相冲突，可能会导致 O（n）查找时间。您可以通过增加 HASHSIZE 的值来减少碰撞的可能性。有关数据结构的完整讨论，请参阅本书。

One of the things which I miss while writing programs in C is a dictionary data structure. What's the most convenient way to implement one in C? I am not looking for performance, but ease of coding it from scratch. I don't want it to be generic either -- something like string->int will do. But I do want it to be able to store an arbitrary number of items.

This is intended more as an exercise. I know that there are 3rd party libraries available which one can use. But consider for a moment, that they don't exist. In such a situation what's the quickest way you can implement a dictionary satisfying the above requirements.

解决方案

Section 6.6 of The C Programming Language presents a simple dictionary (hashtable) data structure. I don't think a useful dictionary implementation could get any simpler than this. For your convenience, I reproduce the code here.

struct nlist { /* table entry: */
    struct nlist *next; /* next entry in chain */
    char *name; /* defined name */
    char *defn; /* replacement text */
};

#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* pointer table */

/* hash: form hash value for string s */
unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
      hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

/* lookup: look for s in hashtab */
struct nlist *lookup(char *s)
{
    struct nlist *np;
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
          return np; /* found */
    return NULL; /* not found */
}

char *strdup(char *);
/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;
    if ((np = lookup(name)) == NULL) { /* not found */
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = strdup(name)) == NULL)
          return NULL;
        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else /* already there */
        free((void *) np->defn); /*free previous defn */
    if ((np->defn = strdup(defn)) == NULL)
       return NULL;
    return np;
}

char *strdup(char *s) /* make a duplicate of s */
{
    char *p;
    p = (char *) malloc(strlen(s)+1); /* +1 for ’\0’ */
    if (p != NULL)
       strcpy(p, s);
    return p;
}

Note that if the hashes of two strings collide, it may lead to an O(n) lookup time. You can reduce the likelihood of collisions by increasing the value of HASHSIZE. For a complete discussion of the data structure, please consult the book.

这篇关于C中实现字典的快速方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！