IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Dur Listes chainées


Sujet :

C

  1. #1
    Membre éclairé
    Homme Profil pro
    Étudiant
    Inscrit en
    Février 2008
    Messages
    391
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Février 2008
    Messages : 391
    Par défaut Dur Listes chainées
    Bonjour voila j'ai du mal a comprendre les listes chainées... Comment peut on la parcourir itérativement ? ou récursivement ? Cela m'énerve un peu, je préfère les tableaux mais je voudrais bien comprendre quand même les listes chainées !!

  2. #2
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    bah une mini-recherche ici t'aurais amene a ce fil :

    http://www.developpez.net/forums/sho...d.php?t=495214

  3. #3
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 851
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Devilju69 Voir le message
    Bonjour voila j'ai du mal a comprendre les listes chainées...
    C'est une liste où chaque élément, quelle que soit sa position en mémoire, connait l'adresse de l'élément qui le suit de façon logique

    Citation Envoyé par Devilju69 Voir le message
    je préfère les tableaux
    En général c'est effectivement plus facile. Mais la liste chainée possède l'avantage inégalable de pouvoir insérer n'importe quel nouvel élément à n'importe quelle place. L'élément qui s'insère récupère l'adresse du suivant et l'élément placé avant récupère l'adresse de l'élément qui s'insère et c'est tout. Avec un tableau faut tout décaler...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  4. #4
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Sve@r Voir le message
    Mais la liste chainée possède l'avantage inégalable de pouvoir insérer n'importe quel nouvel élément à n'importe quelle place.
    ET de prendre beaucoup moins de place memoire lorsuqe l'on doit faire varier le nombre d'elements grandement....

  5. #5
    Membre chevronné Avatar de corentin59
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    462
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2006
    Messages : 462
    Par défaut
    Citation Envoyé par souviron34 Voir le message
    ET de prendre beaucoup moins de place memoire lorsuqe l'on doit faire varier le nombre d'elements grandement....
    Euh, dites-moi si je me trompe mais une liste chainée prend a priori plus de place mémoire qu'un tableau dans la mesure où il faut, pour chaque élément, stocker en plus un pointeur vers l'élément suivant et/ou précédent. Par contre, quand le nombre d'éléments varie beaucoup, c'est plus lourd à gérer pour les tableaux car on peut être amené à faire des realloc

  6. #6
    Expert confirmé

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Par défaut
    Citation Envoyé par corentin59 Voir le message
    Euh, dites-moi si je me trompe mais une liste chainée prend a priori plus de place mémoire qu'un tableau dans la mesure où il faut, pour chaque élément, stocker en plus un pointeur vers l'élément suivant et/ou précédent. Par contre, quand le nombre d'éléments varie beaucoup, c'est plus lourd à gérer pour les tableaux car on peut être amené à faire des realloc
    Et comme on veut limiter ceux-ci, on alloue plus, ce qui a un cout en memoire. En fait, de ce point de vue l'avantage va a l'un ou a l'autre suivant la strategie de reallocation, la taille des valeurs mises dans la liste et la presence ou non d'effacements.

    Un facteur qui peut etre a l'avantage du tableau, c'est que le fait qu'il soit contigu donne generalement une meilleure utilisation des caches a divers niveaux.

  7. #7
    Membre émérite Avatar de valefor
    Profil pro
    Inscrit en
    Décembre 2006
    Messages
    711
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2006
    Messages : 711
    Par défaut
    Et, je dirais que pour certaines applications les allocations dynamiques de mémoire sont pénalisantes en perf. Donc si on a besoin d'implémenter les listes chainées, on est bon pour implémenter un mécanisme d'attribution de mémoire pré-alouée.

  8. #8
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    je mentionnais simplement parce que cela me semble être plus l'avantage déterminant que le fait d'insérer à n'importe quel endroit...


    J'ai eu à manipuler des variations de 0 à 300 000+ éléments en continu 7j/7, et avec des tableaux et des reallocs, ça finissait par crasher...

    Mais en fait c'est Jean-Marc qui a raison... c'est surtout dépendant de quel type de données on dispose et de de leur nombre et de la stratégie que l'on veut utiliser...

  9. #9
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 851
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par souviron34 Voir le message
    J'ai eu à manipuler des variations de 0 à 300 000+ éléments en continu 7j/7, et avec des tableaux et des reallocs, ça finissait par crasher...
    Ouais mais bon, ca venait ptet aussi du programmeur...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  10. #10
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Sve@r Voir le message
    Ouais mais bon, ca venait ptet aussi du programmeur...
    non

    mais a cause du free qui ne libere pas et du realloc, si tu avais par exemple 200 000, puis 50, puis 25 000, puis 350 000, avec des allocs d'autre chose au milieu, la memoire utilisee augmente de maniere constante....

    Alors qu'avec une liste chainee, vu que la taille est petite, si tu as entre temps alloue et/ou desalloue disons une chaine temporaire, un petit tableau, etc, tu trouveras toujours un petit coin pour stocker ta structure.. Donc en gros, ta memoire reste stable une fois que tu as atteint une fois ton max...

    T'en fais pas, j'avais commence par un tableau ... Et c'est apres avoir eu crash, et fouille des semaines, que je me suis rendu compte que le free ne liberais pas vraiment, et que du coup un realloc ne faisait qu'augmenter la memoire... Alors que des que j'ai remplace par une liste chainee, tout s'est bien passe

  11. #11
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 851
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 851
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par souviron34 Voir le message
    mais a cause du free qui ne libere pas et du realloc, si tu avais par exemple 200 000, puis 50, puis 25 000, puis 350 000, avec des allocs d'autre chose au milieu, la memoire utilisee augmente de maniere constante....
    Vu => Fragmentation de l'espace libre de la mémoire...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  12. #12
    Expert confirmé

    Profil pro
    Inscrit en
    Janvier 2007
    Messages
    10 610
    Détails du profil
    Informations personnelles :
    Âge : 67
    Localisation : France

    Informations forums :
    Inscription : Janvier 2007
    Messages : 10 610
    Billets dans le blog
    2
    Par défaut
    voila..

    C'est pour ca que pour moi c'est vrament l'avantage inegalable, comme tu dis...

    Maintenant, l'autre aussi

    Donc je mettrais au pluriel

Discussions similaires

  1. Réponses: 12
    Dernier message: 08/02/2005, 23h42
  2. Bibliothèque de listes chainées
    Par gege2061 dans le forum C
    Réponses: 29
    Dernier message: 17/12/2004, 20h15
  3. copie de liste chainée
    Par tomsoyer dans le forum C++
    Réponses: 15
    Dernier message: 31/08/2004, 18h20
  4. Trie liste chaine
    Par Congru dans le forum C
    Réponses: 2
    Dernier message: 30/03/2004, 19h05
  5. tri de liste chainée
    Par RezzA dans le forum C
    Réponses: 7
    Dernier message: 26/01/2003, 20h25

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