Exercice liste chainée générique JAVA - Structures de données abstraites

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

class ListeChainee {

    private Noeud debut = null;
    private Noeud fin = null;
    private Noeud courant = null;

    //constructeurs
    public ListeChainee() {};

    public ListeChainee(Object valeur) {
        courant = new Noeud(valeur);
        fin = courant;
        debut = courant;
    }

    /** ajouter un élément à la liste */
    public void ajouterElement(Object valeur) {
        // on crée un nouvel élément de la liste
        // contenant le double <valeur>
        Noeud nouvelleFin = new Noeud(valeur);

        if (debut == null) {
            //c'est le tout premier élément de la liste
            // i.e. la liste était vide
            debut = nouvelleFin;
            fin = nouvelleFin;
        courant = nouvelleFin;
        } else {
            // la liste contenait déjà des éléments
            fin.setSuivant(nouvelleFin);
            fin = nouvelleFin;
        }
    }

    /** tester si l'élément courant n'est pas null */
    public boolean aCourant() {
        return (courant != null);
    }

    // retourner la valeur de l'élément courant de la liste
    public Object valeur() {
        if (aCourant()) {
            return (courant.getValeur());
        } else {
            return null;
        }
    }

    /** retourner le premier élément de la liste */
    public Noeud premier() {
        courant = debut;
        if (debut == null) {
            return null;
        } else {
            return debut;
        }
    }

    /** retourner l'élément suivant dans la liste */
    public Noeud suivant() {
        if (courant != null) {
            courant = courant.getSuivant();
        }

        if (courant == null) {
            return null;
        } else {
            return courant;
        }
    }
}

class Noeud {
    /** la valeur stockée */
    private Object valeur; 
    /** la référence à l'élément suivant de la liste */
    private Noeud suivant;

    public Noeud(Object valeur) {
        this.valeur = valeur;
        suivant = null;
    }

    public Object getValeur() {
        return valeur;
    }

    public void setValuer(Object newValeur) {
        valeur = newValeur;
    }

    public Noeud getSuivant() {
        return suivant;
    }

    public void setSuivant(Noeud newSuivant) {
        suivant = newSuivant;
    }

}

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

class MoyenneListe2 {

  public static void main(String[] args) {
        ListeChainee notes = new ListeChainee();

        /* Notre liste chaînée est programmée pour contenir
           des "Object"s.
           Si on veut travailler avec des valeurs numériques, il
           serait donc normalement nécessaire de stocker dans la 
           liste, des objets de type Double (qui sont des Objects)
           et non pas de type double (qui ne sont pas des Objects).
           Bref, il faudrait "emballer" nos doubles dans des Doubles:

           notes.ajouterElement(new Double(2.0));

           C'est en fait comme cela qu'il faut procéder dans toutes 
           les version de Java antérieures à la 1.5.
           Dans Java 1.5, le compilateur fait automatiquement 
           l'emballage/déballage pour vous, 
           (c'est ce qu'on appelle l'"autoboxing").
           Ec ceci nous permet d'écrire sans souci le code suivant:
        */
        notes.ajouterElement(2.0);
        notes.ajouterElement(1.0);
        notes.ajouterElement(6.0);
        notes.ajouterElement(5.5);

        notes.premier(); // on se positionne au début
        // de la liste
        // (notes.courant pointe sur le 1er noeud)

        double moyenne = 0.0;
        int n = 0;
        // tant que notes.courant n'est pas null
        // on avance dans le liste en calculant
        // la somme des notes
        while (notes.aCourant()) {
            // notes.valeur() donne le double stocké dans
            // notes.courant
          Double note = (Double)notes.valeur();
          if (note == null){
            note = Double.NaN; // Double.NaN est définie dans
                               // la classe Double et signifie
                               // "Not a Number"
          }
          moyenne += note.doubleValue();
          // En utilisant à nouveau l'autoboxing (JDK 5.0),
          // on peu écrire la ligne précédente comme suit:
          // moyenne += note;
          notes.suivant();
          n++;
        }

      System.out.println("La moyenne est: " + moyenne / n);
    }

}