[C] LE TRI, L'ÉCHANGE ET LES POINTEURS

Commentaire de djl le 22/05/2004 19:44:54

la seul fois ou tu utilise swap c'est pour faire
swap(&tab[0], &tab[1], sizeof(char));
alors que swap(char,char) aurait suffit

Commentaire de Dri le 23/05/2004 00:00:59

Pour répondre à djl, c'est un swap générique, là pour l'exemple j'utilise des char mais c'est supposer être fonctionnel pour n'importe quel type...

Sinon pour les memcpy() inutiles, comme je ne savais pas faire autrement j'ai fais comme ca... Ce serait sympa de me donner un exemple avec cette fonction là.

Dri

Commentaire de djl le 23/05/2004 00:32:15

dans swap tu cast un void* en void*

buffer3 = (void*) malloc(size); ?? il n'y a pas de cast qui tienne avec les types de bases

Commentaire de djl le 23/05/2004 10:54:42

en c99 tu peux faire

inline void AFFICHER_LE_TABLEAU()
{
for (int i=0; i<TAB_COUNT; i++)
printf("%d\n", tab[i]);
}

Commentaire de djl le 23/05/2004 11:01:43

POURQUOI tu fais buffer3 = (void*) malloc(size); et pas
buffer3 = malloc(size); ??

Commentaire de JCDjcd le 23/05/2004 12:06:38

Heu une petite question pour Dri :
dans ta structure bidon tu as different type; et donc dans le printf tu mets des "%d", cela marhce pour le int (taille 4 octets passes en pile), pour le char, je crois que par convention du C, il est convertie en int et passe a printf, dont jusqu'ici pas de probleme, mais pour l'histoire des short et des long, pk ca marche ?? coup de chance ?
car si un long represente plus de 32 bits, alors le printf va prendre les 7 premiers octets de la pile, qu'il comprendera comme etant un int.  C'est comme si je passait un __int64, ca ne devait pas marcher , non??

Commentaire de djl le 23/05/2004 12:26:59

oui long = 32bits sur une architecture 32bits

JCDjcd > en c, regarde du coté de la promotion de type losr du passage en parametre

char, short > int
unsigned char, unsigned short > unsigned
float > double

Dri > si tu compile avec un compilo c doit pas y avoir d'erreur ni warning

Commentaire de Dri le 27/05/2004 14:36:16

void sort(void *buffer, size_t size, size_t count, int (*compare)(void*, void*))

La fonction trie une zone continue de mémoire de n'importe quel type
Le type à une taille
On trie un tableau de count éléments
On les trie selon une fonction de comparaison qui accepte donc forcément n'importe quel type.

J'ai voulu faire une simple fonction
int char_superieur_ou_egal(char*, char*);
mais le seul problème c'est qu'à la compilation c'était refusé...

Donc la fonction doit accepter un type void et pas char. Regarde l'exemple de swap sur la structure bidon que j'ai mis dans un de mes commentaires... Elle fonctionne aussi bien sur du char que sur la structure bidon... Bah pareil avec ma fonction de tri... Elle est suppossée pouvoir trier ce qu'on lui donne et pas spécialement du char... Donc les fonctions utilisées pour la comparaison doivent s'harmoniser avec... Et utiliser du void... Enfin c'est le problème que j'ai rencontré...

Dri

Commentaire de Dri le 27/05/2004 15:39:21

Voila un exemple de tri de chaine de caractere... Je répete bien le but de la fonction... C'est de pas etre un simple sort... Mais bien de trier un peu n'importe quoi... Ca s'adresse en particulier aux types qui ne sont pas ceux de base mais pour l'exemple c'est eux que j'ai pris. BruNews l'a bien souligné ^^).
Je maitrise pas trop le C... Mais par exemple si on travaille avec un type comme :
structure
  chaine nom
  chaine prenom
finstructure
et qu'on désire trier un tableau de ces structures... Il faut bien soit se faire sa propre fonction de tri, soit uiliser une fonction qui en serait capable... C'est pour ca que j'ai codé cette fonction... Par exemple là on pourrai d'abord trier par nom, puis en cas de nom identique par prénom... Si ca intéresse je peux aussi coder un exemple d'utilisation avec cette structure...

Voila l'exemple pour les chaines :

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void sort(void*, size_t, size_t, int (*)(void*, void*));

int string_inferieur_ou_egal(void *a, void *b)
{
  char *c, *d;
  memcpy(&c, a, sizeof(char*));
  memcpy(&d, b, sizeof(char*));
  return (strcmp(c, d)<=0);
}

int string_superieur_ou_egal(void *a, void *b)
{
  char *c, *d;
  memcpy(&c, a, sizeof(char*));
  memcpy(&d, b, sizeof(char*));
  return (strcmp(c, d)>=0);
}

void sort(void *buffer, size_t size, size_t count, int (*compare)(void*, void*))
{
    size_t left, right, i;
    void *temp;
    
    temp = (void*) malloc(size);
    
    for(right=0; right<count; right++)
    {
    memcpy(temp, buffer+size*right, size);
    for(left=0; left<right; left++)
        if(compare(buffer+size*right, buffer+size*left)==1) break;
    if(left<right)
    {
        for(i=right; i>left; i--)
          memcpy(buffer+size*i, buffer+size*(i-1), size);
        memcpy(buffer+size*left, temp, size);
    }
    }
    
    free(temp);
    
}

#define TAB_COUNT 5


main()
{
  char *str[TAB_COUNT] = {
                           "chaine",
                           "caractere",
                           "mot",
                           "phrase",
                           "comparaison"
                         };
  int i, (*compare)(void*, void*);;
  
  for(i=0; i<TAB_COUNT; i++)
    printf("%s\n", str[i]);
  
  printf("\n");
  //on trie dans un ordre
  sort(str, sizeof(char*), TAB_COUNT, &string_superieur_ou_egal);
  for(i=0; i<TAB_COUNT; i++)
    printf("%s\n", str[i]);
  
  printf("\n");
  //puis dans l'autre
  sort(str, sizeof(char*), TAB_COUNT, &string_inferieur_ou_egal);
  for(i=0; i<TAB_COUNT; i++)
    printf("%s\n", str[i]);

  getch();
}

Dri

Commentaire de StanOfSky le 27/05/2004 22:06:32

si tu veux faire une fonctions qui compares des chaines de caracteres suffit de faire ca :
int char_superieur_ou_egal(void *a, void *b)
{
    return (strcmp((char*)a, (char*)b) >= 0);
}

ca sert a rien de recopier avant de faire le test....

j'avais bien compris que ta fonction de tri se voulait générique
d'ailleurs c pourquoi faut faire une fonction de comparaison que tu passes en parametre dans ta fonction de tri pour chaque type a trier : int (*compare)(void*, void*) qui perso j'aurai faire renvoyer un bool (meme si c pareil mais je prefere pour la compression)

mais c vrai que j'avais po fait gaffe a comment tu l'utilises dans ta fonction sort et c vrai qu'il faut que ce soit du int(*)(void*,void*) en parametre
c pour quoi vive les classes et les templates!!! ;)

sinon a part ca d'un point de vue algorithmique ta fonction sort n'est pas tres efficace puisqu'elle te fait faire n² comparaisons et dans le pire des cas n² swap...
mate des fonctions comme le tri fusion ou tri rapide qui sont des fonctions récursives faciles a comprendre et tres efficaces

Commentaire de Dri le 28/05/2004 08:54:04

Dsl mais cette fois je l'ai codée à la volée au bureau... Et j'ai pas pris le temps de "bien" faire les choses... Et je l'ai dit... Je maitrise pas tout ca... C'est même le but de maitriser en m'exercant... Sinon désolé de donner l'impression de faire parler dans le vide...
Pour le temp, en fait je l'avais fait comme ca des le début et je ne l'ai jamais corrigé... Donc tant que je ne la voyais pas je pouvais pas la corriger...

Aussi je répete que quand je cast un malloc c'est que j'ai un message d'erreur dessus et que souvent l'erreur est aiilleurs mais que le compilo me sort celle là...

return (strcmp(a, b) >= 0
Il me semble que faire ca n'est justement pas bon. Je vérifirai mais il me semble qu'en le faisant on ne donne pas l'adresse des chaines à comparer mais l'adresse de leurs poibteurs respectifs... C'est pour ca que je voulais passer cette adresse à d'autres variables et que je suis passé par des memcpy, ne sachant faire autrement

En tout cas merci de vos remarques

Dri

Commentaire de Dri le 28/05/2004 22:28:15

J'utilise DevC++ donc mingw
Quand j'utilise cette fonction le tri est faussé

Dri

Commentaire de Dri le 29/05/2004 17:41:11

Bah je l'ai dit je le fais en C... Donc forcément j'ai fait gaffe à l'enregistrer en C

Dri

Commentaire de Dri le 30/05/2004 11:17:28

Nan justement, je l'ai peut être mal expliqué, quand le compilo me balance cette erreur, c'est qu'il y en a une autre ailleurs (c'est ce que j'ai constaté) et du coup je réglai le problème de cette maniere alors qu'avant il l'acceptait... Et là bah ca génere aucune erreur... Parce qu'il n'y en a pas ailleurs.

Dri