[C] Structure de données à utiliser pour le parcours de dossier

Structure de données à utiliser pour le parcours de dossier [C] - C - Programmation

Marsh Posté le 02-11-2010 à 19:25:55    

Bonjour à tous.
 
J'ai un programme à faire qui à pour but de parcourir un répertoire et ses sous-répertoires, pour ensuite afficher divers résultats (Nombre de fichiers par utilisateur, leur taille totale cumulées, etc).
 
Je suis en train de réfléchir à la structure de données à utiliser, mais je n'arrive pas à voir comment je pourrais stocker toutes ses informations.
 
J'aimerais procéder ainsi :
- Parcours de tous les fichiers (dossier et sous-dossiers)
- A chaque fichier, je stock l'utilisateur (l'owner), la taille du fichier et le nom du fichier bien sûr
- Je parse le résultat suivant ce qui m'est demander
 
Pour la structure à utiliser, j'étais parti sur une liste par dossier, seulement j'ai un problème :  
- Je vais parcourir le premier dossier, créer une liste comprenant un nombre de noeuds égal au nombre de fichier dans le dossier. Quid des sous-dossiers ? Il me faudrait alors une liste de liste. Mais quid des sous-sous-dossiers ?
 
Je sais pas si vous voyez mon soucis, mais je ne vois pas trop quelle genre de structure 'dynamique' adopter pour un tel projet ...
 
Merci par avance pour vos réponses.
 :hello:  


---------------
:o
Reply

Marsh Posté le 02-11-2010 à 19:25:55   

Reply

Marsh Posté le 02-11-2010 à 20:21:05    

Peut-être qu'il serait plus simple d'afficher les résultats au fur et à mesure plutôt que de les stocker.
 
Sinon, la structure est celle d'une arborescence, c'est-à-dire :

Code :
  1. struct _node {
  2.   char name[256]; // Nom du dossier ou du fichier, sans le chemin
  3.   char type; // Dossier ou fichier
  4.   struct _node *parent_node; // pointeur vers le noeud père (ou on pourrait faire un pointeur vers le fils)
  5.   struct _node *next_node; // pointeur vers le noeud suivant au même niveau
  6. }


Reply

Marsh Posté le 03-11-2010 à 00:23:34    

Je rajouterais un pointeur child_node, sur le premier élément fils dans le cas d'un répertoire.


---------------
sheep++
Reply

Marsh Posté le 03-11-2010 à 01:10:06    

Merci pour vos réponses.

 

J'ai donc utilisé ta structure de données (Tree ?) en rajoutant un pointeur vers le premier élément fils.

 
Code :
  1. typedef struct Leaf
  2. {
  3. struct File *file;
  4. struct Leaf *parent;  // pointeur vers le noeud père
  5. struct Leaf *next;  // pointeur vers le noeud suivant au même niveau
  6. struct Leaf *child; // pointeur vers le fils
  7. } Leaf;
  9. typedef struct Tree
  10. {
  11. Leaf *first;
  12. } Tree;
 

Ma structure File est toute simple :

 
Code :
  1. typedef struct File
  2. {
  3. char *name;
  4. char *owner;
  5. int type;   // 0: dossier, 1: fichier régulier
  6. long long size;
  7. } File;
 


J'ai créé une méthode d'insertion qui va bien :

 
Code :
  1. void addLeaf (Tree *tree, Leaf *parent, Leaf *child)
  2. {
  3. child->child = NULL; // Dans tous les cas, le node qu'on ajoute n'a pas de fils ni de suivant
  4. child->next = NULL;
  6. if (parent == NULL) // Premier élément du Tree
  7. {
  8.  tree->first = child;
  9.  child->parent = NULL;
  10. }
  11. else if (parent->child == NULL) // On ajoute un fils à un parent qui n'a aucun fils
  12. {
  13.  parent->child = child;
  14.  child->parent = parent;
  15. }
  16. else // Le parent a au moins un fils, on ajoute 'child' a la suite
  17. {
  18.  Leaf *current = parent->child;
  19.  Leaf *prev = parent->child;
  20.  while (current != NULL)
  21.  {
  22.   prev = current;
  23.   current = current->next;
  24.  }
  25.  prev->next = child;
  26.  child->parent = parent;
  28. }
  29. }
  31. void addFile (Tree *tree, Leaf *parent, File f) // Méthode qui fait appel à addLeaf ensuite
  32. {
  33. File *file;
  34. file = malloc (sizeof (File));
  35. (*file) = f;
  37. Leaf *child;
  38. child = malloc (sizeof (Leaf));
  39. child->file = file;
  41. addLeaf (tree, parent, child);
  43. }
 


