Bonjour à tous !

Je vous fait part ici d'un exercice qui m'a été donné à résoudre. Le principe est de créer un dictionnaire grâce à des listes chainées.

Ce dictionnaire se remplit via la fonction addWord et chaque fin de mot et marqué par le symbole $. Si dans mon dictionnaire j'ai déjà ajouté le mot "MY" et que je souhaite y ajouter "MYTH" la fonction addWord va comparer les caractères un à un. Les 2 premiers caractères de "MY" et "MYTH" correspondent donc on ne fait rien mais ensuite l'algo va comparer le $ (correspondant au fin de mot de "MY") et le "T" de MYTH. Voyant que ces deux caractères ne sont pas égaux addWord va créer un nouveau mot (nw = new word et nl = new letter). On y ajoute donc le "T" et le "H" et on n'oublie pas de finir le mot par un "$".

J'espère avoir été clair dans l'explication de la fonction addWord. Je vous joins le code de cette fonction mais après moulte vérifications je pense l'avoir bien codé.

Voici un schéma de ce que devrait ressembler le dictionnaire :

La raison de mon post n'est donc pas cette fonction mais plutôt le codage d'une fonction permettant d'afficher le dictionnaire. Je voudrais la coder en récursif afin qu'elle parcourt tous les chemins possible et m'affiche tous les mots du dictionnaire. Cependant j'ai beau m'arracher les cheveux je n'arrive pas à passer par tous les chemins. De plus j'ai encore du mal à visualiser correctement la récursivité.

Voici mon code :

void debugTreeLoc(char racine[],t_chain* newElm);

void debugTree(){

	char tab[32]={0};
	//element pour parcourir la liste
	t_chain * actuel = (t_chain*)malloc(sizeof(t_chain));
	actuel = start;
	int i = 0;
	//Tant que je ne tombe pas sur un $
	while(actuel -> caractere != '$')
	{
		tab[i] = actuel->caractere;	//J'incrémente mon tableau de char
		i++;
		actuel = actuel -> nl;
		if(actuel->caractere == '$'){	//si je tombe sur le $
			actuel = actuel -> nw;		//Je passe au nouveau mot
			debugTreeLoc(tab,actuel);
		}


	}


}
void debugTreeLoc(char racine[],t_chain* newElem){
	t_chain * actuel = (t_chain*)malloc(sizeof(t_chain));
	actuel = newElem;
	char tab2[32]={0};
	char * tab3 = (char*)malloc(32*sizeof(char));
	int i = 0;
	int j = 0;
	//J'affiche mon mot jusqu'au $
	for(i = 0; i < strlen(racine); i++)
	{
		printf("%c",racine[i]);
	}
	printf("\n");
	//Je parcours la liste à partir de là où je m'étaits arrêté
	while(actuel -> caractere !='$')
	{
		tab2[j] = actuel -> caractere;	//J'incrémente mon deuxieme tableau
		actuel = actuel -> nl;
		j++;
		if(actuel->caractere == '$'){
			strcpy(tab3,racine);
			strcat(tab3,tab2);		//Je concatène mon ancien tableau avec le nouveau

			actuel = actuel -> nw;	//Je passe à un nouveau mot
			debugTreeLoc(tab3,actuel);	//Je rappelle ma fonction pour afficher le nouveau mot 
		}
	}

}

Je sollicite donc votre aide afin de rendre ce code d'affichage opérationnel !

Merci!

-
Edité par VitamineD 2 novembre 2019 à 14:34:45

A quoi sert le malloc sur le pointeur actuel si c'est pour lui affecter une autre adresse dans la foulée ?

D'où sort la variable start dans la fonction debugTree ? C'est une variable global ? Il serait plus judicieux de la mettre en local et de la passer en paramètre à la fonction. 

Tu n'as pas de point d'arrêt sur ton chaînage. C'est à dire quand j'arrive sur un '$', je vais lire le pointeur nw mais si il n'a rien qu'est qui me dit que je suis à la fin.

PS : tu peux poster la définition de la structure et la fonction addWord.

Indication pour la récursion :

Regarde le dictionnaire suivant

a -- l -- f 
|    |
|    d -- a 
|
j -- a -- c -- k
     |
     o -- e

pour afficher tous les noms, tu dois afficher

• tous ceux qui commencent par "a"
• puis tout ceux qui commencent par "j"

