Discussion :

[platnorm]

Bonsoir tout le monde, j'ai un tout petit exercice que j'ai du mal a finir. Bon l'énoncée est la suivante : Ecrire une fonction qui affiche le nombre d'occurences de chaque élément d'une liste chainée :
voila le code que je propose :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Occurences2(Noeud *T){ 
    int compteur; Noeud *P=T;Noeud *Q;
    while(P){
            compteur = 0;
            Q=T;
            while(Q){
                if(Q->v == P->v) compteur++;
                Q=Q->suiv;
            }
            printf("%d figure %d fois\n",P->v,compteur);
            P=P->suiv;
    }
}
}

la structure est la suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
typedef struct Noeud{
    int v; // valeur du noeud
    struct Noeud* suiv; // pointeur sur l'élement suivant
    }Noeud;

-> le probleme c'est qu'il ya une redondance au niveau des affichage, par exemple : la liste est 45567664 le resultat de la fonction
est : 4 figure 2 fois
5 figure 2 fois
5 figure 2 fois
6 figure 3 fois
7 figure 1 fois
6 figure 3 fois
6 figure 3 fois
4 figure 2 fois
-> Comment pourais je remedier a ce probleme et merci.

[Médinoc]

Tu peux te faire une autre liste, de valeurs déjà visitées, ou tu peux faire un autre algorithme, plus lent:

1. Chercher la plus petite valeur
2. Compter cette valeur
3. Afficher la valeur et son compte
4. Chercher la plus petite valeur supérieure à celle-ci
5. Recommencer à 2 si une telle valeur est trouvée.

[foetus]

Ou alors dans chaque maillon un booléen "is_visited" (ou un enum ou ...) mais il faut faire attention à sa valeur initiale.

Et éventuellement un compteur de maillons visités pour arrêter ta boucle plus tôt.

[emixam16]

Si le nombre de valeurs que peuvent prendre ta liste est assez réduit tu peux faire un tri comptage (ou tri par casier). Comme ça tu auras un tri simple à mettre en œuvre, et surtout en O(n).