Comment stocker les informations de contact

Question

Quelle est la meilleure structure de données pour stocker les informations de contact [nom, numéro de téléphone]?

Trie peut être utile pour rechercher un numéro de téléphone lorsque le nom est donné.
Que faire si je veux trouver un nom de personne donné à son numéro de téléphone. c'est-à-dire comment puis-je trouver un nom lorsque je connais le numéro de téléphone?
Est-il efficace pour une telle recherche?

Answer 1

Oui, un trie est bon. Au lieu d'utiliser les caractères de la chaîne comme clé à chaque niveau, vous pouvez utiliser les bits du numéro de téléphone (si vous les stockez comme entiers). Pour des raisons de vitesse, vous pouvez décider d'utiliser 3 ou 4 bits à la fois. Cela fonctionnerait en ayant une structure trie qui stocke les informations d'identité en cours, puis un tableau de pointeurs vers les structures enfant.

struct phone_number_trie { 
    struct contact_info *info; 
    struct phone_number_trie *children[4]; // or 2, 8 or 16 etc. 
}; 

E.g. stocker le numéro de téléphone '83' (qui est 1100011 en binaire) dans un arbre où la racine est root, vous pouvez masquer les 2 bits inférieurs (par exemple & 3), qui sont 11, de sorte que vous vous recurerez en root->children[3] avec les bits restants du numéro de téléphone 11000 (c.-à-décalage de droite 2). Les indices suivants seraient 0, puis 10 puis 1 (vous pointeriez donc root->children[3]->children[0]->children[2]->children[1]). À ce stade, vous n'avez plus aucun bit dans votre numéro de téléphone, vous avez donc trouvé le bon endroit pour l'insérer.

(Vous pouvez également envisager d'utiliser un Patricia trie, mais cela est beaucoup plus difficile à mettre en œuvre.)