pour afficher tous ceux qui commencent par "a", tu dois afficher

• tous ceux qui commencent par "al"
• tous ceux qui commencent par "ad"

etc.

Ca suggère que tu aies une fonction récursive qui fait afficher tous les mots qui commencent par un certain préfixe, à partir d'un certain noeud.

Pour donner une idée (avec une représentation un peu différente de la tienne, pour changer et te laisser du boulot) :

#include <stdio.h>

struct Noeud {
    char c;
    struct Noeud * next, *alt;
};

// Scusez les macros, c'est pour simplifier l'écriture
// de l'exemple dans le main. W pour word et S pour single letter.

#define W(c,n,a) &(struct Noeud){c,n,a}
#define S(c) W(c, NULL, NULL)

void afficher_mots(char *prefixe, int longueur, struct Noeud *n) {
    if (n == NULL) {
        prefixe[longueur] = '\0';
        printf("%s\n", prefixe);
    }
    else {
        // on passe en revue les alternatives
        for (struct Noeud *a = n; a != NULL; a = a->alt) {
            prefixe[longueur] = a->c;
            afficher_mots(prefixe, longueur+1, a->next);
        }
    }
}

void afficher_dictionnaire(struct Noeud *d) {
    char prefixe[20];
    if (d != NULL) {
        afficher_mots(prefixe, 0, d);
    }
}

int main()
{
   struct Noeud * dictionnaire =
           W('A', W('d', S('a'),
                  W('l', S('f'), NULL)
                   ),
           W('J', W('a', W('c', S('k'), NULL),
                  W('o', S('e'), NULL)
                      ),
           NULL));

    afficher_dictionnaire(dictionnaire);
    return 0;
}

et ça imprime

Ada
Alf
Jack
Joe

PS : la structure de données ci dessu sne permet pas d'avoir, dans le dictionnaire, des mots qui sont préfixes d'autre mots (comme  "john" et "johnny"). C'est pour résoudre ce problème qu'on ajoute un marqueur de fin ($), ce qui permet de leur associer des alternatives

-- j - o - h - n - $
                   |
                   n - y - $

-
Edité par michelbillaud 3 novembre 2019 à 12:06:54

A quoi sert le malloc sur le pointeur actuel si c'est pour lui affecter une autre adresse dans la foulée ?

Effectivement il est possible de se passer du malloc. Comme tu l'as bien deviné l'élément start est déclaré en globale dans mon code et représente le premier élément de la liste chainée. Tout comme toi je l'aurais aussi déclaré en locale mais c'est de cette façon que l'on m'a demandé de coder et donc je la respecte.

Tu n'as pas de point d'arrêt sur ton chaînage. C'est à dire quand j'arrive sur un '$', je vais lire le pointeur nw mais si il n'a rien qu'est qui me dit que je suis à la fin.

Quand j'arrive sur un '$' et qu'il n'engendre pas un nouveau mot, les pointeurs nw et nl sont à NULL. Ce serait cela la condition d'arrêt.

Voici la définition de la structure

typedef struct chainlist{
	char caractere;
	struct chainlist *nl, *nw;
}t_chain;

Quant à la fonction addWord je vous l'ai épargné afin de ne pas trop surcharger le post mais vu que tu me la demande, la voilà. Elle est précédé du prototype et de la déclaration du start et last. Last étant bien sur le dernier élément.

int addWord(char  * string);
t_chain * start;
t_chain * last;

