Probleme fonction tri

Version imprimable

21/02/2008, 13h41
Miko95

Probleme fonction tri

Bonjour,
J'explique mon probleme:
j'ai trois tableaux, un contenant des int,un contenant de float et un contenant des chaines de caracteres( char * ).Le but est de creer une fonction qui permettent de trier ces trois types de tableaux.
Pour cela j'utilise une fonction générale qui utilise le tri a bulle.Cette fonction a pour prototype :

Code:

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

La fonction recoit comme premier argument le pointeur sur la premiere case du tableau(le nom du tableau);le deuxieme est le nombre de case du tableau;le troisieme la taille en octet de chaque case du tableau et le quatrieme c'est un pointeur sur une fonction de comparaison qui recoit deux const void* et qui renvoit un int.
Le probleme est que dans cette fonction, quand je compare deux cases voisines à l'aide de fonctions de comparaisons(que je n'ai pas mentionnées ici,il y en a une pour chaque type) passées en parametre de la fonction qsort,et qui se trouve que le premier élément est plus grand que le suivant alors je dois echanger les deux cases et mon probleme est là :
je dois normalement utiliser une variable temporaire pour l'échange mais je ne sais pas de quel type déclarer cette variable temporaire vu que les éléments comparés peuvent etre soit tout 2 des int, ou des float ou des char*.
Peut etre il y aurait une solution de creer une variable de type void (pas void *) ou sinon une autre solution?
Merci
21/02/2008, 14h09
Davidbrcz

Ca me semble être du C plus que du C++ ton code.
As tu une bonne raison de ne pas utiliser les vectors,std::sort et tout la clique ?

Si tu ne peux aps faire autrement, 2 pistes:
*Une fonction swap par type possible
*Les templates
21/02/2008, 14h12
Miko95

En fait on a pas encore appris les vector ni les templates donc je vais regarder du coté de la fonction swap.
Merci je vous tiens au courant
21/02/2008, 17h03
nikko34

Citation:

Envoyé par Miko95

En fait on a pas encore appris les vector ni les templates donc je vais regarder du coté de la fonction swap.
Merci je vous tiens au courant

ce qu'il faut que tu retiennes c'est que pour l'instant tu apprends le C ( le forum d'en face :) )
La plupart du temps C et le C++ sont très mal expliqués en cours. Ce sont deux langages différents. Le point commun entre les deux est que le C++ intègre le C.

Le problème de commencer l'apprentissage du C++ par sa partie C, c'est qu'on en oublie ce qui en fait un langage à part.
21/02/2008, 18h08
Davidbrcz

HS : Je en comprend pas comment des prof de fac n d'iut ou de bts peuvent enseigner le C++ en commençant par une approche C-like.
21/02/2008, 18h24
Garulfo

Citation:

Envoyé par nikko34

[...]La plupart du temps C et le C++ sont très mal expliqués en cours. [...]

J'espère bien sûr que tu bases cette remarque sur quelques études sérieuses et non sur un avis personnel et la connaissance de ce qui se fait autour de toi ?
21/02/2008, 18h32
nikko34

Citation:

Envoyé par Garulfo

J'espère bien sûr que tu bases cette remarque sur quelques études sérieuses et non sur un avis personnel et la connaissance de ce qui se fait autour de toi ?

ben je sais pas si il y a des études à ce sujet, mais tu serais le premier à me dire que le C++ est bien enseigné.
21/02/2008, 18h47
Namtar

Même si il n'y a aucun rapport avec la discution de départ je vais dire mons avis :P

Pour ma part j'ai commencé par le C puis le C++. Pour les deux langage j'ai eu de bon cour. Des amis a moi dans d'autre IUT non pas eu un bon enseignement, cela est due au faite qu'un prof est plus ou moins compétent.

Par exemple je suis dans un groupe ou certain on appris le C++ en mode Java (donc avec des return(*(new...)) )

Par contre pour d'autre cour on peu pas dire que les profs étaient bon.

Bref en gros pour avoir un exellent enseignement dans un IUT informatique il faut avoir un peu de chance quand même ^^

Mais bon, si on bosse un peu je pense aue l'on s'en sort bien.
22/02/2008, 01h12
Miko95

Bonsoir,
J'ai reflechi pour l'option une fonction swap par type possible, mais le probleme est que je dois appeler cette fonction swap dans la fonction qsort(qui est unique pour les 3 types) donc il faudrait que je trouve un moyen de connaitre quel type de données vont etre triées dans la fonction,j'ai pensé à comparer la valeur de l'argument size pour les 3 types (int, float et char *) et j'ai 4 octets pour les 3 donc je ne peux faire la distinction, finalement je ne trouve pas de solution.
Si quelqu'un a une idee?
Merci
22/02/2008, 09h34
JolyLoic

La manière d'obtenir une généricité en C (puisque visiblement, tu ne connais pas encore les outils C++ qui te permettraient de faire ça) est d'accèder directement à la mémoire puis d'utiliser des memcpy pour copier des blocs de mémoire d'un endroit à l'autre, ce qui revient à bouger les objets.

Attention ! Cette méthode est à déconseiller en C++, car dès que tu auras de vrais objets dans ton tableau (et pas uniquement des nombres ou des pointeurs), elle ne marchera plus, et provoquera en plus des erreurs qui peuvent être subtiles à repérer.
22/02/2008, 10h50
Miko95

Merci pour la réponse c'est bien vu puisque c'est exactement ce qu'on me demande d'utiliser, la fonction memcpy, j'ai son prototype mais je ne sais pas ce qu'elle fait exactement,je sais qu'elle recoits un pointeur destination, un pointeur sur une constante source,et un nombre entier,mais que fait elle exactement?
Merci
22/02/2008, 11h23
Miko95

Finalement je crois que la fonction memcpy est juste la pour déplacer un certains nombre d'octets qu'on lui fournit en argument d'une source vers une destination mais le probleme se pose toujours car quand je veux faire un échange entre les deux cases du tableau, j'ai besoin d'utiliser une variable temporaire dont le type doit etre compatible avec un int,un float et un char* donc je ne vois pas en quoi memcpy serait une solution?
Merci

