creation d'une liste doublement chaînée circulaire avec n cellules

1 pièce(s) jointe(s)

voilà le fichier attaché .c je veut creer une fonction creerliste qui crée une liste doublement chaînée circulaire mais j'arrive pas a la construire(la fonction) il m'affiche une erreure "error: two or more data types in declaration of `creerliste' "
alors si quelqu'un peut m'aider merci.

Salut,

Théoriquement, liste circulaire et doublement chainée sont pour ainsi dire "antinomyques"...

Le but recherché par une liste doublement chainée est... de pouvoir détermier, en fonction de la place d'un élément dans la liste, s'il s'agit d'aller "vers l'avant" ou "vers l'arriere".

Cela implique que, d'une manière ou d'une autre, tu dois pouvoir effectuer une comparaison du genre de element n-1<element n<element n+1...

Le problème d'une liste circulaire, c'est que, du fait de la "circularité de la liste (l'élément "de fin de liste" pointe sur l'élément "de début"), tu ne peux pas estimer te trouver sur le Nieme élément (par exemple sur le 5eme) de la liste.

En effet, quel que soit ta position dans la liste et le nombre de fois que tu souhaites accéder "à l'élément qui suit" tu es sur de ne pas atteindre "la fin de la liste", quitte à passer dix, vingt ou cent fois au meme endroit :P

Tu ne peux donc meme pas envisager de te dire "d'ici, il faut retourner x fois en arriere pour rejoindre le début de la liste", simplement parce ... qu'il n'y a pas de début de liste à proprement parler...

C'est la raison pour laquelle il ne sert à rien d'utiliser une liste doublement chainée, ni meme d'effectuer un tri sur une liste circulaire.

Pour ceux que ca intéresse, je place ici le code du fichier joint, ce sera plus facile.

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
/* Creation de liste chainée circulaire avec n cellules */
#include<stdio.h>
#include<stdlib.h>
typedef struct cell cell;
struct cell {
  int n;
  struct cell * s;
  struct cell * p;
}
 
void creerliste(cell * debut) 
{
  int n = 4, i;
  cell * oldcell;
  cell * newcell;
  debut = malloc(sizeof (cell));
  debut->n = 1;
  debut->s = debut;
  debut->p = debut;
  oldcell  = debut;
  for(i = 2; i <= n; i++) {
    newcell = malloc(sizeof *newcell);
    printf("%d ", newcell->n = i);
    newcell->s = debut;
    newcell->p = oldcell;
    oldcell->s = newcell;
    debut->p   = newcell;
    oldcell = newcell;
  }  
putchar('\n');
}
 
 
cell * d;
int main() {
  creerliste(d);
  return 0;
}

Il attire déjà quelques remarques d'ordre générale:

Les variables globales, c'est mal, et, surtout, il ne faut pas passer une variable globale en tant que parametre d'une fonction :P... choisi plutot de créer des fonctions qui demandent des parametre et/ou qui renvoient quelque chose
Le nom des différents champs des strucutres devraient, idéalement, etre plus explicites: next, previous et number ou suivant, precedent et nombre seraient des noms bien plus précis que s, p et n ;)
une liste circulaire ne devrait pas etre doublement chainée ou une liste doublement chainée ne devrait pas etre circulaire, selon l'usage que tu en prévois
le résultat de chaque appel à une fonction de la famille des *alloc doit etre dument vérifié
fait attention à la ligne newcell->p = oldcell; au fait que oldcell n'est pas défini lors du premier passage dans la boucle ;)

Prenant ces remarque en compte, tu pourrais avoir, selon ce qu'il te faut, une structure pour une liste circulaire ressemblant à

Code:

1
2
3
4
5
6
 
typedef snoeudcirc
{
    int number;
    snoeudcirc *next;
}noeudcirc;

ou, pour une liste doublement chainée une structure ressemblant à

Code:

1
2
3
4
5
6
7
 
typedef snoeuddouble
{
    int number;
    snoeudcirc *next;
    snoeuddouble * previous;
}noeuddouble;

la fonction de création d'une liste circulaire pourrait prendre la forme suivante

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
 
