comment trier par insertion un tableau bidimentionnel??

Version imprimable

donc voila je dois realisé un tri de tableau pour ca il faut que j'affiche le tableau sans etre trier et ensuite trier la 3eme colone
c'est un tableau avec 4 caracteristiques

Code:

1
2
3
4
5
6
 
origine   extremité   prix  durée
 
 0          0           0    0
 0          0           0    0
 0          0           0    0

dans ce style!
mon debut de programme est comme ca

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
#include <stdio.h>
#include <stdlib.h>
/************************
 *DECLARATION DES TYPES**
 ***********************/
 
struct tuyaux{
  int origine;
  int extremite;
  int prix;
  int duree;
};
 
 
int main()
{
 
  int nbTuyaux;
  printf ("entrez le nombre de tuyaux dans le reseau >");
  scanf ("%d",&nbTuyaux);
 
  struct tuyaux reseau[nbTuyaux];
  int i;
   printf("entrer l'origine,l'extremite,le prix et la durée des travaux \n");
    for(i=0;i<nbTuyaux;i++){
     printf("pour le %d =>",i+1);
       scanf("%d %d %d %d",&reseau[i].origine,&reseau[i].extremite,&reseau[i].prix,&reseau[i].duree);
  }
  printf("origine extremite prix   duree\n");
  for(i=0;i<nbTuyaux;i++){
     printf("   %d        %d       %d      %d \n",reseau[i].origine,reseau[i].extremite,reseau[i].prix,reseau[i].duree);
  }

19/05/2006, 18h29
joan_al_catala

par contre je ne voudrait pas la solution mais juste comment demarrer , la demarcher a suivre au debut pour commencer

en fait je me demande surtout comment dire qu'il faut trier telle colone
il faut faire [tuyaux] [reseau[i].prix]??
19/05/2006, 23h29
Rafy
Il serai beaucoup plus simple et plus élégant de travailler avec les outils du C++ :
-> Remplacer les scanf par des std::cin
-> Remplacer les printf par des std::cout
-> Utiliser des conteneurs de la librairie standard plutôt que des tableaux C (std::list<> ou std::vector<>)
-> Tu n'est pas obligé de mettre le mot clef struct devant une instanciation.

Et le tri sera possible de deux manières :
-> Tu définis un opérateur de comparaison (l'opérateur <) pour ta class tuyau :
Code:

1 2 3 4 5 bool operator<(const CTuyau& T1, const CTuyau& T2) { return T1.prix < T2.prix; }
et tu apelles la méthode sort() de ton conteneur.
-> Tu apelles la méthode sort() en passant par argument un prédicat.
Un prédicat est une fonction qui retourne un bool et qui prend en arguments deux objets de même type.
Ce prédicat aura le même effet que l'opérateur <...

Tu peux aller voir ici, ça pourra surement t'aider pour les conteneurs.
Et ici, pour les prédicats.
20/05/2006, 12h11
b Oo
Bonjour joan_al_catala,
je crois que tu t'es trompé de forum, car c'est du code C et non C++.
Pour ta question, tu peux accéder à prix avec :
Code:

1 2 3 reseau[i]; //accède à la i ème case du tableau reseau reseau[i].prix; // accède au prix de la i ème case du tableau reseau
A+

b Oo
20/05/2006, 13h40
joan_al_catala

oui je crois bien m'etre trompé c'est bien du c non pas du c++
oui je peux y acceder en faisant reseau[i] mais le probleme c'est que comment va t'il savoir qu"il s'agit de la colone des prix? car les variable sont defini apart du tableau
20/05/2006, 14h34
Emmanuel Delahaye

Citation:

Envoyé par joan_al_catala

donc voila je dois realisé un tri de tableau pour ca il

qsort().
20/05/2006, 14h35
Emmanuel Delahaye

<delestage>

Je vais faire un bout de code et expliquer ce qui se passe :

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
 
// les includes
 
struct tuyaux
{
  int origine;
  int extremite;
  int prix;
  int duree;
};
 
int main()
{
   struct tuyaux monTuyau;
   /* Comme monTuyau est un tuyau je peux accéder a son origine, à son extremite, à son prix et à sa durée */
 
   monTuyau.origine = monTuyau.extremite = 0; /* monTuyau a désormais une origine et une extrémité de 0 */
   monTuyau.prix = 3; // monTuyau coute desormais 3 euros
   monTuyau.duree = 1; // monTuyau dure 1 minute
 
   struct tuyaux tabTuyau[10];
   /* je crée un tableau qui contient 10 tuyaux :
        le premier est tabTuyau[0] et le dernier tabTuyau[9]
      Chaque élément du tableau est un tuyau donc par exemple :
      tabTuyau[0] est un tuyau et donc on peut acceder à son origne, son extremite, etc ...
   */
   tabTuyau[0].prix = 1; // le prix du tuyau contenu à la case 0 est de 1
 
  return 0;
}

voila j'espere que tu as compris, donc pour trier ton tableau, il faut que tu parcours le tableau élément par élément.

b Oo

[oui on est bien dans le forum C, mais il avait posté le message dans le forum C++]

20/05/2006, 15h10
joan_al_catala

okay c'est bon ca m'eclaircie vachement! merci!
20/05/2006, 15h31
joan_al_catala

no nmais en fait ce n'est pas ca lol

en fait voila quand j'ai crée mon tableau avec
origine extrmité prix et durée des travaux je voudrai pouvoir trier la colone des prix

Arf, bon dis clairement ce que tu veux.
Prenons l'exemple suivant :

Code:

1
2
3
4
5
6
 
origine   extrémité   prix   durée
   1            2          3       4
   1            2          5       6
   3            4          1       1
   1            5          2       2

J'ai donc un tableau qui contient 4 tuyaux.
Le tuyau 0 à pour origine 1, pour extrémité 2, pour prix 3, et pour durée 4.
Le tuyau 1 à pour origine 1, pour extrémité 2, pour prix 5, et pour durée 6.
Le tuyau 2 à pour origine 3, pour extrémité 4, pour prix 1, et pour durée 1.
Le tuyau 0 à pour origine 1, pour extrémité 5, pour prix 2, et pour durée 2.

Tu veux que le tableau soit trié en fonction du prix (on echange la place des tuyaux dans le tableau), donc le tableau trié sera :

Code:

1
2
3
4
5
6
 
origine   extrémité   prix   durée
   3            4          1        1
   1            5          2        2    
   1            2          3        4
   1            2          5        6

C'est bien ça que tu veux, tu ne veux pas juste trier le prix et donc avoir ceci :

Code:

1
2
3
4
5
6
 
 origine   extrémité   prix   durée
   1            2          1        1
   1            2          2        2
   3            4          3        4
   1            5          5        6

Il faut savoir que lorsque tu fais :

Code:

1
2
 
struct tuyaux monTuyau;

cela alloue la mémoire pour monTuyau de type tuyaux, et donc 4 entiers sont alloués.
Pour trier, il faut que tu regardes le prix donc en fait :

Code:

1
2
3
4
5
6
7
8
9
10
 
for(i = 0; i < nbTuyaux-1; ++i)
{
  if (reseau[i].prix > reseau[i+1].prix)
  {
     struct tuyau temporaire = reseau[i+1].prix;
     reseau[i+1].prix = reseau[i].prix;
     reseau[i].prix = temporaire;
  }
}

Ici ça ne va pas complétement trier le tableau, je t'ai juste montrer comment comparer.
Ici, le résultat du code sur l'exemple que j'ai donné au début est :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
// tableau non trié
origine   extrémité   prix   durée
   1            2          3       4
   1            2          5       6
   3            4          1       1
   1            5          2       2
 
// résultat du code écrit avant
origine   extrémité   prix   durée
   1            2          3       4
   3            4          1       1
   1            5          2       2
   1            2          5       6

J'espère avoir été plus clair.

A+

b Oo

20/05/2006, 16h27
joan_al_catala

oui c'est exactement ca! je vais mediter dessus....un bon moment
20/05/2006, 16h39
joan_al_catala

le probleme c'est que je ne peut pas stocker dans un tuyau temporaire

je dois directement changer
20/05/2006, 17h05
joan_al_catala

je dois utiliser une methode speciale que j'ai compris mais je m'enbrouille en essayant de la coder en c

http://jean341.free.fr/tri%20prix.JPG

pour vous expliquer plus en detail la case de droite prend le numero de la case qui contient le plus petit prix( n-1 donc vu que l'on commence a 0)
prenons par exemple 2

si la case de droite initialisé a 0 recoit 2( le plus petit prix du tableau donc )
il va falloir se positionner sur la case 2(donc la troisieme ) du tableau de gauche et chercher la deuxieme plus petite valeur
nous dirons que la plus petite deuxieme valeur se trouve a la case 1(donc indice 0)
on va donc marquer le 0 dans la 3eme case du tableau de gauche et aller se positionner devant la case 0(donc la premiere) et ainsi de suite

c peut etre compliquer a comprendre comme ca

je vais essayer de vous expliquer grace a ce dessin

http://jean341.free.fr/Sans%20titre.JPG
20/05/2006, 20h54
Rafy

Citation:

Envoyé par Emmanuel Delahaye

On est bien sur le forum C ici ?

J'ai posté quand le sujet était encore sur le forum C++, sujet déplacé...

:koi:
Bon je crois avoir compris ce que tu veux.
En fait tu ne veux pas trier ton tableau, je veux dire par là que tu ne modifies pas ton tableau de départ.
Tu veux juste que dans un autre tableau de même taille que le premier, que chaque case contienne l'indice de la première case qui a le plus petit prix supérieur. Et pour l'élément maximum tu lui mets -1 comme indice.
Donc :
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 int tab[nb_tuyau]; tuyaux reseau[nb_tuyau]; /* on cherche le minimun */ int indiceMin = 0; // indice de l'élément minimum for (int i = 1; i < nb_tuyau; ++i) { if (reseau[i].prix < reseau[indiceMin].prix) { indiceMin = i; } } /* le minimum se trouve à l'indice indiceMin*/ int mininmum = 100000; int indice = -1; /* on cherche le minimum mais supérieur à la valeur du minimum courant*/ for (int i = 0; i < nb_tuyau; ++i) { if (reseau[i].prix < minimum && reseau[i].prix > reseau[indiceMin].prix) { minimum = reseau[i].prix; indice = i; } } /*on a le deuxième plus petit élément*/ tab[indiceMin] = indice; /* on met dans la case du plus petit élément l'indice du prix immédiatement supérieur */ ... /* faire la même chose pour les autres. Une fonction récursive doit pouvoir être implémentée, ou sinon une autre boucle peut faire l'affaire */
J'espère que cela t'auras éclairé.

A+

b Oo

21/05/2006, 10h44
joan_al_catala

oué c ca! hier soir j'avais commencé a partir la dessus et apparement c 'est bon! merci pour tout!
21/05/2006, 15h06
joan_al_catala

est ce que cette methode de tri aurait un nom specifique?
21/05/2006, 15h10
joan_al_catala

il y a quelque chose que je ne comprend pas bien

Citation:

/* on cherche le minimun */
int indiceMin = 0; // indice de l'élément minimum
for (int i = 1; i < nb_tuyau; ++i)
{
if (reseau[i].prix < reseau[indiceMin].prix)
{
indiceMin = i;
}

ici le bout de code dit que pour i de 1 a nb de tuyau si le prix d'une ligne est inferieur a indicemin on le met a sa place

mais moi je vois que indicemin=0
alors comment on peut trouver une valeur <0 pour la remplacer?:lol:
21/05/2006, 19h20
b Oo

Salut,
pour trouver le minimum du tableau, je dis que le minimum se trouve sur la première case donc celle d'indice 0.
Ensuite je teste si les autres valeurs, donc les cases d'indice 1 à n-1, sont inférieures à la valeur de la première case. Donc si c'est le cas, je change indiceMin.
indiceMin ne me sert ici qu'à sauvegarder l'indice de la case la plus petite. Je ne compare pas les indices mais la valeur d'une case d'indice i avec la valeur de la case d'indice indiceMin.

A+

b Oo