Eh bien, je fais une petite application de répertoire téléphonique et j'ai décidé que l'utilisation de cartes serait la meilleure structure de données à utiliser mais Je ne sais pas où commencer. (Doit mettre en œuvre la structure de données à partir de zéro - travail scolaire)Comment implémenter une structure de tableau associatif array/map/hash (en général et en C++)
Tries sont assez efficaces pour implémenter des cartes où les clés sont des chaînes courtes. L'article wikipedia l'explique plutôt bien.
Pour faire face à des doublons, il suffit de faire chaque nœud de l'arbre stocke une liste chaînée de double correspond
Voici une structure de base pour une structure arborescente
struct Trie {
struct Trie* letter;
struct List *matches;
};
malloc (26 * sizeof (struct Trie)) pour la lettre et vous avez un tableau. Si vous souhaitez prendre en charge les ponctuations, ajoutez-les à la fin du tableau de lettres. Les correspondances peuvent être une liste chaînée de correspondances, implémentées comme bon vous semble, je ne définirai pas struct List pour vous.
ah mon mauvais, cela aurait dû être un pointeur –
Désolé mais d'après ce que je comprends, serait-il plus intuitif de le nommer nœud au lieu de Trie? 'struct Node { struct Node * lettre; struct List * correspond à; }; ' Merci ... Editer: Désolé, il semble que nous ne puissions pas mettre les commentaires en format" code ". – Dois
Utilisez 'new', pas' malloc'. – GManNickG
Une approche simple pour vous aider à démarrer serait de créer une classe de carte qui utilise deux vecteurs - un pour la clé et un pour la valeur. Pour ajouter un élément, vous insérez une clé dans l'une et une valeur dans une autre. Pour trouver une valeur, il suffit de boucler toutes les clés. Une fois que vous avez ce travail, vous pouvez penser à utiliser une structure de données plus complexe.
Solution la plus simple: utilisez un vecteur qui contient vos entrées d'adresse et faites une boucle sur le vecteur à rechercher.
Une carte est généralement implémentée en tant qu'arbre binaire (recherche d'arbres rouges/noirs pour l'équilibrage) ou en tant que carte de hachage. Les deux ne sont pas insignifiants: les arbres ont des frais généraux pour l'organisation, la gestion de la mémoire et l'équilibrage, les cartes de hachage ont besoin de bonnes fonctions de hachage, qui ne sont pas non plus triviales. Mais les deux structures sont amusantes et vous aurez beaucoup de compréhension en implémentant l'une d'entre elles (ou mieux, les deux :-)). Considérez également de conserver les données dans la liste des vecteurs et de laisser la carte contenir des indices au vecteur (ou des pointeurs vers les entrées): alors vous pouvez facilement avoir plusieurs indices, disons un pour le nom et un pour le numéro de téléphone , de sorte que vous pouvez rechercher des entrées par les deux.
Cela dit je veux juste de recommander fortement d'utiliser les structures de données fournies par la bibliothèque standard pour les tâches réelles :-)
Combien C++ vous avez couvert? Les réponses peuvent aller de la «carte codée en dur» à la réécriture de la version du modèle de «std :: map» si nous devons deviner. :) – GManNickG
les tableaux associatifs ne gèrent pas les doublons, et si vous avez un doublon dans votre annuaire? Je vous suggère d'utiliser un arbre binaire. –
@Charles std :: multimap peut contenir des doublons –