/* fonction qui crée une liste circulaire de N éléments
   @in:  nombre d'éléments nécessaires (allant de 1 à N inclu ;))
   @out: pointeur sur l'un des éléments de la liste
noeudcirc* CreeListe(int x)
{
    /* il va nous falloir quelques pointeurs pour travailler
       le pointeur "de début" (qui sera perdu dans la masse en fin 
       de fonction) */
    noeudcirc* debut=NULL; /* ne jamais oublier d'initialiser à null tant que
                              l'on a pas une valeur valide ;-)
    /* le dernier pointeur alloue */
    noeudcirc* dernier=NULL; /* idem */
    /* un noeud "de travail" pour l'allocation dynamique */
    noeudcirc* travail=NULL;
    int i;
    /* on crée une boucle pour le nombre d'éléments
    for(i=1;i<=x;i++)
    {
        /* tentative d'allocation d'un nouvel élément */
        travail=malloc(sizeof(noeudcirc));
        /* vérification de la réussite de l'allocation */
        if(travail!=NULL)
        {
            /* ca a marche, on continue */
            travail->number=i;
            /* on n'a pas encore l'élément suivant, on definit donc
               travail->next à NULL */
            travail->next=NULL;
            /* c'est peut etre le premier élément */
            if(debut==NULL)
                debut=travail;
            /* on ne peut définir dernier->next que si dernier est valide */
            if(dernier!=NULL)
                dernier->next=travail;
            /* l'élément qu'on vient de rajouter devient le dernier */
            dernier=travail;
        }
        else
        {
            /* ca a foiré, on libère les éléments créés */
            while(debut!=NULL)
            {
                /* récupération de l'élément qui suit dans la liste */
                dernier=debut->next;
                /* déconnexion du premier élément du reste de la liste */
                debut->next=NULL;
                /* libération de la mémoire */
                free(debut);
                /* l'élément suivant devient le premier de la liste */
                debut=dernier;
            }
            /* affichage d'erreur */
            printf("erreur d'allocation de la memoire, desole, on quitte\n");
            /* force à quitter la boucle */
            x=n+1;
        }
    }
    /* il est temps de rendre la liste circulaire (si la liste existe)*/
    if(debut!=NULL)
        dernier->next=debut;
    /* et de la renvoyer */
    return debut;
}

qui sera utilisée sous la forme de

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
int main()
{
    noeudcirc* liste=CreeListe(10);/* pourrait etre une variable ;) */
    /* comme la fonction utilise l'allocation dynamique, il faut vérifier
       ce qu'elle renvoie */
    if(liste!=NULL)
    {
        /* ici, c'est ok */
        /*suite du traitement */
        /* ... */
        /* n'oublions pas qu'il faudra libérer la mémoire de la liste ;) */
    }
    else
    {
        /* la fonction avait échoué */
        return EXIT_FAILURE;
    }
    return 0;
}

Le code de création d'une liste doublement chainée ressemblerait plutot (quelques commentaires identiques supprimés)

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
 
/* fonction rajoutant un éléments dans une liste doublement chainée
   @in élément apres lequel rajouter les éléments
     valeur à ajouter
    @out pointeur vers la valeur rajoutée
noeuddouble* AjouteVal(noeuddouble* in, int val)
{
    /* il ne nous faut qu'un pointeur de travail en plus */
    noeuddouble* travail;
    travail=malloc(sizeof(noeuddouble));
    if(travail!=NULL)
    {
        travail->number=val;
        /* la liste est peut etre vide */
        if(in==NULL)
        {
            travail->precedent=NULL;
            travail->suivant=NULL;
        }
        else
        {
            /* permet d'insérer un élément entre deux existants
            travail->suivant=in->suivant;
            travail->precedent=in;
            in->suivant=travail;
        }
    }
    else
    {
        /* L'allocation a échoué, mais la liste, si elle existait, 
           existe toujours*/
        printf("erreur d'allocation, désolé");
    }
    /* yapuka renvoyé l'élément créé */
    return travail;
}

qui pourrait etre utilisée sous la forme de

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
 
int main()
{
    /* le "point de depart" de la liste */
    noeuddouble* depart=NULL;
    /* un pointeur de travail, toujours intéressant */
    noeuddouble*travail=NULL;
    /* une boucle pour remplir la liste de 10 éléments, numérotés de 1 à 10 */
    int i;
    for(i=1;i<=10;i++)
    {
        travail=AjouteVal(i);
        /* vérification du bon déroulement de ajouteval */
        if(travail!=NULL)
        {
            /* c'était peut etre le premier élément */
            debut=travail;
        }
        else
        {
            /* ca a foiré, il faudra voir si on peut continuer ou non... 
               quoi qu'il en soit, ca ne sert à rien d'essayer d'allouer de
               nouveaux éléments ;) */
            i=11;
        }
    }
    /* utilisation de ta liste doublement chainée */
    /* n'oublie pas d'en libérer la mémorie quand tu n'en a plus besoin ;)
}

Edit:

Une autre possibilité pour la liste circulaire serait une fonction prenant la forme de

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
/* fonction qui insère un élément dans une liste existante
   @in pointeur apres lequel ajouter un élément
       valeur à rajouter
   @out pointeur vers l'élément rajouté
noeudcirc* Ajoute(noeudcirc* in, int val)
{
    /* il nous faut un pointeur de travail;
    noeudcirc* travail;
    travail=malloc(sizeof(noeudcirc));
    if(travail!=NULL)
    {
        travail->number=val;
        /* la liste in est peut etre vide */
        if(in!=NULL)
        {
            travail->next=in;
            in->next=travail;
        }
    }
    else
    {
        /* l'allocation dynamique a éhcoué, mais la liste, si elle existait avant
           existe encore*/
        printf("erreur d'allocation");
    }
    /* yapuka renvoyer un pointeur sur l'élément fraichement rajouté */
    return travail;
}

