Schneller Weg zum Implementieren von Wörterbüchern in C

Lesezeit: 8 Minuten

Benutzeravatar von Rohit
Rohit

Eines der Dinge, die ich beim Schreiben von Programmen in C vermisse, ist eine Dictionary-Datenstruktur. Was ist der bequemste Weg, um eine in C zu implementieren? Ich suche nicht nach Leistung, sondern nach einfacher Codierung von Grund auf neu. Ich möchte auch nicht, dass es generisch ist – so etwas wie char*int Wird besorgt. Aber ich möchte, dass es in der Lage ist, eine beliebige Anzahl von Elementen zu speichern.

Dies ist eher als Übung gedacht. Ich weiß, dass es Bibliotheken von Drittanbietern gibt, die man verwenden kann. Aber bedenke für einen Moment, dass sie nicht existieren. Wie können Sie in einer solchen Situation am schnellsten ein Wörterbuch implementieren, das die oben genannten Anforderungen erfüllt?

  • Wenn Sie es vermissen, es für Sie bereitgestellt zu haben, warum wollen Sie es dann von Grund auf neu erstellen, anstatt eine Implementierung eines Drittanbieters zu verwenden?

    – Karl Knechtel

    8. Dezember 2010 um 5:12 Uhr

  • Ja, diese Alternative gibt es immer. Ich habe diese Frage eher als Übung gestellt.

    – Rohit

    8. Dezember 2010 um 5:16 Uhr

  • Das Schreiben einer Hashtabelle in C ist eine unterhaltsame Übung – jeder ernsthafte C-Programmierer sollte es mindestens einmal tun.

    – Lee

    8. Dezember 2010 um 5:24 Uhr

  • Ich denke, ein Wörterbuch ist eher ein Datentyp als eine Datenstruktur, da es auf viele Arten implementiert werden könnte – eine Liste, eine Hashtabelle, ein Baum, ein selbstausgleichender Baum usw. Fragen Sie nach einem Wörterbuch oder einer Hashtabelle? ?

    – Paul Hankin

    21. April 2013 um 7:54 Uhr

  • Verwandte: Wie stellt man ein Python-ähnliches Wörterbuch in C dar?[](stackoverflow.com/questions/3269881/…)

    – Gaurang Tandon

    23. Juni 2018 um 6:05 Uhr

Benutzeravatar von Vijay Mathew
Vijay Mathew

Abschnitt 6.6 von The C Programming Language stellt eine einfache Dictionary-(Hashtable-)Datenstruktur vor. Ich glaube nicht, dass eine nützliche Wörterbuchimplementierung einfacher werden könnte. Der Einfachheit halber reproduziere ich den Code hier.

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

Beachten Sie, dass wenn die Hashes zweier Strings kollidieren, dies zu einem führen kann O(n) Suchzeit. Sie können die Wahrscheinlichkeit von Kollisionen verringern, indem Sie den Wert von erhöhen HASHSIZE. Für eine vollständige Diskussion der Datenstruktur konsultieren Sie bitte das Buch.

  • warum ist hier hashval = *s + 31 * hashval; genau 31 und nichts anderes?

    – Incerteza

    25. September 2014 um 8:50 Uhr

  • 31 ist eine Primzahl. Primzahlen werden häufig in Hash-Funktionen verwendet, um die Wahrscheinlichkeit von Kollisionen zu verringern. Es hat etwas mit ganzzahliger Faktorisierung zu tun (dh Sie können eine Primzahl nicht faktorisieren).

    – jnovacho

    4. Oktober 2014 um 11:08 Uhr

  • @アレックス 31 schnitt bei Testdaten gut ab. Die Wahl einer Primzahl hat ihre Vorteile, wäre aber nicht notwendig, wenn die Größe der Hash-Tabelle selbst eine Primzahl wäre.

    – G. Bach

    3. April 2016 um 16:43 Uhr

  • Beachten Sie, dass der K&R C-Hash-Algorithmus ein entsetzlicher Hash-Algorithmus ist. Sehen: programers.stackexchange.com/questions/49550/… für Einzelheiten darüber, wie wirklich schrecklich es wirklich ist. Hör auf es zu benutzen!!

    – Schnitzel

    6. August 2016 um 11:01 Uhr

  • @Overdriver: In diesem Fall nicht erforderlich. Hashtab ist von statischer Dauer. Nicht initialisierte Variablen mit statischer Dauer (d. h. solche, die außerhalb von Funktionen deklariert wurden, und solche, die mit der Speicherklasse static deklariert wurden) beginnen garantiert als Null des richtigen Typs (d. h.: 0 oder NULL oder 0.0).

    – Schnitzel

    6. August 2016 um 11:20 Uhr

Benutzeravatar von paxdiablo
paxdiablo

Das am schnellsten Der Weg wäre, eine bereits vorhandene Implementierung zu verwenden, z uthash.

