Bonsoir a toute la communaute de classroom j'ai besoin de votre pour mon devoir d'implementation d'une liste doublement chainee en langage C.

Hello,

On ne va pas en permanence tout répéter: voir  ici

-
Edité par edgarjacobs 21 mai 2022 à 0:42:47

@edgarjacobs: garde précieusement ce lien.
@Ashuka:
Ça demande une certaine concentration pour implémenter les listes chaînées, surtout les listes doublement chaînées.
Je te suggère de prendre du papier et un crayon et de dessiner des schéma représentant les maillons et des flèches montrant vers quoi "pointent" les pointeurs.
Portes une attention toute particulière à l'ordre dans lequel tu modifies les pointeurs.

J'ai trouvé ceci qui n'est pas mal:

https://chgi.developpez.com/dblist/

Ça ne montre pas comment insérer ou supprimer en milieu de liste, mais c'est un début.

Il y a également ceci:

http://sdz.tdct.org/sdz/les-listes-doublement-chainees-en-langage-c.html

Du coup, j'ai eu le goût de chercher le code pour inverser l'ordre d'une liste doublement chaînée.
Les exemples du web ne m'ont pas satisfait. J'ai donc écrit mon propre code.
J'ai illustré les structures de maillon et de descripteur de liste.
Ça marche même avec une liste vide pourvu que le descripteur de liste existe.
-
typedef struct Node Node;
struct Node {
    Node *prev;
    Node *next;
    int value;
};
typedef struct List List;
struct List {
    Node *first;
    Node *last;
    int length;
};
void reverse(List *list) {
    Node *node = list->first;
    list->first = list->last;
    list->last = node;
    while(node) {

        Node *temp = node->next;
        node->next = node->prev;
        node->prev = temp;
        node = temp;
    }
}

-
Edité par PierrotLeFou 21 mai 2022 à 2:45:54

Dans les cours, on montre comment insérer en début de liste et en fin de liste. On montre aussi comment insérer à une position donnée.
Puisqu'on est avec une liste doublement chaînée, on peut chercher la position à partir du début ou à partir de la fin.
Par exemple, si on a 351 noeuds dans la liste et qu'on veut insérer avant la position 349, on peut reculer de 2 au lieu d'avancer de  349.
(reculer avant 350, avant 349)
On numérote généralement les noeuds comme les indices d'un tableau, soit de 0 à N-1.
Insérer au début est équivalent à insérer avant la position 0. Insérer à la fin est équivalent à insérer avant la position N.
De même, on peut numéroter les noeuds à l'envers. Mais ppuisqu'on ne peut pas écrire -0, on doit commencer à -1
Insérer à la position -1 veut dire insérer à la fin, -2 juste avant le dernier, -N-1 juste avan le premier.
On peut écrire une seule fonction qui tient compte de tous ces cas.

Je me refère au message précédent.
J'ai utilisé quelques astuces pour coder en une seule fonction tous les cas de figure pour l'insertion.
J'en ai fait de même pour la suppression.
L'astuce principale est la sttructure de liste et de noeud qui utilisent des union et des sous-structures.
On peut se déplacer facilement aussi bien du début vers la fin que l'inverse avec le même code.
La position positive ou négative est ajustée pour un déplacement correct.
Elle est choisie ainsi que la direction pour le parcours le plus court.
Ce code ne vise pas à optimiser la vitesse mais la simplicité du code.
La boucle principale fait de 6 à 7 lignes.
-
#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node Node;
struct Node {
    union {
        struct {
            Node *next;
            Node *prev;
        };
        Node *link[2];
    };
    int value;
};
typedef struct List List;
struct List {
    union {
        struct {
            Node *head;
            Node *tail;
        };
        Node *link[2];
    };
    int length;
};
 
void *getArea(const char *name, const size_t size) {
    void *area = malloc(size);
    if(area) return area;
    perror(name);
    printf("Required: %d\n", size);
    exit(EXIT_FAILURE);
}
List *getList() {
    List *list = getArea("getList", sizeof(List));
    list->head = NULL;
    list->tail = NULL;
    list->length = 0;
    return list;
}
Node *getNode(const int value) {
    Node *node = getArea("getNode", sizeof(Node));
    node->prev = NULL;
    node->next = NULL;
    node->value = value;
    return node;
}
int getSize(const List *list) {
    return list->length;
}
 
void display(const List *list) {
    printf("[");
    Node *node = list->head;
    char *s = "";
    while(node) {
        printf("%s%d", s, node->value);
        s = ", ";
        node = node->next;
    }
    printf("]\n");
}

enum {DELETE=0, INSERT=1};
int limits(int *position, const int limit, const int mode) {
    int lower = -limit-mode;
    int upper = limit+mode-1;
    if(*position < lower || *position > upper) {
        printf("%s: error, index out of range, got %d, expected [%d - %d]\n", (mode==1) ? "insert" : "delete", *position, lower, upper);
        exit(EXIT_FAILURE);
    }
    if(*position < 0) *position += limit + 1;
    if(*position <= limit - *position) return FORWARD;
    *position = limit - *position;
    return BACKWARD;
}
 
void insert(List *list, const int value, int position) {
    int direction = limits(&position, list->length, INSERT);
    Node *follower[2] = {NULL, NULL};
    Node *current = list->link[direction];
    while(current && position--) {
        follower[direction] = current;
        current = current->link[direction];
    }
    follower[TOGGLE - direction] = current;
    Node *newnode = getNode(value);
    newnode->prev = follower[0];
    newnode->next = follower[1];
    if(newnode->prev) newnode->prev->next = newnode; else list->head = newnode;
    if(newnode->next) newnode->next->prev = newnode; else list->tail = newnode;
    list->length++;
}
 
void delete(List *list, int position) {
    int direction = limits(&position, list->length, DELETE);
    Node *follower[2] = {NULL, NULL};
    Node *current = list->link[direction];
    while(current && position--) {
        follower[direction] = current;
        current = current->link[direction];
    }
    if(current) follower[TOGGLE - direction] = current->link[direction];
    free(current);
    if(follower[0]) follower[0]->next = follower[1]; else list->head = follower[1];
    if(follower[1]) follower[1]->prev = follower[0]; else list->tail = follower[0];
    list->length--;
}
 
void reverse(List *list) {
    Node *node = list->head;
    list->head = list->tail;
    list->tail = node;
    while(node) {
        Node *temp = node->next;
        node->next = node->prev;
        node->prev = temp;
        node = temp;
    }
}
 
int main(void) {
    List *list = getList();
    insert(list, 0, 0);
    insert(list, 10, -1);
    insert(list, 1, 1);
    insert(list, 9, 2);
    insert(list, 8, -3);
    insert(list, 11, getSize(list));
    display(list);
    reverse(list);
    insert(list, -1, -getSize(list)-1);
    display(list);
    //insert(list, 12, getSize(list)+1);
    delete(list, 0);
    delete(list, -2);
    display(list);
    delete(list, getSize(list));
    return EXIT_SUCCESS;
}

-
Edité par PierrotLeFou 23 mai 2022 à 4:49:40

Les Secrets Que Les Programmeurs Ne Veulent Pas Que Vous Connaissiez (a):

• penser systématiquement aux cas-limites : liste vide, un seul élément, début de la liste, fin de la liste, ailleurs. (b)
• gribouiller des petits dessins (c) pour trouver l'ordre dans lequel il faut modifier es chaînages (d)

(a) en fait si, ça éviterait de répondre toujours aux même questions

(b) ça ne veut pas dire qu'il y aura 4 cas dans le code : souvent, le même code fait le boulot pour plusieurs cas. Mais il faut s'en assurer.

(c) à l'aide d'un simple crayon et d'un bout de papier, qu'on jette à la poubelle immédiatement après. C'est un outil de travail, pas une oeuvre d'art. Vous devriez toujours avoir un bloc de papier brouillon à côté du clavier (ça sert aussi de tapis souris).

(d) 1. faire deux dessins : la situation de départ, la situation voulue. 2. Ensuite regarder la première opération à effectuer, la dessiner, etc.

-
Edité par michelbillaud 27 mai 2022 à 11:04:02

et je permets de rajouter

• liste chaînée n'implique pas automatiquement l'utilisation de pointeurs à la C en C

Salut,

Mes travaux sur le sujet.

Perso, je ne me suis jamais servi des listes chaînées depuis que je me suis amusé à développer ça, donc une dizaine d'années..

Toujours réussi à m'en passer avec des systèmes plus simples et plus rapides.

Bonne continuation.

On est dans la 3ieme décennie du IIIe millénaire, et ça serait idiot de réimplémenter pour la trouze millième fois une structure de données hyper-classique parce qu'on voudrait s'obstiner mordicus à utiliser un langage des années 60-70 privé de la généricité qui permet d'avoir ça en bibliothèque, écrit une fois pour toutes.

Mais ça c'est pour la production de logiciels.  Pour apprendre à programmer, il faut pratiquer en passant par des exercices classiques, qui permettent de se faire la main sur de la petite algorithmique (qui ne pète pas trois pattes à un canard), et aussi de comprendre le fonctionnement interne des "conteneurs" des langages modernes. Toujours utile pour prendre conscience qu'on choisit un conteneur en fonction des opérations qu'on veut lui appliquer, et de leur coût (complexité).

Deux points de vue complémentaires...

-
Edité par michelbillaud 27 mai 2022 à 13:00:57

Puisque les pointeurs existent en C, les listes chaînées sont un très bon exercice pour les maîtriser.
J'ai écrit du code de fainéant qui ne voulait pas coder une multitude de fonctions.

Personnellement, j'ai appris à manipuler des listes chaînées en Fortran IV, langage qui n'a ni pointeurs,  ni structures.

Un tableau de valeurs, + Un tableau pour l'indice du suivant + indice du premier.

C'est le même concept, avec une implementation plus rustique. 

-
Edité par michelbillaud 27 mai 2022 à 14:54:41

En Fortran, on pouvait faire plus que des listes chaînées comme un réseau avec l'énoncé  equivalence

On pouvait donner des flottants (real) comme valeurs. Utile pour calculer le flot maximum dans un réseau.
Au lieu d'avoir des adresses, on avait des indices.
C'était commode car les indices devaient commencer à 1 et non 0
reseau(1)=4          indice du noeud suivant
reseau(2)=0          pas de précédent
reseau(3)=65          valeur
reseau(4)=22          noeud suivant
reseau(5)=1             noeud précédent
reseau(6)=103             valeur
...

-
Edité par PierrotLeFou 27 mai 2022 à 18:12:39