Maintenant j'essaie de parcourir mon arbre. Un parcours en profondeur me suffirait. Après diverses recherches, il semblerait qu'une fonction récursive soit nécessaire. Voici ce à quoi j'arrive :

 
Code :
  1. void displayTree (Tree *tree)
  2. {
  3. if (tree == NULL)
  4. {
  5.  printf("The tree is empty\n" );
  6. }
  7. else
  8. {
  9.  displayChildren (tree->first, 0); // Niveau 0
  10. }
  11. }
  13. void displayChildren (Leaf *leaf, int depth)
  14. {
  15. int i;
  16. for (i=0; i<depth; i++)
  17. {
  18.  printf("\t" ); // Pour indenter l'affichage
  19.  leaf = leaf->child; // On récupère le fils suivant le niveau de profondeur auquel on est arrivé
  20. }
  22. displayFile (*(leaf->file));
  24. while (leaf->next != NULL) // Tant qu'on a un suivant
  25. {
  26.  displayChildren (leaf->next, depth+1);
  27.  leaf = leaf->next;
  28. }
  29. }
 

Bien entendu, ça ne m'affiche pas tout, et je vois pourquoi :
- 1er appel à displayChildren avec le premier noeud, il l'affiche. Ensuite il fait appel au next (des fois qu'il y en aurait), et comme il n'y en a pas, il s'arrête. Or mon premier noeud à des fils, et ces derniers sont ignorés ...

 

Je suis mal parti ?


Message édité par Ydalb le 03-11-2010 à 01:11:06

---------------
:o
Reply

Marsh Posté le 03-11-2010 à 09:37:06    

Je n'ai pas regardé dans le détail, je laisse cela aux bon spécialistes du C de ce forum.
 
Juste quelques remarques sur la nomenclature :

Code :
  1. typedef struct Tree
  2. {
  3. Leaf *first;
  4. } Tree;

Il ne faut pas nommer de la même manière la structure (le premier Tree) et l'espace alloué pour la structure (le dernier Tree). Une convention assez répandue est de nommer la structure en la faisant commencer par un tiret de soulignement, ce qui donnerait :

Code :
  1. typedef struct _Tree
  2. {
  3. Leaf *first;
  4. } Tree;

En plus, il y a une confusion à cause du typedef.
Pour infos, le typedef n'est pas obligatoire, mais les profs l'aiment beaucoup. Quand on l'utilise, une convention assez répandue est de donner un nom tout en majuscules.
Si on utilise un typedef, alors, il dvient inutile de répeter le mot struct. Gagner ces 6 lettres est un avantage (pour certains (personnellement, je n'utilise japmais typedef car je trouve que cela rend le code moins lisible en cachant ce mot struct, mais c'est un débat de trolls)).

Citation :

Leaf *leaf ... File *file;

Il vaut mieux éviter d'avoir des noms qui se ressemblent trop, car on a vite fait d'oublier la majuscule ou la minuscule.


Message édité par olivthill le 03-11-2010 à 09:41:59
Reply

Marsh Posté le 03-11-2010 à 12:39:41    

Merci pour tes remarques, mais j'ai toujours eu l'habitude (grâce / à cause des profs ;)) d'utiliser typedef.
 
pour les noms de variables, je me sers de la règles : commence par une majuscule, c'est un type, commence par une minuscule, c'est une variable, et ça se passe bien.
 
Reste plus qu'à voir pour le parcours de l'arbre :D


---------------
:o
Reply

Marsh Posté le 03-11-2010 à 14:46:11    

Je verrais plutot ton fonction displayChildren comme ca (non testée!):

Code :
  1. void displayChildren (Leaf *leaf, int depth)
  2. {
  3.          int i;
  4.         if (leaf != NULL)
  5.        {
  7.      for (i=0; i<depth ; i++)
  8.     {
  9.  printf("\t" ); // Pour indenter l'affichage
  10.     }
  11.             displayChildren(Leaf->child, depth+1); // on affiche d'abord les fils (donc a une profondeur de plus)
  13.             displayChildren (leaf->next, depth); // Les nœuds "frères" sont au même niveau!, on n'affiche que le premier (qui lui affichera a son tour son premier, etc)
  15.      displayFile (*(leaf->file)); // on affiche les fichiers du répertoire courant.
  16.         }
  17. }


Message édité par breizhbugs le 03-11-2010 à 14:47:45
Reply

Marsh Posté le 03-11-2010 à 14:55:53    

pour faire ce genre de traitements, j'aurais intuitivement envie d'éviter de stocker des infos sur chaque fichier en mémoire vu que le nombre de fichiers à traiter va probablement être conséquent.
 
Je te conseillerais plutôt de partir plus dans une optique de requête et appliquer cette requête sur chaque fichier / dossier en faisant une passe sur ton disque.
 
La requête sachant elle-même si elle doit compter des fichiers, calculer une taille ou autre. Ca a un autre avantage, c'est que tu pourras faire des requêtes composites assez aisément avec un système de ce genre.
 


---------------
last.fm
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed