Discussion :

[hbx360]

Bonjour j'aimerais savoir quand on tri (avec le tri par tas par exemple) des structs comment ça se passe doit-on passer par des pointeurs ou par un tableau de struct ?

Comment on doit faire pour les échanges entre struct ?

Exemple si j'ai une struct de se style :

Code :

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

1
2
3
4
5
6
struct personne
{
char *nom;
char *prenom;
int age;
};

Imaginons que 10 personnes doivent rentrés leurs nom, prénom, âge ; tout d'abord dois-je déclarer un tableau de struct et donc faire :
personne Pers[10] ou bien faire : un tableau de 10 pointeurs pointant chacun sur une struct Personne comme ceci ?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
typedef struct _personne
{
char *nom;
char *prenom;
int age;
}personne;
 
personne **Pers=malloc(10*sizeof*Pers); 
 
for(i=0;i<10;i++)
  tab[i]=malloc(sizeof**tab);

Ensuite si je dois trié les struct par ordre alphabétique des noms comment fait-on ?
Pour le tableau Pers[10] je pense qu'il faudra faire l'échange nom avec nom, prénom avec prénom, âge avec âge ? Comme ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
tmp=tab[0]->nom;
tab[0]->nom=tab[1]->nom;
tab[1]->nom=tmp;
 
tmp=tab[0]->prénom;
tab[0]->prénom=tab[1]->prénom;
tab[1]->prénom=tmp;
 
tmp=tab[0]->age;
tab[0]->age=tab[1]->age;
tab[1]->age=tmp;

Méthode que je trouve lourding.

En ce qui concerne le tableau de pointeur de struct ;
Quand le programme aura trouvé deux noms à échangés est-ce qu'il faudra faire l'échange de tous les noms prénoms et âge (comme vu si dessus) ou bien faudra t-il juste échanger les pointeurs?

Je sais pas si j'ai été clair, merci par avance pour votre aide.

[Sve@r]

Imaginons que 10 personnes doivent rentrer leurs nom, prénom, âge ; tout d'abord dois-je déclarer un tableau de struct et donc faire :
personne Pers[10] ou bien faire : un tableau de 10 pointeurs pointant chacun sur une struct Personne comme ceci ?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
typedef struct _personne
{
char *nom;
char *prenom;
int age;
}personne;
 
personne **Pers=malloc(10*sizeof*Pers); 
 
for(i=0;i<10;i++)
  tab[i]=malloc(sizeof**tab);

Bonjour

Il n'y a aucune différence entre un tableau de 10 structures ou une zone allouée de 10 fois la taille d'une structure. Sauf que généralement on réserve l'allocation dynamique aux codes dans lesquels on ne connait pas la taille du tableau au moment où on l'écrit. C'est à dire que c'est plus facile de déclarer un tableau de 10 items plutôt que d'allouer dynamiquement un tableau de 10 items. Ne serait-ce que par la gestion que tu dois faire en cas d'allocation échouée...

Ensuite si je dois trier les struct par ordre alphabétique des noms comment fait-on ?
Pour le tableau Pers[10] je pense qu'il faudra faire l'échange nom avec nom, prénom avec prénom, âge avec âge ? Comme ceci :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
tmp=tab[0]->nom;
tab[0]->nom=tab[1]->nom;
tab[1]->nom=tmp;
 
tmp=tab[0]->prénom;
tab[0]->prénom=tab[1]->prénom;
tab[1]->prénom=tmp;
 
tmp=tab[0]->age;
tab[0]->age=tab[1]->age;
tab[1]->age=tmp;

Méthode que je trouve lourdingue.

Exact, lourdingue. Surtout que tu utilises la même variable tmp pour manipuler successivement un pointeur et un int...
C'est pourquoi il existe memcpy() destiné à copier l'intégralité d'une zone mémoire et qui te permet donc de swapper directement l'intégralité de tes 2 structures...

Code c :

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

1
2
3
memcpy(&tmp, &tab[0], sizeof(personne);
memcpy(&tab[0], &tab[1], sizeof(personne);
memcpy(&tab[1], &tmp, sizeof(personne);

En ce qui concerne le tableau de pointeur de struct ;
Quand le programme aura trouvé deux noms à échanger est-ce qu'il faudra faire l'échange de tous les noms prénoms et âge (comme vu ci dessus) ou bien faudra t-il juste échanger les pointeurs?

Les deux solutions fonctionnent. Soit swapper les structures, soit swapper les pointeurs. Bien entendu le swap des pointeurs (déplacement de 4 octets) est bien plus rapide que le swap des structures (déplacement de la taille de la structure) mais nécessite une indirection supplémentaire...

j'aimerais savoir quand on trie (avec le tri par tas par exemple)

Généralement (c'est à dire sauf exercices d'école) on ne trie jamais soi-même. En effet, il existe une fonction qsort déjà implémentée permettant de trier absolument n'importe quoi. Tout ce qu'on a à lui fournir c'est l'adresse du départ du tableau à trier (évident), le nombre d'éléments (évident là aussi), la taille d'un élément (pour que la fonction puisse swapper ce qui évite de se casser le noeud avec des trucs "lourdingues") et une fonction (à écrire soi-même) permettant de comparer deux éléments (parce que ça, la fonction ne peut pas le deviner). Et une fois tout-ça bien défini, on l'appelle et hip hop, le tableau est trié.

PS: Merci de surveiller ton orthographe. Ce n'est pas parce qu'on est dans un forum informatique que ce doit-être oublié. L'orthographe ce n'est pas qu'un truc qu'on apprend à l'école et qui doit être oublié juste après mais un moyen de traduire fidèlement sa pensée et de se faire comprendre des autres. "à essayer" et "a essayé" se prononcent de la même façon mais signifient deux choses totalement différentes et seule leur orthographe permet de choisir l'une ou l'autre signification. Et c'est aussi une marque de politesse que d'écrire correctement pour éviter au lecteur de lagguer à relire 10 fois un paragraphe où le sens des mots va en contradiction avec le sens général de la phrase.

[fearyourself]

Si c'est clair

Mais en fait, ton souci est que la solution dépend comme tu le vois de ta structure de données.

A) Si tu as un tableau de structures sans pointeurs internes, tu vas devoir faire des copies de structures.
B) Si tu as un tableau de structures avec pointeurs internes, tu peux faire un échange de pointeurs comme tu as fait (ou remarquer que c'est aussi une copie de structure donc de nouveau (A) mais plus rapide vu que c'est plus petit)
C) Si tu as un tableau de pointeurs vers une structure, tu peux faire un échange des pointeurs directement et donc le plus rapide

Maintenant comment choisir entre A-B-C? Et bien cela dépend du programme:

1) Ton programme fait beaucoup de tris mais pas beaucoup de lectures -> (C)
2) Ton programme fait beaucoup de lectures mais très peu de tris -> (A)
3) C'est entre les deux? -> (B)

Ensuite, pour vraiment être sûr:
- Tu implémentes les 3, tu fais des tests, tu tires tes conclusions

[Matt_Houston]

Nul besoin de passer sur tous les champs ou de faire un memcpy explicite pour un simple swap de valeur, en C un objet de type struct se copie par simple affectation :

Code :

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

1
2
3
const struct foo tmp = a;
a = b;
b = tmp;

Pour répondre au problème originel, tout dépend comme d'habitude du contexte. Si tu as 20 objets de 32 octets tu te fous royalement aussi bien de la structure de données que de l'algorithme de tri et tu vas au plus simple. Si tu en as 20000 de 32 kilooctets, c'est autre chose.

Quelle que soit la méthode de stockage choisie, il faudra toutefois se prévaloir d'une bonne raison pour ne pas utiliser qsort pour le tri effectif.

[Pyramidev]

@hbx360 :

• Pour trier un tableau de _personne :
  Dans le cas de ta structure _personne, tu peux utiliser directement qsort.
  Comme ça, tu auras juste à lui passer une fonction de comparaison.
  Appel :
  

  Code :

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

  qsort(tableau, nbElements, sizeof(_personne), fonction_de_comparaison)

• Pour trier un tableau de pointeurs (par exemple des pointeurs vers des _personne) :
  Pareil, tu peux utiliser directement qsort et tu auras juste à lui passer une fonction de comparaison.
  Appel :
  

  Code :

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

  qsort(tableau, nbElements, sizeof(_personne*), fonction_de_comparaison)

• Pour le code de la fonction de comparaison, je te laisse lire la doc de qsort.
• Choix entre trier un tableau de _personne et un tableau de pointeurs vers _personne :
  Si tu as besoin que les pointeurs vers tes objets _personne restent valides après un tri, il faut utiliser un tableau de pointeurs.
  Sinon, suis le conseil de fearyourself.

Edit 1 : Doublé par Matt_Houston pour la mention de qsort.
Edit 2 (23h10) : J'aurais dû lire en entier le message de Sve@r. Je n'avais pas remarqué qu'il avait déjà mentionné qsort lui aussi.

[hbx360]

Merci beaucoup à tous pour vos réponses très instructives je pense avoir la réponse aux questions que je me posai (je me posai : imparfait (je me posais) ou passé simple (je me posai) ?).

@Sve@r je suis désolé pour les fautes d'orthographe mais à bien y regarder il n'y en as pas tellement que ça ; dans tous les cas j'essaye au maximum d'éviter de faire des fautes mais je suis désolé j'ai des lacunes je le sais
même en me relisant.