[C] Tri bulle sur chaîne de caractères

Tri bulle sur chaîne de caractères [C] - C - Programmation

Marsh Posté le 11-11-2004 à 22:18:51    

Bonsoir à tous,
 
Je viens vous demander un petit coup de main :)
Ce que je cherche à faire :
Un tri bulle sur plusieurs chaînes de caractères.
 
Ce qui ne marche pas :
Il me sort des valeurs étranges et j'ai 2 warning à la compilation.
 
Voici mon code :

Code :
  1. #include <stdio.h>
  2. struct typeliste
  3. {
  4. char nom[100];
  5. };
  6. void Inverse(int *x, int *y)
  7. {
  8. int adr_temp;
  9. adr_temp = *x;
  10. *x = *y;
  11. *y = adr_temp;
  12. }
  13. void TriBulle(struct typeliste liste[])
  14. {
  15. int i, arr_lenght, permut = 1;
  16. arr_lenght = sizeof(liste);
  17. while(permut == 1)
  18. {
  19.  permut = 0;
  20.  for(i=0;i<arr_lenght - 1;i++)
  21.  {
  22.   if(strcmp(liste[i].nom, liste[i+1].nom) > 0)
  23.   {
  24.    Inverse(&liste[i].nom, &liste[i+1].nom);
  25.    permut = 1;
  26.   }
  27.  }
  28. }
  29. }
  30. int main()
  31. {
  32. // Var
  33. int i;
  34. struct typeliste liste[4];
  35. // Saisie
  36. printf("Saisir le premier nom : " );
  37. scanf("%s", &liste[0].nom);
  38. printf("Saisir le deuxieme nom : " );
  39.         scanf("%s", &liste[1].nom);
  40. printf("Saisir le troisieme nom : " );
  41. scanf("%s", &liste[2].nom);
  42. for(i=0; i<3; i++) {
  43.  printf(": %s\n", liste[i].nom);
  44. }
  45. // Affichage par ordre alphabetique
  46. TriBulle(liste);
  47. for(i=0; i<3; i++) {
  48.                 printf(": %s\n", liste[i].nom);
  49.         }
  50. }


 
J'ai donc une structure ("liste" ) dans laquelle je stocke 3 chaines. Ensuite tri sur mon tableau mais là ça foire un peu.
Si je rentre dans l'ordre :
cc
bb
aa
 
il me sort :
(chaine vide)
aa
bb
 
Voilà si quelqu'un à une solution, c'est sûrement très bête m'enfin bon ça fait trop longtemps que je suis dessus, je vais craquer :D
 
EDIT : les 2 warnings sont :
l.26 "passage de l'argument N°1 de "inverse" d'un type pointeur incompatible"
l.26 "passage de l'argument N°2 de "inverse" d'un type pointeur incompatible"


Message édité par ofbdood le 11-11-2004 à 22:21:11
Reply

Marsh Posté le 11-11-2004 à 22:18:51   

Reply

Marsh Posté le 12-11-2004 à 00:36:49    

Commences déjà par changer le prototype de Inverser. Ce ne sont pas des pointeurs sur des int que tu as besoin.
De plus je doute que ce soit la structure qui te convienne.


Message édité par fafounet le 12-11-2004 à 00:37:33
Reply

Marsh Posté le 12-11-2004 à 01:08:07    

arr_lenght = sizeof(liste);
te retorune 4*100 et pas 4

Reply

Marsh Posté le 12-11-2004 à 01:14:21    

sizeof variable
sizeof(type)

Reply

Marsh Posté le 12-11-2004 à 01:42:01    

ofbdood a écrit :

Code :
  1. ...
  2. struct typeliste
  3. {
  4. char nom[100];
  5. };
  6. ...


Tu es sûr que l'inversion des chaînes fonctionne bien ?
Elles sont déclarées comme des tableaux et non comme des pointeurs : "char* nom;" que tu allouerais plus tard.
Je me demande comment il est possible d'inverser les adresses de ces tableaux dans ton tableau de structures "typeliste".


Message édité par darkoli le 12-11-2004 à 01:42:57

---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html
Reply

Marsh Posté le 12-11-2004 à 16:56:55    

darkoli a écrit :

Tu es sûr que l'inversion des chaînes fonctionne bien ?
Elles sont déclarées comme des tableaux et non comme des pointeurs : "char* nom;" que tu allouerais plus tard.
Je me demande comment il est possible d'inverser les adresses de ces tableaux dans ton tableau de structures "typeliste".


 
Bah non justement ça marche pas parfaitement ... d'ailleurs je ne sais pas si ma méthode est la bonne je voulais juste essayer de ré-utiliser ma fonctione de tri bulle sur des chaînes de caractères.

