Probleme liste chainee

Signaler
Messages postés
3
Date d'inscription
jeudi 4 novembre 2004
Statut
Membre
Dernière intervention
20 novembre 2004
-
Messages postés
3
Date d'inscription
jeudi 4 novembre 2004
Statut
Membre
Dernière intervention
20 novembre 2004
-
Comme je ne vois pas l'arbre au milieu de la foret je m'en remet a vous

C'est un dictionnaire et pour l'instant je ve juste afficher mon arbre bianaire. Mais le programme fonctione correctement pour une liste de 5 mots, puis au dela il me fait un access violation.

typedef struct noeud
{
struct noeud *suivant[26];
int fin_de_mot;
char symbole;
} NOEUD;

void insertion(char mot_a_inserer[80],NOEUD *p)
{

int indice,i;
indice=0;
char lettre;
int CODE_ASCII;
NOEUD *nouveau;
lettre=mot_a_inserer[indice];
CODE_ASCII=lettre;
NOEUD *suivant[CODE_ASCII];
if (mot_a_inserer[1]=='\0')
{
return ;
}

else
{
if (p->suivant[CODE_ASCII]==NULL)
{
printf("le caractere %c n'existe pas\n",mot_a_inserer[indice]);

nouveau=(NOEUD*)malloc (sizeof(NOEUD));
p->suivant[CODE_ASCII] = nouveau;
for (i=65;i<=90;i++)
nouveau->suivant[i]=NULL;
nouveau->symbole=mot_a_inserer[indice];
if(mot_a_inserer[indice+1]!='\0')
nouveau-> fin_de_mot=0;
else
nouveau-> fin_de_mot=1;
p= nouveau;
}
else
p=p->suivant[CODE_ASCII];
supprimer_premiere_lettre(mot_a_inserer,mot_a_inserer);
if (mot_a_inserer[indice]!='\0')
printf("nouveau mot a inserer: %s\n",mot_a_inserer);

insertion(mot_a_inserer,p) ;

}




}

La connerie est universel

6 réponses

Messages postés
1267
Date d'inscription
mercredi 1 janvier 2003
Statut
Membre
Dernière intervention
28 février 2007
3
Au vu de ton code tu tiens apparemment à rester en C pur, alors déjà, quand tu dis :

typedef struct noeud
{
struct noeud *suivant[26];
int fin_de_mot;
char symbole;
} NOEUD;

tu peux plus simplement dire :

typedef struct
{
NOEUD *suivant[26];
int fin_de_mot;
char symbole;
} NOEUD;

A part ça, toujours au niveau de ton "écriture", on ne met d'habitude que les constantes en majuscules, donc on créerais plutôt une structure Noeud et non NOEUD.
Ensuite, tu mets :
struct noeud *suivant[26];

Donc si je traduis, un pointeur vers un tableau de 26 autres noeuds...tu ne voulais pas plutôt faire juste un pointeur vers le noeud suivant??

Ensuite :

void insertion(char mot_a_inserer[80],NOEUD *p)

Je remplacerais le "char mot_a_inserer[80]" par un "char* mot_a_inserer" voire un "const char* mot_a_inserer", sinon pour quelqu'un qui voudra compiler ton prog en C++ (ce que je te conseille de faire d'ailleurs), ça va couiller...vu qu'en général on ne passe pas un tableau d'exactement 80 caractères non? ;)

Ensuite, tu peux condenser :

int indice,i;
indice=0;

en int indice=0, i;

"lettre=mot_a_inserer[indice];
CODE_ASCII=lettre;" -> ta variable "lettre" te sert après? sinon c'est redondant...

Bon pour la suite j'ai la flemme de chercher à comprendre le code...faudrait que tu corriges pas mal de trucs comme ça, et surtout que tu mettes des commentaires ;)
Et puis aussi j'ai vu un malloc() mais pas de free() correspondant : c'est un memory leak, faut éviter, tu gaspilles de la mémoire...

---------------------------------------------------------
Patience et longueur de temps font plus que force ni que rage....
Coucous flingueurs 3D : http://www.freewebs.com/cf3d/
Messages postés
2070
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
3 juillet 2006
8
ton problème vient de ton tableau sur les noeuds suivant :
struct noeud *suivant[26];
le 26 c'est pour les 26 lettres de l'alphabet je suppose ?

les indices du tableau vont de 0 à 25 et toi tu essaye d'y accéder par les codes ASCCi des lettres (de 65 à 90)
for (i=65;i<=90;i++)
nouveau->suivant[i]=NULL;

=> plante irrémédiablement

si lettre est entre 'A' et 'Z', l'indice est lettre-'A'
si lettre est entre 'a' et 'z', l'indice est lettre-'a'
Messages postés
3
Date d'inscription
jeudi 4 novembre 2004
Statut
Membre
Dernière intervention
20 novembre 2004

c'est exactement ce dont je me suis rendu compte

comme apparemment un tableau commence de 0 à n.
Dans mon cas je suis obligé de prendre l'ascii de ma lettre et de lui retranche 64. Comme je ne gere que des majuscules.

Le C fait directement la converstion lettre en ASCCII
c'est a dire que si je passe tableau['A'] cela representerais la 64eme case de mon tableua? c'est ce que je'ai cru comprendre lors de mes recherches.

Merci de vos reponses et de vous etre attarde sur le sujet.

La connerie est universel
Messages postés
2070
Date d'inscription
mardi 22 avril 2003
Statut
Membre
Dernière intervention
3 juillet 2006
8
oui faire tableau['A'] est équivalent à tableau[65] mais c'est la 66 ème case tu tableau !!!
Messages postés
1267
Date d'inscription
mercredi 1 janvier 2003
Statut
Membre
Dernière intervention
28 février 2007
3
Et puis je le répète mais pense à mettre un free() qui correspond à ton malloc()...

---------------------------------------------------------
Patience et longueur de temps font plus que force ni que rage....
Coucous flingueurs 3D : http://www.freewebs.com/cf3d/
Messages postés
3
Date d'inscription
jeudi 4 novembre 2004
Statut
Membre
Dernière intervention
20 novembre 2004

Voila l'ensemble de mon programme de gestion de mon arbre qui regroupe une fonction de recherche d'un mot dans l'arbre une fonction pour tout mettre en majuscules et une fonction pour inserer mes noeuds. et une fonction pour détruire l'arbre.

Le programme fonctionne correctement

Mais j'ai du mal a utiliser les pointeurs du coup j'ai fait passer en argument dans mes fonctions de recherche, un int indice si quelqu'un avait le courage de regarder sans se bruler les yeux. merci

#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include "structure.h"
#define MAX 80
#define ASCII_A 65
#define ASCII_Z 90
#define CTE_CAR 65
#define SORTIE 1
#define NB_ARGUMENT 2

/*
**++
** FUNCTIONAL DESCRIPTION:
**
** fonction qui change la casse du mot extrait de la liste, afin que tous
** les mots soient en majuscule.
**
** FORMAL PARAMETERS:
**
** en entree elle recoit le mot extrait du fichier texte
**
** RETURN VALUE
** en sortie elle renvoit le meme mot en majuscule
**
**--
*/

void changer_casse(char ligne[MAX],char ligne_modifie[MAX])
{
int caractere;
caractere=0;
while(ligne[caractere]!='\0')
{
ligne_modifie[caractere]=toupper(ligne[caractere]);
caractere++;
}

ligne_modifie[caractere]='\0';
}

/*
**++
** FUNCTIONAL DESCRIPTION:
**
** fonction insertion qui insere un noeud dans l arbre n aire si le noeud
** n existe pas deja
**
** FORMAL PARAMETERS:
**
** en entree elle recoit le mot a inserer ainsi que la position courante
** du pointeur dans l arbre
**
**--
*/



