Cara Cepat untuk Menerapkan Kamus di C

Salah satu hal yang saya rindukan saat menulis program di C adalah struktur data kamus. Apa cara paling nyaman untuk mengimplementasikannya di C? Saya tidak mencari kinerja, tetapi kemudahan mengkodekannya dari awal. Saya tidak ingin menjadi generik juga - sesuatu seperti string-> int akan dilakukan. Tapi saya ingin bisa menyimpan jumlah item yang sewenang-wenang.

Ini lebih dimaksudkan sebagai latihan. Saya tahu bahwa ada perpustakaan pihak ke-3 yang tersedia yang bisa digunakan. Tetapi pertimbangkan sejenak, bahwa mereka tidak ada. Dalam situasi seperti itu, apa cara tercepat Anda dapat mengimplementasikan kamus yang memenuhi persyaratan di atas.

Bagian 6.6 dari Bahasa Pemrograman C menyajikan struktur data kamus sederhana (hashtabel). Saya tidak berpikir implementasi kamus yang berguna bisa menjadi lebih sederhana dari ini. Untuk kenyamanan Anda, saya mereproduksi kode di sini.

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

Perhatikan bahwa jika hash dari dua string bertabrakan, itu dapat menyebabkan O(n)waktu pencarian. Anda dapat mengurangi kemungkinan tabrakan dengan meningkatkan nilai HASHSIZE. Untuk diskusi lengkap tentang struktur data, silakan baca buku.

Cara tercepat adalah dengan menggunakan implementasi yang sudah ada, seperti uthash .

Dan, jika Anda benar - benar ingin membuat kode sendiri, algoritme dari uthashdapat diperiksa dan digunakan kembali. Ini dilisensikan BSD jadi, selain dari persyaratan untuk menyampaikan pemberitahuan hak cipta, Anda cukup tak terbatas dalam hal apa yang dapat Anda lakukan dengannya.

Untuk kemudahan implementasi, sulit untuk mengalahkan pencarian secara naif melalui array. Selain dari beberapa pengecekan kesalahan, ini adalah implementasi lengkap (belum diuji).

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

Buat fungsi hash sederhana dan beberapa daftar struktur yang ditautkan, tergantung pada hash, tetapkan daftar tautan mana yang akan dimasukkan nilainya. Gunakan hash untuk mengambilnya juga.

Saya melakukan implementasi sederhana beberapa waktu lalu:

...
#define K 16 // koefisien rantai

dikte struct
{
    nama karakter; / * nama kunci * /
    int val; / * nilai * /
    struct dict * selanjutnya; / * bidang tautan * /
};

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


membatalkan putval (char *, int);

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


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

}


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

GLib dan gnulib

Ini kemungkinan adalah taruhan terbaik Anda jika Anda tidak memiliki persyaratan yang lebih spesifik, karena tersedia secara luas, mudah dibawa-bawa dan kemungkinan efisien.

• GLib: https://developer.gnome.org/glib/ oleh proyek GNOME. Beberapa kontainer didokumentasikan di: https://developer.gnome.org/glib/stable/glib-data-types.html termasuk "Tabel Hash" dan "Pohon Biner Seimbang". Lisensi: LGPL

• gnulib: https://www.gnu.org/software/gnulib/ oleh proyek GNU. Anda seharusnya menyalin tempel sumber ke kode Anda. Beberapa kontainer didokumentasikan di: https://www.gnu.org/software/gnulib/MODULES.html#ansic_ext_container termasuk "rbtree-list", "daftar-hash-list" dan "-rbtreehash-list". Lisensi GPL.

Lihat juga: Apakah ada pustaka sumber terbuka C dengan struktur data umum?

di sini adalah implementasi cepat, saya menggunakannya untuk mendapatkan 'Matrix' (sruct) dari sebuah string. Anda dapat memiliki array yang lebih besar dan mengubah nilainya saat dijalankan juga:

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

Saya terkejut tidak ada yang disebutkan hsearch / hcreate set perpustakaan yang walaupun tidak tersedia di windows, tetapi diamanatkan oleh POSIX, dan karena itu tersedia di sistem Linux / GNU.

Tautan ini memiliki contoh dasar yang sederhana dan lengkap yang menjelaskan penggunaannya dengan sangat baik.

Ia bahkan memiliki varian thread yang aman, mudah digunakan dan sangat performant.

Hashtable adalah implementasi tradisional dari "Kamus" sederhana. Jika Anda tidak peduli dengan kecepatan atau ukuran, cukup google untuk itu . Ada banyak implementasi yang tersedia secara bebas.

inilah yang pertama saya lihat - sekilas, itu terlihat ok untuk saya. (Ini cukup mendasar. Jika Anda benar-benar ingin menyimpan data dalam jumlah yang tidak terbatas, maka Anda perlu menambahkan beberapa logika untuk "realokasi" memori tabel saat itu tumbuh.)

semoga berhasil!

Hashing adalah kuncinya. Saya pikir menggunakan tabel pencarian dan kunci hashing untuk ini. Anda dapat menemukan banyak fungsi hashing online.

Metode tercepat akan menggunakan pohon biner. Kasus terburuknya juga hanya O (logn).