Trier une liste chainée

Version imprimable

02/06/2010, 20h33
punisher999

Trier une liste chainée

Bonjours à tous

Je voudrais être en mesure de pouvoir trier une liste chainée.

Comment je pourrais être en mesure d'y arriver ?

Je n'arrive tout simplement pas à permuter 2 éléments entre eux
02/06/2010, 20h48
tchize_

montre ton code de permutation?

Je n'ai pas tenté de permuter parce que je ne sais pas comment m'y prendre en fait.

Ma liste chainée ressemble à ceci.

Est-ce suffisant ?

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
 
public class ListeChainee {
 
	Noeud debut;
	Noeud fin;
	int size = 0;
 
	public ListeChainee() {
	}
 
 
	private void addDebut(Forme o) {
		Noeud nouveau = new Noeud(o);
		nouveau.suivant = debut;
		debut = nouveau;
		size++;
		if (fin == null) {
			fin = debut;
 
		}
	}
 
	private void addFin(Forme o) {
		Noeud nouveau = new Noeud(o);
		if (fin == null) {
			fin = nouveau;
			debut = fin;
		} else {
 
			fin.suivant = nouveau;
			fin = fin.suivant;
		}
		size++;
	}
 
	public void add(int index, Forme o) {
		if (index == 0) {
			addDebut(o);
		} else if (index >= size) {
			addFin(o);
		} else {
			Noeud nouveau = new Noeud(o);
			Noeud preced = debut;
			for (int i = 1; i < index; i++) {
				preced = preced.suivant;
 
			}
			nouveau.suivant = preced.suivant;
			preced.suivant = nouveau;
			size++;
		}
 
	}
 
	public void clear() {
		debut = null;
		fin = null;
		size = 0;
 
	}
 
	public boolean contains(Object o) {
		Noeud courant = debut;
		for (int i = 0; i < size; i++) {
			if (courant.element.equals(o)) {
 
				return true;
			}
			courant = courant.suivant;
 
		}
		return false;
	}
 
 
 
	public Forme get(int index) {
		if (index < 0 || index >= size) {
			return null;
		} else {
			Noeud courant = debut;
			for (int i = 1; i <= index; i++) {
				courant = courant.suivant;
 
			}
			return courant.element;
 
		}
 
	}
 
 
 
 
	public Forme supprimer(int index) {
		 if (index < 0 || index >= size) {
			return null;
		} else {
			Noeud preced = debut;
			for (int i = 1; i < index; i++) {
				preced = preced.suivant;
			}
			Noeud temp = preced.suivant;
			preced.suivant = temp.suivant;
			size--;
			return temp.element;
		}
 
	}
 
 
	public String toString() {
		StringBuffer chaine = new StringBuffer("[");
		Noeud courant = debut;
		for (int i = 0; i < size; i++) {
			if (courant != debut)
				chaine.append(", ");
			chaine.append(courant.element);
			courant = courant.suivant;
		}
 
		chaine.append("]");
		return chaine.toString();
 
	}
 
	private class Noeud {
		Forme element;
		Noeud suivant;
 
		public Noeud(Forme o) {
			element = o;
		}
 
	}
 
}

Bonjour,

Vous pouvez dans un premier temps essayer ceci :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
public void permuter(int indice1, int indice2) {
    Forme forme1 = this.get(indice1);
    Forme forme2 = this.get(indice2);
    this.add(indice2, forme1);
    if (indice2>0)
        this.supprimer(indice2-1);
    else
        this.supprimer(0);
    this.add(indice1, forme2);
    if (indice1>0)
        this.supprimer(indice1-1);
    else
        this.supprimer(0);
}

Par contre, au niveau complexité ... je réfléchis à une solution plus rapide :)

Voilà, je pense que ceci pourrait être pas mal :

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
public void permuter(unsigned int indice1, unsigned int indice2) throws Exception{
	if (indice1 != indice2) {
		if (indice1 > size || indice2 > size) {
			throw Exception("Les indices ne sont pas corrects");
		}
		int indiceCourant, indiceInferieur, indiceSuperieur;
		Noeud noeudTemporaire, noeudInferieur, noeudSuperieur;
		noeudTemporaire = debut;
		noeudInferieur = null;
		noeudSuperieur = null;
		if (indice1 < indice2) {
			indiceInferieur = indice1;
			indiceSuperieur = indice2;
		} else {
			indiceInferieur = indice2;
			indiceSuperieur = indice1;	
		}
		indiceCourant = 0;
		while (indiceCourant++ < indiceInferieur) {
			noeudTemporaire = noeudTemporaire.suivant;
		}
		noeudInferieur = noeudTemporaire;
		while (indiceCourant++ < indiceSuperieur) {
			noeudTemporaire = noeudTemporaire.suivant;
		}
		noeudSuperieur = noeudTemporaire;
		noeudTemporaire = noeudSuperieur.suivant;
		noeudSuperieur.suivant = noeudInferieur.suivant;
		noeudInferieur.suivant = noeudTemporaire;
		noeudTemporaire = noeudSuperieur.precedent;
		noeudSuperieur.precedent = noeudInferieur.precedent;
		noeudInferieur.noeudTemporaire;
	}
}

Qu'en pensez-vous ?

02/06/2010, 21h33
punisher999

Je ne crois pas utilisé ceci. Merci quand même. C'est un peu trop compliquer à mon goût.
03/06/2010, 00h53
punisher999

La première solution ne fonctionnais pas.

En fait, si je met l'indice 0 et l'indice 1 en paramètre.

Exemple :

0
1
2
3

Elle va changé pour

1
1
2
3

En utilisant tes fonctions, tu peux faire :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
public void permuter(int indice1, int indice2) {
    int indice_min = Math.min(indice1, indice2);
    int indice_max = Math.max(indice1, indice2);
 
    Forme forme_min = this.get(indice_min);
    Forme forme_max = this.get(indice_max);
 
    this.supprimer(indice_min);
    this.supprimer(indice_max);
    this.add(indice_min, forme_min);
    this.add(indice_max, forme_max);
}

12/06/2011, 13h07
hanniballectter

help supprimer les doublons d'une liste chaine generique en java

salut tout le monde ,
je veux coder un programme en java qui implementer une liste chainee generique et de supprimer les doublons dans cette listes.
Merci a l'avance .
12/06/2011, 13h13
tchize_

un peux comme ce que fait déjà LinkedHashSet?