Insertion dans liste chaînée circulaire

Version imprimable

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:

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.

Salut,

Voici un exemple de ce que j'aurais fait :

Code:

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é. :oops:

Citation:
Envoyé par 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:

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...

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:

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;
}

17/10/2010, 15h45
diogene
La raison est là :
Code:

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.
17/10/2010, 16h09
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:

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:

1 2 3 4 typedef struct { Article *debut; } ListeArticles;
La fonction ajout() commence alors par :
Code:

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:

1 2 3 4 5 int main(void) { ListeArticles liste = {NULL}; ..... AjoutArticle(&liste, article1);
17/10/2010, 16h18
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 :ccool:
17/10/2010, 16h27
diogene

Quelles sont exactement tes contraintes
- sur le typedef définissant ListeArticles
- sur le prototype des fonctions
17/10/2010, 16h33
Cladouros
La structure Article doit obligatoirement être définie de la sorte :
Code:

1 2 3 4 typedef struct Art { float PU; struct Art *nextArticle; } Article;
Même chose pour ListeArticles :

Code:

typedef Article *ListeArticles;

Et le prototype d'AjoutArticle doit être le suivant :

Code:

void AjoutArticle(ListeArticles liste, Article *a)

Ce sont les trois contraintes à respecter.
17/10/2010, 17h29
diogene
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. En fait, cela revient à "simuler" le prototype void Ajout(Article ** liste, Article *a) de jeroman qui est interdit en masquant le double pointeur.

Conséquence sur le code :

- Dans le corps des deux fonctions AjoutArticle() et AfficheListe() , cela impose alors de changer liste en liste->nextArticle
- main() doit être modifié pour initialiser la liste avec ce maillon d'adressage:
Code:

1 2 3 4 5 Article dummy = {0,NULL}; ListeArticles liste = &dummy; .... AjoutArticle(liste, article1); AfficheListe(liste);
Tu constateras comment la clarté du code est détériorée par cet artifice.
17/10/2010, 18h06
Cladouros

Merci beaucoup diogene. En effet, les modifications que tu as proposées ont fait fonctionner le code. Je vais continuer le reste en utilisant cette méthodologie, mais nulle doute que j'en ferai part et que j'implémenterai l'autre façon de faire de mon côté, juste histoire de conserver un esprit sain.

:ccool:
17/10/2010, 18h32
Invité

Bonjour Diogène.
Je parie que dans l'énoncé, il y a une phrase du genre"On dispose d'une liste chainée de prix unitaires.", et que la suite est du genre : "ils sont organisée en ordre croissant dans une liste chainée...".
Si c'est le cas, l'initialisation avec un prix à 0, parait assez logique.
Cordialement:cry:
17/10/2010, 18h38
Cladouros

Presque. En réalité un article contient plus de champs, mais je les aient omis car ils n'avaient pas d'intérêt ici. Et les articles doivent classés par ordre décroissants suivant le prix unitaire dans une liste chaînée circulaire :)
17/10/2010, 19h22
Sve@r

Citation:

Envoyé par diogene

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...

Citation:

Envoyé par diogene

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...