Pile, file... [C/C++] - Programmation
Marsh Posté le 13-12-2001 à 15:24:44
la pile :
si on a une fonction recursive et qu'on veut la derecursiver pour optimiser
la file :
je m'en suis servit pour des parcours en largeur d'arbres ( aratique dans certains cas
Marsh Posté le 13-12-2001 à 15:26:23
ben ca depend
Imagine un undo pour un prog d'image : a chaque modif tu met l'image avant modif sur une pile
quand le type click sur undo tu depile un coup
(exemple a la con )
Marsh Posté le 13-12-2001 à 15:28:39
flo850 a écrit a écrit : la pile : si on a une fonction recursive et qu'on veut la derecursiver pour optimiser la file : je m'en suis servit pour des parcours en largeur d'arbres ( aratique dans certains cas |
J'suis pas super a l'aise avec les fonctions recursives donc dmc
C'est koi ton histoire d'arbre ? arbre binaire ?
chris -> au contraire, tres bon exemple
Marsh Posté le 13-12-2001 à 16:23:27
Très bon exemple dans le principe, c'est sur, mais faut une grosse pile si l'image est volumineuse.
Marsh Posté le 13-12-2001 à 17:19:36
Godbout a écrit a écrit : C'est koi ton histoire d'arbre ? arbre binaire ? |
bein les arbres c comme les listes chaines a peu de chose pres (ca te rapelle rien lol ) l'arbre contien un maillon tete et d'autre maillons ki eux comporte 2 pointeurs une pour le maillons fils et le maillon suivant c surtout utiliser en compression fin du moins c la que je l'ai vu utiliser genre la compression d'huffman si tu connais
Marsh Posté le 13-12-2001 à 17:33:58
qxn a écrit a écrit : bein les arbres c comme les listes chaines a peu de chose pres (ca te rapelle rien lol ) l'arbre contien un maillon tete et d'autre maillons ki eux comporte 2 pointeurs une pour le maillons fils et le maillon suivant c surtout utiliser en compression fin du moins c la que je l'ai vu utiliser genre la compression d'huffman si tu connais |
ouais je connais
mais je voulais savoir si c'etait bien de ca qu'il parlait, puisqu'il n'a pas precise
edit: c'est le terme 'largeur d'arbre' qui me tracasse un peu
[edtdd]--Message édité par Godbout--[/edtdd]
Marsh Posté le 13-12-2001 à 18:53:20
nan c'est pas "largeur d'arbre"
c'est "parcours en largeur" d'arbre
en gros quand tu fais une recherche exhaustive dans un arbre
tu as deux options: parcours en largeur ou parcours en profondeur.
pour le parcours en profondeur, tu entasses
les noeuds a visiter sur une pile (LIFO)
et quand tu reviens sur tes pas tu depiles (recursivite classique) ceux que tu as visite.
Pour le parcours en largeur, tu pars du noeud
racine, tu places les enfants dans
une file (FIFO). Et tu visites le noeud le plus ancien
de ta file, et a chaque fois que tu as visite un noeud
tu l'enleves de la file en prenant soin de mettre ses enfants
a la fin de la file. (en gros tu parcours
les noeuds au niveau 1 puis au niveau 2 etc..)
A noter que si l'element a trouver existe dans ton arbre
le parcours en largeur garantit de le trouver.
Par contre le parcours en profondeur peut ne pas terminer
(si une branche se prolonge a l'infini).
LEGREG
Marsh Posté le 13-12-2001 à 19:06:07
Et apres j'm'etonne de passer pour un con
Bon etant donne que les arbres c'est encore flou (eh oui j'suis pas tres doué , pis comme je les utilise jamais ), j'vais voir ca de plus pres !
Merci
Marsh Posté le 13-12-2001 à 21:53:48
Récemment dans mon cours d'info, le prof nous a demandé de faire un gestionnaire de fichiers multi-tâches sous Dos. J'ai du me servir des piles, files, arbres et listes.
Je vais te parler pour le multî-tâches car j'ai trouvé ça vraiment bien pour te parler des piles ou files ( je sais pas trop ce que j'avais fait mais ca marchais ).
J'avais une fonction pour gérer la souris, d'après l'endroit où je cliquais dans l'écran. Une pour gérer le scroll, détruire un fichier, créer un dossier, blablabla... gestionnaire de fichiers !!! Tout cela devait être multi-tache donc quand je voulais les fichiers contenu dans le répertoire sélectionné, je ne pouvais pas faire quelque chose comme :
...
while(findnext(&fblock) == 0)
{
moule = malloc(sizeof(struct lafile));
fin -> suivant = moule;
moule -> avant = fin;
moule -> suivant = NULL;
fin = moule;
moule -> position = position_fichiers_1;
position_fichiers_1++;
strcpy(moule -> nom_fichier, fblock.ff_name);
ltoa(fblock.ff_fsize, grosseur, 10);
strcpy(moule -> size_fichier, grosseur);
}
Il faut se faire une pile afin que tout fonctionne en meme temps. Exemple :
1:Gère_souris
2:Lire UNE entrée du répertoire.
3:Quelque chose dautre qu'on aurait cliqué...
Ensuite retourner à gère souris et blablabla... vous comprenez ?
Ça peut paraître idiot, mais quand je suis arrivé à copier un fichier caractère par caractère ( le prof demandait cela pour nous prouver ce qu'il disait ... ), la copie d'un fichier de 30 Ko prenait environ 30 secondes... pendant ce long laps de temps, tout le système était paralyser par la boucle :
if(feof(pfichier) == 0)
{
c = fgetc(pfichier);
fputc(c, pfichier2);
}
Pour le multitaches, je mettais une fois dans ma pile LIRE, ensuite les fonctions necessaire au système, et ensuite ÉCRIRE, ainsi de suite... Windows fonctionne un peu de la même manière
Ma pile contenait des valeurs, correspondant aux étapes dans le SWITCH général.
Vous avez des commentaires ?
Marsh Posté le 13-12-2001 à 15:05:47
J'me demandais juste quand on pouvait s'en servir parce que la je cherche mais je vois pas
Je parle d'un exemple concret en prog (pas d'une pile d'assiete ou d'une file d'attente).