Problème de max dans liste chainée

Version imprimable

Bonjour a tous,

j'ai un soucis dans ma fonction maximum. Le prof nous a imposé de la faire de façon récursive. Quand je compile, j'ai seulement les deux premiers qui sont bien passé dans ma condition mais je n'arrive pas a accéder à la cellule suivante. J'ai du mal sur les fonctions récursive. :( Est-ce que quelqu'un pourrait m'aider à y voir plus clair.

voici mon code :

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
 
 
public class Cellule {
	int valeur;
	Cellule suivant;
 
	Cellule(int pvaleur) {
		valeur = pvaleur;
		suivant = null;
	}
 
}
 
import java.util.Random;
 
public class ListeChainee {
	Cellule tete;
 
	ListeChainee() {
		tete = null;
	}
 
	public void Afficher() {
		Cellule c = tete;
		while (c != null) {
			System.out.print(c.valeur + " ");
			c = c.suivant;
		}
	}
 
	public void Ajouter(int valeur) {
		Cellule nc = new Cellule(valeur);
 
		nc.suivant = tete;
		tete = nc;
	}
 
	public void Init(int n) {
		Random rand = new Random();
		for (int i = 0; i < n; i++) {
			this.Ajouter(rand.nextInt(1000));
 
 
		}
	}
 
	public int Minimum() {
		int valMin = 10000;
		Cellule c = tete;
		while (c != null) {
 
			if (c.valeur < valMin) { 										
				valMin = c.valeur;
 
			}
			c = c.suivant;
		}
 
		System.out.print(" la valeur minimum est : " + valMin);
 
		return valMin;
	}
 
	static int Maximum(Cellule c) {
		int max = c.valeur;
		if (c != null) {
			if (c.valeur < c.suivant.valeur) {
				max = c.suivant.valeur;
				max = ListeChainee.Maximum(c.suivant);
			}
		}
		return max;
	}
 
	void Supprimer(int n) {
		ListeChainee l = new ListeChainee();
		Cellule c = tete;
		while (c != null) {
			if (c.valeur != n) {
 
				l.Ajouter(c.valeur);
			}
			c = c.suivant;// on passe à la cellule suivante
		}
 
		System.out.println(" La nouvelle liste est : ");
 
		l.Afficher();
 
	}
}
import java.util.Scanner;
 
 
public class test {
 
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print(" Début liste chainée : ");
	ListeChainee l1 = new ListeChainee();
	l1.Init(10);
	l1.Afficher();
	l1.Minimum();
	Cellule c2=new Cellule (0);
	c2. suivant=l1.tete;
	l1.tete = c2;
	 System.out.println(" le chiffre maximum de la liste est : " + 
	ListeChainee.Maximum(c2)); 
       System.out.print(" Deuxième liste chainée : ");
	ListeChainee l2 = new ListeChainee ();
	for (int i = 0; i < 10; i++) {
		l2.Ajouter(i);
	}
	l2.Afficher();
	l2.Supprimer(2);
	}
 
}

salut
voici le code de maximum:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int Maximum(Cellule c) {
		int max = c.valeur;
		while (c != null) {
			 
			if (c.valeur > max) { 										
				max = c.valeur;
 
			}
			c = c.suivant;
		}
 
		System.out.print(" la valeur Maximun est : " + max);
 
		return max;
	}

Eric

19/11/2014, 14h27
chikita

merci mais la méthode doit impérativement être récursive

Salut,

En gros, le max d'une liste, c'est le max entre le premier et le max du reste de la liste, et comme le max du reste de la liste, c'est le max entre premier du reste de la liste, et le max entre ce qu'il y ensuite... etc...

Pour l'écrire de façon récursive, il suffit de prendre pour forme générale :

Code:

1
2
3
max( cellule ) 
si suivante de cellule existe ,  return la cellule avec la plus grande valeur entre cellule et max ( de sa suivante )
sinon return cellule

autrement dit, en Java, par exemple :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public Cellule max(Cellule cellule) {
   if ( cellule.suivante!=null ) {
 
      Cellule celluleMax = max( cellule.suivante );
 
      if( celluleMax.value>cellule.value ) {
         return celluleMax;
      }
      else {
         return cellule;
      }
 
   }
   else {
       return cellule;
   }
}

qu'on peut simplifier en (en perdant un peu de sémantique) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
public Cellule max(Cellule cellule) {
   if ( cellule.suivante!=null ) {
 
      Cellule celluleMax = max( cellule.suivante );
 
      if( celluleMax.value>cellule.value ) {
         return celluleMax;
      }
 
   }
   return cellule;
}

ou encore:

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
 
public static int maximumRecursive(Cellule c, Integer max, boolean debut) {
 
		if(c != null)
		{
		  if(debut) 
		  {
			  max = c.valeur;
			 return maximumRecursive(c, max, false);
		  }
		  else
		  {
			  if(c.suivant != null)
			  {
				  if (c.suivant.valeur > max) { 										
						max = c.suivant.valeur;
					}
				  return maximumRecursive(c.suivant, max, false);  
			  }
			  else
				  return max;
		  }
 
		}
		else
		{
		return max;
		}
	}

et dans la main:

Code:

1
2
 
max =  ListeChainee.maximumRecursive(c2, -1, true);

19/11/2014, 15h18
thelvin

Ouaip enfin le principe du récursif, au départ, c'est qu'on n'a pas besoin de tous ces paramètres.
Coller au plus proche de la définition récursive mathématique.
19/11/2014, 15h30
jeffray03

Oui je comprend.

Eric

j'ai réussi

a force de chercher on trouve. mon code fonctionne :mouarf:et je vous remercie de tout vos conseil

Voici le code final

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
 
static  int Maximum(Cellule c) {
		Cellule c1 = c ;
		int max = c.valeur;
		if (c.suivant != null)  {
 
			 if (c.valeur < c.suivant.valeur){
			 max = c.suivant.valeur;
 
		 c1.valeur = max;
 
 
			 }
				c1.suivant = c.suivant.suivant;
			  max = ListeChainee.Maximum(c1);
 
		}
 
		return max;
 
	}

19/11/2014, 18h55
joel.drigo

Il doit y avoir quelque chose que je n'ai pas compris dans ton énoncé : parce qu'une fonction maximum() sur une liste n'est pas normalement censé modifier des éléments de la liste. Je pensais que le but était d'obtenir la cellule dont la valeur était la plus grande.
19/11/2014, 19h16
tchize_

Je ne comprends même pas pourquoi la méthode est statique plutot que de travailler sur la cellule courante :/

En général, quand tu crée dans une classe X une méthode statique qui prend en paramètre la classe X c'est que cette méthode n'a pas a être statique.