Tri spécial et vecteurs

**vinzzzz** · 21/11/2007, 15h13

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

**Marsiou** · 21/11/2007, 15h59

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

2.un Vecteur en C???

**acx01b** · 21/11/2007, 16h06

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)

**vinzzzz** · 21/11/2007, 16h18

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

**souviron34** · 21/11/2007, 16h46

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 :

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
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]] );

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 :

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
#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 :

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
#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 ;
        }
   }

**acx01b** · 21/11/2007, 17h48

salut

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

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
#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]);
}

**vinzzzz** · 21/11/2007, 18h47

Merci a tous je vais potasser ca!

Tri spécial et vecteurs

C

Discussions similaires

Partager

Partager