Creation arbre avec liste

Marsh Posté le 27-12-2005 à 16:40:09

Bonjour

Je dois créer un arbre avec une liste contenant un code morse déja rempli.

Exemple:
Ma liste contient par exemple
A .-
B -...
C -.-.
etc ....

Déclaration de l'arbre

Code :

struct noeud
{
char lettre;
struct noeud* fdroit;
struct noeud* fgauche;
}
typedef struct noeud Noeud;
typedef Noeud* arbre;

Avec cette déclaration, a chaque fois que je vais par exemple sur le fils gauche je dois l'aasocier à un "-" sous entendu pr pouvoir faire mes recherches sur la liste et récupérer la lettre correspondante.
Pour fils droit je dois "."

Je ne sait pas comment faire ou par ou commencé car je sui un peu perdu et compren pas comment faire pr sous entendre que droit c un "." et gauche "-"

Reply

Marsh Posté le 27-12-2005 à 16:40:09

Reply

Marsh Posté le 27-12-2005 à 17:07:22

en clair, ce que tu veux, c'est un arbre dont les feuilles sont des lettres et dont le chemin d'accès correspond à leur code en morse ?

Message cité 1 fois

Reply

Marsh Posté le 27-12-2005 à 17:08:01

theshockwave a écrit :

en clair, ce que tu veux, c'est un arbre dont les feuilles sont des lettres et dont le chemin d'accès correspond à leur code en morse ?

Oui c'est exactement ça

Reply

Marsh Posté le 27-12-2005 à 17:14:40

Je ne m'y connais pas en morse, mais j'imagine qu'il n'y aura pas une lettre associée à chaque noeud ...

normalement, avec un algorithme récursif, tu devrais t'en sortir. Tu prends chacune des lettres et tu appliques ton algo à son chemin. Ton algo devra simplement s'assurer que tout noeud par lequel il passe est créé (et le créer s'il ne l'est pas) et positionner la lettre en question au bout du chemin.
essaye de faire les premiers pas, on t'aidera si tu as du mal

Message cité 2 fois

Reply

Marsh Posté le 27-12-2005 à 17:17:41

theshockwave a écrit :

Je ne m'y connais pas en morse, mais j'imagine qu'il n'y aura pas une lettre associée à chaque noeud ...

normalement, avec un algorithme récursif, tu devrais t'en sortir. Tu prends chacune des lettres et tu appliques ton algo à son chemin. Ton algo devra simplement s'assurer que tout noeud par lequel il passe est créé (et le créer s'il ne l'est pas) et positionner la lettre en question au bout du chemin.
essaye de faire les premiers pas, on t'aidera si tu as du mal

jvé essayé merci

Reply

Marsh Posté le 27-12-2005 à 17:40:01

theshockwave a écrit :

Je ne m'y connais pas en morse, mais j'imagine qu'il n'y aura pas une lettre associée à chaque noeud ...

normalement, avec un algorithme récursif, tu devrais t'en sortir. Tu prends chacune des lettres et tu appliques ton algo à son chemin. Ton algo devra simplement s'assurer que tout noeud par lequel il passe est créé (et le créer s'il ne l'est pas) et positionner la lettre en question au bout du chemin.
essaye de faire les premiers pas, on t'aidera si tu as du mal

J'ai un soucis j'arrive pas à continuer à partir d'ici en je ne sais pas comment faire pr extraire un caractere d'une chaine

voila ce que j'ai :

Code :

boolean estVide(Arbre a)
{
if (a==NULL) return vrai;
else return faux;
}
Arbre* Creer(Arbre* a, Liste l)
{
Arbre acre=NULL;
int i;
if estVide(*a)
{
acre = (Arbre) malloc(sizeof(Noeud)); // racine de l'arbre
acre->lettre =' '; // caractere à la racine espace
acre->fdroit=NULL;
acre->fgauche=NULL;
*a = acre;
}
else
{
while (l!=NULL)
{
i=0;
while ((l->morse+i)!='\0') // j'ai un soucis ici pr extraire
{
}
}
}
}

Reply

Marsh Posté le 27-12-2005 à 17:45:49

attention : NULL est une valeur particulière désignant une adresse invalide pour un pointeur. Dans ta fonction estVide, tu la compares à ta structure de noeud et ca n'a pas de sens.