Reply

Marsh Posté le 12-11-2004 à 17:23:04    

ofbdood a écrit :

Bah non justement ça marche pas parfaitement ... d'ailleurs je ne sais pas si ma méthode est la bonne je voulais juste essayer de ré-utiliser ma fonctione de tri bulle sur des chaînes de caractères.

Dans ce cas, il faut que tu appelles la fonction Inverse de la façon suivante : "Inverse(liste[i].nom, liste[i+1].nom);", les paramètres de la fonction étant de type "char*".
Et dans la fonction il suffit de copier le contenu des chaînes de caractères en utilisant une chaîne temporaire de la même taille (fonction strcpy).
Une fois que tu auras fait ça, ton programme devrait fonctionner mais il y a encore d'autres améliorations à faire. :D
Bon courage.


Message édité par darkoli le 12-11-2004 à 17:25:18

---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html
Reply

Marsh Posté le 12-11-2004 à 18:31:12    

Bon alors d'après tes conseils j'ai fait ça :

Code :
  1. #include <stdio.h>
  2. struct typeliste
  3. {
  4. char nom[100];
  5. };
  6. void Inverse(char *x, char *y)
  7. {
  8. char adr_temp[100];
  9. strcpy(adr_temp, x);
  10. strcpy(x, y);
  11. strcpy(y, adr_temp);
  12. }
  13. void TriBulle(struct typeliste liste[])
  14. {
  15. int i, arr_lenght, permut = 1;
  16. arr_lenght = sizeof(liste);
  17. while(permut == 1)
  18. {
  19.  permut = 0;
  20.  for(i=0;i<arr_lenght - 1;i++)
  21.  {
  22.   printf("indice : %i val : %s\n", i, liste[i].nom);
  23.   if(strcmp(liste[i].nom, liste[i+1].nom) > 0)
  24.   {
  25.    Inverse(liste[i].nom, liste[i+1].nom);
  26.    permut = 1;
  27.   }
  28.  }
  29. }
  30. }
  31. int main()
  32. {
  33. // Var
  34. int i, ib, lenght, len_mod, pal = 1;
  35. struct typeliste liste[4];
  36. // Saisie
  37. printf("Saisir le premier nom : " );
  38. scanf("%s", &liste[0].nom);
  39. printf("Saisir le deuxieme nom : " );
  40.         scanf("%s", &liste[1].nom);
  41. printf("Saisir le troisieme nom : " );
  42. scanf("%s", &liste[2].nom);
  43. // Affichage par ordre alphabetique
  44. TriBulle(liste);
  45. }


 
Bon j'ai plus les erreurs de compilation mais j'ai toujours pas un résultat correct.
en entrée :
cc
bb
aa
 
en sortie :  
 ÖP
aa
bb
 
Pourtant là j'envoie les chaînes ça devrat être bon nan ?

Reply

Marsh Posté le 12-11-2004 à 18:57:28    

Tu as toujours des char et non des char* dans ta structure

Reply

Marsh Posté le 12-11-2004 à 23:51:48    

Je me mele de ce qui ne me regarde pas, mais qsort() c'est bien aussi.

Reply

Marsh Posté le 12-11-2004 à 23:51:48   

Reply

Marsh Posté le 13-11-2004 à 00:37:31    

ofbdood a écrit :

Bon j'ai plus les erreurs de compilation mais j'ai toujours pas un résultat correct.
en entrée :
cc
bb
aa
 
en sortie :  
 ÖP
aa
bb
 
Pourtant là j'envoie les chaînes ça devrat être bon nan ?

Ton tri fonctionne très bien ! :D
Je vais te laisser réflechir avant de te dire ce qui ne va pas.
Voilà un indice : de quelle taille est ton tableau ?


Message édité par darkoli le 13-11-2004 à 00:38:23

---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html
Reply

Marsh Posté le 13-11-2004 à 00:45:52    

fafounet a écrit :

Tu as toujours des char et non des char* dans ta structure

Non c'est bon car dans la structure c'est un tableau et c'est presque équivalent à un char*. Et il est tout à fait possible de copier l'adresse du tableau dans un pointeur.


---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html
Reply

Marsh Posté le 13-11-2004 à 11:33:26    

ofbdood a écrit :

Bon alors d'après tes conseils j'ai fait ça :

Code :
  1. #include <stdio.h>
  2. struct typeliste
  3. {
  4. char nom[100];
  5. };
  6. void Inverse(char *x, char *y)
  7. {
  8. char adr_temp[100];
  9. strcpy(adr_temp, x);
  10. strcpy(x, y);
  11. strcpy(y, adr_temp);
  12. }
  13. void TriBulle(struct typeliste liste[])
  14. {
  15. int i, arr_lenght, permut = 1;
  16. arr_lenght = sizeof(liste);
  17. while(permut == 1)
  18. {
  19.  permut = 0;
  20.  for(i=0;i<arr_lenght - 1;i++)
  21.  {
  22.   printf("indice : %i val : %s\n", i, liste[i].nom);
  23.   if(strcmp(liste[i].nom, liste[i+1].nom) > 0)
  24.   {
  25.    Inverse(liste[i].nom, liste[i+1].nom);
  26.    permut = 1;
  27.   }
  28.  }
  29. }
  30. }
  31. int main()
  32. {
  33. // Var
  34. int i, ib, lenght, len_mod, pal = 1;
  35. struct typeliste liste[4];
  36. // Saisie
  37. printf("Saisir le premier nom : " );
  38. scanf("%s", &liste[0].nom);
  39. printf("Saisir le deuxieme nom : " );
  40.         scanf("%s", &liste[1].nom);
  41. printf("Saisir le troisieme nom : " );
  42. scanf("%s", &liste[2].nom);
  43. // Affichage par ordre alphabetique
  44. TriBulle(liste);
  45. }


 
Bon j'ai plus les erreurs de compilation mais j'ai toujours pas un résultat correct.
en entrée :
cc
bb
aa
 
en sortie :  
 ÖP
aa
bb
 
Pourtant là j'envoie les chaînes ça devrat être bon nan ?


Dans un premier temps, pour faire fonctionner correctement ton tri, donne-lui un tableau de la bonne taille

Code :
  1. struct typeliste liste[3];


Là, cela devrait marcher
 
Dans un second temps, si je regarde ton tout premier source, ton idée d'inverser les adresses des chaînes n'est pas mal du tout, et cela est beaucoup plus rapide qu'inverser des chaînes. Mais il faut, comme l'a dit fafounet, déclarer les bons types.
Par exemple, si tu appelles "inverse(&liste[i].nom)" alors tu passes à ta fonction "inverse" un pointeur sur une chaîne. Mais comme une chaîne c'est un tableau de char, tu obtiens en final un pointeur sur un pointeur sur un char, donc un "char **"
A mon avis, tu devrais écrire ta fonction "Inverse" comme ceci:

Code :
  1. void Inverse(char **x, char **y)
  2. {
  3.     char *adr_temp;
  4.     adr_temp = *x;
  5.     *x = (*y); // Parenthèses pour éviter la confusion avec "*x=*x * y"
  6.     *y = adr_temp;
  7. }


j'ai pas testé mais à mon avis, cela devrait fonctionner. Et au lieu de permuter des chaînes tu ne permutes que les adresses de ces chaînes donc c'est plus rapide !!!
 
Enfin dernier truc: Avec la magie des maths, on peut permuter deux valeurs "a" et "b" sans utiliser de variables intermédiaires en utilisant ces 3 instructions:
a=a ^ b
b=a ^ b
a=a ^ b
 
A+

Reply

Marsh Posté le 13-11-2004 à 12:00:00    

Sve@r a écrit :

j'ai pas testé mais à mon avis, cela devrait fonctionner. Et au lieu de permuter des chaînes tu ne permutes que les adresses de ces chaînes donc c'est plus rapide !!!

Je suis d'accord avec toi, mais modififier la fonction "Inverse" n'est pas suffisant car ce sont toujours des tableaux qui sont déclarés dans la structure "typeliste".
Dans ce cas il faut remplacer le tableau par un pointeur et faire l'allocation mémoire pour chaque chaîne lue (sans oublier de désallouer à la fin).


---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html
Reply

Marsh Posté le 13-11-2004 à 12:05:01    

# void Inverse(char *x, char *y)
# {
#     char adr_temp[100];
#     strcpy(adr_temp, x);
#     strcpy(x, y);
#     strcpy(y, adr_temp);
# }
 
 
[:rofl]

Reply

Marsh Posté le 13-11-2004 à 12:08:26    

'fectivement, dans le genre bourrin... :D


Message édité par el muchacho le 13-11-2004 à 12:08:48
Reply

Marsh Posté le 13-11-2004 à 12:16:28    

je parle pas du char adr_temp[100];  on est d'accord

Reply

Marsh Posté le 13-11-2004 à 12:17:32    

darkoli a écrit :

Je suis d'accord avec toi, mais modififier la fonction "Inverse" n'est pas suffisant car ce sont toujours des tableaux qui sont déclarés dans la structure "typeliste".
Dans ce cas il faut remplacer le tableau par un pointeur et faire l'allocation mémoire pour chaque chaîne lue (sans oublier de désallouer à la fin).


 
Il se peut que tu aies grandement raison. Même si un tableau se comporte souvent comme un pointeur, il ne doit pas être possible de changer sa valeur comme ça, ce qui oblige donc à n'utiliser que des pointeurs alloués au départ et libérés en final...


---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 13-11-2004 à 12:25:32    

Bon cette fois ci c'est la bonne :)
Alors voilà ça ça marche :
 

Code :
  1. #include <stdio.h>
  2. const TAB_LONG = 3;
  3. struct typeliste
  4. {
  5. char nom[100];
  6. };
  7. void Inverse(char *x, char *y)
  8. {
  9. char adr_temp[100];
  10. strcpy(adr_temp, x);
  11. strcpy(x, y);
  12. strcpy(y, adr_temp);
  13. }
  14. void TriBulle(struct typeliste liste[])
  15. {
  16. int i, permut = 1;
  17. while(permut == 1)
  18. {
  19.  permut = 0;
  20.  for(i=0;i<TAB_LONG - 1;i++)
  21.  {
  22.   printf("indice : %i val : %s\n", i, liste[i].nom);
  23.   if(strcmp(liste[i].nom, liste[i+1].nom) > 0)
  24.   {
  25.    Inverse(liste[i].nom, liste[i+1].nom);
  26.    permut = 1;
  27.   }
  28.  }
  29. }
  30. }
  31. int main()
  32. {
  33. // Var
  34. int i, ib, lenght, len_mod, pal = 1;
  35. struct typeliste liste[TAB_LONG];
  36. // Saisie
  37. for(i=0;i<TAB_LONG;i++) {
  38.  printf("Saisir le nom %i : ", i+1);
  39.         scanf("%s", &liste[i].nom);
  40. }
  41. // Affichage par ordre alphabetique
  42. TriBulle(liste);
  43.         return 0;
  44. }


 
J'ai mis la longueur du tableau en constante et ce qui faisait tout foirer c'était juste la longueur du tableau (merci darkoli ;))
en fait le "sizeof" retournait 4 et non 3. J'ai réduit au passage la taille de mon tableau à 3 (je ne sais pas pourquoi j'avais mis 4 d'ailleurs, la fatigue sûrement)
 
Sinon j'ai quand même testé la solution donnée par Sve@r mais ça ne marche pas.
 
Un grand merci à tous, vous m'avez bien aidé !
Si certains veulent chercher pour la solution de Sve@r je suis toujours preneur, enfin ne gâchez pas votre week-end à cause de ça ;)


Message édité par ofbdood le 13-11-2004 à 12:25:49
Reply

Marsh Posté le 13-11-2004 à 12:55:16    

ofbdood a écrit :

Sinon j'ai quand même testé la solution donnée par Sve@r mais ça ne marche pas.
 
Un grand merci à tous, vous m'avez bien aidé !
Si certains veulent chercher pour la solution de Sve@r je suis toujours preneur, enfin ne gâchez pas votre week-end à cause de ça ;)


 
Pas besoin de tout un WE. Ya qu'à prendre ton code et changer qq trucs...
Essaye ceci (je n'ai pas essayé, je ne compile qu'au boulot mais cela devrait être pas mal...)
 

Code :
  1. #include <stdio.h>
  2. const TAB_LONG = 3;
  3. struct typeliste
  4. {
  5. char *nom;
  6. };
  7. void Inverse(char **x, char **y)
  8. {
  9. char *tmp;
  10. tmp=(*x);
  11. *x=(*y);
  12. *y=tmp;
  13. }
  14. void TriBulle(struct typeliste liste[])
  15. {
  16. int i, permut = 1;
  17. while(permut == 1)
  18. {
  19.  permut = 0;
  20.  for(i=0;i<TAB_LONG - 1;i++)
  21.  {
  22.   printf("indice : %i val : %s\n", i, liste[i].nom);
  23.   if(strcmp(liste[i].nom, liste[i+1].nom) > 0)
  24.   {
  25.    Inverse(&liste[i].nom, &liste[i+1].nom);
  26.    permut = 1;
  27.   }
  28.  }
  29. }
  30. }
  31. int main()
  32. {
  33. // Var
  34. int i;
  35. struct typeliste liste[TAB_LONG];
  36. // Initialisation + Saisie
  37. for(i=0;i<TAB_LONG;i++) {
  38.  liste[i].nom=(char*)malloc(100);
  39.  printf("Saisir le nom %i : ", i+1);
  40.         scanf("%s", &liste[i].nom);
  41. }
  42. // Affichage par ordre alphabetique
  43. TriBulle(liste);
  44. // Nettoyage
  45. for(i=0;i<TAB_LONG;i++)
  46.  free(liste[i].nom);
  47.         return 0;
  48. }


