Implémentation d'une liste chainée

c'est bien cela :ccool:

ça marche très bien, j'avais aussi remarquer qu'il me prenais qu'1 seule voisine donc forcément ma liste redevenais vide et s'arréter,

par contre j'aimerai revenir dessus pour voir si j'ai bien compris ( le but étant avant tout de comprendre ;) )

création d'une liste stationvoisines ou on stock les stations voisines

Code:

---

1 2	ListeStation stationsvoisines=stationcourant.voisines

---

si cette liste n'est pas vide (donc si il y a des voisines)...

Code:

---

1 2	while(stationsvoisines!=null){

---

on ajoute le nom de station de ces voisines dans la liste file

Code:

---

1 2	file.ajouterEnQueue(stationsvosines.station);

---

la suivante de la voisine devient la voisine et donc on reprend la boucle While. jusqu'a ce que la suivant soit une Null et donc fin de la boucle.

Code:

---

1 2	stationsvoisines=stationsvoisines.suivant;

---

voila comment je le comprend , bien sur corrige moi si je me trompe;



je vais donc pouvoir passer a la dernière partie "le chemin le plus court".

voici le début de mon prog:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public ListeStations trouverLePlusCourtChemin(int i, int j) {   // on parcourt le reseau en partant de la station i parcourir(i); // si la station j n'a pas ete atteinte, il n'existe pas de chemin if (station[j].ordreDeVisite == 0) return null; // s'il existe un chemin, on le construit en partant de la fin ListeStations chemin = new ListeStations(station[j], null);   // while(station[j]!= station[i]){   chemin.ajouterEnQueue(meilleurvoisine); }   return chemin;   }   }

---

je bloque une nouvelle fois sur ma boucle , comment représenter :

Tant que la première station constituant le chemin n'est pas la station de départ
---> ok
On parcourt toutes les voisines de la première station du chemin pour trouver celle qui a le plus petit ordre de visite, que l'on appelle par exemple meilleureVoisine
----> j'ai du mal a le concevoir

On ajoute meilleureVoisine en tête du chemin --->ok

Citation:

---

Envoyé par bendébutantenprog

c'est bien cela :ccool:

ça marche très bien, j'avais aussi remarquer qu'il me prenais qu'1 seule voisine donc forcément ma liste redevenais vide et s'arréter,

par contre j'aimerai revenir dessus pour voir si j'ai bien compris ( le but étant avant tout de comprendre ;) )

création d'une liste stationvoisines ou on stock les stations voisines

Code:

---

1 2	ListeStation stationsvoisines=stationcourant.voisines

---

---

On ne créé rien ici : on déclare une variable stationsvoisines et on lui affecte la référence stockée dans stationcourant.voisines (la référence d'une instance de classe ListeStation)

Citation:

---

Envoyé par bendébutantenprog

si cette liste n'est pas vide (donc si il y a des voisines)...

---

si cette référence n'est pas null (une référence n'est jamais vide, une liste peut être vide, c'est à dire n'avoir aucun élément, mais c'est autre chose, que d'être null )

Citation:

---

Envoyé par bendébutantenprog

Code:

---

1 2	while(stationsvoisines!=null){

---

on ajoute le nom de station de ces voisines dans la liste file

---

on ajoute la station (c'est à dire l'instance de classe Station référencée par stationsvoisines.station)

Citation:

---

Envoyé par bendébutantenprog

Code:

---

1 2	file.ajouterEnQueue(stationsvoisines.station);

---

la suivante de la voisine devient la voisine et donc on reprend la boucle While. jusqu'a ce que la suivant soit une Null et donc fin de la boucle.

---

stationvoisines devient la suivante, et on boucle, si la suivante est null, alors stationvoisines est null, et donc la boucle s'arrête en effet : donc on itère bien sur toutes les stations de la liste chainée jusqu'à ce qu'on en ait plus
[quote=bendébutantenprog;7335820]

Code:

---

1 2	stationsvoisines=stationsvoisines.suivant;

---

Citation:

---

Envoyé par bendébutantenprog

voila comment je le comprend , bien sur corrige moi si je me trompe;

---

tu comprends le sens global ! c'est déjà très bien ! juste quelques termes inappropriés et inexacts ;)

Citation:

---

Envoyé par bendébutantenprog

je vais donc pouvoir passer a la dernière partie "le chemin le plus court".

---

vas-y :D

Citation:

---

Envoyé par bendébutantenprog

On parcourt toutes les voisines de la première station du chemin pour trouver celle qui a le plus petit ordre de visite, que l'on appelle par exemple meilleureVoisine
----> j'ai du mal a le concevoir

---

lorsqu'on cherche "le plus petit" dans une liste, on commence toujours par créé un "compteur" qu'on initialise toujours à une valeur strictement plus grande que la "valeur la plus grande"
si on ne peut pas l'initialiser, alors on utilise la référence de ce qu'on cherche : comme au début de la recherche on la forcément pas trouvé, alors on peut savoir quoi faire au début

donc la tu vas devoir parcourir les stations voisines d'une stations : ça tombe bien, on l'a déjà fait juste dans l'exo d'avant

donc tu déclares une variable qui va nous servir à déterminer si l'ordrevisite du la station voisine courant est plus petit ou pas, et une variable qui nous permet de stocker la référence de la station voisine trouvée

ici on peut se passer du compteur, parce qu'on peut utiliser directement la variable ordrevisite de la classe Station à la place

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Station meilleureVoisine=null; // début de la recherche : donc forcément on a encore rien trouvé   // on itère ListeStation stationsvoisines=station[j].voisines; while(stationsvoisines!=null){ // cette station a elle un ordre plus petit que celle déjà trouvée ? if (meilleureVoisine==null) { // on en a pas encore trouvé, donc la courant est forcément celle d'ordre le plus petit qu'on ait déjà itérée meilleureVoisine=stationsvoisines; } else if ( stationsvoisines.ordrevisite<meilleureVoisine.ordrevisite ) { // la station courante a un ordre de visite plus petit que celle trouvée précédemment, on prend celle là meilleureVoisine=stationsvoisines; } stationsvoisines=stationsvoisines.suivant; }   // maintenant meilleureVoisine contient bienla station d'ordre de visite le plus petit parmi les stations voisine de station[j]

---

Merci encore une fois de cette réponse (Et avec des explications en prime :ccool:)

par contre tous ne ce compile pas ;

Code:

---

1 2	meilleureVoisine=stationsvoisines;

---

une listestations != Station

je l'ai donc modifier en

Code:

---

1 2	meilleureVoisine=stationsvoisines.station;

---

ça te semble bon ?

idem pour

Code:

---

1 2	( stationsvoisines.ordrevisite<meilleureVoisine.ordrevisite )

---

la je vois pas....:(

ah oui, au temps pour moi, j'oublie toujours que stationsvoisines est une ListeStation, pas une Station

pour

Code:

---

if ( stationsvoisines.ordrevisite<meilleureVoisine.ordrevisite )

---

c'est simple ! c'est pareil !

Code:

---

if ( stationsvoisines.station.ordrevisite<meilleureVoisine.ordrevisite )

---

:lol:

en fait c'est ce que j'avais fait , mais il y avais une erreur de synthaxe que je n'avais pas vu :oops:

ce n'est pas

Code:

---

1 2	if ( stationsvoisines.station.ordrevisite<meilleureVoisine.ordrevisite )

---

mais

Code:

---

1 2	if ( stationsvoisines.station.ordreDeVisite<meilleureVoisine.ordreDeVisite )

---

voila pourquoi Eclipse voyais rouge :mouarf:

dernier détail je pense :

Code:

---

1 2	chemin.ajouterEnQueue( meilleureVoisine);

---

erreur sur ajouterEnQueue , il veux que ça devienne une ListeStation.... or mon chemin est une ListeStation.

Citation:

---

Envoyé par bendébutantenprog

:lol:

dernier détail je pense :

Code:

---

1 2	chemin.ajouterEnQueue( meilleureVoisine);

---

erreur sur ajouterEnQueue , il veux que ça devienne une ListeStation.... or mon chemin est une ListeStation.

---

mmm, je ne te suis pas là : meilleureVoisine est une Station, et chemin est une ListeStation
en relisant les posts, ta méthode ajouterEnQueue() de ListeStations prend bien en argument une Station

"il veut que ça devienne une ListeStation" ? quoi devrait devenir une ListeStation ?

je me suis peut être mal exprimer, alors je reformule :

l'idée étant de "On ajoute meilleureVoisine en tête du chemin"
je suppose qu'il faut prend AjouterEnqueue , étant donner qu'on m'a pas créer AjouterEnTête...

donc j'ai mis

Code:

---

1 2	chemin.ajouterEnQueue( meilleureVoisine);

---

Mais notre ami Eclipse me note Create method ajouterEnQueue(station) in type Listestations.
euh 8O pourquoi ?

Citation:

---

Envoyé par bendébutantenprog

je me suis peut être mal exprimer, alors je reformule :

l'idée étant de "On ajoute meilleureVoisine en tête du chemin"
je suppose qu'il faut prend AjouterEnqueue , étant donner qu'on m'a pas créer AjouterEnTête...

---

si l'algo de ton énoncé dit qu'il faut ajouter en tête, à priori, il faut ajouter en tête et pas en queue,
si la méthode n'existe pas, il faut peut être que tu l'écrives ?

Citation:

---

donc j'ai mis

Code:

---

1 2	chemin.ajouterEnQueue( meilleureVoisine);

---

Mais notre ami Eclipse me note Create method ajouterEnQueue(station) in type Listestations.
euh 8O pourquoi ?

---

euh, là, je comprends pas...
à moins que tu aies supprimé la méthode ajouterEnQueue(Station) de la classe ListeStation, ou que tu aies modifié sa signature

elle y est ou pas la méthode ? si tu demandes la création, il te crées la méthode en double ou pas ? ça peut arriver qu'une méthode ne soit pas détectée par eclipse si on l'ajoute à un source sans sauvegarder, mais comme cette méthode a été ajoutée y'a un moment, je suppose que tu as sauvegarder depuis

ah non mais attends ListeStation c'est la classe lien de ta liste chainée
ta classe de liste chainées c'est FileDattenteStation

c'est confusant

normalement la classe lien d'une liste chainée ne doit pas etre manipulée à l'extérieur de la classe de liste de chainée

donc soit chemin doit être une FileDattentStation,

soit au lieu de

Code:

---

chemin.ajouterEnTete(stationvoisines)

---

fait

Code:

---

chemin=new ListeStation(stationvoisines, chemin);

---

non ,je pense que ta premiere idée est la bonne ;

je fais fausse route !!!

"si l'algo de ton énoncé dit qu'il faut ajouter en tête, à priori, il faut ajouter en tête et pas en queue,
si la méthode n'existe pas, il faut peut être que tu l'écrives ?"

donc je vais réfléchir dans ce sens.

salut bendébutantenprog!

est-ce que tu pourrais mettre ton exercice?

mets aussi ta classe Station

Bonjour,

bien sur , mon TD est tirer du site de polytechnique, dont voici l'adresse, je suis actuellement sur le dernier exo.

https://www.enseignement.polytechniq...11-td_10-1.php

la class Station :

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

public class Station {   String nom; //nom de la station String ligne; //ligne du métro ListeStations voisines; //station suivante   int ordreDeVisite; //ordre sur la ligne   public Station(String nom, String ligne, ListeStations voisines) {   //initialisation des champs this.nom=nom; this.ligne=ligne; this.voisines=voisines; ordreDeVisite = 0; }   public String chaineLigneNom() {   //affichage de la chaine de caractére return ligne+" - "+nom ; }   public void afficher() {   System.out.println("Station : "+nom); System.out.println("Ligne : "+ligne); if (ordreDeVisite == 0) { System.out.println("ordre de visite : jamais visite. "); } else { System.out.println("ordre de visite : "+ ordreDeVisite); } if (voisines == null) {   System.out.println("Stations voisines : aucune "); } else { System.out.print("Stations voisines : " ); voisines.afficher(); System.out.println(" "); } }   public void ajouterVoisine(Station s) {   voisines= new ListeStations (s, voisines);     } }

---

bon , je viens de me remettre un peu dessus,

normalement , si je "On ajoute meilleureVoisine en tête du chemin"

mon code devrai être

Code:

---

1 2	chemin = new ListeStations (meilleureVoisine,chemin);

---

mais la j'ai :
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space


il tourne en rond c'est ça ?

Citation:

---

Envoyé par bendébutantenprog

bon , je viens de me remettre un peu dessus,

normalement , si je "On ajoute meilleureVoisine en tête du chemin"

mon code devrai être

Code:

---

1 2	chemin = new ListeStations (meilleureVoisine,chemin);

---

mais la j'ai :
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space


il tourne en rond c'est ça ?

---

oui le programme ne s'arrête, la mémoire se remplit, jusqu'à ce qu'il n'y en ait plus assez d'allouée pour ton prog (64Mo par défaut)

pourtant si je rajouter meilleurevoisines en tête de chemin , je le code comme cela, non ? :(

donc c'est dans la boucle qu'il y a un hic ?

tu n'aurais pas tout bêtement oublié de décrémenter j ?

??? c'est à dire ;

bon je reprend :

je parcourt les chemins à partir du sommet i

Code:

---

1 2	parcourir(i);

---

si je peux pas aller jusque j, je dis que c'est pas possible

Code:

---

1 2 3

if (station[j].ordreDeVisite == 0) return null;

---

sinon je créer le chemin qui ne contient pour le moment que j

Code:

---

1 2	ListeStations chemin = new ListeStations(station[j], null);

---

et je l'implémente,
si le point d'arriver j , n'est pas égale au point de départ i

Code:

---

1 2	while(station[j]!= station[i])

---

on crée la station meilleurvoisine

Code:

---

1 2	Station meilleureVoisine=null;

---

et la Liste stationvoisines qui contient les voisines de j

Code:

---

1 2	ListeStations stationsvoisines=station[j].voisines;

---

on chercher ensuite la meilleur station

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

while(stationsvoisines!=null){ // cette station a elle un ordre plus petit que celle déjà trouvée ? if (meilleureVoisine==null) { // on en a pas encore trouvé, donc la courant est forcément celle d'ordre le plus petit qu'on ait déjà itérée meilleureVoisine=stationsvoisines.station; } else if ( stationsvoisines.station.ordreDeVisite<meilleureVoisine.ordreDeVisite ) { // la station courante a un ordre de visite plus petit que celle trouvée précédemment, on prend celle là meilleureVoisine=stationsvoisines.station; } stationsvoisines=stationsvoisines.suivant; }

---

et enfin on rajoute le résultat de cette recherche à chemin (mais si la station n'est pas i on revient au premier While.

Code:

---

1 2	chemin = new ListeStations (meilleureVoisine,chemin);

---

donc pourquoi décrémenter j ?, j'ai besoin de le renvoyer dans chemin, je comprend pas...

Citation:

---

Envoyé par bendébutantenprog

??? c'est à dire ;

---

dans un de tes posts précédent ton début de code était :

Code:

---

1 2 3 4

while(station[j]!= station[i]){   chemin.ajouterEnQueue(meilleurvoisine); }

---

ni j ni i ne varient (ni le tableau) donc la boucle est forcément infinie