Probleme liste circulaire

Version imprimable

Bonjour,

Je ne comprends pas la solution de cet exercice
comment ajoute t-on un élément en queue dans un liste circulaire doublement chainée ?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ajouterApres (Liste_Circulaire_Doublement_Chainee* element, int val)
{
    Liste_Circulaire_Doublement_Chainee* nouvel_element = malloc ( sizeof *nouvel_element );
    if ( nouvel_element != NULL )
    {
        nouvel_element->val = val;
        /* on définit les pointeurs du nouvel élément */
        nouvel_element->prec = element;
        nouvel_element->suiv = element->suiv;
        /* on modifie les éléments de la liste */
        element->suiv->prec = nouvel_element;
        element->suiv = nouvel_element;
    }
}

01/11/2013, 16h24
Invité

1 pièce(s) jointe(s)

Bonjour,

Le mieux est de s'aider d'un schéma qui retrace ces lignes :
01/11/2013, 17h37
Mat.M

bonjour sans comprendre et bien assimiler la notions et l'usage des pointeurs en C ce n'est pas possible de comprendre ce qu'est une liste chainée

Un pointeur c'est une adresse mémoire désignée par une variable et notée avec une étoile afin que le compilateur comprenne qu'on accède directement en RAM c.a.d. la mémoire
Ensuite dans ta fonction ajouter_element tu passes un pointeur de structure de type élément, tu alloues de manière locale un autre pointeur et tu ne fais que "connecter" les membres de structure de l'un et de l'autre
01/11/2013, 18h26
nadine01

Citation:

Envoyé par Winjerome

Bonjour,

Le mieux est de s'aider d'un schéma qui retrace ces lignes :

merci beaucoup j'ai bien compris, mais comment utilisant les listes circulaire doublement chainées avec la structure file .

Enfiler()
01/11/2013, 18h59
Invité

Je n'ai pas compris ta question...
01/11/2013, 19h08
nadine01

Citation:

Envoyé par Winjerome

Je n'ai pas compris ta question...

c-a-d implémenter la structure file en utilisant les listes circulaires doublement chainées. Réaliser la primitive : Enfiler()

Bonsoir

Si tu as une liste circulaire doublement chainée dont la déclaration (par exemple) est la suivante :

Code:

1
2
3
4
5
6
7
8
struct list {
    int data;
    struct list *next;
    struct list *prev;
};
 
typedef struct list* myList;
myList newNode, first = NULL, last = NULL;

Je pense que la fonction enfiler doit être comme ceci :

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
void enqueue() {
    int value;
    printf("Tapez une valuer : ");
    scanf("%d", &value);
 
    newNode = (myList) malloc(sizeof (list));
    newNode->data = value;
    newNode->next = NULL;
    newNode->prev = NULL;
 
    if (first == last && first == NULL) {
        printf("La liste etait vide, création du premier noeud en cours ..");
        first = last = newNode;
        first->next = last->next = NULL;
        first->prev = last->prev = NULL;
    } else {
        last->next = newNode;
        newNode->prev = last;
        last = newNode;
        first->prev = last;
        last->next = first;
    }
 
}

Code:

1 2 3 4 5 6 if (first == last && first == NULL) { printf("La liste etait vide, création du premier noeud en cours .."); first = last = newNode; first->next = last->next = NULL; first->prev = last->prev = NULL;
j'ai pas compris bien, car les listes circulaires (le queue lie avec la tête )
donc, le premier élément les 2 pointeurs(prev et next) pointent sur l’élément elle même

01/11/2013, 23h46
Snack3r

1 pièce(s) jointe(s)
Citation:

j'ai pas compris bien, car les listes circulaires (le queue lie avec la tête )
donc, le premier élément les 2 pointeurs(prev et next) pointent sur l’élément elle même

Désolé, J'ai écrit le code rapidement et je n'ai pas bien vérifié ce que j'ai tapé.
apparemment, ce que j'avais fait dans le if, c'est plutôt l'initialisation de la liste et non l'insertion d'un nouveau élément.

Voici le code de l'insertion du premier nœud :
Code:

1 2 3 4 5 last->next = newNode; newNode->prev = last; last = newNode; first->prev = last; last->next = first;
regarde le schéma suivant pour bien comprendre la démarche suivie :

merci,
mais le premier premier nœud c'est la racine on peut utilise cette code:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
Liste_Circulaire_Doublement_Chainee* creeListe (void)
{
    Liste_Circulaire_Doublement_Chainee* racine = malloc ( sizeof *racine );
    if ( racine != NULL )  /* si la racine a été correctement allouée */
    {
        /* pour l'instant, la liste est vide,
           donc 'prec' et 'suiv' pointent vers la racine elle-même */
        racine->prec = racine;
        racine->suiv = racine;
    }
    return racine;
}

moi j'ai pas compris comment ajouter des élément après cette élément (racine).

03/11/2013, 14h12
Jean-Marc.Bourguet

Citation:

Envoyé par nadine01

moi j'ai pas compris comment ajouter des élément après cette élément (racine).

Ajpouter un élément après la racine n'est en rien différent d'ajouter un élément après un autre nœud.
03/11/2013, 14h20
nadine01

oui c'est vrai mais comment lie le dernier élément avec la racine