+ Répondre à la discussion Actualité déjà publiée
  1. #1
    Community Manager

    Avatar de Siguillaume
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    août 2007
    Messages
    5 100
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Côte d'Ivoire

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Produits et services télécom et Internet

    Informations forums :
    Inscription : août 2007
    Messages : 5 100
    Points : 25 067
    Points
    25 067

    Par défaut Apprendre à programmer les listes chaînées en C

    Chers membres,

    Je vous présente ce tutoriel de CGi « Apprendre à programmer les listes chaînées en C » :

    Une liste chaînée est un système informatique qui permet la sauvegarde dynamique de données en mémoire tout comme des variables ou tableaux, mais sans se préoccuper de leur nombre et en rendant leur allocation plus transparente.
    Dans ce tutoriel, vous allez apprendre à programmer les listes chaînées en C.
    Bonne lecture
    Vous avez envie de contribuer au sein du Club Developpez.com ? Contactez-nous maintenant !
    Vous êtes passionné, vous souhaitez partager vos connaissances en informatique, vous souhaitez faire partie de la rédaction.
    Il suffit de vous porter volontaire et de nous faire part de vos envies de contributions :
    Rédaction d'articles/cours/tutoriels, Traduction, Contribution dans la FAQ, Rédaction de news, interviews et témoignages, Organisation de défis, de débats et de sondages, Relecture technique, Modération, Correction orthographique, etc.
    Vous avez d'autres propositions de contributions à nous faire ? Vous souhaitez en savoir davantage ? N'hésitez pas à nous approcher.

  2. #2
    Membre habitué
    Étudiant
    Inscrit en
    juin 2010
    Messages
    64
    Détails du profil
    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juin 2010
    Messages : 64
    Points : 182
    Points
    182

    Par défaut

    Bon j'ai lu attentivement le contenu de ce tutoriel et certains points m'ont paru un peu étrange voir incomplet.
    et ça commence dès la définition...
    C'est un système informatique qui permet la sauvegarde dynamique de données en mémoire tout comme des variables ou tableaux, mais sans se préoccuper de leur nombre et en rendant leur allocation plus transparente.
    On peut faire la même chose avec un tableau...
    exemple simplifié:
    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
     
    //je zappe les test d'allocations ,etc...
     
    typedef struct TableauSansLimite TableauSansLimite;
    struct TableauSansLimite
    {
     int* tab;
     int nbCase;
    };
     
    void init_TableauSansLimite(TableauSansLimite* tsl)//initialise proprement
    {
     tsl->tab=NULL;
     tsl->nbCase=0;
    }
     
    void free_TableauSansLimite(TableauSansLimite* tsl)//vide proprement
    {
     free(tsl->tab);
     init_TableauSansLimite(tsl);
    }
     
     
    void needRealloc_TableauSansLimite(TableauSansLimite* tsl,int newSize)//ré-alloue si nécessaire
    {
     if(newSize>=tsl->nbCase)
     {
      tsl->tab=realloc (tsl->tab,newSize*sizeof(int));
      tsl->nbCase=newSize;
     }
    }
     
    int getCase_TableauSansLimite(TableauSansLimite* tsl,int indice)
    {
     needRealloc_TableauSansLimite(tsl,indice+1);
     return tsl->tab[indice];
    }
     
    void setCase_TableauSansLimite(TableauSansLimite* tsl,int indice,int valeur)
    {
     needRealloc_TableauSansLimite(tsl,indice+1);
     tsl->tab[indice]=valeur;
    }
     
    //utilisation
     
    TableauSansLimite tab;
    init_TableauSansLimite(&tab);
    setCase_TableauSansLimite(&tsl,42,123);
    printf("%d\n",getCase_TableauSansLimite(&tsl,42));//affichera 123
    D'après la définition, cette structure est une liste chaînée...


    Le tableau correspond à une architecture mémoire.
    La liste chaînée en est une autre.
    C'est sans tenir compte d'un nombre ou d'allocation mémoire...

    un tableau
    • Les éléments DOIVENT être contiguë en mémoire.
    • Accès à n'importe quel élement avec un temps constant ( O(1) )
    • insersion ou suppression de case aléatoire "longue" (peut demander de décaler les éléments pour garder un tableau) ( O(n) )

    une liste
    • Les éléments peuvent ne pas être contiguë en mémoire
    • Insertion avec un temps constant ( O(1) )
    • Accès séquentiel pour accéder aux éléments ( O(n) )


    On dit liste chaînée, car les données sont chaînées les unes avec les autres. On accède aux données à l'aide d'un ou deux points d'entrée qui se situent la plupart du temps aux extrémités de la liste.

    Dans la pratique ces points d'entrée seront des pointeurs soit sur le premier ou le dernier élément de la liste, voire sur les deux ou même mobile.

    Les éléments de la liste sont chaînés entre eux à l'aide de pointeurs sur leur élément suivant ou précédent, voire sur les deux. Ces pointeurs doivent donc faire partie de l'élément. Ce qui nous orientera vers l'utilisation d'une structure du langage C (struct). Cette structure aura donc la particularité d'avoir au moins un pointeur sur des variables du même type qu'elle. Ce pointeur servira à relier les éléments de la liste entre eux. La structure contiendra bien sûr aussi les données que l'on veut mémoriser.
    Très mal dit ou trop confus...
    Cette parti peut être reformuler plus simplement (je propose "à froid" )

    "
    On dit chaînée car chaque élément possède au moins un lien vers un autre élément.
    • On parle de liste simplement chaînée lorsqu'un élément ne possède qu'un lien vers l'élément suivant.
    • On parle de liste doublement chaînée lorsqu'un élément possède un lien vers l'élément suivant ET précédant.


    Dans la pratique, un élément sera représenté par une structure contenant la donnée ainsi qu'un pointeur vers l'élément suivant
    et dans le cas d'une liste doublement chaînée, un pointeur vers l'élément précédant.

    On mettra à NULL lorsque qu'u élément n'a plus de suivant (ou précédant).
    [code exemple]

    "


    La pile n'est pas le meilleur exemple car elle ne fait pas intervenir LA propriété des listes à savoir l'insertion rapide.
    Et se représente très bien avec un tableau ( exemple : la stack )
    Un exemple visuel serait,par exemple, un maillon par ligne et faire une insertion et suppression de ligne.


    Et pourquoi commencer de 0 à présenter les listes sans faire un comparatif avec les tableau ?

    la "liste triée" aurait été un très bon endroit pour !
    (comparaison avec le tri par insertion par exemple !)

    Ensuite, pour donner le meilleur exemple, les "const" c'est pas pour les chiens
    int Length(const pile *p)
    void View(const pile *p)
    //...
    Là ou l'information serait utile au niveau des insertions/suppressions
    pas un commentaire...

    et au niveau des listes doublement chaînées, au moins un schémas de plus ne serait pas de trop ...


    Ensuite classique... aucune optimisation sur les listes.

    Parlera-t-on des liste chaînées circulaire ?
    Parlera-t-on des liste chaînées avec sentinelle ? (un élément par défaut pour généraliser les insertions/suppressions ! )
    Parlera-t-on de l'optimisation mémoire avec un chaînage XOR ? (bon celui là il est un peu à part)

    Conclusion :

    Bonne initiative à la base, mais incomplet...

    (je ne veux pas être méchant, je dit ce que je pense être manquant ou à modifier )

    voilà,voilà

Discussions similaires

  1. Les listes chaînées
    Par dyala dans le forum Langage
    Réponses: 2
    Dernier message: 22/05/2007, 10h09
  2. petit problème sur les listes chaînées
    Par poche dans le forum C
    Réponses: 14
    Dernier message: 19/03/2007, 16h53
  3. [TP 7] Problème avec les listes chaînées (error 202)
    Par thelinekioubeur dans le forum Turbo Pascal
    Réponses: 4
    Dernier message: 06/12/2006, 23h15
  4. Réponses: 7
    Dernier message: 22/10/2005, 19h20

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo