Tri spécial et vecteurs

Version imprimable

21/11/2007, 16h13
vinzzzz

Tri spécial et vecteurs

Hello,

J'aurai deux petites questions:

1 - Je dispose d'un tableau d'entiers. Je souhaite trier ce tableau en utilisant un algorithme performant (type quick sort). En revanche, je veux en sortie non pas les valeurs elles mêmes triées, mais les indices des valeurs d'entrées dans le tableau trié! La dessus ma question est simple: savez vous si il existe des codes déja implémenté pour ca? La réutilisation de code fait toujours gagner du temps...

2 - Je soutaite créer un vecteur contenant deux types de données. En gros, un tableau de pointeurs, chaque élement du tableau pointant vers une structure A ou une structure B. J'aimerai savoir si, à partir d'une instance de ce type de tableau, il existe un moyens de connaitre le type de l'un de ces pointeurs? Car l'opérateur sizeof renverra toujours la taille du pointeur et ne fait donc pas la différence entre les deux types de données, et j'avoue ne pas avoir d'autre idées. En gros l'éaquivalent de instanceof en JAVA, mais pour le C...

Merci d'avance ;)
21/11/2007, 16h59
Marsiou

1. Si tu veux un algo rapide fais le à la main :D

2.un Vecteur en C???
21/11/2007, 17h06
acx01b

salut

non en C il n'est pas possible de savoir (dynamiquement) vers quel type d'objet pointe un pointeur, à moins que ça ne soit toujours vers le même type d'objet et donc c'est fait à la compilation (statiquement)

par contre rien ne t'empèche d'utiliser le même principe que dans les langages de haut niveau (comme C++ ou Java): un int quelque part en mémoire qui t'indique le type de l'objet

pour ce qui est du tri tu devrais trouver facilement sur google pour le quicksort ou le tri fusion (pour le heap sort tu vas peut-être plus galérer)
21/11/2007, 17h18
vinzzzz

Merci a vous deux.

Pour le vecteur, oui en effet je suis idiot de pas y avoir pensé... Merci de m'avoir éclairé :)

Concernant l'algorithme de tri, le problème n'est pas l'algo lui même, mais le fait que je souhaite récupérer les indices des valeurs d'entrées dans le tableau trié... Mais bon je vais me lancer dans le code, c'est juste que je pensais que ca existait déja, et tant qu'à faire... ;)

Meric en tout cas ;)

Citation:

Envoyé par vinzzzz

Hello,

J'aurai deux petites questions:

1 - Je dispose d'un tableau d'entiers. Je souhaite trier ce tableau en utilisant un algorithme performant (type quick sort). En revanche, je veux en sortie non pas les valeurs elles mêmes triées, mais les indices des valeurs d'entrées dans le tableau trié! La dessus ma question est simple: savez vous si il existe des codes déja implémenté pour ca? La réutilisation de code fait toujours gagner du temps...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct ptoto {
    int *ind ;
    int   num ;
} toto ;

int TABLE[xxx] ;
toto TEMPO[xxx] ;

for ( i = 0 ; i < xxx ; i++ )
  {
       TEMPO[i].ind = &(TABLE[i]) ;
       TEMPO[i].num = i ;
  }

/* La le qsort sur TEMPO */

/* Et la tu recuperes */
fprintf ( stdout, "\nResultat du tri :\n");
for ( i = 0 ; i < xxx ; i++ )
  fprintf ( stdout, "%d : %d",i,TABLE[TEMPO[i].num]] );

Citation:

Envoyé par vinzzzz

Hello,

2 - Je soutaite créer un vecteur contenant deux types de données. En gros, un tableau de pointeurs, chaque élement du tableau pointant vers une structure A ou une structure B. J'aimerai savoir si, à partir d'une instance de ce type de tableau, il existe un moyens de connaitre le type de l'un de ces pointeurs? Car l'opérateur sizeof renverra toujours la taille du pointeur et ne fait donc pas la différence entre les deux types de données, et j'avoue ne pas avoir d'autre idées. En gros l'éaquivalent de instanceof en JAVA, mais pour le C...

Merci d'avance ;)

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
#define TYPE_0 0
#define TYPE_1 1
 
typedef stuct ptoto {
    int type ;
    int ind ;
    double d ;
} toto ;
 
typedef struct ptiti {
    int type ;
    char Text[100] ;
    int    Indic ;
} titi ;
 
typedef struct pany {
    int type ;
} any ;
 
typedef union panystruct {
     any  any ;
     toto to ;
     titi   ti ;
} anystruct ;
 
....
 
anystruct TABLE[10] ;
...
for ( i = 0 ; i < 10 ; i++ )
  {
    TABLE[i].any.type = i % 2 ;
    if ( TABLE[i].any.type == TYPE_0 )
      {
          TABLE[i].to.ind = i ;
          TABLE[i].to.d = i ;
      }
    else
      {
         sprintf ( Table[i].ti.Text, "C'est le %d ieme element",i);
      }
  }
....
 
for ( i = 0 ; i < 10 ; i++ )
   {
      switch (TABLE[i].any.type )
        {
           case TYPE_0 :
               fprintf ( stdout, "la structure est de type 0 : ind=%d d=%g\n",
                           TABLE[i].to.ind,TABLE[i].to.d);
               break ;
 
           case TYPE_1 :
               fprintf ( stdout, "la structure est de type 1 : text=[%s]\n",
                           TABLE[i].ti.Text);
               break ;
        }
   }

ou bien plus simple :

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
#define TYPE_0 0
#define TYPE_1 1
 
typedef stuct ptoto {
    int ind ;
    double d ;
} toto ;
 
typedef struct ptiti {
    char Text[100] ;
    int    Indic ;
} titi ;
 
typedef struct pany {
    int type ;
    void *pt ;
} any ;
 
....
toto[10] ;
titi[10] ;
 
any TABLE[10] ;
...
for ( i = 0 ; i < 10 ; i++ )
  {
      toto[i].ind = i ;
      toto[i].d = i ;
      sprintf ( titi[i].Text, "C'est le %d ieme element",i);
 
      TABLE[i].type = i%2 ;
       if ( TABLE[i].type == TYPE_0 )
           TABLE[i].pt = (void *) &(toto[i]) ;
       else
           TABLE[i].pt = (void *)&(titi[i]);
  }
....
 
for ( i = 0 ; i < 10 ; i++ )
   {
      switch (TABLE[i].type )
        {
           case TYPE_0 :
               fprintf ( stdout, "la structure est de type 0 : ind=%d d=%g\n",
                           ((toto*)TABLE[i].pt)->ind,((toto *)TABLE[i].pt)->d);
               break ;
 
           case TYPE_1 :
               fprintf ( stdout, "la structure est de type 1 : text=[%s]\n",
                           ((titi*)TABLE[i].pt)->Text);
               break ;
        }
   }

salut

j'ai une autre proposition pour les types juste pour dire que ça existe (et que j'aime bien)

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
#include <stdio.h>
 
#define type(t) #t
#define new_typed_thing(t) malloc(sizeof (typed_thing) + sizeof(t))
#define typed_data(x,t) *((t*)x->data)
 
typedef struct {
   char * type;
   void *data[0];
} typed_thing;
 
int main() {
    int i;
    typed_thing *tab[3];
 
    tab[0] = new_typed_thing(int);
    tab[0]->type = type(int);
    typed_data(tab[0],int) = 8;
 
    tab[1] = new_typed_thing(char);
    tab[1]->type = type(char);
    typed_data(tab[1],char) = 122;
 
    tab[2] = new_typed_thing(char*);
    tab[2]->type = type(char*);
    typed_data(tab[2],char*) = "salut";
 
    for (i = 0; i < 3; i++) {
        if (tab[i]->type == type(int)) {
            printf("%d\n",typed_data(tab[i],int));
        }
        else if (tab[i]->type == type(char)) {
            printf("%d\n",typed_data(tab[i],char));
        }
        else if (tab[i]->type == type(char*)) {
            printf("%s\n",typed_data(tab[i],char*));
        }
        else {
            printf("type non reconnu\n");
        }
    }
 
    free(tab[0]);
    free(tab[1]);
    free(tab[2]);
}

21/11/2007, 19h47
vinzzzz

Merci a tous je vais potasser ca! ;)