Je poste quand meme le code complet du programme(la fonction bubblesort n'est pas terminé, c'est la ou j'ai mon probleme) :

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
 
#include <iostream>
using namespace std;
 
const int N=10;
void BubbleSort(void *base,size_t num,size_t size,int (*comparator)(const void *elem1,const void *elem2));
int intCompare(const void* elem1,const void* elem2);
int floatCompare(const void* elem1,const void* elem2);
int strCompare(const void* elem1,const void* elem2);
 
int main()
{
	int a[N],choice;  //a, b et c sont les 3 tableaux de chaque type qui seront triés dans le main
	float b[N],temp_choice;
	char * c[N];
    int (*comparator)(const void *elem1,const void *elem2);//pointeur sur les fonctions de comparaisons
	cout<<"1.Integer Sort"<<endl
		<<"2.Float Sort"<<endl
		<<"3.String Sort"<<endl
		<<"4.Exit"<<endl
		<<"What is your choice? "<<endl;
	cin>>temp_choice;
	while (temp_choice<1 || temp_choice>4 || temp_choice-(int)temp_choice!=0)
	{
		cout<<"Wrong value! Enter again : ";
		cin>>temp_choice;
	}
	choice=(int)temp_choice;
	switch (choice)
	{
	case 1:BubbleSort(a,N,sizeof(int),intCompare);
		break;
	case 2:BubbleSort(b,N,sizeof(float),floatCompare);
		break;
	case 3:BubbleSort(c,N,sizeof(char *),strCompare);
		break;
	case 4:return 0;
		break;
	}
 
return 0;
 
}
    //fonction générale de tri du tableau(de int,float ou char*)
	void BubbleSort(void *base,size_t num,size_t size,int (*comparator)(const void *elem1,const void *elem2))
	{
		for (int i=0;i<num;++i)
			for (int j=0;j<num-i-1;++j)
				if ( (*comparator)(*(base+j*size),*(base+(j+1)*size))==1)
				{
 
 
 
 
 
 
 
	}
	//fonction de comparaison entre deux entiers
	int intCompare(const void* elem1,const void* elem2)
	{
		if (*((int*)elem1)>*((int*)elem2))
			return 1;
		else
		{
			if (*((int*)elem1)<*((int*)elem2))
				return -1;
			else
				return 0;
		}
	}
    //fonction de comparaison entre deux float
	int floatCompare(const void* elem1,const void* elem2)
	{
		if (*((float*)elem1)>*((float*)elem2))
			return 1;
		else
		{
			if (*((float*)elem1)<*((float*)elem2))
				return -1;
			else
				return 0;
		}
	}
	//fonction de comparaison entre deux chaines de caracteres
    int strCompare(const void* elem1,const void* elem2)
	{
		return (strcmp(*((char**)elem1),*((char**)elem2)));
	}

24/02/2008, 12h12
Miko95

Personne n'a de réponses?

Petit aparté : Poster un programme complet a ceci d'intéressant que les lecteurs peuvent le lire sans qu'il y manque quoi que ce soit. Le problème est qu'il y a beaucoup à y lire, et donc que l'on peut pas se concentrer sur les points à problème. Dans ton exemple, la gestion du menu,... ne font que décourager les gens qui n'ont qu'une minute à accorder au post. D'où probablement le manque de réponses à ton post. L'idéal est d'avoir un code à la fois minimal et complet.

A part ça, quel est ton problème ? Tu vas vouloir échanger deux valeurs. La fonction memcpy permet de copier, sans l'analyser de quelque manière que ce soit, de la mémoire d'un emplacement à un autre. Donc, effectivement, pour échanger deux valeurs, il suffit de passer non pas pas une variable (car ce n'est pas ce que manipule memcpy), mais par une zone mémoire intermédiaire.

Un truc style :
Code:

1 2 3 4 5 6 7 8 void exchange(void *elem1, void *elem2, size_t size) { void*buffer = malloc(size); // Alloue la zone de mémoire temporaire memcpy(buffer, elem1, size); memcpy(elem1, elem2, size); memcpy(elem2, buffer, size); free(buffer); }
Maintenant, encore une fois, ce genre de code ne marche pas dans le cas général en C++, aussi il ne correspond pas du tout à la manière qu'on les gens faisant du C++ de coder (d'ailleurs, il y a peut-être des fautes dans mon code, ça fait plusieurs années que je n'ai pas utilisé malloc...). Pour plus d'infos sur la manipulation à la main de la mémoire, le forum C serait sans doutes plus approprié.

Petit détail : Dans tes fonctions de comparaisons, tu utilises des opérateurs > et > sur les types que tu compares. Dans une optique d'extensibilité, utiliser un seul de ces opérateurs pourrait être intéressant.

24/02/2008, 12h34
Miko95

Merci pour la réponse, donc à ce que j'ai compris je n'ai pas besoin d'utiliser de variable temporaires, je dois allouer une zone memoire temporaire dont la taille est fournie en argument de la fonction qsort, mais comme on a appris tout ca en syntaxe du c++, je veux dire qu'on utilise pas malloc mais new donc comment je peux faire une allocation de memoire avec new sans préciser de type mais en précisant la taille à allouer en octets?
Merci

Dans ce cas, écrire plutôt :

Code:

1
2
3
4
5
6
7
8
void exchange(void *elem1, void *elem2, size_t size)
{
  char*buffer = new char[size]; // Alloue la zone de mémoire temporaire
  memcpy(buffer, elem1, size);
  memcpy(elem1, elem2, size);
  memcpy(elem2, buffer, size);
  delete[] buffer;
}

Car char est un type qui a par définition une taille de 1.

24/02/2008, 13h39
Miko95

Merci pour la réponse ca régle le problème mais j'ai une autre question :
est ce que je peux utiliser les opérations(addition particulierement) sur les pointeurs de type void, je pense que non vu qu'on ne connait pas la taille de l'élément pointé.Peut etre il y aurait un moyen de se deplacer connaissant la taille en octet de l'élément pointé?
Merci