Il y a plein de manière de faire.

1) Tu peux stocker ton fichier texte au format tsv ou csv (une ligne par structure, chaque membre apparaît dans l'ordre séparé par un caractère spécial, par exemple tabulation pour un tsv ou ; pour un csv). Du coup il est assez simple de relire ton fichier, par exemple à l'aide des fonctions getline et strtok.
http://fr.wikipedia.org/wiki/Comma-separated_values
http://fr.wikipedia.org/wiki/Format_TSV
http://man.developpez.com/man3/getline.3.php
http://www.linux-kheops.com/doc/man/manfr/man-html-0.9/man3/­strtok.3.html

- Avantages : tu ne dépends d'aucune librairie, c'est simple, et tu peux l'importer dans un tableur (par exemple OpenOffice - oocalc).

- Inconvénients : il faut le coder, c'est lent, le format n'est pas forcément simple à faire évoluer (en particulier si tu décides de rajouter des attributs pour décrire tes contacts).

2) Tu peux stocker ton fichier au format xml. Il existe plein de librairies pour manipuler des fichiers xml (lecture / écriture).
http://fr.wikipedia.org/wiki/Extensible_Markup_Language

Par exemple :
http://xerces.apache.org/xerces-c/

- Avantages : c'est déjà codé, le format peut facilement évoluer, il existe des parseurs xml dans plein d'autres langages et donc ce format de fichier est facilement réutilisable.

- Inconvénients : il faut coupler ton PC avec une libraire et prendre le temps de voir comment ça marche, et comme c'est un fichier texte, c'est lent (il faut le lire, l'insérer dans la structure etc...).

3) Encore mieux, plutôt que de stocker ton annuaire sous forme de fichier texte (ce qui est lent à lire et à écrire quand le fichier devient très volumineux, même si tu n'en as a priori pas le besoin car je doute que tu aies plusieurs milliers de contacts), c'est d'écrire ta structure directement sous forme d'un binaire en utilisant des opérations de serialization et deserialization. Là c'est pour les barbus, et c'est ici que ça se passe :
http://www.boost.org/doc/libs/1_38_0/libs/serialization/doc/­index.html

- Avantages : c'est déjà codé, le format peut facilement évoluer, c'est la méthode la plus rapide en terme de temps d'exécution

- Inconvénients : c'est la plus compliquée (boost n'est pas facile à prendre en main), le fichier ne peut pas être facilement réutilisé par une autre application. L'utilisation de structures sérialisées impose certaines contraintes de programmation (pas de pointeurs, de référence dans les structures à sérialiser).

Bonne chance