Partage

Nombre de chaines identiques

1 2 >>

Sujet résolu

27 décembre 2007 à 13:04:33

Bonjour,
Voila je vous explique mon probleme. J'ai un fichier et dans ce fichire
a chaque ligne j'ai un nom. Des fois j'ai le meme nom a d'autres lignes.
En fait ce que je voudrais faire c'est pouvoir compter le nombre de fois que ce nom apparait.
Exemple :

albert
roger
david
albert
tat
toto
titi
david
frank
toto

Je veux compter combien de fois apparait chaque nom.
J'ai chercher, mais je vois pas comment faire

Merci d'avance

-ed-

27 décembre 2007 à 13:10:00

Citation : GomuSan

Je veux compter combien de fois apparait chaque nom.
J'ai chercher, mais je vois pas comment faire

Algorithme classique de recherche de doublons...

Tu fais un tableau de chaines dans lequel tu places les noms.
pour chaque nom, tu cherches si le même existe ailleurs. Si tu le trouves, tu incrémente un compteur.

Il faut 2 indices, 2 boucles, strcmp()...

Autre méthode, trier, puis parcourir en comptant les mots identiques... Bref, il faut un peu réfléchir. L'informatique, c'est ça. Le codage, c'est rien...

Music only !

Gambit2099

27 décembre 2007 à 13:10:22

Mmh ça sent les tableaux + malloc.

Comme ça je te dirais de faire ainsi: un tableau parcourant chaque ligne:: si on trouve un nouveau nom on l'inscrit dans un tableau de chaine où l'on modifierai sa taille à chaque nouveau nom.

Il doit avoir une meilleure solution mais je vois que ça moi ôÔ

Au pire des cas si tu veux pas te fatiguer à faire à chaque fois un malloc -> tu parcoures tout ton fichier -> tu comptes les sauts de lignes -> Malloc de ce nombre sur le tableau et tu es tranquilles.

Citation : Pas de titre

Tu fais un tableau de chaines dans lequel tu places les noms.

Et Malloc ? On fait comment pour définir la taille d'un tableau 2D?

www.juliandropsit.com

aurek

27 décembre 2007 à 13:13:08

Il faut que tu crées un tableau de nom pour avoir chacun d'eux.

Exemple : tu as albert, tu regardes dans le tableau (celui contenant les noms des fichiers) tu vois qu'il n'y est pas donc tu l'ajoutes. Par contre, si tu le trouves alors tu incrémentes la variable en conséquence.

Pour parcourir le fichier je pense qu'une structure du type :

typedef struct
{
char nom[20];
int nb;
}Pers;

conviendrait pour répondre à la question.

-ed-

27 décembre 2007 à 13:14:43

Citation : Gambit2099

Citation : Pas de titre

Tu fais un tableau de chaines dans lequel tu places les noms.

Et Malloc ? On fait comment pour définir la taille d'un tableau 2D?

http://mapage.noos.fr/emdel/notes.htm#tabdyn_2d
Mais qui a parlé d'un tableau 2D ?

Un simple tableau 1D de char* auquel on accroche une copie de chaque chaine (strdup()) est suffisant.

Music only !

Gambit2099

27 décembre 2007 à 13:17:30

Citation : -ed-

Citation : Gambit2099

Citation : Pas de titre

Tu fais un tableau de chaines dans lequel tu places les noms.

Et Malloc ? On fait comment pour définir la taille d'un tableau 2D?

http://mapage.noos.fr/emdel/notes.htm#tabdyn_2d
Mais qui a parlé d'un tableau 2D ?

Un simple tableau 1D de char* auquel on accroche une copie de chaque chaine (strdup()) est suffisant.

En fait j'aurais du dire:
Et comment il faut pour définir la taille de son tableau 2D? (c'est ça que je pensais que tu avais oublié dans ton post: parler de malloc).

www.juliandropsit.com

GomuSan

27 décembre 2007 à 13:20:11

Citation : -ed-

Tu fais un tableau de chaines dans lequel tu places les noms.
pour chaque nom, tu cherches si le même existe ailleurs. Si tu le trouves, tu incrémente un compteur.

Il faut 2 indices, 2 boucles, strcmp()...

J'y avais pensé sur papier. Mais je voulais juste avoir vos avis, pour ne pas partir dans une mauvaise direction

En fait mon idée c'est d'avoir un tableau a 2 dimensions, ou je rentre tout les noms, et un tableau d'entier. A chaque fois que je trouve un nom je le rentre dans le tableau et je verifie avant s'il n'existe pas, s'il existe deja j'incremente mon tableau d'entiers au meme indice du nom.

Mais le probleme, c'est que je saurais pas a quel case du tableau correspond chaque nom :S

Par contre ed, je vois pas comment faire sa avec un tableau a 1 une dimension.

-ed-

27 décembre 2007 à 13:28:08

Citation : GomuSan

Par contre ed, je vois pas comment faire sa avec un tableau a 1 une dimension.

Si tu ne réfléchis jamais au moyen de trouver les solutions, tu ne vas pas avancer...

calculer le nombre de mots (N)
allouer un tableau de N char *
lire le fichier ligne à ligne (fgets())
à chaque ligne,
- nettoyer (fclean(), faire une recherche sur le forum)
- dans chaque pointeur du tableau, stocker l'adresse d'une
copie dynamique du nom
(strdup() peut aider. C'est POSIX.1, donc très portable.
De plus, facile à reproduire si nécessaire).
etc.

Pour ta question précédente, si tu affiches l'information au fur et à mesure, tu n'as besoin que d'un seul compteur.

Music only !

GomuSan

27 décembre 2007 à 13:31:58

Desolé, mais je comprends toujours pas et dire que je ne reflechis pas, c'est nimporte quoi parce que je reflechi depuis 11h du matin. Desolé mais on a pas tous ton niveau.

Bref, je veux pas m'embrouillé, donc pour te dire, qu'on doit pas utilisé des trucs qu'on a pas vu, donc strdup et fclean, sont a bannir. Et ton histoire de pointeur du tableau, je capte pas.

aurek

27 décembre 2007 à 13:37:42

Alors, si tu veux que l'on t'aide dit nous ce que tu as vu histoire de pas partir n'importe où.

Pour fclean, c'est une fonction qui vide le buffer d'entrée pour enlever les reste des saisies précédentes. strdup permet de faire une copie dynamique de la chaîne mais je peux pas en dire plus.

GomuSan

27 décembre 2007 à 13:42:09

J'ai tout vu, sauf les tableaux a 2 dimensions et strdup et fclean
J'ai vu strcmp, strcat, strcpy

aurek

27 décembre 2007 à 13:45:19

Tu n'as pas plus précis, car si tu as tout vu sauf ce que tu cites alors tu ne devrais pas avoir de problème avec les pointeurs, l'allocation dynamique ... donc tout ce qu'a mis -ed- devrait être clair comme de l'eau de roche. (enfin presque car faut un peu y réfléchir)

GomuSan

27 décembre 2007 à 13:47:04

Ouais j'ai vu tout sa, mais il me parle de strdup. Nan mais j'ai compris qu'il fallait les utiliser mais je vois pas comment.

Et j'ai pas compris ton struct, comment parcourir avec, faut faire un tableau de struct?

Frava

27 décembre 2007 à 13:51:09

La solution de l'arbre avec une branche par lettre et une valeur est la plus efficace.
Par exemple :

Liste :
julien
jean
jean
julien
julie
julien
Arbre :
J
/ 0 \
E U
/ 0 0 \
A L
/ 0 0 \
N I
2 0 \
E
1 \
N
3

GomuSan

27 décembre 2007 à 14:01:28

Citation : Frava

La solution de l'arbre avec une branche par lettre et une valeur est la plus efficace.
Par exemple :

Liste :

        julien

        jean

        jean

        julien

        julie

        julien

Arbre :

                J

              / 0 \

             E     U

           / 0     0 \

          A           L

        / 0           0 \

       N                I

       2                0 \

                          E

                          1 \

                            N

                            3

Oula, plus vous me repondrez et moins je comprends... C'est quoi cet arbre ?

Sinon, j'ai encore reflechi et je pense que la reponse d'aurek est pas mal, avec le struct. J'ai pensé a faire un tableau de struct.

Frava

27 décembre 2007 à 14:11:39

Citation : GomuSan

Oula, plus vous me repondrez et moins je comprends... C'est quoi cet arbre ?

C'est une representation graphique de l'arbre que tu obtiendrais apres avoir parcouru une (et une seule) fois la liste de noms. Il y a tout : les noms ainsi que le nombre de fois qu'ils sont apparus.
Mais bon, si le concept que je t'ai donne te depasse je ne peux pas t'aider car l'implementation ne serait pas a ta portee ... Sache juste que c'est l'algorithme de meilleure complexité pour ton cas.

GomuSan

27 décembre 2007 à 14:15:57

Bon c'est pas la peine, je vais chercher tout seul, sa me fera du bien et au moins j'aurais le merite d'avoir trouvé.

Merci quand meme, et desolé ceux que j'ai un peu embrouillé

Frava

27 décembre 2007 à 14:26:18

Citation : GomuSan

Bon c'est pas la peine, je vais chercher tout seul, sa me fera du bien et au moins j'aurais le merite d'avoir trouvé.

Oups

Bonne chance

GomuSan

27 décembre 2007 à 14:27:13

Merci, je vous tiens au courant de ma solution

Frava

27 décembre 2007 à 19:23:45

L'algo de l'arbre devrait etre quelque chose du genre :

typedef struct noeud
{
int n; /* nombre de fois que ce noeud a terminé un nom */
struct noeud* t[26]; /* un noeud fils par lettre de l'alphabet */
} noeud;
noeud* nouveau_noeud ()
{
int i;
noeud *p = (noeud*) malloc (sizeof (noeud));
p->n = 0;
for (i=0; i<26; i++) p->t[i] = NULL;
return p;
}
void ajoute_nom (noeud *n, char *s )
{
if (s == NULL || n == NULL)
{
return;
}
if (s[0] == '\0')
{
n->n++ ;
return; /* On est arrivés au bout du nom */
}
if ( n->t[s[0] - 'a'] == NULL )
{
n->t[ s[0] - 'a' ] = nouveau_noeud();
}
ajoute_nom (n->t[ s[0] - 'a' ] ,&(s[1]));
}
}

Si on veut pouvoir lire un dictionnaire ou des noms avec accent ou majuscules il faudrait utiliser une liste chainee triee a la place du tableau de 26 cases

Frava

28 décembre 2007 à 20:00:53

Je me demandais si tu avais reussit a trouver GomuSan. Si ce n'est pas le cas, essaie ca :

#include <stdlib.h>
#include <stdio.h>
typedef struct noeud
{
int n; /* nombre de fois que ce noeud a terminé un nom */
struct noeud* t[26]; /* un noeud fils par lettre de l'alphabet */
} noeud;
noeud* nouveau_noeud ()
{
int i;
noeud *p = (noeud*) malloc (sizeof (noeud));
p->n = 0;
for (i=0; i<26; i++) p->t[i] = NULL;
return p;
}
void ajouter_nom (noeud *n, char *s )
{
if (s == NULL || n == NULL)
{
return;
}
if (s[0] == '\0')
{
n->n++ ;
return; /* On est arrivés au bout du nom */
}
if ( n->t[s[0] - 'a'] == NULL )
{
n->t[ s[0] - 'a' ] = nouveau_noeud();
}
ajouter_nom (n->t[ s[0] - 'a' ] ,&(s[1]));
}
int nombre_d_occurrences (noeud *n, char *s)
{
int r;
if (n == NULL || s == NULL)
r = 0 ;
else if (s[0] == '\0')
r = n->n;
else if (n->t[s[0] - 'a'] == NULL)
r = 0;
else
r = nombre_d_occurrences(n->t[s[0] - 'a'], &s[1]);
return r;
}
void afficher_arbre (noeud *n)
{
int i;
int vide = 1;
if (n == NULL) return;
printf ("(%d", n->n);
for (i = 0; i < 26; i++)
{
if (n->t[i] == NULL) continue;
if (vide) printf (",");
vide = 0;
printf ("%c", 'a' + i);
afficher_arbre( n->t[i] );
}
printf (")");
}
int main ()
{
const int N = 7;
char *liste [] = {"julien", "jean", "jean", "julien", "julie", "julien", "juliette"};
noeud *racine = nouveau_noeud();
int i = 0;
for (i = 0; i < N; i++)
{
ajouter_nom (racine, liste[i]);
}
/* On affiche la liste de noms */
printf ("Liste =");
for (i = 0; i < N; i++) printf (" %s",liste[i]);
printf ("\n\n");
/* On affiche l'arbre resultant */
printf ("Arbre resultant = ");
afficher_arbre(racine);
printf ("\n\n");
/* On affiche quelques recherches de noms */
printf ("Quelques recherches sur les noms :\n");
printf ("juliette = %d\n", nombre_d_occurrences(racine,"juliette"));
printf ("julien = %d\n", nombre_d_occurrences(racine,"julien"));
printf ("julie = %d\n", nombre_d_occurrences(racine,"julie"));
printf ("toto = %d\n", nombre_d_occurrences(racine,"toto"));
printf ("jean = %d\n", nombre_d_occurrences(racine,"jean"));
}

