Recherche par ordre alphabétique dans un fichier Fermé

Question

Bonjour, 

Je poste ce sujet car ce que je trouve sur le net c'est plutôt "comment trier un tableau par ordre alphabétique". Dans mon cas ce n'est pas du tout le cas, en effet, je récupère une chaîne de caractère et je voudrai trouver la ligne correspondante dans un fichier trié par ordre alphabétique.
J'aimerai éviter de scanner tout le fichier car le programme risque d'être très long à force de parcourir tout le temps tous le fichier.

Est-ce que vous connaissez un programme ou une technique qui pourrait m'aider à réaliser ce que je veux?

Je vous remercie.

yg_be · Answer

bonjour, moi, pour réaliser cela, je lirais une fois tout le fichier, je créerais en mémoire une structure d’accès, qui indexe le fichier, puis, pour chaque chaîne de caractères, j'utiliserais la technique expliquée ici pour lire la partie utile du ficher.

[Dal] · Answer

Salut  hymenoptera,

J'ai 3 questions :

Les lignes sont-elles longues ?
Il y a combien de lignes dans ton fichier ?
Quelle est sa taille sur le disque ?

Si les lignes sont relativement courtes, que le nombre de lignes correspond à un entier pouvant être représenté par les types standard du C et que sa taille sur le disque est raisonnable par rapport à ta mémoire vive disponible pour que tu puisses le charger en totalité et gérer un index, et vu que les lignes de ton fichier sont déjà triées alphabétiquement, tu devrais juste :

- déclarer un tableau de pointeurs sur char pouvant contenir un nombre de pointeurs sur char égal au nombre de lignes du fichier
- avec fread charger la totalité du fichier dans un tampon mémoire
- sur ce tampon utiliser strtok avec '
' comme caractère séparateur pour délimiter les chaînes en insérant au fur et à mesure au tableau de pointeurs, les pointeurs vers les chaînes délimitées

pour programmer cela, tu peux t'inspirer de ce code que j'ai posté il y a quelques temps : https://forums.commentcamarche.net/forum/affich-35265601-novice-dans-la-programmation#17 (exemple sur un fichier de 575133 mots d'un dictionnaire libre de mots en grec comportant un mot par ligne)

à ce stade tu as ton index vers les chaînes chargées en mémoire sous la forme d'un tableau ordonné de pointeurs sur char, que tu peux utiliser en implémentant un algorithme de recherche dichotomique pour rechercher l'existence d'une chaîne.

https://fr.wikipedia.org/wiki/Recherche_dichotomique

Tu pourrais aussi utiliser un hash ou d'autres algorithmes de recherche, mais si ton fichier présente les caractéristiques décrites ci-dessus, c'est probablement des complications pour pas grand chose :-)


Dal

Recherche par ordre alphabétique dans un fichier

2 réponses

Discussions similaires