Und wenn Du Ja wirklich selbst codieren wollen, die Algorithmen aus uthash eingesehen und wiederverwendet werden können. Es ist BSD-lizenziert, so dass Sie, abgesehen von der Anforderung, den Urheberrechtshinweis zu übermitteln, ziemlich unbegrenzt sind, was Sie damit tun können.

Um die Implementierung zu vereinfachen, ist es kaum zu überbieten, ein Array naiv zu durchsuchen. Abgesehen von einigen Fehlerprüfungen ist dies eine vollständige Implementierung (ungetestet).

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

  • “Zur Erleichterung der Implementierung”: Sie haben genau Recht: Das ist am einfachsten. Außerdem implementiert es die OP-Anforderung “Ich möchte, dass es eine beliebige Anzahl von Elementen speichern kann” – die am höchsten bewertete Antwort tut dies nicht (es sei denn, Sie glauben, dass die Auswahl einer Kompilierzeit konstant erfüllt “beliebig”…)

    – davidbak

    5. Juni 2015 um 4:23 Uhr

  • Dies kann je nach Anwendungsfall ein gültiger Ansatz sein, aber das OP hat ausdrücklich ein Wörterbuch angefordert, und dies ist definitiv kein Wörterbuch.

    – Dan Bechard

    14. April 2019 um 21:20 Uhr


Benutzeravatar von fkl
fkl

Ich bin überrascht, dass niemand erwähnt hat hsuchen/herstellen Satz von Bibliotheken, der zwar nicht unter Windows verfügbar ist, aber von POSIX vorgeschrieben wird und daher in Linux / GNU-Systemen verfügbar ist.

Der Link enthält ein einfaches und vollständiges Basisbeispiel, das die Verwendung sehr gut erklärt.

Es hat sogar eine Thread-sichere Variante, ist einfach zu bedienen und sehr leistungsfähig.

GLib und gnulib

Dies sind Ihre wahrscheinlich besten Wetten, wenn Sie keine spezifischeren Anforderungen haben, da sie allgemein verfügbar, portabel und wahrscheinlich effizient sind.

Siehe auch: Gibt es Open-Source-C-Bibliotheken mit gemeinsamen Datenstrukturen?

abc def Benutzeravatar von foo bar
abc def foo bar

Erstellen Sie eine einfache Hash-Funktion und einige verknüpfte Listen von Strukturen, weisen Sie je nach Hash zu, in welche verknüpfte Liste der Wert eingefügt werden soll. Verwenden Sie den Hash auch zum Abrufen.

Ich habe vor einiger Zeit eine einfache Implementierung durchgeführt:

...
#define K 16 // chaining coefficient

struct dict
{
    char *name; /* name of key */
    int val;   /*  value */
    struct dict *next; /* link field */
};

typedef struct dict dict;
dict *table[K];
int initialized = 0;


void  putval ( char *,int);

void init_dict()
{   
    initialized = 1;
    int i;  
    for(i=0;iname = (char *) malloc (strlen(key_name)+1);
    ptr->val = sval;
    strcpy (ptr->name,key_name);


    ptr->next = (struct dict *)table[hsh];
    table[hsh] = ptr;

}


int getval ( char *key_name )
{   
    int hsh = hash(key_name);   
    dict *ptr;
    for (ptr = table[hsh]; ptr != (dict *) 0;
        ptr = (dict *)ptr->next)
    if (strcmp (ptr->name,key_name) == 0)
        return ptr->val;
    return -1;
}

Benutzeravatar von dagoltz
dagoltz

Hier ist eine schnelle Implementierung, ich habe sie verwendet, um eine ‘Matrix’ (sruct) aus einer Zeichenfolge zu erhalten. Sie können ein größeres Array haben und seine Werte auch während der Ausführung ändern:

typedef struct  { int** lines; int isDefined; }mat;
mat matA, matB, matC, matD, matE, matF;

/* an auxilary struct to be used in a dictionary */
typedef struct  { char* str; mat *matrix; }stringToMat;

/* creating a 'dictionary' for a mat name to its mat. lower case only! */
stringToMat matCases [] =
{
    { "mat_a", &matA },
    { "mat_b", &matB },
    { "mat_c", &matC },
    { "mat_d", &matD },
    { "mat_e", &matE },
    { "mat_f", &matF },
};

mat* getMat(char * str)
{
    stringToMat* pCase;
    mat * selected = NULL;
    if (str != NULL)
    {
        /* runing on the dictionary to get the mat selected */
        for(pCase = matCases; pCase != matCases + sizeof(matCases) / sizeof(matCases[0]); pCase++ )
        {
            if(!strcmp( pCase->str, str))
                selected = (pCase->matrix);
        }
        if (selected == NULL)
            printf("%s is not a valid matrix name\n", str);
    }
    else
        printf("expected matrix name, got NULL\n");
    return selected;
}

1424650cookie-checkSchneller Weg zum Implementieren von Wörterbüchern in C

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy