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

Caml Discussion :

liste doublement chainée


Sujet :

Caml

  1. #1
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut liste doublement chainée




    pour une fois, c'est moi qui poserais les questions...


    je cherche à construire une liste doublement chainée modifiable, afin de pouvoir partager l'espace mémoire des différences listes intermédiaires, et bénéficier de la concaténation en temps constant

    en revanche, j'ai un petit soucis en ce qui concerne le parcours d'une telle liste... comment faire pour avoir déterminer qu'on est revenu au début ?
    j'ai tenté un test d'égalité sur la première cellule, mais étant donné la structure cyclique, le test caml plante avec un joli Out_of_memory (on boucle infiniment dans le test )

    pour infos, dans un langage comme C, j'aurais utilisé l'adresse de la première cellule pour comparer, mais ici, je ne vois pas comment m'y prendre


    Code ocaml : 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
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    (* vim:set ts=4 sw=4: *)
     
    type 
        'a cellule = {head : 'a; mutable next : 'a liste; mutable prev : 'a liste}
    and
        'a liste = Nil | Liste of 'a cellule
    ;;
     
     
    let cons a l = 
        let res = {head=a ; next=l; prev=Nil} in
        let p =
            match l with
                 Nil -> Liste(res)
                |Liste(c) -> c.prev
        in
        let _ = res.prev <- p in
        let _ = match l with
             Nil -> ()
            |Liste(c) -> c.prev <- Liste(res)
        in
        let _ = if res.next = Nil then res.next <- Liste(res) in
        Liste(res)
    ;;
     
    let concat l1 l2 =
        match (l1,l2) with
             (Nil,_) -> l2
            |(_,Nil) -> l1
            |(Liste(c1),Liste(c2)) ->
                let Liste(c1_p) = c1.prev in
                let Liste(c2_p) = c2.prev in
                c1_p.next <- l2 ;
                c2.prev <- Liste(c1_p) ;
                c2_p.next <- l1 ;
                c1.prev <- Liste(c2_p) ;
                l1
    ;;
     
    let rec print print_elt l =
        let first =
            match l with
                 Nil -> {head=0;next=Nil;prev=Nil}
                |Liste(c) -> c
        in
        let rec aux l =
            match l with
                 Nil -> print_string "nil"
                |Liste(c) -> print_elt (c.head); print_string " "; aux (c.next)
        in
        aux l ;
        print_newline ()
    ;;
     
    let main () =
        let l = Nil in
        print print_int l ;
        let l1 = (cons 2 l) in
        let l2 = (cons 3 l) in
        print print_int (concat l1 l2)
    ;;
     
    main ();;


    par avance
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  2. #2
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    j'ai une solution "moche" avec un identifiant auto-incrémenté... mais ça ne me plait pas

    Code ocaml : 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
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    (* vim:set ts=4 sw=4: *)
     
    type 
        'a cellule = {id: int; head : 'a; mutable next : 'a liste; mutable prev : 'a liste}
    and
        'a liste = Nil | Liste of 'a cellule
    ;;
     
    let compteur = ref 1;;
     
     
    let cons a l = 
        let res = {id=(!compteur); head=a ; next=l; prev=Nil} in
        let _ = compteur := !compteur + 1 in
        let p =
            match l with
                 Nil -> Liste(res)
                |Liste(c) -> c.prev
        in
        let _ = res.prev <- p in
        let _ = match l with
             Nil -> ()
            |Liste(c) -> c.prev <- Liste(res)
        in
        let _ = if res.next = Nil then res.next <- Liste(res) in
        Liste(res)
    ;;
     
    let concat l1 l2 =
        match (l1,l2) with
             (Nil,_) -> l2
            |(_,Nil) -> l1
            |(Liste(c1),Liste(c2)) ->
                let Liste(c1_p) = c1.prev in
                let Liste(c2_p) = c2.prev in
                c1_p.next <- l2 ;
                c2.prev <- Liste(c1_p) ;
                c2_p.next <- l1 ;
                c1.prev <- Liste(c2_p) ;
                l1
    ;;
     
    let rec iter f l =
        let first =
            match l with
                 Nil -> 0
                |Liste(c) -> c.id
        in
        let rec aux l =
            match l with
                 Nil -> ()
                |Liste(c)  -> if ((c.id) <>  first)  then begin f (c.head) ; aux (c.next) end
        in
        match l with
             Nil -> aux l
            |Liste(c) -> f (c.head) ; aux (c.next)
    ;;
     
    let print print_elt l =
        print_string " [ " ;
        iter (fun x -> print_elt x ; print_string " ") l ;
        print_string "] " ; print_newline ()
    ;;
     
    let main () =
        let l = Nil in
        print print_int l ;
        let l1 = (cons 2 l) in
        let l2 = (cons 3 l) in
        print print_int (concat l1 l2)
    ;;
     
    main ();;
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  3. #3
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par gorgonite
    pour infos, dans un langage comme C, j'aurais utilisé l'adresse de la première cellule pour comparer, mais ici, je ne vois pas comment m'y prendre
    Tu peux tester l'égalité physique et non logique par "==". Ca devrait résoudre ton problème. Mais attention de bien encapsuler ton type dans un module avec une interface restrictive ! Sinon il est possible de (mal) definir un "liste" avec une sous boucle. Par exemple, deux cellule, la première pointant sur la seconde, et la seconde pointant sur elle même. Ce n'est évidement pas une liste chainé, mais c'est "dans l'absolu" autorisé par la structure, d'où l'intéret d'une bonne interface :-)

  4. #4
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    Citation Envoyé par alex_pi
    Tu peux tester l'égalité physique et non logique par "==".

    ça marche





    Citation Envoyé par alex_pi
    Mais attention de bien encapsuler ton type dans un module avec une interface restrictive ! Sinon il est possible de (mal) definir un "liste" avec une sous boucle. Par exemple, deux cellule, la première pointant sur la seconde, et la seconde pointant sur elle même.
    a priori, je comptais faire un module avec les mêmes fonctionnalités que le module List, et donc interdire à l'utilisateur de connaître la structure interne de ma liste, et devoir passer par cons, iter, concat ou map

    que penses-tu du début ?
    (perso, je suis assez mécontant de mon cons dans le cas d'une "queue" non vide )

    Code ocaml : 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
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    type 
        'a cellule = {head : 'a; mutable next : 'a liste; mutable prev : 'a liste}
    and
        'a liste = Nil | Liste of 'a cellule
    ;;
     
    let concat l1 l2 =
        match (l1,l2) with
             (Nil,_) -> l2
            |(_,Nil) -> l1
            |(Liste(c1),Liste(c2)) ->
                let Liste(c1_p) = c1.prev in
                let Liste(c2_p) = c2.prev in
                c1_p.next <- l2 ;
                c2.prev <- Liste(c1_p) ;
                c2_p.next <- l1 ;
                c1.prev <- Liste(c2_p) ;
                l1
    ;;
     
    let rec cons a l = 
        match l with
             Nil -> 
                let res = { head=a ; next=l; prev=Nil } in
                let _ = res.next <- Liste(res) in
                let _ = res.prev <- Liste(res) in
                Liste(res)
            |Liste(_) -> concat l (cons a Nil)
    ;;
     
    let rec iter f l =
        let first =
            match l with
                 Nil -> {head=0 ; next=Nil ; prev=Nil }
                |Liste(c) -> c
        in
        let rec aux l =
            match l with
                 Liste(c) when c==first -> ()
                |Liste(c) -> f (c.head) ; aux (c.next) 
        in
        match l with
             Nil -> ()
            |Liste(c) -> f (c.head) ; aux (c.next)
    ;;
     
    let print print_elt l =
        print_string "[ " ;
        iter (fun x -> print_elt x ; print_string " ") l ;
        print_string "]" ; print_newline ()
    ;;
     
    let main () =
        let l = Nil in
        print print_int l ;
        let l1 = (cons 2 l) in
        let l2 = (cons 3 l) in
        let r = concat l1 l2 in
        print print_int r ;
        let s = cons 1 (cons 2 (cons 3 Nil)) in
        print print_int s 
    ;;
     
    main ();;
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  5. #5
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par gorgonite
    que penses-tu du début ?
    (perso, je suis assez mécontant de mon cons dans le cas d'une "queue" non vide )
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    type 
        'a cellule = {head : 'a; mutable next : 'a liste; mutable prev : 'a liste}
    and
        'a liste = Nil | Liste of 'a cellule
    ;;

    Je pense qu'il y a un problème avec ta structure. Si je comprends bien, tu es plus en train de définir des listes nécessairement circulaire plutôt que juste doublement chainée. J'aurais plutôt proposé quelque chose comme :
    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
    type 'a cell = {content: 'a;
    		mutable next: 'a cell option;
    		mutable prev: 'a cell option;}
    type 'a dl = {first: 'a cell;
    	      last: 'a cell;}
    type 'a doubleList = 
        EmptyList
      | Liste of 'a dl
     
     
    let concat l1 l2 = match l1,l2 with
      | EmptyList, l
      | l, EmptyList -> l
      | Liste dl1, Liste dl2 -> 
          dl1.last.next <- Some dl2.first;
          dl2.first.prev <- Some dl1.last;
          Liste {first = dl1.first;
    	     last = dl2.last;}
     
    let cons a = function
      | EmptyList -> 
          let c = {content = a;
    	       next = None;
    	       prev = None} in
          Liste {first = c;
    	     last = c}
      | Liste dl ->
          let c = {content = a;
    	       next = Some dl.first;
    	       prev = None} in
          Liste {first = c;
    	    last = dl.last}

  6. #6
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    Juin 2007
    Messages
    1 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Juin 2007
    Messages : 1 704
    Points : 2 990
    Points
    2 990
    Par défaut
    Tu ne préfèrerais pas plutôt une VList ?

    Description de la structure de donnée:

    http://icwww.epfl.ch/publications/do...ORT_200244.pdf

    Une implémentation en OCaml:

    http://www.imada.sdu.dk/~bardur/pers...list-1.tar.bz2
    Du même auteur: mon projet, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  7. #7
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    Citation Envoyé par alex_pi
    Je pense qu'il y a un problème avec ta structure. Si je comprends bien, tu es plus en train de définir des listes nécessairement circulaire plutôt que juste doublement chainée.
    selon toi, une doublement chainée 'simple' n'est jamais circulaire ?
    parce que selon mes cours d'algo l'avantage étaient justement de pouvoir concaténer en temps constant

    Citation Envoyé par alex_pi
    J'aurais plutôt proposé quelque chose comme :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    type 'a cell = {content: 'a;
    		mutable next: 'a cell option;
    		mutable prev: 'a cell option;}
    type 'a dl = {first: 'a cell;
    	      last: 'a cell;}
    type 'a doubleList = 
        EmptyList
      | Liste of 'a dl

    dans ta structure, on dirait que tu considères que les prédecesseurs et les successeurs n'existe pas forcemment... or dans mon cas, ils existent systématiquement dès que la liste est non vide

    qu'est-ce qui t'a amené à proposer cela ? je ne sais pas si cela est mieux dans mon cas précis ; mon seul but étant de résoudre le defi 1 sans surcout mémoire, et en minimisant le cout des concaténations
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  8. #8
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    Citation Envoyé par SpiceGuid
    Tu ne préfèrerais pas plutôt une VList ?

    le lien à l'epfl ne fonctionne plus... et j'ai pas trop envie de lire le code ce soir
    faudra que je demande à l'admin où est le fichier


    peux-tu me "résumer" les fonctionnalités et les avantages/inconviénients, stp ?

    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  9. #9
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par gorgonite
    selon toi, une doublement chainée 'simple' n'est jamais circulaire ?
    Si si, elle peut être circulaire, il suffit de la concatener avec elle même. En revanche, contrairement à ton approche, elle peut ne pas l'être
    parce que selon mes cours d'algo l'avantage étaient justement de pouvoir concaténer en temps constant
    Dans ma version la concatenation se fait à temps constant aussi.

    dans ta structure, on dirait que tu considères que les prédecesseurs et les successeurs n'existe pas forcemment... or dans mon cas, ils existent systématiquement dès que la liste est non vide
    Le premier élément de la liste n'a pas de prédécesseur, et le dernier élément n'a pas de successeur.

    mon seul but étant de résoudre le defi 1 sans surcout mémoire, et en minimisant le cout des concaténations
    Fais bien attention au fait que tu n'es pas en train de manipuler une structure fonctionnelle. Instinctivement, je dirais que ça ne va pas résoudre ton problème. Mais vu que je ne sais pas exactement ce que tu comptes faire, je ne m'avancerai pas trop ;-)

  10. #10
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    Juin 2007
    Messages
    1 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Juin 2007
    Messages : 1 704
    Points : 2 990
    Points
    2 990
    Par défaut
    L'avantage de 'a VList c'est qu'elle immutable (comme 'a list), consomme moins de mémoire que 'a list, et peut concaténer en temps constant (d'après le papier de Phil Bagwell), voir:

    http://lampwww.epfl.ch/papers/techlists.pdf
    http://citeseer.ist.psu.edu/bagwell02fast.html

    ou alors en cas de grand désespoir:

    http://en.wikipedia.org/wiki/VList

    La mauvaise nouvelle c'est que le code OCaml implémente iter, map, fold_left, for_all, exists, find, filter, partition, split, combine, mais pas concat ni même append

    Et le gros inconvénient c'est que cons n'est plus un constructeur mais une fonction, conséquence: pas de filtrage.
    Du même auteur: mon projet, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  11. #11
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    Juste comme ça, au passage...

    On peut faire une structure de liste non cyclique et non doublement chaînée dont la concaténation se fait en temps constant : il suffit de conserver une référence vers le dernier élément de la liste.
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  12. #12
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    Citation Envoyé par InOCamlWeTrust
    On peut faire une structure de liste non cyclique et non doublement chaînée dont la concaténation se fait en temps constant : il suffit de conserver une référence vers le dernier élément de la liste.


    j'avais compris, mais disons que l'idée du record debut/fin me semble peu élégante
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  13. #13
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    Et celle de devoir gérer à tout instant deux pointeurs pour chaque élément de la liste ?
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

  14. #14
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    Citation Envoyé par InOCamlWeTrust
    Et celle de devoir gérer à tout instant deux pointeurs pour chaque élément de la liste ?

    vu de l'extérieur, on ne voit pas la différence
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  15. #15
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    Juin 2007
    Messages
    1 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Juin 2007
    Messages : 1 704
    Points : 2 990
    Points
    2 990
    Par défaut
    Si on voit une différence: ça prend deux fois plus de mémoire que la solution de InOCamlWeTrust.

    Te fatigue pas pour le défi n°1, la solution est dans la Lettre de Caml n°6

    Faut écrire à qui pour proposer un défi ?
    Du même auteur: mon projet, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  16. #16
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    Citation Envoyé par SpiceGuid
    Si on voit une différence: ça prend deux fois plus de mémoire que la solution de InOCamlWeTrust.

    pas forcemment... la mémoire "supplémentaire" consommée peut être négligeable selon le type d'éléments stockés dans la liste
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  17. #17
    alex_pi
    Invité(e)
    Par défaut
    Citation Envoyé par gorgonite
    j'avais compris, mais disons que l'idée du record debut/fin me semble peu élégante
    En même temps, vu que tu veux acceder à temps constant au premier et au dernier élément, t'as pas vraiment trop le choix :-\ Après tu peux faire un peu les horreurs du module Queue, qui consiste effectivement a stocker le premier élément comme étant le suivant de la queue, et à ne pas faire d'erreur en stockant la longeur de la queue, mais bon, je considère que c'est une approche valable pour une bibliothèque standard (càd lu, relue et rerelue, et ayant pour but de vraiment viser une grande efficacité), mais pas vraiment naturelle pour une utilisation normale.

Discussions similaires

  1. liste doublement chainée
    Par Ucom-C++ dans le forum C
    Réponses: 11
    Dernier message: 07/06/2007, 14h34
  2. Réponses: 2
    Dernier message: 24/03/2007, 13h48
  3. Problème sur les listes doublement chainée
    Par Traouspont dans le forum C
    Réponses: 5
    Dernier message: 05/01/2007, 13h02
  4. Pb Liste doublement chainée template
    Par ederf dans le forum Langage
    Réponses: 5
    Dernier message: 19/11/2006, 11h35
  5. Liste doublement chainée
    Par sorry60 dans le forum C
    Réponses: 23
    Dernier message: 03/12/2005, 18h12

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