C Program yazarken özlediğim şeylerden biri sözlük veri yapısı. C uygulamak için en uygun yol nedir? Performans, ama sıfırdan kodlama kolaylığı aramıyorum. Bu iki dize - ^ gibi genel bir şey olmak istemiyorum . int. Ancak bu öğeler rasgele bir sayı saklamak mümkün olmak istiyorum.

Bu daha çok bir alıştırma olarak düşünülmüştür. Bir kullanabileceğiniz 3. parti kütüphaneler mevcut olduğunu biliyorum. Ama bir an için düşünün, bundan yok. Böyle bir durumda ne bir sözlük yukarıdaki gereksinimlerini tatmin etmek için uygulayabilirsiniz en hızlı yolu bu.

The C Programming Language Bölüm 6.6 (karma tablo) basit bir sözlük veri yapısı sunar. Faydalı bir sözlük uygulaması hiç bu kadar kolay elde edebileceğini sanmıyorum. Size kolaylık sağlamak için, ben kodu buraya yeniden.

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;
}

Eğer iki dizeleri karma çakışıyorsa, O(n) Arama zamanı neden olabileceğini unutmayın. HASHSIZE değerini artırarak çarpışma olasılığını azaltır. Veri yapısının tam bir tartışma için, lütfen kitap danışın.