liste doublement chaînée: tutorial ou cours sur sites internet

Version imprimable

11/05/2008, 16h44
johnny3

liste doublement chaînée: tutorial ou cours sur sites internet

Bonjour,

j'ai fait des recherches internet infructueuses sur les listes doublement chaînées. Mon but est d'en écrire une, donc de ne pas utiliser LinkedList, ni ListIterator, bien que ces fonctions soient très pratiques.

Ce lien est très bien fait: http://brassens.upmf-grenoble.fr/IMS.../ListeLiee.htm, mais il traite de ListIterator et de l'interface List, ce qui ne m'arrange pas.

J'ai commandé tout à l'heure deux livres (un de Schaum sur les structures de données en java et un de Dunod sur l'algorithme en java), mais je ne les aurai pas entre les mains avant jeudi soir, avec un peu de chance mercredi soir.

J'aimerais écrire cette classe avant samedi prochain. Si jamais quelqu'un connaitrait un lien internet sur l'implémentation des listes doublement chaînées (que ce soit en java ou en langage algorithmique) avec des bouts de code (sachant que ce qui me pose problème est le codage de l'insertion et de la suppression en milieu de liste), cela m'arrangerait.

Pour éviter tout malentendu, je ne demande à personne de faire cet exercice à ma place, ni d'écrire du code ici.

Je désire juste être orienté sur des sites (qui m'auraient échappés) autres que ceux que l'on trouve en tapant "liste doublement chaînée" et que certains connaitraient, pour voir des modèles d'algorithme de suppression et d'insertion (car si je comprends le principe des pointeurs, et que l'addition ou la suppression en tête ou en queue ne me posent pas problème, cela est différent pour ces mêmes opérations en milieu de liste)

En vous remerciant par avance,

Johnny3

PS: j'ai déjà regardé les cours ou tutoriaux sur developpez.com, mais rien qui ne réponde à mes questions.

PPS: si jamais personne ne peut me répondre, ne vous inquiétez pas, il s'agit juste d'un exercice d'entraînement pour la prochaine séance d'ED, donc j'aurai dans tous les cas la réponse samedi prochain, mais j'aimerais le faire malgré tout.

bonjour,

en algorithmique en gros cela donnerait:

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
ELEMENT : ENREGISTREMENT
   CLEF
   SUIVANT   : ELEMENT
   PRECEDENT : ELEMENT
FIN ENREGISTREMENT

LISTE : ENREGISTREMENT
   TETE  : ELEMENT
   QUEUE : ELEMENT
FIN ENREGISTREMENT

FONCTION DOUBLE_LISTE:RECHERCHER(LISTE, CLEF)
   ELEMENT := LISTE.TETE
   TANT QUE ELEMENT != NIL ET ELEMENT.CLEF != CLEF
      ELEMENT := ELEMENT.SUIVANT
   FIN TANT QUE'
   RETOURNER ELEMENT
FIN FONCTION

FONCTION DOUBLE_LISTE:INSERER_DEVANT(LISTE, NOUVEL_ELEMENT)
   ELEMENT := LISTE.TETE
   LISTE.TETE := NOUVEL_ELEMENT
   NOUVEL_ELEMENT.SUIVANT = ELEMENT
   NOUVEL_ELEMENT.PRECEDENT = ELEMENT
   SI LISTE.QUEUE = NIL ALORS
      LISTE.QUEUE := NOUVEL_ELEMENT
   FIN SI
FIN FONCTION

FONCTION DOUBLE_LISTE:SUPPRIMER(LISTE, ELEMENT_SUPPRIME)
   SI ELEMENT_SUPPRIME.PRECEDENT != NIL ALORS
      ELEMENT_SUPPRIME.PRECEDENT.SUIVANT := ELEMENT_SUPPRIME.SUIVANT
   SINON
      LISTE.TETE := ELEMENT_SUPPRIME.SUIVANT
   FIN SI

   SI ELEMENT_SUPPRIME.SUIVANT != NIL ALORS
      ELEMENT_SUPPRIME.SUIVANT.PRECEDENT := ELEMENT_SUPPRIME.PRECEDENT
   SINON
      LISTE.QUEUE := ELEMENT_SUPPRIME.PRECEDENT
   FIN SI
FIN FONCTION

avec compelxité O(1) pour la supression et l'ajout (l'avantage par rapport aux lsites simplement chainées)

voilà, à implémenter ce n'est pas trop compliquer, demande si besoin ;)

@++

merci!

Je te remercie, je n'en demandais pas tant, merci beaucoup. Mais voilà, ce que je ne comprends pas en général, c'est ceci: ELEMENT_SUPPRIME.SUIVANT.PRECEDENT := ELEMENT_SUPPRIME.PRECEDENT

je ne saisis pas suivant.précédent. Je veux dire, à quoi cela renvoie. J'ai bien saisis le principe d'une liste doublement chaînée, avec chaque maillon ayant un pointeur sur le suivant et un sur le précédent.

Sinon, je suis en train de lire "Structures de données en Java, C++ et Ada 95) de Carrez, qui parle des listes doublement chaînées.

Il a écrit ceci, qui est la même chose que toi:
Code:

1 2 3 4 5 6 7 public void Supprimer_Courant () throws Erreur_Specification { Place P = Courant; if (Courant == null) throw new Erreur_Specification (this); Courant = Courant.Suivant; if (Precedent == null) Tete = Courant; else Precedent.Suivant = Courant; longueur = longueur - 1;
et je retrouve ce Precedent.Suivant = Courant!
Et je ne saisis finalement pas bien son code.
En fait, c'est étrange, car, si j'ai bien compris, j'ai, par exemple:
Code:

1 2 Prec|Element|Suivant -> Prec|Element|Suivant-> Prec|Element|Suivant 1 <- 2 <- 3
Attends attends... dis-moi si je comprends bien s'il te plait.

Si je supprime celui du milieu, je dois réaliser 2 étapes:

- le suivant de 1 pointe sur 3 : ELEMENT_SUPPRIME.PRECEDENT.SUIVANT := ELEMENT_SUPPRIME.SUIVANT

- Si 1 n'existe pas, 2 est supprimé et la tête de la liste pointe sur 3: LISTE.TETE := ELEMENT_SUPPRIME.SUIVANT

- le précédent de 3 pointe sur 1 : ELEMENT_SUPPRIME.SUIVANT.PRECEDENT := ELEMENT_SUPPRIME.PRECEDENT

- Si 3 n'existe pas, 2 est supprimé et la queue de la liste pointe sur 1: LISTE.QUEUE := ELEMENT_SUPPRIME.PRECEDENT

La vache, je crois que je viens de comprendre grâce à ton algorithme. C'est bien cela? Je ne me suis pas trompé?

En tout cas, si c'est ça, merci, car je pourrais écrire ma classe dès demain!

Par contre, je n'ai pas encore vu O(1). C'est dans le chapitre juste après que nous sommes censés n'étudier que dans une semaine. C'est normal? Je suis mes cours au CNAM (cours en ligne sur le site: http://deptinfo.cnam.fr/Enseignement/CycleA/APA/, dans notes de cours. C'est là que j'ai vu qu'on retrouvait O(1), mais je n'ai pas encore lu le cours (on peut le lire en avance, mais les exos tombent une fois par semaine, et comme ils sont souvent longs à faire, il est rare de pouvoir lire les cours en avance)

Johnny3