Discussion :

[Jayceblaster]

Bonjour à tous....
Je debute en C...Et je dois effectuer un tri alpha numérique sur un tableau de caractere tres grand....
Pouvez vous m'aiguiller sur un algorithm simple (à la relecture du code) et ne demandant pas trop de temps...

Merci d'avance à vous.

[souviron34]

man qsort ..

[yakamoneye]

Pour les algorithmes de tri va voir ici

[gastoon]

il y a le tri rapide (quick sort)
le tri par insertion
le tri par selection
le tri sequenciel
le tri par permutation

il suufit de voir sur google, il ya des algorithmes tout fait pour ça

[diogene]

Tu trouveras des exemples de code sur DVP ici

[Jayceblaster]

Bonjour;
En faite je souhaite trier un tableau de tableau de char avec Qsort...voici mon code:

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
 
static int compare (void const *a, void const *b)
{
   /* definir des pointeurs type's et initialise's
      avec les parametres */
   char const *const *pa = a;
   char const *const *pb = b;
 
   /* evaluer et retourner l'etat de l'evaluation (tri croissant) */
   return strcmp (*pa, *pb);
}
 
int main (void)
{
/* tableau a trier (tableau de pointeurs sur char const) */
   t_MonTab tab[100];    /*mon tableau est initialisé plus haut dans une boucle for*/
   /*t_MonTab et un type déclarer en char [12]*/
   /*j'ai donc un tableau de 100 chaine de caractere (chaque chaine pouvant faire 12  
   caractere*/
 
   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare);
 
/* affichage du tableau apres le tri */
   aff (tab, sizeof tab / sizeof *tab);
 
   return 0;
}

A la compile ca passe tres bien mais à l'exécution ca plante sur la ligne Qsort...en fait en regardans bien l'aide http://emmanuel-delahaye.developpez.com/qsort.htm
il déclare:

Code :

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

1
2
 
char const *tab[] = { "world", "hello", "wild" };

mais moi je ne peut pas faire

Code :

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

1
2
 
t_MonTab *tab[100];

Ca plante à la compile ...
help please

[nicodn02]

Donne nous le code en entier s'il te plait
que l'on puisse compiler

[Jayceblaster]

j'ai trouvé en fait il faut déclarer un *tab et faire un malloc....
C'etait pas tres dure...enfin je code le source final des que j'ai debugger

[Jayceblaster]

Donc comme promis voici mon source:

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
62
63
64
65
66
 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct
{
        char c[12];
} T_type;
 
 
 
/* fonction utilisateur de comparaison fournie a qsort() */
static int compare (void const *a, void const *b)
{
   /* definir des pointeurs type's et initialise's
      avec les parametres */
   char const *const *pa = a;
   char const *const *pb = b;
 
   /* evaluer et retourner l'etat de l'evaluation (tri croissant) */
   return strcmp (*pa, *pb);
}
 
 
/* affichage du tableau */
static void aff (char const **a, size_t n)
{
   size_t i;
   for (i = 0; i < n; i++)
   {
      printf ("%s\n", a[i]);
   }
   printf ("\n");
}
 
 
int main(int argc, char *argv[])
{
 
  /* tableau a trier (tableau de pointeurs sur char const) */
   //char const *tab[] = { "100", "300", "200" };
 
   int *p = malloc(10*sizeof(int));
   T_type const *tab[4];
   *tab = malloc(4*sizeof(T_type));
 
   strcpy(tab[0], "c");
   strcpy(tab[1], "b");
   strcpy(tab[2], "a");
 
/* affichage du tableau dans l'etat */
   aff (tab, sizeof tab / sizeof *tab);
 
   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare);
 
/* affichage du tableau apres le tri */
   aff (tab, sizeof tab / sizeof *tab);
 
 
 
  system("PAUSE");	
 
 
 
  return 0;
}

en fait ca compile ca m'affiche dans la console:

Code :

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

1
2
3
4
 
c
b
a

et non

Code :

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

1
2
3
4
 
a
b
c

et en plus j'ai une erreur d'execution: "la memoire ne peut etre read...
Quelqu'un peut m'aider?

[Jayceblaster]

j'ai trouvé la taille du tableau n'est pas bonne ce n'est pas 4 mais 3

[orfix]

Salut,

j'ai trouvé la taille du tableau n'est pas bonne ce n'est pas 4 mais 3