là, tu pars sur une base itérative, je ne dis pas que c'est impossible à faire, mais ce sera probablement moins naturel que de l'écrire en récursif. quel est le type de l ? Liste n'est pas un type standard

(pour ton problème d'extraction, il s'agit simplement de parcourir la chaine, normalement : tu prends un pointeur sur le premier élément puis tu le fais avancer jusqu'à rencontrer le 0 terminal)

Message cité 1 fois

Reply

Marsh Posté le 27-12-2005 à 17:53:35

theshockwave a écrit :

attention : NULL est une valeur particulière désignant une adresse invalide pour un pointeur. Dans ta fonction estVide, tu la compares à ta structure de noeud et ca n'a pas de sens.

là, tu pars sur une base itérative, je ne dis pas que c'est impossible à faire, mais ce sera probablement moins naturel que de l'écrire en récursif. quel est le type de l ? Liste n'est pas un type standard

(pour ton problème d'extraction, il s'agit simplement de parcourir la chaine, normalement : tu prends un pointeur sur le premier élément puis tu le fais avancer jusqu'à rencontrer le 0 terminal)

Code :

Arbre* Creer(Arbre* a, Liste l)
{
Arbre acre=NULL;
Arbre g =NULL;
Arbre d = NULL;
char* p;
int i;
if estVide(*a)
{
acre = (Arbre) malloc(sizeof(Noeud)); // racine de l'arbre
acre->lettre =' '; // caractere à la racine espace
acre->fdroit=NULL;
acre->fgauche=NULL;
*a = acre;
}
else
{
while (l!=NULL)
{
i=0;// pr parcourir la chaine morse enfin je croi
p = l->morse;
while (*p != '\0')
{
if (*p=='-')
{
if (acre->fgauche==NULL)
{
g = (Arbre) malloc(sizeof(Noeud)); //créer à gauche
g->lettre =' ';
g->fgauche = NULL;
g->fdroit = NULL;
}
acre->fgauche = g;
}
else // c'est un .
{
if (acre->fdroit==NULL)
{
d = (Arbre) malloc(sizeof(Noeud)); //créer à droite
d->lettre =' ';
d->fgauche = NULL;
d->fdroit = NULL;
}
acre->fdroit = d;
}
}
acre->lettre = l->c; // on le copie à l'adrrese de fin
p++;
}
}
}

Le problème du estVide je ne voit pas comment faire pr le résoudre sinon pr le traitement récursif c'est un peu hard pr mon niveau.Dans ce cas, faudra que je modifie les valeurs en param. Je ne sais pas.

Pourrait tu me donnez un coup de main avec ce que je vbien de de présenter

Reply

Marsh Posté le 27-12-2005 à 18:03:21

le estVide comme tu le vois aurait plutôt cette forme là :

Code :

int estVide(Arbre *noeud)
{
return noeud == NULL;
}

le récursif a un nom qui peut faire peur quand on n'en a pas fait, mais tu verras, ce n'est pas si compliqué que ca

sinon, diverses remarques :
* p n'est pas incrémenté dans el bon bloc => boucle infinie.
* ta liste de chaines de caractères n'est pas parcourue (pas d'incrémentation du pointeur sur le premier élément)
* il manque le return pour ton arbre
* acre vaut NULL quand tu t'embarques dans ta création d'arbre.
* Comment vas-tu remonter à la racine de l'arbre après avoir fait ton parcours pour la première lettre ?

Reply

Marsh Posté le 27-12-2005 à 18:05:30

Avec les modifs

Code :

#include "arbre.h"
boolean estVideA(Arbre* a)
{
return a==NULL;
}
Arbre* Creer(Arbre* a, Liste l)
{
Arbre acre=NULL;
Arbre g =NULL;
Arbre d = NULL;
char* p;
int i;
if (estVideA(*a))
{
acre = (Arbre) malloc(sizeof(Noeud)); // racine de l'arbre
acre->lettre =' '; // caractere à la racine espace
acre->fdroit=NULL;
acre->fgauche=NULL;
}
else
{
acre=*a;
while (l!=NULL)
{
i=0;// pr parcourir la chaine morse enfin je croi
p = l->morse;
while (*p != '\0')
{
if (*p=='-')
{
if (acre->fgauche==NULL)
{
g = (Arbre) malloc(sizeof(Noeud)); //créer à gauche
g->lettre =' ';
g->fgauche = NULL;
g->fdroit = NULL;
}
acre->fgauche = g;
}
else // c'est un .
{
if (acre->fdroit==NULL)
{
d = (Arbre) malloc(sizeof(Noeud)); //créer à droite
d->lettre =' ';
d->fgauche = NULL;
d->fdroit = NULL;
}
acre->fdroit = d;
}
p++;
}
acre->lettre = l->c; // on le copie à l'adrrese de fin
}
}
return acre;
}

Message édité par rabzouze le 27-12-2005 à 18:09:24

Reply

Marsh Posté le 27-12-2005 à 18:05:30

Reply

Marsh Posté le 27-12-2005 à 18:10:04

pr remonter à la racine je ne compren pas le concept je sais pas comment faire.
Peut tu m'expliquer

Reply

Marsh Posté le 27-12-2005 à 18:14:14

ilf aut simplement que tu prévoies de garder un pointeur sur la racine de côté (ce que tu vas retourner) qui soit une variable différente de celle qui te sert à parcourir ton arbre ...

(note que ton appel à estVideA est invalide puisque l'argument que tu lui donnes est du type "Arbre" alors qu'il attent un "Arbre *" ... inutile de déréférencer ta variable a pour cet appel, donc)

essaye de découper un peu plus le procédé. Ca rendra ton code plus lisible. Avoir ta fonction de création qui itère sur les éléments de la liste et fait ensuite appel à une autre fonction pour l'insertion d'un élément de la liste dans l'arbre serait probablement une bonne chose, non ?

Reply

Marsh Posté le 27-12-2005 à 18:17:00

tu as raison

Reply

Marsh Posté le 27-12-2005 à 18:22:49

coup de pouce :

Arbre Creer(Arbre a, liste l) :
si a est vide :
creerArbre(a)
pour chaque lettre de la liste :
insereMorse(a, lettre.morse, lettre.caractere)
retourne a

insereMorse(Arbre a, chaine morse, char caractere) :
si morse est vide :
a.lettre = caractere
sinon
si le premier caractère de morse est '.' :
si a.droit est vide :
creerArbre(a.droit)
insereMorse(a.droit, morse sans le premier caractère, caractere)
sinon
si a.gauche est vide :
creerArbre(a.gauche)
insereMorse(a.gauche, morse sans le premier caractère, caractere)

voilà en gros le procédé que tu devrais avoir pour du récursif

Edit : je te l'accorde, ce n'est pas très formel ... mais c'est juste pour présenter brièvement l'idée. A toi d'écrire ca en C ... Attention aux types (je me suis permis quelques écarts de ce point de vue là)

Message cité 1 fois
Message édité par theshockwave le 27-12-2005 à 18:24:47

Reply

Marsh Posté le 27-12-2005 à 18:33:36

theshockwave a écrit :

coup de pouce :

Arbre Creer(Arbre a, liste l) :
si a est vide :
creerArbre(a)
pour chaque lettre de la liste :
insereMorse(a, lettre.morse, lettre.caractere)
retourne a

insereMorse(Arbre a, chaine morse, char caractere) :
si morse est vide :
a.lettre = caractere
sinon
si le premier caractère de morse est '.' :
si a.droit est vide :
creerArbre(a.droit)
insereMorse(a.droit, morse sans le premier caractère, caractere)
sinon
si a.gauche est vide :
creerArbre(a.gauche)
insereMorse(a.gauche, morse sans le premier caractère, caractere)

voilà en gros le procédé que tu devrais avoir pour du récursif

Edit : je te l'accorde, ce n'est pas très formel ... mais c'est juste pour présenter brièvement l'idée. A toi d'écrire ca en C ... Attention aux types (je me suis permis quelques écarts de ce point de vue là)

Pourrais tu me dire à que représente creerArbre. A moins que ce soit la meme que creer
Merci pr le code

Reply

Marsh Posté le 27-12-2005 à 18:34:43

C'est bon j'ai compris

Reply

Marsh Posté le 27-12-2005 à 18:35:06

creerArbre serait en fait une méthode d'allocation et d'initialisation d'un arbre (mettre les fils à NULL est une étape à ne pas oublier )

Message cité 1 fois

Reply

Marsh Posté le 27-12-2005 à 18:36:27

Mici

Reply

Marsh Posté le 27-12-2005 à 18:36:38

je v faire la traduction et te montrer

Reply

Marsh Posté le 27-12-2005 à 18:53:37

theshockwave a écrit :

creerArbre serait en fait une méthode d'allocation et d'initialisation d'un arbre (mettre les fils à NULL est une étape à ne pas oublier )

Voila j'ai fini peut tu y jeter un coup d'oeil STP

Code :

#include "arbre.h"
boolean estVideA(Arbre* a)
{
return a==NULL;
}
void creerArbre(Arbre* a)
{
Arbre p=NULL;
p = (Arbre) malloc(sizeof(Noeud)); // racine de l'arbre
p->lettre =' '; // ????? C'est bon si je met un espace pr initialiser
p->fdroit=NULL;
p->fgauche=NULL;
*a=p;
}
void insereMorse(Arbre* a,char* morse,char car)
{
char* p = morse;
if (strcmp(morse,"" )==0) // pr dire que c'est egale
a->lettre=car;
else
{
if (*p=='.')
{
if (estVideA(a->fdroit))
creerArbre(a->fdroit);
insereMorse(a->fdroit,*(p++),car);
}
else
{
if (estVideA(a->fgauche))
creerArbre(a->fgauche);
insereMorse(a->fgauche,*(p++),car);
}
}
}
Arbre* creer(Arbre* a,Liste l)
{
if (estVideA(a))
{
creerArbre(a);
}
else
{
while (l!=NULL)
{
insereMorse(a,l->morse,l->c);
}
}
return a;
}

Merci

Reply

Marsh Posté le 27-12-2005 à 20:59:08

awww ... je me suis fourvoyé en relisant ton code ... Je me suis fait avoir par le typedef ... désolé

Erm, pour éviter les ennuis, soit tu remplaces Arbre par Noeud dans ce fichier, soit tu ajoutes en début de fichier (ou dans arbre.h) :

Code :

typedef Noeud Arbre;

(auquel cas tu devras garder en tête la différence qu'il y a à mettre une majuscule à Arbre ou non, ce qui n'est pas terrible pour la lisibilité)

pour créerArbre, il faut que cette fonction puisse modifier l'argument qu'on lui passe dans le contexte de la fonction appelante. Il faut donc passer un pointeur sur le pointeur d'arbre que tu désires modifier :

Code :

void creerArbre(Noeud **a)
{
Arbre p=NULL;
p = malloc(sizeof(Noeud)); // pas de cast sur un malloc
p->lettre =' '; // a toi de voir en fonction de l'énoncé
p->fdroit=NULL;
p->fgauche=NULL;
*a=p;
}

j'en profite pour te refaire ta fonction estVide() :

Code :

int estVide(Noeud *a)
{
return a == NULL;
}

Pour la fonction d'insertion, j'espère que tu as saisi le principe en l'écrivant ... En tout cas, on ne fait pas un strcmp pour voir si on a atteint la fin, mais on regarde simplement si la valeur pointée est nulle. Attention aux déréférencements, par contre : tu changes le type. Tu dois bien voir que p est du même type que morse, donc si tu déréférence p au moment où tu le passes en paramètre à ta fonction, alors tu n'as pas le type attendu
Ensuite, modifier morse directement ne modifiera pas les données du contexte appelant, donc créer une variable p ne sert pas vraiment

Code :

void insereMorse(Noeud* a, char* morse, char car)
{
if(*morse==0) // si morse pointe sur le caractère de fin de chaine
a->lettre=car;
else
{
if (*morse=='.')
{
if (estVideA(a->fdroit))
creerArbre(a->fdroit);
insereMorse(a->fdroit, p+1, car);
}
else
{
if (estVideA(a->fgauche))
creerArbre(a->fgauche);
insereMorse(a->fgauche, p+1, car);
}
}
}

et maintenant, pour la fonction elle-même, j'ai de gros doute sur la manière dont tu parcours ta liste (et d'ailleurs, tu n'as toujours pas répondu à ma question à ce sujet : où est la définition de Liste ?)

Message cité 1 fois

Reply

Marsh Posté le 29-12-2005 à 17:24:48

theshockwave a écrit :

awww ... je me suis fourvoyé en relisant ton code ... Je me suis fait avoir par le typedef ... désolé

Erm, pour éviter les ennuis, soit tu remplaces Arbre par Noeud dans ce fichier, soit tu ajoutes en début de fichier (ou dans arbre.h) :

Code :

typedef Noeud Arbre;

(auquel cas tu devras garder en tête la différence qu'il y a à mettre une majuscule à Arbre ou non, ce qui n'est pas terrible pour la lisibilité)

pour créerArbre, il faut que cette fonction puisse modifier l'argument qu'on lui passe dans le contexte de la fonction appelante. Il faut donc passer un pointeur sur le pointeur d'arbre que tu désires modifier :

Code :

void creerArbre(Noeud **a)
{
Arbre p=NULL;
p = malloc(sizeof(Noeud)); // pas de cast sur un malloc
p->lettre =' '; // a toi de voir en fonction de l'énoncé
p->fdroit=NULL;
p->fgauche=NULL;
*a=p;
}

j'en profite pour te refaire ta fonction estVide() :

Code :

int estVide(Noeud *a)
{
return a == NULL;
}

Pour la fonction d'insertion, j'espère que tu as saisi le principe en l'écrivant ... En tout cas, on ne fait pas un strcmp pour voir si on a atteint la fin, mais on regarde simplement si la valeur pointée est nulle. Attention aux déréférencements, par contre : tu changes le type. Tu dois bien voir que p est du même type que morse, donc si tu déréférence p au moment où tu le passes en paramètre à ta fonction, alors tu n'as pas le type attendu
Ensuite, modifier morse directement ne modifiera pas les données du contexte appelant, donc créer une variable p ne sert pas vraiment

Code :

void insereMorse(Noeud* a, char* morse, char car)
{
if(*morse==0) // si morse pointe sur le caractère de fin de chaine
a->lettre=car;
else
{
if (*morse=='.')
{
if (estVideA(a->fdroit))
creerArbre(a->fdroit);
insereMorse(a->fdroit, p+1, car);
}
else
{
if (estVideA(a->fgauche))
creerArbre(a->fgauche);
insereMorse(a->fgauche, p+1, car);
}
}
}

et maintenant, pour la fonction elle-même, j'ai de gros doute sur la manière dont tu parcours ta liste (et d'ailleurs, tu n'as toujours pas répondu à ma question à ce sujet : où est la définition de Liste ?)

Excuse je rempli ma liste a partir d'un fichier je v tenvoyé le code que j'ai reussi a faire pour la liste juste un soucis avec le ajout kant je le fait a part tu verra c un pe brouillon mais ca fontionne

fichier typeliste.h

Code :

#ifndef TYPELISTE_H
#define TYPELISTE_H
#include <stdio.h>
#include <stdlib.h>
struct element
{
char c;
char *morse;
struct element* suiv;
};
typedef struct element Element;
typedef Element* Liste;
#endif

fichier liste.c

Code :

#include "liste.h"
boolean estVide(Liste l)
{
if (l==NULL) return vrai;
else return faux;
}
void Ajouter(char c,char *m,Liste *l)
{
Liste p=NULL;
Liste q=NULL;
if (estVide(*l)==vrai)
{
p= (Liste) malloc(sizeof(Element));
p->c=c;
p->morse=(char *)malloc((strlen(m)+1)*sizeof(char));
strcpy(p->morse,m);
p->suiv=NULL;
*l=p;
}
else
{
p=Precedent(c,*l);
q= (Liste) malloc(sizeof(Element));
q->c=c;
q->morse=(char *)malloc((strlen(m)+1)*sizeof(char));
strcpy(q->morse,m);
q->suiv=p->suiv;
p->suiv=q;
}
}
Liste InitListe(char *Fcode)
{
FILE *fp;
char c;
char ligne[100];
char car;
int j;
char *code;
Liste l = NULL;
fp=fopen(Fcode,"r" );
if(fp==NULL) printf("Fichier existe pas\n" );
else
{
printf("Initliste" );
c=fscanf(fp,"%c %s\n",&car,ligne);
while(c!=EOF)
{
j=strlen(ligne)+1;
code=(char*) malloc(sizeof(char)*j);
strcpy(code, ligne);
/***Ajoute sur liste ****/
Ajouter(car,code,&l);
/***************************/
printf("Initliste Ajouter" );
c=fscanf(fp,"%c %s\n",&car,ligne);
}
fclose(fp);
}
Afficher_liste(l);
return l;
}
Liste Precedent(char c,Liste l) // renvoi l'element precedent c
{
Liste q,prec;
prec=l;
q=l->suiv;
while(q!=NULL && ((char)q->c) < ((char)c))
{
prec=q;
q=q->suiv;
}
return prec;
}
int position(char c,char* m,Liste l)
{
int i=0;
while (l!=NULL)
{
if (c==l->c && strcmp(l->morse,m)==0) return i;
i++;
l=l->suiv;
}
return -1;
}
void Afficher_liste(Liste l)
{
int k;
Liste p = l;
while(l)
{
printf("Element : %c %s ",l->c,l->morse);
k = position(l->c,l->morse,p);
if (k==-1) printf("Element n'existe pas" );
printf(" (%d)\n",k);
l=l->suiv;
}
}
char RechercheLettreListe(char *m,Liste l)
{
Liste p = l;
while(p)
{
if (strcmp(p->morse,m)==0) return p->c;
p=p->suiv;
}
return '0';
}
char* RechercheMorseListe(char c,Liste l)
{
Liste p = l;
while(p)
{
if (p->c==c) return p->morse;
p=p->suiv;
}
return NULL;
}
void suprAvecLettre(char c,Liste *l)
{
Liste p,prec;
if (estVide(*l)==faux)
{
p=*l;
if (p->c==c)
{
p=*l;
*l=p->suiv;
free(p);
}
else
{
prec=Precedent(c,*l);
if (((prec->suiv==NULL)) || (prec->suiv->c)!=c )
{
printf("La lettre tapé n'est pas dans la liste" );
}
else
{
p=prec->suiv;
prec->suiv=p->suiv;
free(p);
}
}
}
else
{
printf("La Liste est vide" );
}
}
void TraduireEnMorse(Liste l,char *Fsource,char *Fdest)
{
/*****Travaile sur fichier code*///
FILE *Fcode;
char *c;
char ligne[100];
int i;
char *recupMorse;
/**********************************/
/******Fichier convert****************/
FILE *FenMorse;
/******************************/
Fcode=fopen(Fsource,"r" );
FenMorse=fopen(Fdest,"w" );
if(Fcode==NULL) printf("Fichier existe pas\n" );
else
{
while((c=fgets(ligne,100,Fcode))!=NULL)
{
i=0;
// while((ligne[i]!='\0') && (i<strlen(ligne)))
while(ligne[i]!='\0')
{
if(ligne[i]==' ')
{
fprintf(FenMorse," * " );
}
else if (ligne[i]=='\n')
{
fprintf(FenMorse,"\n" );
}
else
{
recupMorse = RechercheMorseListe(ligne[i],l);
fprintf(FenMorse,"%s$",recupMorse);
}
i++;
}
}
}
fclose(Fcode);
fclose(FenMorse);
}

fichier qui teste princliste.c

Code :

#include "liste.h"
#define FICHIER "code.txt"
#define FICHIER2 "Traduit.txt"
#define FICHIER3 "ConvertMorse.txt"
main()
{
Liste l = InitListe(FICHIER);
Afficher_liste(l);
TraduireEnMorse(l,FICHIER2,FICHIER3);
}

Il ya aussi le fichier liste.h mais bon tu sait que j'y ai mit seulement les entetes de fonctions voila mnt tu as tout ce que j'ai si tu ne compren pas di le moi pr la liste pr l'arbre par contre jai un blocage mais je verrai
Tiens moi o courant si ca ne tiens pas la route

Reply

Marsh Posté le 29-12-2005 à 17:29:39

Excuse moi en parlant de lhistoire du typedef j'ai ceci

fichier typearbre.h

#ifndef TYPEARBRE_H
#define TYPEARBRE_H

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

struct noeud
{
char lettre;
struct noeud* fdroit;
struct noeud* fgauche;
};

typedef struct noeud Noeud;
typedef Noeud* Arbre;

#endif

tOn code ne fonctionnera pas il y aura des soucisde poiinteurs Type différents avec mon typedef

Reply

Marsh Posté le

Reply

Creation arbre avec liste

Sujets relatifs:

Leave a Replay