et l'appel de cette fonction serait, sommes toutes (en adaptant les types) fort semblable à celui de AjouteVal...

Seul le fait de rendre la liste circulaire devrait etre ajouté, lorsqu'on teste si on a déjà une liste, sous la forme de

Code:

1
2
3
4
5
6
7
8
9
10
11
 
/* ...*/
/* obtenir le résultat */
travail=Ajoute(debut,5);
/* l'élément rajouté devient le debut de la liste */
debut=travail;
/* si la liste n'est pas circulaire, elle le devient */
if(debut->next=NULL)
{
    debut->next=travail;
}

Citation:

Envoyé par koala01

Théoriquement, liste circulaire et doublement chainée sont pour ainsi dire "antinomyques"...

Parce que tu te place dans le cas où tu classe les données, mais par exemple dans le cas du stockage d'info relatif à des onglets (pour un navigateur par exemple). Le fait d'utiliser une liste circulaire permet que lorsque tu te trouve sur le dernier et que tu veux accéder au suivant, tu te retrouve sur le premier au lieu de ne rien faire (ou pire remonter toute la liste parce que ton nouveau chef aimerai bien avoir cette fonctionnalité :aie:)

merci pour gege2061 et surtout koala01 je vous tiens au courant .
encore merci.

Citation:

Envoyé par gege2061

Parce que tu te place dans le cas où tu classe les données, mais par exemple dans le cas du stockage d'info relatif à des onglets (pour un navigateur par exemple). Le fait d'utiliser une liste circulaire permet que lorsque tu te trouve sur le dernier et que tu veux accéder au suivant, tu te retrouve sur le premier au lieu de ne rien faire (ou pire remonter toute la liste parce que ton nouveau chef aimerai bien avoir cette fonctionnalité :aie:)

Ce que je voulais dire, surtout, c'est qu'il n'est théoriquement pas logique, sauf cas extrèmement particulier, de vouloir utiliser une liste circulaire en avant et en arrière...

Dans le cas des onglets de navigateur, le fait que le dernier permette de rejoindre le premier, une liste circulaire "normale" suffit amplement...

Ce serait plutot si le premier devait permettre de rejoindre le dernier, occasionnant un parcourt "à reculon" qu'éventuellement, on *pourrait* l'envisager...

Et, comme je l'ai indiqué, c'était la remarque purement théorique, et l'expérience m'a démontré à bien des reprises qu'entre la théorie et la pratique, il y a souvent un monde de différence :P

Citation:

Envoyé par koala01

Ce que je voulais dire, surtout, c'est qu'il n'est théoriquement pas logique, sauf cas extrèmement particulier, de vouloir utiliser une liste circulaire en avant et en arrière...

Dans le cas des onglets de navigateur, le fait que le dernier permette de rejoindre le premier, une liste circulaire "normale" suffit amplement...

Ce serait plutot si le premier devait permettre de rejoindre le dernier, occasionnant un parcourt "à reculon" qu'éventuellement, on *pourrait* l'envisager...

Ce ne sont pas des cas si particulier que ca. Il est frequent de vouloir parcourir une liste dans les deux sens en bouclant sur le premier et le dernier element (quelques exemples en plus de celui des onglets : mens d'applications, certains historiques de commandes, les listes deroulantes, etc.).
Une liste circulaires doublement chainee est tout aussi frequente que les listes circulaires simplement chainees et que les liste doublement chinees non circulaires (meme si dans certains domaines l'une est plus frequente).
Le choix de l'une ou l'autre etant affaire de besoin.

Citation:

Envoyé par koala01

Théoriquement, liste circulaire et doublement chainée sont pour ainsi dire "antinomyques"...

Non. Mais c'est une question d'algorithme et de structure de données, pas de C.

Citation:

Envoyé par koala01

Et, comme je l'ai indiqué, c'était la remarque purement théorique, et l'expérience m'a démontré à bien des reprises qu'entre la théorie et la pratique, il y a souvent un monde de différence :P

La pratique montre que les listes circulaires doubles sont utiles et utilisées.

Ok, ok, n'en jetez plus...

De fait, j'ai confondu avec un idée tout autre :oops:

Donc, faisons comme si je n'avais rien dit ;):D

1 pièce(s) jointe(s)

voilà après quelques modifications mon programme marche comme je l'ai voulu (j'ai un doute pour la fonction liberer je ne sais pas si elle libere tout)