/** * program: freq-C+.c * author: felipe@dift2030 * date: 1/09/2002 * * COMMENTS: lit depuis l'entree standard des mots (un par ligne) et * calcule la frequence de chaque mot, puis affiche (sur la sortie * standard) la liste des mots avec leur frequence (en ordre * croissant de frequence) * * NOTES: la table words est en permanence triee sur les mots lors des * lectures (ordre lexicographique), puis triee selon les frequences a * la fin (ordre croissant de frequence). * * Je ne libere pas la memoire occupee par les strings allouees au fur * et a mesure * * A compiler avec: gcc -o freq-C freq-C.c * Exemple de lancement: cat corpus-1 | freq-C * * Une implementation avec des listes serait ici plus efficace * * OBJET: illustrer l'interet de l'usage d'un language avec librairie * et vous preparer aux pointeurs (cad: oubliez C, passez a C++ !) * (n.b. il existe probablement plusieurs librairies C qui vous * donne acces au type HTable, mais ce sera tjs moins elegant que * d'utiliser un langage ou le type est accessible directement) */ #include #include #include // max car per string (plante s'il y en a plus sur une ligne) #define MAX_STRING 1000 /* declaration d'un type */ typedef struct item { int freq; char *mot; } Item ; /* les variables globales */ Item *words; // le tableau (mot,freq) int nbElt = 0; // le nombre de mots differents int maxSize = 1000; // la taille maximale de la table /** * @param pa pointeur sur un elt * @param pb pointeur sur l'elt suivant * @return un entier =0 si egalite, <0 si le premier elt est inferieur au second, >0 si le premier elt est superieur au second */ int sortFunction(const void *pa, const void *pb) { return ((Item *)pa)->freq - ((Item *)pb)->freq; } /** * @param mot le mot a rechercher dans la table mot * @return le rang du mot dans la table ou -1 si le mot n'est pas dans la table */ int recherche(char *mot) { int deb=0,milieu,fin=nbElt-1,c; while (deb <= fin) { milieu = (deb+fin)/2; if (!(c=strcmp(words[milieu].mot,mot))) return milieu; if (c<0) deb = milieu+1; else fin = milieu-1; } return -1; } /** @param mot le mot nouveau a ajouter dans la table implique un decalage vers la gauche de tous les mots superieurs a mot (pas tres efficace en pratique). Une recopie de structure est ici effectuee. */ void add(char *mot) { int index = nbElt-1; while (index && (strcmp(words[index-1].mot,mot) > 0)) { words[index] = words[index-1]; // affectation de structure index--; } /* on sort de la avec index qui pointe sur l'emplacement libre */ words[index].freq = 1; // nouveau mot; words[index].mot = strdup(mot); // allocation + recopie } /** la fonction principale qui se charge de la lecture des mots et pilote les autres fonctions */ int main() { char s[MAX_STRING]; int index,i,sent=0,mot=0; /* allocation des 1000 premiers elements */ words = (Item *) malloc(sizeof(Item)*maxSize); /* lecture mot a mot */ while (gets(s)) { if (!strcmp(s,"{sent}")) sent++; else { mot++; if ((index = recherche(s)) == -1) { nbElt++; if (nbElt == maxSize) { /* realloc */ maxSize *= 2; words = (Item *) realloc(words,sizeof(Item) * maxSize); } add(s); } else words[index].freq++; } } /* tri du tableau */ qsort(words,nbElt,sizeof(Item),sortFunction); /* affichage du tableau */ for (i=0; i < nbElt; i++) printf("%s\t%d\n",words[i].mot,words[i].freq); /* peanuts */ fprintf(stderr,"%d phrases lues, %d mots, %d formes\n", sent,mot,nbElt); return 0; // aucune erreur }