-Avant que j'oublie il faut inclure "string.h" !
-Le prototype de ta fonction 'aff' ne correspond pas aux appels que tu fais depuis ton main le premier paramètre doit être de type 'T_type' et non 'char' ...
-L'allocation du tableau n'est pas jolie jolie ...voici une façon de faire :

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
 
   T_type *tab[4];
   size_t i;
   for( i=0;i<4;i++ )
   {
   		tab[i] = malloc(sizeof *tab[i] );
		if( tab[i]==NULL )
		{	/* Erreur d'allocation on libere tout ...*/
			do
			{
				free( tab[i] );
				tab[i]=NULL;
				i--;
			}while(i>=0);
		}
   }

-La fonction compare n'est pas bonne non plus il ne faut pas oublier que tu as encapsulé ta chaine de caracteres dans une structure !

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
static int compare (void const *a, void const *b)
{
   /* definir des pointeurs type's et initialise's
      avec les parametres */
   T_type const *const *pa = a;
   T_type const *const *pb = b;
 
   /* evaluer et retourner l'etat de l'evaluation (tri croissant) */
   return strcmp ((*pa)->c, (*pb)->c);
}

@++

[souviron34]

-L'allocation du tableau n'est pas jolie jolie ...voici une façon de faire :

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
 
   T_type *tab[4];
   size_t i;
   for( i=0;i<4;i++ )
   {
   		tab[i] = malloc(sizeof *tab[i] );
		if( tab[i]==NULL )
		{	/* Erreur d'allocation on libere tout ...*/
			do
			{
				free( tab[i] );
				tab[i]=NULL;
				i--;
			}while(i>=0);
		}
   }

ta libération non plus

Code :

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

1
2
3
4
5
6
7
8
9
10
11
		if( tab[i]==NULL )
		{	/* Erreur d'allocation on libere tout ...*/
                        i-- ;
			do
			{
				free( tab[i] );
				tab[i]=NULL;
				i--;
			}while(i>=0);
		}

[Jayceblaster]

merci pour votre aide...je n'y comprend vraiment pas grand chose en C....
avec mon code y a un probleme quand je dimensionne la taille de mon tableau à 3 ca marche mais lorsque je le dimensionne à 4 ca plante à l'execution:

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
 
int main(int argc, char *argv[])
{
 
  /* tableau a trier (tableau de pointeurs sur char const) */
 
   int *p = malloc(10*sizeof(int));
   T_type const *tab[3];
   *tab = malloc(3*sizeof(T_type));
 
   strcpy(tab[0], "c");
   strcpy(tab[1], "b");
   strcpy(tab[2], "a");
 
/* affichage du tableau dans l'etat */
   aff (tab, sizeof tab / sizeof *tab);
 
   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare);
 
/* affichage du tableau apres le tri */
   aff (tab, sizeof tab / sizeof *tab);
 
 
 
  system("PAUSE");	
 
 
 
  return 0;
}

ca ca marche
par contre ca ca ne marche plus...

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
 
int main(int argc, char *argv[])
{
 
  /* tableau a trier (tableau de pointeurs sur char const) */
 
   int *p = malloc(10*sizeof(int));
   T_type const *tab[4];
   *tab = malloc(4*sizeof(T_type));
 
   strcpy(tab[0], "c");
   strcpy(tab[1], "b");
   strcpy(tab[2], "a");
   strcpy(tab[3], "a");
 
/* affichage du tableau dans l'etat */
   aff (tab, sizeof tab / sizeof *tab);
 
   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare);
 
/* affichage du tableau apres le tri */
   aff (tab, sizeof tab / sizeof *tab);
 
 
 
  system("PAUSE");	
 
 
 
  return 0;
}

quelqu'un peut il m'expliquer?

[orfix]

ta libération non plus

mmmmmOui mais bon, un free( NULL ) n'a jamais fait de mal à personne :

Code §7.20.3.2 :

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

1
2
3
4
The free function causes the space pointed to by ptr to be deallocated, that
 is, made available for further allocation. If ptr is a null pointer, no action 
occurs ...

P.S : avec votre correction si cela foire à la première allocation (i=0), on risque de faire un i-- (i=-1 ) puis le free qui viens après ça va pas être jolie jolie non plus :p

quelqu'un peut il m'expliquer?

Je n'avais pas remarqué mais les strcpy sont incorrect :

Code :

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

1
2
3
4
   strcpy(tab[0]->c, "c");
   strcpy(tab[1]->c, "b");
   strcpy(tab[2]->c, "a");

Je rappelle que ta chaine est encapsulée dans une structure...


Bonne chance !

[Jayceblaster]

mais ca ne marche toujours pas avec:

Code :

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

1
2
3
4
 
   strcpy(tab[0]->c, "c");
   strcpy(tab[1]->c, "b");
   strcpy(tab[2]->c, "a");

a partir de 4 elements ca plante ...

