Les notes de cours de Prof. J-Y Nie ont été largement utilisées pour le paragraphe en rapport avec les Listes. La classe Vector ================ ================ Un tableau contient un ensemble de variables qui partage le même nom (de tableau) et qui sont stockés de manière séquentielle, de 0 à N-1 où N représente la taille du tableau. Cette taille est la plus part du temps fixe, on est en présence d'un tableau rigide. Les éléments sont directement accessibles via leur index. Ils sont stockés de telle manière qu'il est difficile de changer l'ordre (nécessite un traitement parfois coûteux). En Java, il existe la classe Vector du type tableau dont la taille croit ou décroît de manière dynamique à la demande. Pour utiliser les méthodes de la classe Vector, vous devez importer le paquetage: import java.util.*; Quelques méthodes de la classe Vector: constructeurs ------------- Vector(); Vector(int capacite_initiale); Vector(int capacite_initiale,int increment); des méthodes ------------ void addElement(Object element); insère un élément à la fin du vecteur. void add(int index, Object element); insère un élément à la position index. remove(int index); retire et retourne l'élément se trouvant à index. boolean remove(Object o); retire la première occurrence de l'élément. void clear(); retire tous les éléments boolean contains(Object elem); Teste si l'élément se trouve dans le vecteur. int indexOf(Object elem); recherche la première occurrence de l'élément. boolean isEmpty(); teste si le vecteur est vide. int size(); retournes le nombre de composantes dans le vecteur. void ensureCapacity(int minCapacity); augmente la capacité du vecteur pour s'assurer de contenir minCapacity void setSize(int newSize); fixe la taille. Si celle de départ est plus petite il va agrandir le vecteur, sinon il y aura une perte des données excédentaires. void trimToSize(); réduire le vecteur à sa taille exacte. voir exemple monvector.java LISTES ====== ====== Un tableau est intéressant quand on a une idée du nombre d'éléments. Il reste inefficace quand on veut insérer un élément dans une position donnée. À ce niveau la, il y aura décalage de tous les éléments pour pouvoir insérer le nouveau dans sa bonne place. Parfois cela, est très coûteux, dans le cas par exemple d'un tableau volumineux. Dans ce cas la, nous avons recours aux liens dynamiques, comme par exemple les listes. Dans une liste, le nombre d'éléments et l'ordre de ses éléments peuvent se changer facilement. Par contre dans une liste simplement chaînée, il faut parcourir la liste à partir de la tête pour retrouver un élément donné et cette opération est moins rapide que d'accéder grâce à l'index à un élément d'un tableau donné. Liste simplement chaînée ------------------------ C'est une liste d'éléments, généralement d'une même classe enchaînés par des pointeurs d'un élément vers son successeur. --------- --------- --------- | | | | | | | | | l --> | | ----->| | -----> ..... | | -----> null | | | | | | | | | --------- --------- --------- référence à une liste: référence au 1er élément qui constitue la tête. le dernier élément (queue) pointe vers un objet vide (null). Un élément de la liste est composants de 2 parties: - les attributs pour spécifier la "valeur" de l'élément - un pointeur vers son successeur. class element { déclaration des attributs de l'élément; element prochain; éventuellement des méthodes; } exemple ------- liste des entiers: class Cellule { int valeur; Cellule prochain; } ou bien: class Cellule { int valeur; Cellule prochain; Cellule(int valeur, Cellule prochain) { this.valeur = valeur; this.prochain = prochain; } } ADT ou TAD Type d'abstraction de données ---------------------------------------- - Consiste à définir des opérations standard sur un type de structure de données. - ne s'occupe pas de leur implantation. avantages: - partage des ressources: peut être donc utilisée par d'autres programmes sans soucier de la manière avec laquelle son implémentation a été réalisée. - rationaliser une implémentation: aide à faire la spécification. Exemple de ADT: Liste, les piles, les arbres etc. On spécifie ce que nous souhaitons avoir comme opérations mais nous ne spécifions pas comment implémenter ces opérations. Opérations possibles sur une liste ---------------------------------- - ajouter un élément à la tête: 1 + [2,3,4] => [1,2,3,4] - connaître la longueur d'une liste [1,2,3,4,5] => 5 - trouver le énième élément [1,2,3,4,5] 3ième => 3 - concaténer deux listes [1,2,3] + [4,5] => [1,2,3,4,5] - enlever un élément de certaine valeur [1,2,3,4,5] - 4 => [1,2,3,5] -1- ajouter un élément ====================== Cellule ajout_elt(int v) { Cellule tete = new Cellule(v,this); return tete; // return (new Cellule(v,this); } -2- connaître la longueur d'une liste ===================================== int longueur() { int l=0; Cellule ref = this; while(ref!=NULL) { l++; ref = ref.prochain; } return l; } // version recursive. int longueur() { int l=1; if (this.prochain != null) l+=this.prochain.longueur(); return l; } -3- trouver le énième élément et le retourner ============================================ Le traitement des erreurs de déplacement ne sont pas traitées. Cellule nieme_cellule(int n) { Cellule t; if (n==1) t=this; else t = prochain.nieme(n-1); return t; } -4- trouver le énième élément et retourner sa valeur =================================================== int nieme_valeur(int n) { int valeur ; if (n==1) valeur=this.valeur; else valeur = prochain.nieme(n-1); return valeur; } -5- concatener deux listes ========================== void append(Cellule l) { if (prochain == null) prochain =l; else prochain.append(l); } -6- ajouter une cellule de valeur v à la queue de la liste ========================================================== void ajout_queue(int v) { if (prochain == null) prochain = new Cellule(v,null); else prochain.ajout_queue(v); } -7- enlever le premier élément de valeur v ========================================== Cellule enlever_premier(int v) { if (valeur == v) return prochain; else { prochain = prochain.enlever_premier(v); return this; } } -8- enlever tous les éléments de valeur v ========================================= Cellule enlever_tous(int v) { if (valeur == v) return prochain.enlever_tous(v); else { prochain = prochain.enlever_tous(v); return this; } } Une autre implantation de la liste ---------------------------------- Afin de réaliser une meilleure abstraction, dans l'implantation on peut distinguer entre l'élément et la suite d'éléments. L'élément est représenté par une Cellule (noeud) et la suite d'élément chaînés par la Liste. La Liste peut garder par exemple des informations comme le nombre d'éléments qu'elle contient, un pointeur vers le premier élément ainsi que vers le dernier élément etc. Class Cellule { int valeur; Cellule prochain; } Class Liste { Cellule tete, queue; int longueur; etc. } void ajout_tete(int v) { Cellule t = new Cellule(v,tete); tete = t; longueur++; if (queue = null) queue=t; // si t est le 1er élément ajouté. } void ajout_queue(int v) { if (queue = null) tete=queue= new Cellule(v,null); else { queue = queue.prochain; } longueur++; } void append(Liste l) { if (queue==null){ queue=l.queue; tete=l.tete; }else{ queue.prochain = l.tete; queue = l.queue; } longueur += l.longueur; } Exemple ------- une liste d'entiers Liste maListe = new Liste(); // tete=queue=null;longueur=0; maListe.ajout_queue(1); maListe.ajout_queue(2); maListe.ajout_queue(3); maListe.ajout_tete(0); maListe ---------- | | | tete ---- |__________| | | | | ---- ---- ---- ---- | queue ---|- -->|0| -|->|1| -|->|2| -|->|3| -|-> null |__________| | ---- ---- ---- ---- | | | ^ | longueur | |______________________________| | 4 | |__________|