Schnelle Möglichkeit, das Wörterbuch in C zu implementieren

132

Eines der Dinge, die ich beim Schreiben von Programmen in C vermisse, ist eine Wörterbuchdatenstruktur. Was ist der bequemste Weg, um einen in C zu implementieren? Ich bin nicht auf der Suche nach Leistung, sondern nach einer einfachen Codierung von Grund auf. Ich möchte auch nicht, dass es generisch ist - so etwas wie string-> int reicht aus. Aber ich möchte, dass es eine beliebige Anzahl von Elementen speichern kann.

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

Rohit
quelle
4
Wenn Sie es nicht zur Verfügung stellen möchten, warum möchten Sie es dann von Grund auf neu erstellen, anstatt eine Implementierung eines Drittanbieters zu verwenden?
Karl Knechtel
Ja, diese Alternative gibt es immer. Ich habe diese Frage eher als Übung gestellt.
Rohit
10
Das Schreiben einer Hashtabelle in C macht Spaß - jeder ernsthafte C-Programmierer sollte dies mindestens einmal tun.
Lee
Ich denke, ein Wörterbuch ist eher ein Datentyp als eine Datenstruktur, da es auf viele Arten implementiert werden kann - eine Liste, eine Hashtabelle, ein Baum, ein selbstausgleichender Baum usw. Fragen Sie nach einem Wörterbuch oder einer Hashtabelle? ?
Paul Hankin
1
Verwandte: Wie man ein Python-ähnliches Wörterbuch in C darstellt? [] ( Stackoverflow.com/questions/3269881/… )
Gaurang Tandon

Antworten:

114

Abschnitt 6.6 der Programmiersprache C enthält eine einfache Wörterbuchdatenstruktur (Hashtabelle). Ich denke nicht, dass eine nützliche Wörterbuchimplementierung einfacher sein 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 eine Kollision der Hashes zweier Zeichenfolgen zu einer O(n)Suchzeit führen kann. Sie können die Wahrscheinlichkeit von Kollisionen verringern, indem Sie den Wert von erhöhen HASHSIZE. Eine vollständige Beschreibung der Datenstruktur finden Sie im Buch.

Vijay Mathew
quelle
1
Wenn es aus dem C-Buch stammt, frage ich mich, ob es eine kompaktere Implementierung geben kann.
Rohit
30
@Rohit, für einen nützlichen C-Code wird es nicht viel kompakter. Ich nehme an, Sie könnten immer ein Leerzeichen entfernen ...
Ryan Calhoun
7
warum ist hier hashval = *s + 31 * hashval;genau 31 und sonst nichts?
ス レ ッ ク.
12
31 ist Prime. 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 keine Primzahl faktorisieren).
Jnovacho
2
@Overdrivr: In diesem Fall nicht erforderlich. Hashtab ist von statischer Dauer. Nicht initialisierte Variablen mit statischer Dauer (dh solche, die außerhalb von Funktionen deklariert wurden, und solche, die mit der statischen Speicherklasse deklariert wurden) beginnen garantiert als Null des richtigen Typs (dh: 0 oder NULL oder 0.0)
carveone
19

Der schnellste Weg wäre, eine bereits vorhandene Implementierung wie uthash zu verwenden .

Und wenn Sie es wirklich selbst codieren möchten, können die Algorithmen von uthashüberprüft und wiederverwendet werden. Es ist BSD-lizenziert, so dass Sie, abgesehen von der Anforderung, den Urheberrechtshinweis zu übermitteln, ziemlich unbegrenzt sind, was Sie damit tun können.

paxdiablo
quelle
8

Um die Implementierung zu vereinfachen, ist es schwer, die naive Suche in einem Array zu übertreffen. 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);
}
Paul Hankin
quelle
2
"Zur Vereinfachung der Implementierung": Sie haben genau Recht: Dies ist die einfachste. Außerdem implementiert es die Anforderung des OP "Ich möchte, dass es eine beliebige Anzahl von Elementen speichern kann" - die Antwort mit der höchsten Stimme tut dies nicht (es sei denn, Sie glauben, dass die Auswahl einer Kompilierungszeitkonstante "willkürlich" erfüllt ...)
Davidbak
1
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
3

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 // Verkettungskoeffizient

struct dict
{
    char * name; / * Name des Schlüssels * /
    int val; /* Wert */
    struct dict * next; / * Linkfeld * /
};

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


void putval (char *, int);

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


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

}}


int getval (char * key_name)
{   
    int hsh = Hash (Schlüsselname);   
    dict * ptr;
    für (ptr = Tabelle [hsh]; ptr! = (dict *) 0;
        ptr = (dict *) ptr-> next)
    if (strcmp (ptr-> name, key_name) == 0)
        return ptr-> val;
    return -1;
}}
abc def foo bar
quelle
1
Fehlt Ihnen nicht der halbe Code? Wo ist "hash ()" und "putval ()"?
Swdev
3

GLib und Gnulib

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

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

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
quelle
2

Hier ist eine schnelle Implementierung, ich habe es verwendet, um eine 'Matrix' (sruct) aus einem String zu erhalten. Sie können ein größeres Array haben und seine Werte während des Laufs ä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;
}
Dagoltz
quelle
2

Ich bin überrascht, dass niemand einen Satz von hsearch / hcreate- Bibliotheken erwähnt hat, 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 seine Verwendung sehr gut erklärt.

Es hat sogar eine thread-sichere Variante, ist einfach zu bedienen und sehr performant.

fkl
quelle
2
Es ist erwähnenswert
Ciro Santilli 郝海东 冠状 病 六四 事件 26
1
Fair genug, aber ich habe die Version hcreate_r (für mehrere Hash-Tabellen) in mindestens einer App ausprobiert, die ziemlich lange genug lief, um sie als reale Welt zu betrachten. Einverstanden, dass es sich um eine GNU-Erweiterung handelt, aber das gilt auch für viele andere Bibliotheken. Obwohl ich immer noch argumentieren würde, dass Sie es möglicherweise immer noch für ein großes Schlüsselwertpaar verwenden können, das in einer realen App betrieben wird
fkl
0

Eine Hashtabelle ist die traditionelle Implementierung eines einfachen "Wörterbuchs". Wenn Sie sich nicht für Geschwindigkeit oder Größe interessieren, googeln Sie einfach danach . Es gibt viele frei verfügbare Implementierungen.

Hier ist der erste, den ich gesehen habe - auf einen Blick sieht es für mich in Ordnung aus. (Es ist ziemlich einfach. Wenn Sie wirklich möchten, dass es eine unbegrenzte Datenmenge enthält, müssen Sie eine Logik hinzufügen, um den Tabellenspeicher "neu zuzuweisen", wenn er wächst.)

Viel Glück!

Lee
quelle
-1

Hashing ist der Schlüssel. Ich denke, verwenden Sie hierfür die Nachschlagetabelle und den Hashing-Schlüssel. Sie können viele Hashing-Funktionen online finden.

ashmish2
quelle
-1

Die schnellste Methode wäre die Verwendung eines Binärbaums. Sein schlimmster Fall ist auch nur O (logn).

Programmierer
quelle
15
Das ist falsch. Die Worst-Case-Suche für einen Binärbaum ist O (n) (entarteter Fall aufgrund einer schlechten Einfügereihenfolge, was im Grunde genommen zu einer Linkliste führt), wenn er nicht ausgeglichen ist.
Randy Howard