Salut! Identification

Recherche avancée

arbre binaire de recherche pour décodage de morse en C

Envoyé par Lord of the FLIES 
Ce forum est en lecture seule. C'est une situation temporaire. Réessayez plus tard.
arbre binaire de recherche pour décodage de morse en C
jeudi 26 mars 2015 12:13:58
Salut!
J'essaye de décoder du morse, c'est à dire que j'ai un char avec des '.', des '-' et des '_' (pour les espaces), et que j'aimerais transformer ça en lettres. Au lieu de juste faire un switch avec 26 case, ce qui serait chiant et pas intéressant, je me suit dit que je pourrais m'inspirer de l'arbre morse. C'est un arbre binaire où la branche de droite représente un - et celle de gauche un . et j'aimerais représenter ça avec mon arbre binaire. Ensuite faudrait qu'il suive ce que la chaîne de caractères en char lui dit et quand il y a un _ , il me met la lettre à laquelle il est arrivé dans un autre char.
Du coup, j'ai des notions de base en C, j'ai lu quelques tutos sur l'intertoile et je comprends pas très bien. Vous pourriez m'aider à comprendre comment ça marche?
Merci d'avance,
Lord
Re: arbre binaire de recherche pour décodage de morse en C
jeudi 26 mars 2015 13:13:43
Au lieu de prendre les caractères 3 par 3 et de les analyser avec un tableau de comparaison (ou un switch 26 cases pour les feignants de la BDD qui aiment mettre les valeurs en dur dans le code), tu vas te retrouver à faire 3 niveaux de switch de 3 imbriqués pour représenter les 27 possibilités de .__ à ---
C'est plus compliqué, c'est merdeux parce que là encore t'as trop de données en dur dans ton code, mais c'est peur être plus performant, à voir.
Re: arbre binaire de recherche pour décodage de morse en C
jeudi 26 mars 2015 20:34:35
C'est pas trop compliqué en réfléchissant pas à pas.

Pour la création de l'arbre, à chaque étape, soit tu vas ajouter un '.' ou un '-', soit tu as fini et tu vas mettre dans le noeud actuel le caractère à ajouter.

Pour la recherche, pareil. Tu pars du noeud racine, et pour chaque '.' et '-' dans le caractère morse, tu descends dans la branche correspondante. Quand tu tombes à cours de points/traits, tu retournes le caractère stocké dans le noeud dans lequel tu as atterri.

D'où la structure:
typedef struct Node {

    struct Node *dot ;
    struct Node *dash ;
    char         character ;

} _Node ;
Le _Node est pour éviter que le compilateur se plaigne que la structure est anonyme.

Et une petite fonction pour créer de nouveaux noeuds:
struct Node *new_node() {

    struct Node *node = malloc(sizeof(struct Node)) ;
    if (!node) {
        /* Malloc failed. Probably out of memory. */
        return NULL ;
    }

    node->dot       = NULL ;
    node->dash      = NULL ;
    node->character = '\0' ;

    return node ;

}
Avec cette structure, l'ajout et la recherche d'un caractère deviennent simples. À chaque étape, on regarde s'il nous reste du morse, et si oui on prend la branche dot ou dash du noeud selon le premier caractère du morse restant. Quand il ne nous reste plus de morse, c'est qu'on est sur le bon noeud, et on peut y mettre le nouveau caractère si on est en train de faire un ajout, ou retourner le caractère de ce noeud si on est en train de faire une recherche.

Remarque l'astuce que j'utilise pour passer le tree: en passant un pointeur de pointeur au lieu d'un pointeur simple, je peux créer le noeud à la volée s'il n'existe pas encore. J'utilise également des #define pour les caractères '.', '-' et plus tard '_' comme ça le jour où je veux les changer c'est pas chiant.
struct Node *add_char(struct Node **tree, char *morse, char c) {

    if (!morse || !tree) {
        /* Invalid parameters. Abort. */
        return NULL ;
    }

    if (!*tree) {
        *tree = new_node() ;
        if (!*tree) {
            /* Node creation failed. Probably out of memory. */
            return NULL ;
        }
    }

    if (!*morse) {
        /* We're at the end of the morse code! Put the character here. */
        (*tree)->character = c ;
        return *tree ;
    }

    if (*morse == DOT) {
       return add_char(&(*tree)->dot, ++morse, c) ;
    }

    if (*morse == DASH) {
       return add_char(&(*tree)->dash, ++morse, c) ;
    }

    /* Invalid morse code. :( */
    return NULL ;

}
Pour la recherche, c'est le même topo. Pas besoin d'un pointeur de pointeur cette fois, vu qu'on ne va pas modifier l'arbre.
char lookup_char(struct Node *tree, char *morse) {

    if (!tree) {
        /* Unknown character. :( */
        return '?' ;
    }

    if (!*morse) {
        /* We found our character! :) */
        return tree->character ;
    }

    if (*morse == DOT) {
       return lookup_char(tree->dot, ++morse) ;
    }

    if (*morse == DASH) {
       return lookup_char(tree->dash, ++morse) ;
    }

    /* Invalid morse code. :( */
    return '?' ;

}
Pour transformer un mot de morse entier en texte latin, il faut réfléchir un peu. En gros, le plus simple, c'est d'avancer jusqu'à trouver un séparateur (ton '_'), décoder le bout de morse entre le début et le séparateur que tu viens de trouver, et de continuer comme ça tant qu'il reste du morse à décoder. Il faut garder trace de chaque caractère décodé, mais c'est pas difficile.
char *parse_morse(struct Node *tree, char *morse) {

    char *current = morse ;

    /* Morse returns at most one latin character per morse character, so we
     * know this will be enough. */
    char *parsed = malloc(sizeof(char) * (strlen(morse) + 1)) ;

    if (!parsed) {
        /* Malloc failed. Probably out of memory. */
        return NULL ;
    }

    char *cur_parsed = parsed ;
    int   done = 0 ;

    while (!done) {

        while (*current && *current != SEP) {
            ++current ;
        }

        if (!*current) {
            /* We're at the end of the morse string. This is the last loop. */
            done = 1 ;
        } else {
            /* Turn the separator into a string end. */
            *current = '\0' ;
        }

        *cur_parsed = lookup_char(tree, morse) ;
        ++cur_parsed ;
        ++current ;
        morse = current ;

    }

    *cur_parsed = '\0' ;

    return parsed ;

}
Et maintenant il ne reste plus qu'à tout emballer ensemble dans un main() qui va bien.

Voici le programme complet, j'ai juste mis qu'un petit bout de morse dedans (de mémoire, pas forcément correct, la direction décline toute responsabilité, etc.):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DOT  '.'
#define DASH '-'
#define SEP  '_'

typedef struct Node {

    struct Node *dot ;
    struct Node *dash ;
    char         character ;

} _Node ;

struct Node *new_node() {

    struct Node *node = malloc(sizeof(struct Node)) ;
    if (!node) {
        /* Malloc failed. Probably out of memory. */
        return NULL ;
    }

    node->dot       = NULL ;
    node->dash      = NULL ;
    node->character = '\0' ;

    return node ;

}

struct Node *add_char(struct Node **tree, char *morse, char c) {

    if (!morse || !tree) {
        /* Invalid parameters. Abort. */
        return NULL ;
    }

    if (!*tree) {
        *tree = new_node() ;
        if (!*tree) {
            /* Node creation failed. Probably out of memory. */
            return NULL ;
        }
    }

    if (!*morse) {
        /* We're at the end of the morse code! Put the character here. */
        (*tree)->character = c ;
        return *tree ;
    }

    if (*morse == DOT) {
       return add_char(&(*tree)->dot, ++morse, c) ;
    }

    if (*morse == DASH) {
       return add_char(&(*tree)->dash, ++morse, c) ;
    }

    /* Invalid morse code. :( */
    return NULL ;

}

char lookup_char(struct Node *tree, char *morse) {

    if (!tree) {
        /* Unknown character. :( */
        return '?' ;
    }

    if (!*morse) {
        /* We found our character! :) */
        return tree->character ;
    }

    if (*morse == DOT) {
       return lookup_char(tree->dot, ++morse) ;
    }

    if (*morse == DASH) {
       return lookup_char(tree->dash, ++morse) ;
    }

    /* Invalid morse code. :( */
    return '?' ;

}

char *parse_morse(struct Node *tree, char *morse) {

    char *current = morse ;

    /* Morse returns at most one latin character per morse character, so we
     * know this will be enough. */
    char *parsed = malloc(sizeof(char) * (strlen(morse) + 1)) ;

    if (!parsed) {
        /* Malloc failed. Probably out of memory. */
        return NULL ;
    }

    char *cur_parsed = parsed ;
    int   done = 0 ;

    while (!done) {

        while (*current && *current != SEP) {
            ++current ;
        }

        if (!*current) {
            /* We're at the end of the morse string. This is the last loop. */
            done = 1 ;
        } else {
            /* Turn the separator into a string end. */
            *current = '\0' ;
        }

        *cur_parsed = lookup_char(tree, morse) ;
        ++cur_parsed ;
        ++current ;
        morse = current ;

    }

    *cur_parsed = '\0' ;

    return parsed ;

}

int main(int argc, char *argv[]) {

    struct Node *tree = NULL ;

    /* Populate a few characters. */
    add_char(&tree, ".-\0",   'A') ;
    add_char(&tree, "-...\0", 'B') ;
    add_char(&tree, "-.-.\0", 'C') ;
    add_char(&tree, "-..\0",  'D') ;
    add_char(&tree, ".\0",    'E') ;

    /* Sanity checks. */
#   if 0
    printf("%c", lookup_char(tree, ".-\0")) ;       /* Should print A */
    printf("%c", lookup_char(tree, "-...\0")) ;     /* Should print B */
    printf("%c", lookup_char(tree, "-.-.\0")) ;     /* Should print C */
    printf("%c", lookup_char(tree, "-..\0")) ;      /* Should print D */
    printf("%c", lookup_char(tree, ".\0")) ;        /* Should print E */
    printf("%c", lookup_char(tree, "XXX\0")) ;      /* Should print ? */
    printf("%c", lookup_char(tree, "........\0")) ; /* Should print ? */
    printf("\n") ;
#   endif

    if (argc <= 1) {

      printf("Usage: %s <morse>\n", argv[0]) ;
      return 1 ;

    }

    printf("%s\n", parse_morse(tree, argv[1])) ;

    return 0 ;
}
Voilà, maintenant refais tout toi-même pour vérifier que tu as compris ou sinon ton prof se rendra compte tout de suite que le code est pas de toi. :) Je l'ai fait en récursif par pure flemme, essaie de le refaire avec une boucle, par exemple.
Re: arbre binaire de recherche pour décodage de morse en C
jeudi 26 mars 2015 23:19:21
merci beaucoup :)
Entre nous mon prof comprends rien, il est un peu à la ramasse, mais c'est pour le bac, alors j'ai intérêt à comprendre ce que je code.
Tiens, un cookie de reconnaissance virtuelle!
Re: arbre binaire de recherche pour décodage de morse en C
vendredi 27 mars 2015 10:31:55
Le but c'est aussi que tu apprennes. :) Je recommande vraiment que tu essaies de refaire toi-même l'exercice une fois que tu auras bien compris l'exemple que je propose. Le C, c'est un peu le latin de la programmation, et ça te servira d'en connaître les bases mêmes si en fin de compte tu ne l'utilises pas lui-même (c'est mon cas).

Une bonne façon de faire, c'est de procéder par petits bouts. D'abord la structure, ensuite la fonction de création, ensuite la fonction d'ajout, etc. C'est dans cet esprit que j'ai laissé du code de test commenté dans main(): ça m'a permis de vérifier que mes fonctions d'ajout et de recherche marchaient bien, avant de passer à la suite.

Et puis j'ai laissé plusieurs trucs à améliorer dans le code, donc tu peux facilement faire un programme meilleur que le mien!

Si y'a des trucs que tu ne comprends pas (le coup du pointeur de pointeur par exemple, quand je débutais, je ne pannais rien à ces trucs-là), demande-moi.