[souviron34]

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
 
int main(int argc, char *argv[])
{
 
  /* tableau a trier (tableau de pointeurs sur char const) */
 
   int *p = malloc(10*sizeof(int));
   T_type const *tab[3];
   *tab = malloc(3*sizeof(T_type));
 
   strcpy(tab[0], "c");
   strcpy(tab[1], "b");
   strcpy(tab[2], "a");
 
/* affichage du tableau dans l'etat */
   aff (tab, sizeof tab / sizeof *tab);
 
   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare);
 
/* affichage du tableau apres le tri */
   aff (tab, sizeof tab / sizeof *tab);
 
 
 
  system("PAUSE");	
 
 
 
  return 0;
}

..
quelqu'un peut il m'expliquer?

Oui..

Tu mélanges pointeurs , tableaux, chaines, etc etc...

ça ça marcheras :

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
 
int main(int argc, char *argv[])
{
 
  /* tableau a trier (tableau de pointeurs sur char const) */
 
   int *p = malloc(10*sizeof(int));
   T_type  *tab=NULL;
   tab = malloc(3*sizeof(T_type));
   if ( tab == NULL || p ==NULL )
     {
        if ( tab != NULL )
           free(tab);
        else
             free(p);
 
       fprintf (stderr, "\nErreur memoire");
       exit(1);
     }  
 
   strcpy(tab[0].c, "c");
   strcpy(tab[1].c, "b");
   strcpy(tab[2].c, "a");
 
/* affichage du tableau dans l'etat */
   aff (tab, sizeof tab / sizeof *tab);
 
   qsort (tab, sizeof tab / sizeof *tab, sizeof *tab, compare);
 
/* affichage du tableau apres le tri */
   aff (tab, sizeof tab / sizeof *tab);
 
 
 
  system("PAUSE");	
 
  free(p), p = NULL ;
  free(tab), tab=NULL ;
 
  return 0;
}

avec

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
 static int compare (void const *a, void const *b)
{
   /* definir des pointeurs type's et initialise's
      avec les parametres */
   T_type *pa = (T_type *)a;
   T_type *pb = (T_type *)b;
 
   /* evaluer et retourner l'etat de l'evaluation (tri croissant) */
   return strcmp (pa->c, pb->c);
}

mmmmmOui mais bon, un free( NULL ) n'a jamais fait de mal à personne :

Code §7.20.3.2 :

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

1
2
3
4
The free function causes the space pointed to by ptr to be deallocated, that
 is, made available for further allocation. If ptr is a null pointer, no action 
occurs ...

vrai en C99, pas en C90. Et C99 n'est pas implanté partout..

P.S : avec votre correction si cela foire à la première allocation (i=0), on risque de faire un i-- (i=-1 ) puis le free qui viens après ça va pas être jolie jolie non plus :p

Eh non...

Il y a un do .. whle i >= 0

Donc si on est à i = 0, on fait bien i-1, et le do ne se fait pas...
(enfin, je pense, je fais toujours plutôt à l'envers while (i >= 0), sans le do..)

[Médinoc]

Code :

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

1
2
3
4
5
6
7
8
9
10
static int compare (void const *a, void const *b)
{
   /* definir des pointeurs type's et initialise's
      avec les parametres */
   T_type *pa = (T_type *)a;
   T_type *pb = (T_type *)b;
 
   /* evaluer et retourner l'etat de l'evaluation (tri croissant) */
   return strcmp (pa->c, pb->c);
}

Pourquoi ces horribles casts explicites qui suppriment l'attribut const ?

Code C corrigé :

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

1
2
3
4
5
6
7
8
9
10
 static int compare (void const *a, void const *b)
{
   /* definir des pointeurs type's et initialise's
      avec les parametres */
   T_type const *pa = a;
   T_type const *pb = b;
 
   /* evaluer et retourner l'etat de l'evaluation (tri croissant) */
   return strcmp (pa->c, pb->c);
}

vrai en C99, pas en C90. Et C99 n'est pas implanté partout..

Il me semble avoir lu sur ce même forum que la neutralité de free(NULL) était garantie depuis C89...

[souviron34]

Il me semble avoir lu sur ce même forum que la neutralité de free(NULL) était garantie depuis C89...

Peut-être, mais comme je l'ai dit, mon expérience des SunOS, HPUX, et autres Solaris ou RedHat Linux des années 90/2000 me prouve le contraire

[Médinoc]

Mais dans ce cas, ce n'est pas un problème de C99, mais un problème d'implémentation de standards bien plus vieux...

[Jayceblaster]

ca ne marche toujours pas pourtant j'ai repris le code texto