void insertion( char mot_a_inserer[MAX],NOEUD *courant,int indice)
{
int i;
char lettre;
if(indice==0)
changer_casse(mot_a_inserer,mot_a_inserer);
lettre=mot_a_inserer[indice];
//printf("%c",mot_a_inserer[indice]);
if(mot_a_inserer[indice+1]!='\0')
{
if(courant->suivant[lettre-CTE_CAR]==NULL)
{
NOEUD *nouveau;

//Allocation memoire de l espace necessaire pour le mot

nouveau=malloc(sizeof(NOEUD));
courant->suivant[lettre-CTE_CAR]=nouveau;

//Initialisation des noeuds fils

for(i=ASCII_A-CTE_CAR;i<=ASCII_Z-CTE_CAR;i++)
nouveau->suivant[i]=NULL;

//Insertion de la lettre dans le noeud courant

nouveau->symbole=mot_a_inserer[indice];

//Test qui permet de reperer la fin d un mot

nouveau->fin_de_mot=0;

if(mot_a_inserer[indice+1]=='\0')
courant->fin_de_mot=1;

courant=nouveau;
}
else

//Cette attrbution permet de manger le noeud

courant=courant->suivant[lettre-CTE_CAR];
indice++;

//Appelle recursif de la fonction insertion: cela correspond a une descente

//dans l arbre
if(mot_a_inserer[indice+1]=='\0')
courant->fin_de_mot=1;

insertion(mot_a_inserer,courant,indice);
}


}

/*
**++
** FUNCTIONAL DESCRIPTION:
**
** fonction recherche qui permet de parcourir l'arbre
**
** FORMAL PARAMETERS:
**
** en entree elle recoit le mot a rechercher ainsi que la position courante
** du pointeur dans l arbre
**
**--
*/

void recherche(char mot_recherche[80],char mot_affiche[80],NOEUD *courant,int indice,int caractere)
{
char lettre;
int i;

NOEUD *racine;
changer_casse(mot_recherche,mot_recherche);
lettre=mot_recherche[caractere];

//Si le mot a rechercher est different de " "alors

if (mot_recherche[caractere]!='\0')
{

//Si le pointeur correspondant a la lettre existe alors on mange le noeud


if(courant->suivant[lettre-CTE_CAR]!=NULL)
{
courant=courant->suivant[lettre-CTE_CAR];
caractere++;

// on rapelle la fonction recherche en regardant la lettre d'apres

recherche(mot_recherche,mot_affiche,courant,indice,caractere);
}
}


//comme le mot recherche est vide, on parcours tout l'arbre a la recherche d un indicateur de fin de mot
else
{
mot_recherche[caractere-1]='\0';

if(courant!=racine)
{
mot_affiche[indice]=courant->symbole;
mot_affiche[indice+1]='\0';
indice++;

//si on arrive a une fin de mot on affiche le mot
if(courant->fin_de_mot==1)
{
affichage(mot_recherche,mot_affiche);
}
}

//Permet de descendre dans l'arbre ne parcourant les 26 noeud fils
// descente recursive

for(i=ASCII_A-CTE_CAR;i<=ASCII_Z-CTE_CAR;i++)
{
if(courant->suivant[i]!=NULL)

recherche(mot_recherche,mot_affiche,courant->suivant[i],indice,caractere);
}
}
}

//Voici la fonction qui permet de desallouer l'ensemble dees //espaces memoires cree, elle parcours tout mon arbre et une fois //arrive sur un noeud de fin elle le supprime

void effacer_arbre(NOEUD *courant)
{

NOEUD *racine;
int i;
for(i=ASCII_A-CTE_CAR;i<=ASCII_Z-CTE_CAR;i++)
{
if(courant->suivant[i]!=NULL)
effacer_arbre(courant->suivant[i]);
}
free(courant);

}


La connerie est universel