Comme je l'ai dis precedemment, il faut absolument gerer des listes triees a la place du tableau pour les fils si l'on veut faire quelque chose de plus general, mais bon, l'avantage du tableau c'est que ca m'a prit une petite demi-heure a coder

GomuSan

30 décembre 2007 à 18:22:20

En fait, ma solution marchait pas :S
Mais j'ai toujours pas compris comment fonctionner ton tableau ?
Moi sa serait pour un tableau a 10 000 lignes

Frava

30 décembre 2007 à 18:46:46

Citation : GomuSan

Mais j'ai toujours pas compris comment fonctionner ton tableau ?

Hum, la structure de cette base de donnees de mots n'est pas un tableau mais un arbre. Et comment l'expliquer !!? Ce serait comme si tu avais un tableau avec une case pour chaque lettre de l'alphabet. Quand tu veux ajouter un mot dans la base de donnees, tu regardes sa premiere lettre, tu selectionnes la case correspondant a cette lettre et tu mets le reste du mot (c'est a dire le mot sans sa premiere lettre) dans cette case, sauf que chaque case fonctionne de la meme manniere (et possede donc aussi un tableau avec une case par lettre de l'alphabet), Et le tour est joué

Est-ce assez clair comme explication ?

Citation : GomuSan

Moi sa serait pour un tableau a 10 000 lignes

Tu veux dire une liste de 10000 mots dans un fichier ?

GomuSan

30 décembre 2007 à 20:47:56

Exact une liste de 10000 mots que je stocke dans un tableau de structure.

Ok j'ai capté ton arbre mais bon j'aime pas trop cette solution. Doit y avoir un autre moyen plus ordinaire

aurek

30 décembre 2007 à 21:25:37

Salut !

Je sais pas si ma solution va te convenir, mais je la mets quand même.

Comme je l'ai dit dans mes précédents post, je pensais faire une structure avec nom et le compteur associé à ce nom. Alors voilà le code que j'ai fait pour mettre en place cette idée :

#include <stdio.h>
#include <string.h>
#define NBELE 10
typedef struct
{
char nom[20];
int nb;
}
Pers;
int recherche(Pers *pers, char *nom, int nb);
int chargeTab(Pers *pers, char *nomFichier);
void test(void);
int recherche(Pers *pers, char *nom, int nb)
{
int i;
for(i = 0; i < nb; i++)
if(strcmp(nom, pers[i].nom) == 0)
return i;
return -1;
}
int chargeTab(Pers *pers, char *nomFichier)
{
char nom[20] = "";
int i = 0, ret;
FILE *fichier = fopen(nomFichier, "r");
if(fichier == NULL)
return -1;
fscanf(fichier, "%s%*c", nom);
while(feof(fichier) == 0)
{
/* On cherche si le prenom est deja dans le tableau */
ret = recherche(pers, nom, i);
/* Si prenom pas deja present, on le rajoute */
if(ret == -1)
{
strcpy(pers[i].nom, nom);
pers[i].nb = 1;/* On fixe le compteur a 1 */
i++;/* On ajoute une case utilisée à notre tableau */
}
/* Sinon on ajoute un à son compteur */
else
pers[ret].nb++;
fscanf(fichier, "%s%*c", nom);
}
fclose(fichier);
return i;/* On retourne le nombre de case du tableau */
}
void test(void)
{
Pers pers[NBELE];
int i, ret;
ret = chargeTab(pers, "liste.txt");
if(ret != -1)
for(i = 0; i < ret; i++)
printf("%s %d\n", pers[i].nom, pers[i].nb);
else
printf("erreur à l'ouverture du fichier\n");
}

Fichier texte associé

albert
jean
toto
albert
arnaud
jean
etienne

Resultat :

albert 2

jean 2

toto 1

arnaud 1

etienne 1

Press ENTER to continue.

Si tu n'as pas compris poses des questions.

Frava

30 décembre 2007 à 21:43:26

Citation : GomuSan

Ok j'ai capté ton arbre mais bon j'aime pas trop cette solution.

Libre a toi de choisir l'algo que tu vas implementer. Excuse moi de preferer l'efficacité

Edit: Oh!!! aurek aussi a craqué et a implementé sa solution

Je vais donc lui poser la question. Trouves-tu la solution de l'arbre si etrange que ca ?

GomuSan

31 décembre 2007 à 12:14:00

Salut, merci
Mais perso, j'aurais jamais trouvé un truc aussi poussé.

Y a un truc que je comprends pas c'est ça

fscanf(fichier, "%s%*c", nom);

Sa veut dire quoi %s%*c et pourquoi return -1 ?

Frava

31 décembre 2007 à 13:55:48

Citation : GomuSan

Sa veut dire quoi %s%*c et pourquoi return -1 ?

"%s%*c" : en lisant un peu la doc de fscanf tu devrais pouvoir comprendre

"return -1" : Un nombre de cases negatif ca veut dire quoi d'apres toi ?

aurek

31 décembre 2007 à 13:56:35

Pourquoi -1 ? en fait, dans ma fonction de recherche, je retourne soit la position dans le tableau si le nom existe déjà pour pouvoir par la suite ajouter 1 dans son compteur sinon, je retourne -1 comme ça, je sais qu'il faut que je le rajoute dans le tableau.

%s%*c permet de supprimer le '\n' final qui se trouve dans la chaîne une fois que je l'ai lu dans le fichier.

@Frava: je regarde ta solution pour essayer de la comprendre. Les arbres sont un mystère pour moi. Pour son étrangeté, ben au début je vais dire que j'ai eu du mal à comprendre le schéma que tu avais fait. Mais après, c'est une solution comme une autre. Même si c'est la solution la plus performante.

-ed-

31 décembre 2007 à 14:05:26

Citation : aurek

%s%*c permet de supprimer le '\n' final qui se trouve dans la chaîne une fois que je l'ai lu dans le fichier.

Et si il n'y a pas de '\n' (ça peut arriver avec la dernière ligne) ? Il se passe quoi ? Simple question, je ne connais pas fscanf(), et je ne tiens pas à le connaitre...

Music only !

1 2 >>