Discussion :

[bendébutantenprog]

c'est bien cela

ç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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
ListeStation stationsvoisines=stationcourant.voisines

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
while(stationsvoisines!=null){

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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".

[bendébutantenprog]

voici le début de mon prog:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[joel.drigo]

c'est bien cela

ç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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

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 )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
stationsvoisines=stationsvoisines.suivant;

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

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

vas-y

[joel.drigo]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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]

[bendébutantenprog]

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

par contre tous ne ce compile pas ;

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
meilleureVoisine=stationsvoisines;

une listestations != Station

je l'ai donc modifier en

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
meilleureVoisine=stationsvoisines.station;

ça te semble bon ?

idem pour

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
( stationsvoisines.ordrevisite<meilleureVoisine.ordrevisite )

la je vois pas....

[joel.drigo]

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

pour

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if ( stationsvoisines.ordrevisite<meilleureVoisine.ordrevisite )

c'est simple ! c'est pareil !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[bendébutantenprog]

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

ce n'est pas

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

mais

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

voila pourquoi Eclipse voyais rouge

dernier détail je pense :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
	chemin.ajouterEnQueue( meilleureVoisine);

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

[joel.drigo]

dernier détail je pense :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[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...

donc j'ai mis

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
chemin.ajouterEnQueue( meilleureVoisine);

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

[joel.drigo]

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 ?

donc j'ai mis

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
chemin.ajouterEnQueue( meilleureVoisine);

Mais notre ami Eclipse me note Create method ajouterEnQueue(station) in type Listestations.
euh 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

[joel.drigo]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

chemin.ajouterEnTete(stationvoisines)

fait

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

chemin=new ListeStation(stationvoisines, chemin);

[bendébutantenprog]

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.

[Javamar]

salut bendébutantenprog!

est-ce que tu pourrais mettre ton exercice?

mets aussi ta classe Station

[bendébutantenprog]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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);
 
 
		}
}

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[joel.drigo]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

[bendébutantenprog]

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 ?

[joel.drigo]

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

[bendébutantenprog]

??? c'est à dire ;

bon je reprend :

je parcourt les chemins à partir du sommet i

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
parcourir(i);

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

on crée la station meilleurvoisine

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
Station meilleureVoisine=null;

et la Liste stationvoisines qui contient les voisines de j

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

on chercher ensuite la meilleur station

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

[joel.drigo]

??? c'est à dire ;

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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