int addWord(char  * string)
{
	if(start == NULL)
	{
		start = (t_chain*)malloc(sizeof(t_chain));
		last = (t_chain*)malloc(sizeof(t_chain));
		//On initialise le start
		start -> nl = NULL;
		start -> nw = NULL;
		start -> caractere = string[0];
		//Start est le seul donc aussi le dernier élément
		last = start;

		int i;
		//On créé les autres éléments
		for(i = 1; i < strlen(string); i++)
		{
			t_chain * newElem = (t_chain*)malloc(sizeof(t_chain));
			newElem -> caractere = string[i];
			newElem -> nw = NULL;
			newElem -> nl = NULL;
			last -> nl = newElem;
			last = newElem;
		}
		//On rajoute l'élément de fin de liste
		t_chain * end = (t_chain*)malloc(sizeof(t_chain));
		last -> nl = end;
		end -> caractere ='$';
		end -> nl = NULL;
		end -> nw = NULL;
		last = end;
		return 0;
	}
	else
	{
		//Création d'un élément nous permettant de parcourir la liste
		t_chain * actuel = (t_chain*)malloc(sizeof(t_chain));
		actuel = start;
		last = actuel;
		int i = 0;
		int counter = 0;
		while(string[i] == (actuel -> caractere))
		{
			last = actuel;
			actuel = actuel -> nl;
			//On regarde si après le caractère de fin il y a un nouveau mot
			if(((actuel -> caractere) == '$') && (actuel -> nw != NULL))
			{
				actuel = actuel -> nw;
			}
			counter ++;
			i++;
		}
		if((actuel -> caractere) == '$')
		{
			//Creation du nouveau mot dans le dico
		last = actuel;

		t_chain * firstNewElem = (t_chain*)malloc(sizeof(t_chain));
		last -> nw = firstNewElem;
		//last -> nl = NULL; Non faux si jamais on commence on début
		firstNewElem -> caractere = string[counter];
		firstNewElem -> nl = NULL;
		firstNewElem -> nw = NULL;
		last = firstNewElem;
		//Si counter == strlen(string) alors pas besoin d'entrer dans la boucle
		if(counter != strlen(string))
		{
			//On commence là où il y a la différence
			for(i = counter+1; i < strlen(string); i++)
			{
				t_chain * newElem = (t_chain*)malloc(sizeof(t_chain));
				//On ajoute le nouveau mot
				last -> nl = newElem;
				newElem -> caractere = string[i];
				newElem -> nw = NULL;
				newElem -> nl = NULL;
				last = newElem;
			}
		}

		//Ajout caractere de fin de chaine
		t_chain * end = (t_chain*)malloc(sizeof(t_chain));
		last -> nl = end;
		end -> caractere = '$';
		end -> nl = NULL;
		end -> nw = NULL;
		last = end;
		return 0;
		}
		//pb si fin de chaine
		else if ((actuel -> caractere) != '$')
		{
			if((last -> nw) == NULL)
			{
				for(i = counter; i< strlen(string); i++)
				{
					//création new word
					t_chain * newElem = (t_chain*)malloc(sizeof(t_chain));
					last -> nw = newElem;
					newElem -> nl = NULL;
					newElem -> nw = NULL;
					newElem -> caractere = string[counter];
					last = newElem;
				}
				//ajout caractere de fin
				t_chain * end = (t_chain*)malloc(sizeof(t_chain));
				last -> nl = end;
				end -> caractere = '$';
				end -> nl = NULL;
				end -> nw = NULL;
				last = end;
				return 0;
			}
			else if((actuel -> nw) != NULL)
			{
				while((actuel -> nw) != NULL)
				{
					actuel = actuel -> nw;
					last = actuel;
				}
				for(i = counter; i< strlen(string); i++)
				{
					//création new word
					t_chain * newElem = (t_chain*)malloc(sizeof(t_chain));
					last -> nw = newElem;
					newElem -> nl = NULL;
					newElem -> nw = NULL;
					newElem -> caractere = string[counter];
					last = newElem;
				}
				//ajout caractere de fin
				t_chain * end = (t_chain*)malloc(sizeof(t_chain));
				last -> nl = end;
				end -> caractere = '$';
				end -> nl = NULL;
				end -> nw = NULL;
				last = end;
				return 0;
			}


		}

	}
}

michelbillaud a écrit:

Indication pour la récursion :

Regarde le dictionnaire suivant

a -- l -- f 
|    |
|    d -- a 
|
j -- a -- c -- k
     |
     o -- e

pour afficher tous les noms, tu dois afficher

• tous ceux qui commencent par "a"
• puis tout ceux qui commencent par "j"

pour afficher tous ceux qui commencent par "a", tu dois afficher

• tous ceux qui commencent par "al"
• tous ceux qui commencent par "ad"

etc.

Ca suggère que tu aies une fonction récursive qui fait afficher tous les mots qui commencent par un certain préfixe, à partir d'un certain noeud.

Merci beaucoup pour ton aide ! J'ai réussi à modifier ton code pour que le miens marche. J'ai encore du mal à visualiser ce qu'il fait concrètement je vais m'y pencher dessus sérieusement !

Par ailleurs si des personnes ont des exercices pour s'entrainer à la récursivité je suis preneur !

-
Edité par VitamineD 3 novembre 2019 à 12:02:59