Message édité par Sve@r le 13-11-2004 à 12:57:18

---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 13-11-2004 à 13:12:22    

scanf("%s", &liste[i].nom);
 
y a qui en veulent ...

Reply

Marsh Posté le 13-11-2004 à 13:45:47    

Taz a écrit :

scanf("%s", &liste[i].nom);
 
y a qui en veulent ...


Je débute en C, mais d'après ce qu'on m'a appris on ne met pas de & lorsque le type de la variable est string. J'ai bon?  :??:


Message édité par Ayuget le 13-11-2004 à 13:46:59
Reply

Marsh Posté le 13-11-2004 à 14:14:31    

non. ça a rien à avoir. l'argument de scanf doit être un pointeur vers une zone mémoire capable de stocker la variable. une chaine en C, c'est un tableau ou un pointeur, t, &t[0] ou p sont déjà des pointeurs vers cette zone

Reply

Marsh Posté le 13-11-2004 à 14:20:19    

Taz a écrit :

non. ça a rien à avoir. l'argument de scanf doit être un pointeur vers une zone mémoire capable de stocker la variable. une chaine en C, c'est un tableau ou un pointeur, t, &t[0] ou p sont déjà des pointeurs vers cette zone


merci de l'explication :jap:

Reply

Marsh Posté le 13-11-2004 à 14:26:03    

Taz a écrit :

# void Inverse(char *x, char *y)
# {
#     char adr_temp[100];
#     strcpy(adr_temp, x);
#     strcpy(x, y);
#     strcpy(y, adr_temp);
# }
 
 
[:rofl]


 
se moquer, c'est mal !  :o


---------------
Non au projet de loi DADVSI ! (droits d'auteurs)
Reply

Marsh Posté le 13-11-2004 à 14:27:43    

je me moque, je vois une blague, j'en rie

Reply

Marsh Posté le 13-11-2004 à 14:30:35    

Taz a écrit :

je me moque, je vois une blague, j'en rie


 
il débute, tu vas le braquer, spa gentil gentil ça  :o
t'as pas une idée pour mon defunct ? [:cupra]
 
 
 
PS : t'es toujours ban de osa ou quoi, on te voit plus ?  [:anathema]


---------------
Non au projet de loi DADVSI ! (droits d'auteurs)
Reply

Marsh Posté le 13-11-2004 à 14:33:16    

[:cupralf]


---------------
uptime is for lousy system administrators what Viagra is for impotent people - mes unixeries - github me
Reply

Marsh Posté le 13-11-2004 à 17:37:06    

Taz a écrit :

je me moque, je vois une blague, j'en rie

Elle est où la blague, j'aimerais bien rire aussi ! :??:


Message édité par darkoli le 13-11-2004 à 17:37:16

---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html
Reply

Marsh Posté le 13-11-2004 à 17:47:32    


 
t'as pas bientot fini toi oui !?  :o


---------------
Non au projet de loi DADVSI ! (droits d'auteurs)
Reply

Marsh Posté le 14-11-2004 à 11:05:24    

Remarquez, c'est quand même du tri à bulle, alors qu'il fasse des strcpy au lieu d'échanges de pointeurs, ça ne va pas changer des masses (enfin un peu quand même).
Mais d'un point de vue purement éducatif, apprendre à manipuler les pointeurs, c'est pas plus mal.

Reply

Marsh Posté le 14-11-2004 à 11:50:43    

avec les pointeurs ça serait plus simple, souple et performant. C'est dommage de faire un tri bridé comme ça. Surtout que le passe-passe de pointeur est trivial comparé à sa fonction Inverse. Enfin bon, Inverse(&liste[i].nom, &liste[i+1].nom); il est tout de façon pas près pour les pointeurs ...

Reply

Marsh Posté le 14-11-2004 à 12:02:52    

Taz a écrit :

scanf("%s", &liste[i].nom);
 
y a qui en veulent ...


Ahhh !!! Cette ligne m'avait échappé... MeaCulpa :sleep:


---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed