Discussion :

[Cladouros]

Bonjour,

Je souhaite insérer un élément dans une liste chaînée circulaire, mais je peine un peu. Les éléments doivent être triés selon un ordre décroissant. Bien que cette fonction soit erronée, voilà où j'en suis actuellement (histoire de vous prouver que j'ai essayer de chercher) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Ajout(ListeArticles liste, Article *a) {
    Article *tmp = liste;
 
    while(tmp->nextArticle != liste) {
        if(a->PU >= tmp->nextArticle->PU) {
            a->nextArticle = tmp->nextArticle->nextArticle;
            tmp->nextArticle = a;
        }
 
        tmp = tmp->nextArticle;
    }
 
    if(tmp->nextArticle == liste) {
        a->nextArticle = liste;
        tmp->nextArticle = a;
    }
}

Je débute avec les listes chaînées, veuillez donc m'excuser si la raison pour laquelle je suis bloquée paraît stupide.

PS : La fonction ne peut renvoyer que void à cause de la consigne qu'on m'a donnée.

Merci d'avance pour votre aide.

[jeroman]

Salut,

Voici un exemple de ce que j'aurais fait :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdio.h>
#include <stdlib.h>
 
typedef struct Article
{
    struct Article * nextArticle;
    int PU;
} Article ;
 
void Ajout(Article ** liste, Article *a)
{
    Article * article_courant = *liste;
    Article * article_precedent = *liste;
 
    /* s'il n'existe aucun article dans la liste, on ajoute le premier */
    if (*liste == NULL)
    {
        *liste = a ;
        a->nextArticle = a ;
        return;
    }
 
    /* on cherche où insérer l'article */
    do
    {
        if ( article_courant -> PU >= a -> PU )
        {
            if (article_courant != article_precedent )
                article_precedent = article_courant;
            article_courant = article_courant->nextArticle ;
        } else
            break;
    } while ( article_courant != *liste );
 
    /* si l'article qu'on veut inserer se retrouve premier, il faut trouver le dernier de la liste, pour qu'il précède le premier */
    if (article_courant == *liste && article_courant -> PU < a -> PU )
    {
        article_precedent = *liste ;
        while (article_precedent -> nextArticle != *liste )
            article_precedent = article_precedent -> nextArticle ;
 
        *liste = a; /* on met l'article qu'on va insérer premier de la liste */
    }
 
    /* cette fois, on l'insère */
    a->nextArticle = article_courant;
    article_precedent->nextArticle = a;
}
 
void AfficheListe(Article * premierarticle)
{
    Article * tmp = premierarticle ;
 
    if (tmp != NULL)
    {
        do
        {
            printf("%d\n",tmp->PU);
            tmp=tmp->nextArticle;
        } while ( tmp != premierarticle );
    }
    printf("\n");
}
 
/* EXEMPLE de test */
int main(void)
{
 
    Article * premier_article = NULL; /* Pour savoir qui est en tête de liste */
    Article * article1 = NULL ;
    Article * article2 = NULL ;
    Article * article3 = NULL ;
    Article * article4 = NULL ;
 
    article1 = malloc(sizeof (Article) );
    if (article1 != NULL )
    {
        article1->PU = 10;
        Ajout(&premier_article,article1);
        AfficheListe(premier_article);
    }
 
    article2 = malloc(sizeof (Article) );
    if (article2 != NULL )
    {
        article2->PU = 50;
        Ajout(&premier_article,article2);
        AfficheListe(premier_article);
    }
 
    article3 = malloc(sizeof (Article) );
    if (article3 != NULL )
    {
        article3->PU = 11;
        Ajout(&premier_article,article3);
        AfficheListe(premier_article);
    }
 
    article4 = malloc(sizeof (Article) );
    if (article4 != NULL )
    {
        article4->PU = 7;
        Ajout(&premier_article,article4);
        AfficheListe(premier_article);
    }
 
    free(article1);
    free(article2);
    free(article3);
    free(article4);
 
    return 0;
}

Il y a peut-être moyen d'optimiser.

J'ai volontairement supprimé ListeArticles, car cacher un pointeur dans un typedef est une source de confusions.

S'il y a des choses que tu ne comprends pas, n'hésite pas à demander.

EDIT :
J'ai rajouté mes "free", que j'ai totalement oublié.

[Sve@r]

Bonjour,

Je souhaite insérer un élément dans une liste chaînée circulaire, mais je peine un peu. Les éléments doivent être triés selon un ordre décroissant. Bien que cette fonction soit erronée, voilà où j'en suis actuellement (histoire de vous prouver que j'ai essayer de chercher) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Ajout(ListeArticles liste, Article *a) {
    Article *tmp = liste;
 
    while(tmp->nextArticle != liste) {
        if(a->PU >= tmp->nextArticle->PU) {
            a->nextArticle = tmp->nextArticle->nextArticle;
            tmp->nextArticle = a;
        }
 
        tmp = tmp->nextArticle;
    }
 
    if(tmp->nextArticle == liste) {
        a->nextArticle = liste;
        tmp->nextArticle = a;
    }
}

Je débute avec les listes chaînées, veuillez donc m'excuser si la raison pour laquelle je suis bloquée paraît stupide.

PS : La fonction ne peut renvoyer que void à cause de la consigne qu'on m'a donnée.

Merci d'avance pour votre aide.

Bon, déjà ton premier paramètre "ListeArticles liste" laisse penser qu'il s'agit d'un pointeur masqué. Le type "ListeArticle" étant défini comme pointeur.
Ben désolé mais c'est pas parce qu'on a peur des pointeurs qu'il faut les masquer. La peur n'évite pas le danger. Et au contraire, masquer un pointeur peut te conduire à l'oublier et à te planter.
Chose d'ailleurs que tu fais à la ligne juste en dessous où tu écris Article *tmp=Liste. Ben désolé, Liste est sans doute un pointeur sur un tas de trucs mais Liste n'est certainement pas un pointeur de type "Article *".

Jéroman donne une soluce de base dans laquelle il ne masque pas les pointeurs. Perso, je préconise de mon coté de définir une structure spéciale pour gérer la liste et une structure spéciale pour gérer un élément de la liste. Ca peut paraitre stupide de définir une structure qui ne contiendra en fait que le premier élément mais ça permet ensuite d'y rajouter facilement d'autres trucs (comme par exemple le nombre d'éléments) sans avoir à tout reprendre et surtout, ça évite ainsi les ** qui, autrement, s'imposent quand le premier élément change.

C'est un peu comme une chemise. On peut très bien tenir une chemise par le col. Mais si on la met sur un cintre, ça permet quand-même de mieux la manipuler...

[Cladouros]

Merci pour votre aide, malheureusement ce pointeur masqué m'est imposé, ce n'est donc pas un choix personnel et c'est probablement ce qui me perturbe le plus. Il en va de même concernant la création des structures, je ne peux en rajouter d'autres que celle-ci.

J'ai analysé la solution de jeroman et l'ai assimilée (et je l'en remercie d'ailleurs) mais lorsque j'essaye de la modifier pour utiliser tout de même ListeArticles, les articles ne s'ajoutent pas à la liste. Pourquoi cela ?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <stdlib.h>
 
typedef struct Art {
    float PU;
    struct Art *nextArticle;
} Article;
 
typedef Article *ListeArticles;
 
void AjoutArticle(ListeArticles liste, Article *a) {
    Article *articleCourant = liste;
    Article *articlePrecedent = liste;
 
    // Si la liste est vide
    if (liste == NULL) {
        a->nextArticle = a;
        liste = a;
        return;
    }
 
    // On recherche où insérer l'article
    do {
        if(articleCourant->PU >= a->PU) { // Si le prix de l'article qu'on regarde est plus grand que celui à insérer
            if (articleCourant != articlePrecedent) { // S'il n'y a pas qu'un seul article dans la liste
                articlePrecedent = articleCourant;
            } 
 
            articleCourant = articleCourant->nextArticle; // On passe à l'article suivant
        } else break; // Sinon on sort de la boucle
    } while (articleCourant != liste); // Tant que l'on est pas au bout de la liste
 
    // Si l'article doit être insérer en premier, il faut trouver le dernier élément de la liste pour le faire pointer sur celui-ci
    if (articleCourant == liste && articleCourant->PU < a->PU) {
        articlePrecedent = liste;
        while(articlePrecedent->nextArticle != liste) {
            articlePrecedent = articlePrecedent->nextArticle ;
        }
 
        liste = a; // On insère l'article en premier 
    }
 
    // On insère l'article
    a->nextArticle = articleCourant;
    articlePrecedent->nextArticle = a;
}
 
void AfficheListe(ListeArticles liste) {
    Article *tmp = liste;
 
    if (tmp != NULL) { // Si la liste n'est pas vide
        do {
            printf("%f\n", tmp->PU);
            tmp = tmp->nextArticle;
        } while (tmp != liste); // Tant que l'on est pas au bout de la liste
    } else {
        printf("La liste est vide");
    }
 
    printf("\n");
}
 
int main() {
    ListeArticles liste = NULL;
    Article *article1 = NULL ;
    Article *article2 = NULL ;
    Article *article3 = NULL ;
    Article *article4 = NULL ;
 
    article1 = malloc(sizeof (Article) );
    if (article1 != NULL) {
        article1->PU = 10;
        AjoutArticle(liste, article1);
        AfficheListe(liste);
    }
 
    article2 = malloc(sizeof (Article) );
    if (article2 != NULL) {
        article2->PU = 10;
        AjoutArticle(liste, article2);
        AfficheListe(liste);
    }
 
    article3 = malloc(sizeof (Article) );
    if (article3 != NULL) {
        article3->PU = 10;
        AjoutArticle(liste, article3);
        AfficheListe(liste);
    }
 
    article4 = malloc(sizeof (Article) );
    if (article4 != NULL) {
        article4->PU = 10;
        AjoutArticle(liste, article4);
        AfficheListe(liste);
    }
 
    return 0;
}

[diogene]

La raison est là :

Code :

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

1
2
3
4
5
    if (liste == NULL) {
        a->nextArticle = a;
        liste = a;
        return;
    }

liste = a modifie la variable locale liste, mais pas l'objet liste de main() qui reste inchangé et égal à NULL.

[diogene]

Les remarques concernant tes structures de données faites par jeroman et Sve@r sont judicieuses. D'ailleurs, il est illusoire d'espérer masquer le type de la tête de liste puisque pour pouvoir écrire sans remarques désobligeantes du compilateur

Code :

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

Article *tmp = liste;

ListeArticles doit être un Article *.

Je me range tout à fait à l'avis de Sve@r : la tête de la liste doit avoir son propre type structure. Cela lève beaucoup d'ambiguité dans l'écriture et la lecture du code.
Je te propose, par exemple :

Code :

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

1
2
3
4
typedef struct
{
  Article *debut;
} ListeArticles;

La fonction ajout() commence alors par :

Code :

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

1
2
3
void AjoutArticle(ListeArticles *liste, Article *a) 
{
....

et dans la fonction, il suffit simplement de remplacer liste par liste->debut pour que ça marche.

et de même dans AfficheListe()

L'appel devient :

Code :

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

1
2
3
4
5
int main(void)
{
    ListeArticles liste = {NULL};
.....
    AjoutArticle(&liste, article1);

[Cladouros]

Effectivement, je conçois pourquoi cette solution serait plus adaptée. Cependant, comme je l'ai dit précédemment, je ne suis pas autorisé à modifier les structures et les prototypes de fonctions définies ici, malgré qu'elles puissent constituer de mauvaises pratiques.

Dans de telles circonstances, comme faire pour résoudre mon problème ?

Merci encore pour votre aide

[Sve@r]

Je me range tout à fait à l'avis de Sve@r : la tête de la liste doit avoir son propre type structure. Cela lève beaucoup d'ambiguité dans l'écriture et la lecture du code.

Ca m'énerve. j'avais vu sur ce site un super tuto qui expliquait les listes chainées. "il me semblait" que ce tuto préconisait aussi de définir une structure spéciale apte à manipuler la liste elle-même. Or j'ai fouillé ce site, j'ai trouvé plein de tutos sur les listes mais aucun ne parle de cette fameuse structure particulière.
Soit j'ai rêvé, soit je me vautre dans la recherche. Si qqun se souvient du tuto auquel je fais référence...

Cet ensemble de contraintes est stupide : le prototype de AjoutArticle() fait qu'il est impossible à la fonction de modifier la tête de liste dans le programme qui appelle cette fonction. Or, si on ajoute un élément à une liste vide ou en tête de liste, il faut pouvoir modifier cette tête.

On va alors vers un code illogique : Comme on ne peut passer que l'adresse d'un maillon, celui-ci doit contenir la véritable tête de liste. Donc au départ, il nous faut un élément (qui ne fera pas partie de la collection) sur lequel pointe la (pseudo) tête de liste et qui nous permet de parcourir la liste. Ce premier maillon ne sert en fait qu'à fournir l'adresse du premier maillon utile de la liste par son champ nextArticle. La "pseudo" tete de liste permet d'avoir l'adresse où se trouve le pointeur sur le premier maillon de la liste donc permet de le modifier.

Ouaip. Comme tu peux pas créer de structure apte à manipuler la liste, tu utilises alors un maillon initial jouant le rôle de cette structure...