L'allocation de mémoire adéquate

Question

J'ai la construction suivante:

typedef struct bucket {
    char *key;
    ENTRY *data;
    struct bucket *next;
} bucket;

typedef struct {
    size_t size;
    bucket **table;
} hash_table;

Mais je ne sais pas comment allouer de la mémoire pour cela. J'ai essayé:

hash_table* ht = malloc(sizeof(hash_table)*101);

afin de créer une table de hachage pour 101 entrées mais il din't travailler! Quelqu'un peut-il m'aider? Je voudrais vraiment l'apprécier!

Answer 1

Pas tout à fait. À supposer que c'est C, vous voulez probablement faire une fonction:

 hash_table* init_table(size_t size) {
     size_t i;
     hash_table* ht = (hash_table*)malloc(sizeof(hash_table));
     if (ht == NULL) return NULL;
     ht->size = size;
     ht->table = (bucket**)malloc(sizeof(bucket*)*size);
     if (ht->table == NULL) {
         free(ht);
         return NULL;
     }
     for (i = 0; i < size; ++i) {
         ht->table[i] = NULL;
     }
     return ht;
 }

Vous pourriez avoir besoin d'autres domaines que struct.

Si vous voulez être difficile, et ne jamais réallouer le seau, vous pouvez faire ceci:

 hash_table* init_table(size_t size) {
     hash_table* ht = (hash_table*)malloc(sizeof(hash_table)+sizeof(bucket)*size);
     if (ht == NULL) return NULL;
     ht->size = size;
     ht->table = (bucket**)(ht+1);
     for (i = 0; i < size; ++i) {
         ht->table[i] = NULL;
     }
     return ht;
 }

EDIT: je fixe mon seau * Table de Bucket **

EDIT2. J'ai réussi à se débarrasser des memsets et erreurs ajouté pour vérifier malloc

Answer 2

Il n'a pas de sens d'allouer les 101 (ou mais beaucoup) Seaux dès le départ, on indiquera les allouez un à la fois, lors de l'insertion de nouvelles données dans le tableau.

Finalité logique de pré-allouer le tableau de hachage, ce qui aura une taille fixe, mais qui est un tableau de pointeurs de seau , pas un tableau de godets , donc quelques-unes des réponses sont fausses.

Vous auriez quelque chose comme ça, pour créer une une table de hachage vide, avec un tableau de seau de taille fixe:

hash_table * hash_table_new(size_t capacity)
{
  size_t i;

  hash_table *t = malloc(sizeof *t);
  t->size = capacity;
  t->bucket = malloc(t->size * sizeof *t->bucket);
  for(i = 0; i < t->size; i++)
    t->bucket[i] = NULL;
  return t;
}

Ce code:

• Alloue une structure hash_table pour tenir la table
• Initialise sa taille avec une capacité indiquée
• Affecte un tableau de pointeurs de godet de la bonne longueur
• Makes que chaque pointeur de godet est NULL (qui ne peut pas être faite avec memset (), comme il est dangereux de supposer que « tous les bits zéro » est NULL dans la mémoire façon ressemble)
• Utilise la mesure du possible sizeof, mais pas sur les types, donc pas entre parenthèses
• ne redore pas la valeur de retour de malloc(), puisque c'est jamais une bonne idée dans C
• ne vérifie pas la valeur de retour de malloc (), bien sûr, vous devriez le faire dans votre code

Une deuxième fonction serait nécessaire pour faire une insertion de hachage réelle, qui sera ensuite besoin d'allouer un nouveau seau, calculer la valeur de hachage de la clé, choisissez l'emplacement approprié dans le tableau de la table de hachage, et insérez la nouvelle il y a l'entrée .

Answer 3

Le hash_table sera toujours seulement octets grand sizeof(hash_table). L'élément table est un pointeur vers un réseau de poiinters à bucket éléments. Donc, vous auriez besoin de quelque chose comme ceci:

hash_table* ht = malloc(sizeof(hash_table));
ht->size = 101;
ht->table = malloc(sizeof(bucket*)*ht->size);

Mais je pense qu'il peut y avoir une méthode d'initialisation qui vient avec cela, et vous pourriez faire quelque chose comme ceci:

hash_table* ht = alloc_hash_table(101);

Quoi qu'il en soit, je suis un peu rouillé en C, donc prendre avec un grain de sel.

Answer 4

Il y a quelques petites choses worong avec vos années typedef. En supposant que votre utilisation de MSVC.

Un moyen facile de déclarer les types que vous avez ici serait quelque chose comme:

Cette typedef inclut le type _type {}, * ptype; le format qui déclare le type et le pointeur sur votre commande type tout en même temps. Si vous voyez dans hash_table, vous êtes en mesure d'utiliser pbucket table *, ce qui élimine le supplément *** dans votre code et peut aider à faire lors de l'allocation dynamique (aide afin mucah à garder votre tête droite sur ce que votre allocation etc .. ). Votre typedef original, si vous regardez eu typedef seau struct {} seau ;, vous devez au moins modifier l'un des deux « seau » noms que vous avez là lorsque vous spécifiez votre typedef.

Vous devez également jeter si vous utilisez C ++ paramètres de construction, si vous utilisez C clair que vous ne pouvez pas besoin de la distribution, de sorte que votre ligne de malloc serait (avec les changements suivants typedef j'ai fait);

hash_table* ht = (phash_table) malloc(sizeof(hash_table)*101);

De toute façon, cet extrait devrait fonctionner pour vous;

typedef struct _bucket {    
    char *key;    
    void *data;    
    _bucket *next;
} bucket, *pbucket;

typedef struct _hash_table {    
    size_t size;    
    pbucket *table;
}hash_table, *phash_table;