Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 6 sur 6

Discussion: Liste triée en Java

  1. #1
    Invité de passage
    Inscrit en
    décembre 2011
    Messages
    26
    Détails du profil
    Informations forums :
    Inscription : décembre 2011
    Messages : 26
    Points : 2
    Points
    2

    Par défaut Liste triée en Java

    Bonsoir tout le monde, voila j'ai un soucis à propos des liste chainées.
    Je travaille sur des listes triées, l'ajout d'un élément se fait toujours au bon endroit.
    Et j'ai un soucis à propos de la méthode d'ajout, j'ai du mal à l'implémenter (du point vu algorithmique je l'ai) donc si vous pouvez me donner quelques pistes (je remet aussi peut-être en cause la manière dont je vois les listes chainées en java, j'ai l'impression d'être en C par moment ou leurs implémentations est vachement plus simple!).
    Voici ma classe Liste (classe abstraite car je code plusieurs types listes : les listes triées, liste chainée acceptant les doublons et liste chainée qui n'accepte pas les doublons). Dans cette classe se trouve une classe static Node (qui represente un noeud de ma chaine):
    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
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
     
    /**
     * Classe abstraite pour representant les listes chainées/
     *
     */
    public abstract class Liste {
    	/**
    	 * Classe interne pour representer un Noeud (un entier, un pointeur sur l'element suivant)
    	 *
    	 */
    	public static class Node {
    		private int val;
    		private Node next;
     
    		public Node(int x) {
    			this.val = x;
    			this.next = null;
    		}
     
    		public Node(int x, Node l) {
    			this.val = x;
    			this.next = l;
    		}
     
     
    		public int getVal() {
    			return val;
    		}
     
    		public void setVal(int val) {
    			this.val = val;
    		}
     
    		public Node getNext() {
    			return next;
    		}
     
    		public void setNext(Node next) {
    			this.next = next;
    		}
    	}  // Fin de la classe Interne
     
    	protected Node deb;
     
    	public Liste() {
    		deb = null;
    	}
     
    	public Liste(Node l) {
    		this.deb = l;
    	}
     
    	public boolean estVide() {  /* retourne si la liste est vide */
    		return deb == null; 
    	}
    }
    et voici ma classe Liste_simple qui n'accepte pas les doublons( pour l'instant on s'en fiche,moi je veux juste insérer dans l'ordre) :

    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
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    public class List_S extends Liste implements Operations {
     
     
     
    	public List_S() {
    		super();
    	}
     
    	public List_S(Node l) {
    		super(l);
    	}
     
    	public Liste ajouteElement(int x) {
    		return null;
    	}
     
     
     
    	public String toString() {
    		if(this.estVide()) return "Liste vide";
    		String res = "";
    		Node l = deb;
    		while(l != null) {
    			res += l.getVal() + " --> ";
    			l = l.getNext();
    		}
    		return res += "NULL";
    	}
     
     
    	@Override
    	public Liste supprimerElement(int x) {
    		// TODO Auto-generated method stub
    		return null;
    	}
     
    	@Override
    	public Liste union(Liste l1, Liste l2) {
    		// TODO Auto-generated method stub
    		return null;
    	}
     
    	@Override
    	public void union(Liste l) {
    		// TODO Auto-generated method stub
     
    	}
     
    	@Override
    	public Liste intersection(Liste l1, Liste l2) {
    		// TODO Auto-generated method stub
    		return null;
    	}
     
    	@Override
    	public void intersection(Liste l) {
    		// TODO Auto-generated method stub
     
    	}
     
    }
    Est-ce que vous pensez que j'ai besoin de plus d'information pour faire une telle méthode d'ajout (je parle par exemple d'ajouter des attributs)?
    Merci bcp de votre aide

  2. #2
    Expert Confirmé Sénior
    Avatar de tchize_
    Homme Profil pro
    Responsable de service informatique
    Inscrit en
    avril 2007
    Messages
    21 462
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : Belgique

    Informations professionnelles :
    Activité : Responsable de service informatique
    Secteur : Service public

    Informations forums :
    Inscription : avril 2007
    Messages : 21 462
    Points : 35 326
    Points
    35 326

    Par défaut

    Citation Envoyé par AliFirat91 Voir le message
    Bonsoir tout le monde, voila j'ai un soucis à propos des liste chainées.
    Je travaille sur des listes triées, l'ajout d'un élément se fait toujours au bon endroit.
    Et j'ai un soucis à propos de la méthode d'ajout, j'ai du mal à l'implémenter (du point vu algorithmique je l'ai)
    En même temps, dans le code que tu nous donne tu n'a carrément rien implémenter, tes méthode d'ajout / suppression se contentent de retourne null :s


    les listes triées, liste chainée acceptant les doublons et liste chainée qui n'accepte pas les doublons).
    Les liste chainées sont loin d'être la structure idéale pour stocker des liste triées :s
    Tchize (Чиз) faq java, cours java, javadoc. Pensez à et
    Laisse entrer le jour après une nuit sombre. Si tu es toujours là, tu n'es pas faite pour mourir.

  3. #3
    Invité de passage
    Inscrit en
    décembre 2011
    Messages
    26
    Détails du profil
    Informations forums :
    Inscription : décembre 2011
    Messages : 26
    Points : 2
    Points
    2

    Par défaut

    Le problème c'est que je suis obligé de passer par des listes triées (c'est imposé par mon projet). Ajouter dans une liste non trié, facile mais par contre ajouter dans un element dans une liste triée, je vois comment le faire à peu près en algo mais en java (et surtout dans la manière dont je represente les listes triées).
    Est-ce que par exemple je peux passer par les piles pour representer une liste chainée triée ?

  4. #4
    Invité de passage
    Inscrit en
    novembre 2012
    Messages
    3
    Détails du profil
    Informations forums :
    Inscription : novembre 2012
    Messages : 3
    Points : 3
    Points
    3

    Par défaut

    Je ne pense pas que passer par des piles soit la solution... tu vas te compliquer la vie en faisant ça.
    Pour trier ta liste au moment de l'ajout peut être qu'en utilisant un algorithme dichotomique ça serait plus simple?

  5. #5
    Expert Confirmé Sénior
    Avatar de tchize_
    Homme Profil pro
    Responsable de service informatique
    Inscrit en
    avril 2007
    Messages
    21 462
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : Belgique

    Informations professionnelles :
    Activité : Responsable de service informatique
    Secteur : Service public

    Informations forums :
    Inscription : avril 2007
    Messages : 21 462
    Points : 35 326
    Points
    35 326

    Par défaut

    painfulBetrayal: on ne sais pas utiliser de manière performante des algo dichotomiques sur des listes chainées, parce que le principe de ces algo c'est de sauter à des endroit précis de la liste et de s'orienter progressibmenet, on est obligé, dans une liste chainée, de parcourir la moitié de la chaine juste pour la première étape de l'algo dichotomique. Ca occupe un temps o(n) alors qu'avec un tableau ca occupe un temps o(1). On peux améliorer avec les skip-list, mais je pense qu'on est au delà de la demande initiale
    Tchize (Чиз) faq java, cours java, javadoc. Pensez à et
    Laisse entrer le jour après une nuit sombre. Si tu es toujours là, tu n'es pas faite pour mourir.

  6. #6
    Membre éprouvé
    Femme Profil pro
    Développeur Java
    Inscrit en
    décembre 2009
    Messages
    237
    Détails du profil
    Informations personnelles :
    Sexe : Femme

    Informations professionnelles :
    Activité : Développeur Java
    Secteur : Finance

    Informations forums :
    Inscription : décembre 2009
    Messages : 237
    Points : 428
    Points
    428

    Par défaut

    Bonjour,

    basiquement je ferais quelquechose tel que:

    • si next node est < element à ajouter, continuer
    • sinon creer un nouveau node de valeur element, avec next node= next node de l'element actuel, et ajouter le nouveau node à l'element actuel


    Apres c'est un algo trivial, qui doit pouvoir être amélioré

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •