Liste doublement chainée [Fermé]

Messages postés
95
Date d'inscription
samedi 30 juillet 2011
Statut
Membre
Dernière intervention
13 mai 2017
- - Dernière réponse : stampia02
Messages postés
95
Date d'inscription
samedi 30 juillet 2011
Statut
Membre
Dernière intervention
13 mai 2017
- 19 mars 2017 à 17:29
Bonjour,

Je dois implémenter une liste doublement chainée, y a t'il des exemples fiable + des explications sur les pointeurs etc?

Je ne sais pas très bien par ou commencer

Merci
Afficher la suite 

2 réponses

Messages postés
16075
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 novembre 2019
2455
0
Merci
Bonjour,

"des explications sur les pointeurs"
Il n'y a pas de pointeurs en Java...

"y a t'il des exemples fiable"
Voici une structure de liste qui devrait fonctionner :

public class ListeDoublementChainee<E> {
    private Chaine<E> premiere, derniere;

    private class Chaine<E> {
        private E element;
        private Chaine<E> precedente, suivante;
    }
}

La confiance n'exclut pas le contrôle
stampia02
Messages postés
95
Date d'inscription
samedi 30 juillet 2011
Statut
Membre
Dernière intervention
13 mai 2017
1 -
Je pense avoir compris, cependant je ne suis pas sur de ma logique, qu'en pense tu de cette méthode?

	public void insererEnTete(E element) { 
		Chaine n = new Chaine(null, element, null);
		n.precedent = tete.suivant;
		n.suivant = queue.precedent;
		tete.suivant = n;
		queue.precedent = n;
		numVersion++;
		taille++;
	}
KX
Messages postés
16075
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 novembre 2019
2455 -
n.precedent = tete.suivant;
n.suivant = queue.precedent;
Cela veut dire que n est à la fois le suivant de la tête et le précédent de la queue, c'est à dire qu'il est au milieu des deux ? Ça ne peut pas être correct.

Quelques remarques/questions ?
  • Pourquoi mettre null dans
    new Chaine(null, element, null);
    si c'est pour après affecter les valeurs
    n.precedent
    et
    n.suivant
    ?
  • En terme de nommage
    tete
    et
    queue
    sont de mauvais choix car cela correspond au vocabulaire des files, pas des listes.
  • Il te manque les cas initiaux, que se passe-t-il si
    queue
    ou
    tete
    sont null ?
  • À quoi sert
    numVersion
    ?

Il faudrait que tu testes ton code, tu peux commencer par faire la méthode
toString()
de la liste, ça te sera utile pour l'afficher et voir ses modifications successives.
stampia02
Messages postés
95
Date d'inscription
samedi 30 juillet 2011
Statut
Membre
Dernière intervention
13 mai 2017
1 -
J'utilise
numVersion
pour un itérateur que j'implémente également.
J'ai fais un
toString()
, au départ après 2 insertions javai bien
taille == 2
mais mon toString n'affichai que le dernier element de ma liste.

Exemple: insere "a" puis "insere "b"
Je fais
liste.toString()
et il m'affiche uniquement "b"
Maintenant après modification il m'affiche plus rien

 public void insererEnTete(E element) {
  Chaine n = new Chaine(tete, element, tete.suivant);
  n = tete.suivant;
  numVersion++;
  taille++;
 }


J'ai également mis au début et à la fin une chaine "bidon" sur laquelle la tete pointe histoire de ne jamais avoir de cas null quand j'ajoute un élément.
KX
Messages postés
16075
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 novembre 2019
2455 -
J'utilise numVersion pour un itérateur que j'implémente également.
Il faudrait voir le code complet, mais je pense que ça ne sers à rien.

J'ai fais un toString(), au départ après 2 insertions javai bien taille == 2 mais mon toString n'affichai que le dernier element de ma liste.
En effet, c'est parce que ton insertion ne marche pas. L'incrément de la taille est correct mais il est totalement à part du reste.

"Maintenant après modification il m'affiche plus rien"
A priori c'est normal vu que tu ne modifies ni la tête ni la queue, donc la chaîne est créée dans le vide mais n'est pas associée à la liste.

"J'ai également mis au début et à la fin une chaine "bidon" sur laquelle la tete pointe histoire de ne jamais avoir de cas null quand j'ajoute un élément."
À mon avis c'est une erreur, c'est normal d'avoir des null quand la liste est vide puisqu'il n'y a aucune chaîne...
stampia02
Messages postés
95
Date d'inscription
samedi 30 juillet 2011
Statut
Membre
Dernière intervention
13 mai 2017
1 -
J'ai reussi, je ne liai pas vers la nouvelle chaine effectivement.
Messages postés
95
Date d'inscription
samedi 30 juillet 2011
Statut
Membre
Dernière intervention
13 mai 2017
1
0
Merci
Dans mon programme principale j'aimerai creer un concours avec un nombre de participant de base (un part chaine), j'ai créer cela comme suit mais quand j'essaye d'afficher toute ma chaine cela ne marche pas via mon main, par contre le toString() fonctionne sur ma classe de test.

J'ai testé le chainage et il fonctionne aussi.

Que pourrait être le problème ? J'ai cherche partout

	public static void concourDepart(){
		System.out.print("Entrez le nombre de participants : ");
		int nombreP = scanner.nextInt();
		
		for (int i = 1; i <= nombreP; i++){
			
			System.out.print("\nEntrez le nom du participant " + i + ": ");
			String participant = scanner.next();
			c.nouveauParticipant(participant);
		}
	}


	public String afficherParticipants(){
		return listeParticipants.toString();
	}


Le toString() dans ma liste chainé
	public String toString(){
		String aRenvoyer = "";
		IterateurImpl<E> i = new IterateurImpl<>();
		while(i.hasNext()){
			E element = i.next();
			aRenvoyer += " " + element;
		}
		return aRenvoyer;
	}
KX
Messages postés
16075
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
15 novembre 2019
2455 -
Je n'ai pas tout compris, et ça ne concerne plus trop ta question initiale, mais il y a un piège avec
Scanner
lorsqu'il est utilisé avec
System.in
car lorsque l'on tape au clavier on appuie sur la touche Entrée pour valider la ligne ce qui introduit des caractères supplémentaire.
Je t'invite à utiliser uniquement des
scanner.nextLine();
quitte à les reconvertir en entier avec
Integer.parseInt();
...
stampia02
Messages postés
95
Date d'inscription
samedi 30 juillet 2011
Statut
Membre
Dernière intervention
13 mai 2017
1 -
D'accord merci :)