Bonjour,
j'ai un programme C++ qui effectue un tri rapide sur un tableau.
Petit souci : avec certaines valeurs pour le tableau, une erreur apparait :
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
 
$ ./a.out
Taille du tableau?4
Valeurs du tableau?
T[0]=2
T[1]=1
T[2]=3
T[3]=5
T[0]=2
T[1]=1
T[2]=3
T[3]=5
T[0]=1
T[1]=2
T[2]=3
T[3]=5
*** glibc detected *** ./a.out: free(): invalid next size (fast): 0x0804a008 ***
======= Backtrace: =========
/lib/libc.so.6[0xb7e9c564]
/lib/libc.so.6(cfree+0x90)[0xb7ea0010]
/usr/lib/libstdc++.so.6(_ZdlPv+0x21)[0xb805fa11]
./a.out[0x8048bdb]
/lib/libc.so.6(__libc_start_main+0xe0)[0xb7e47390]
./a.out[0x8048781]
======= Memory map: ========
08048000-08049000 r-xp 00000000 08:04 2804       /home/yugiohjcj/Documents/Textes/Etudes/FLIN402/tp2/a.out
08049000-0804a000 rw-p 00001000 08:04 2804       /home/yugiohjcj/Documents/Textes/Etudes/FLIN402/tp2/a.out
0804a000-0806b000 rw-p 0804a000 00:00 0          [heap]
b7d00000-b7d21000 rw-p b7d00000 00:00 0
b7d21000-b7e00000 ---p b7d21000 00:00 0
b7e30000-b7e31000 rw-p b7e30000 00:00 0
b7e31000-b7f76000 r-xp 00000000 08:02 14420      /lib/libc-2.7.so
b7f76000-b7f77000 ---p 00145000 08:02 14420      /lib/libc-2.7.so
b7f77000-b7f79000 r--p 00145000 08:02 14420      /lib/libc-2.7.so
b7f79000-b7f7a000 rw-p 00147000 08:02 14420      /lib/libc-2.7.so
b7f7a000-b7f7d000 rw-p b7f7a000 00:00 0
b7f7d000-b7f87000 r-xp 00000000 08:02 200        /usr/lib/libgcc_s.so.1
b7f87000-b7f88000 rw-p 00009000 08:02 200        /usr/lib/libgcc_s.so.1
b7f88000-b7fac000 r-xp 00000000 08:02 14424      /lib/libm-2.7.so
b7fac000-b7fad000 r--p 00023000 08:02 14424      /lib/libm-2.7.so
b7fad000-b7fae000 rw-p 00024000 08:02 14424      /lib/libm-2.7.so
b7fae000-b8089000 r-xp 00000000 08:02 3252       /usr/lib/libstdc++.so.6.0.9
b8089000-b808c000 r--p 000da000 08:02 3252       /usr/lib/libstdc++.so.6.0.9
b808c000-b808e000 rw-p 000dd000 08:02 3252       /usr/lib/libstdc++.so.6.0.9
b808e000-b8095000 rw-p b808e000 00:00 0
b80b6000-b80b8000 rw-p b80b6000 00:00 0
b80b8000-b80d4000 r-xp 00000000 08:02 14462      /lib/ld-2.7.so
b80d4000-b80d5000 r--p 0001b000 08:02 14462      /lib/ld-2.7.so
b80d5000-b80d6000 rw-p 0001c000 08:02 14462      /lib/ld-2.7.so
bfdc1000-bfdd6000 rw-p bffeb000 00:00 0          [stack]
ffffe000-fffff000 r-xp 00000000 00:00 0          [vdso]
Abandon
Il me semble, d'après mon expérience, que ce sont des erreurs d'allocation dynamique de mémoire.
Bien sûr mon programme fonctionne dans d'autres cas :
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
 
$ ./a.out
Taille du tableau?4
Valeurs du tableau?
T[0]=9
T[1]=7
T[2]=6
T[3]=4
T[0]=9
T[1]=7
T[2]=6
T[3]=4
T[0]=4
T[1]=6
T[2]=7
T[3]=9
Donc pourriez vous m'expliquer ce phénomène étrange?
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
57
58
59
60
61
 
#include <iostream>
using namespace std;
//Affiche les elements d'un tableau T de taille n
void afficher_tableau(int T[], int n){
	for(int i=0;i<=n;i++){
		cout << "T[" << i << "]=" << T[i] << endl;
	}
}
//Echange les elements d'indice u et v dans un tableau t
void echanger(int u, int v, int t[]){
	int c;
	c=t[u];
	t[u]=t[v];
	t[v]=c;
}
//Partitionne un tableau et renvoi le pivot
int partitionner(int T[], int deb, int fin){
	int pivot = T[deb];
	int ind_pivot=deb;
	for(int i=deb;i<=fin;i++){
		if(T[i] < pivot){ //Si l'element est plus petit que le pivot
			ind_pivot++; //On incremente la position du pivot
			echanger(ind_pivot,i,T); //On echange l'element et le pivot
		}
	}
	echanger(ind_pivot, deb, T);
	return(ind_pivot);
}
//Tri un tableau en utilisant la methode quicksort
void tri_rapide(int T[], int deb, int fin){
	int pivot; //Le pivot
	if(deb<fin){ //Cas d'arret
		pivot=partitionner(T, deb, fin); //Partition du tableau en 2
		tri_rapide(T, deb, pivot-1); //Tri de la 1ere partie
		tri_rapide(T, pivot+1, fin); //Tri de la 2eme partie
	}
}
//Fonction principale
int main(){
	//Creation d'un tableau dynamique
	int* T = new int;
	int n = 0;
	cout << "Taille du tableau?";
	cin >> n;
	cout << "Valeurs du tableau?\n";
	for(int i=0;i<=n-1;i++){
		cout << "T[" << i << "]=";
		cin >> T[i];
	}
	//Affichage du tableau avant le tri
	afficher_tableau(T, n-1);
	//Appel de la fonction de tri
	tri_rapide(T, 0, n-1);
 
	//Affichage du tableau apres le tri
	afficher_tableau(T, n-1);
	//Liberation du tableau
	delete T;
	return(0);
}
Merci.