From c31b68a4e24e74a20f09aa1d7b9906b58d4aa255 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Sun, 2 Apr 2017 17:44:12 +0200 Subject: [PATCH] TP5 exo4: implement more functions MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Properly indent to other C files also Signed-off-by: Jérôme Benoit --- TP4/palindrome.c | 36 ++- TP5/exo4/liste_chainee.c | 33 ++- TP5/exo_c4/liste_correction.c | 363 +++++++++++++-------------- TP6/arbres/arbre_n_aire/dictionnaire | 5 +- 4 files changed, 222 insertions(+), 215 deletions(-) diff --git a/TP4/palindrome.c b/TP4/palindrome.c index a84c08f..8ac573b 100644 --- a/TP4/palindrome.c +++ b/TP4/palindrome.c @@ -5,38 +5,48 @@ #define LEN_MAX 40 -bool palindrome_iter(char* mot, int longeur) { +bool palindrome_iter(char *mot, int longeur) +{ int i = 0; int j = longeur - 1; while (i <= j) { - if (mot[i] != mot[j]) { return false; } - i++; - j--; + if (mot[i] != mot[j]) { + return false; + } + i++; + j--; } return true; } -bool palindrome_rec_aux(char* mot, int i, int j) { - if (i >= j) { return true; } - if (mot[i] != mot[j]) { return false; } - return palindrome_rec_aux(mot, i+1, j-1); +bool palindrome_rec_aux(char *mot, int i, int j) +{ + if (i >= j) { + return true; + } + if (mot[i] != mot[j]) { + return false; + } + return palindrome_rec_aux(mot, i + 1, j - 1); } -bool palindrome_rec(char* mot, int longueur) { - return palindrome_rec_aux(mot, 0, longueur-1); +bool palindrome_rec(char *mot, int longueur) +{ + return palindrome_rec_aux(mot, 0, longueur - 1); } -int main() { +int main() +{ char mot[LEN_MAX]; printf("Saisir un mot\n"); scanf("%s", mot); if (palindrome_rec(mot, strlen(mot))) - printf("%s est un palindrome\n", mot); + printf("%s est un palindrome\n", mot); else - printf("%s n'est pas un palindrome\n", mot); + printf("%s n'est pas un palindrome\n", mot); return 0; } diff --git a/TP5/exo4/liste_chainee.c b/TP5/exo4/liste_chainee.c index a858939..851e354 100644 --- a/TP5/exo4/liste_chainee.c +++ b/TP5/exo4/liste_chainee.c @@ -12,7 +12,7 @@ typedef struct cellule { struct cellule *suivant; } Cellule, *Liste; -Cellule *creer_maillon(element e, Cellule *suivant) +Cellule *creer_maillon(element e, Cellule * suivant) { Cellule *pnouveau = malloc(sizeof(Cellule)); pnouveau->valeur = e; @@ -23,7 +23,6 @@ Cellule *creer_maillon(element e, Cellule *suivant) Liste ajouter_iter(element e, Liste L) { Cellule *pc, *p1 = L, *p2 = NULL; - pc = creer_maillon(e, NULL); if (!L) /* liste vide */ @@ -136,18 +135,19 @@ Liste supprimer_iter(element e, Liste L) { Cellule *pavant = NULL; Cellule *pdebut = L; + while (L != NULL) { /* supprimer en fin de liste */ if (L->valeur == e && L->suivant == NULL) { free(L); pavant->suivant = NULL; return pdebut; - /* supprimer au début de la liste */ + /* supprimer au début de la liste */ } else if (L->valeur == e && pavant == NULL) { Cellule *pcourant = L; free(L); return pcourant->suivant; - /* supprimer au mileu de la liste */ + /* supprimer au mileu de la liste */ } else if (L->valeur == e) { Cellule *pcourant = L; free(L); @@ -162,7 +162,17 @@ Liste supprimer_iter(element e, Liste L) Liste supprimer_rec(element e, Liste L) { - /* ... */ + if (L == NULL) { + return L; + } + if (L->valeur == e) { + Cellule *p = L; + L = L->suivant; + free(p); + } else { + L->suivant = supprimer_rec(e, L->suivant); + } + return L; } Liste inverser_iter(Liste L) @@ -218,13 +228,16 @@ int main() L = ajouter_rec(5, L); L = ajouter_rec(7, L); visualiser_iter(L); - L = supprimer_iter(1, L); - L = supprimer_iter(4, L); - L = supprimer_iter(2, L); + /* L = supprimer_iter(1, L); + L = supprimer_iter(4, L); + L = supprimer_iter(2, L); */ + L = supprimer_rec(1, L); + L = supprimer_rec(4, L); + L = supprimer_rec(2, L); visualiser_rec(L); visualiser_iter(L); - //liberer_rec(L); - liberer_iter(L); + liberer_rec(L); + //liberer_iter(L); /* ... */ } diff --git a/TP5/exo_c4/liste_correction.c b/TP5/exo_c4/liste_correction.c index 7f9d0c6..5c219e7 100644 --- a/TP5/exo_c4/liste_correction.c +++ b/TP5/exo_c4/liste_correction.c @@ -7,266 +7,248 @@ typedef int element; typedef struct cellule { - element valeur; - struct cellule *suivant; + element valeur; + struct cellule *suivant; } Cellule, *Liste; - - Liste ajouter_iter(element e, Liste L) { - Cellule *pc, *p1=L, *p2=NULL; - - pc = (Cellule *)malloc(sizeof(Cellule)); - pc->valeur=e;pc->suivant=NULL; - - if (!L) /* liste vide */ return pc; - while (p1 && (e >= p1->valeur)) - { - p2 = p1; - p1 = p1->suivant; - } - - if (!p2) /* insertion en tete */ {pc->suivant = L; L=pc; } - else {/* insertion entre p2 et p1 */ - p2->suivant = pc; - pc->suivant = p1; - } - - return L; + Cellule *pc, *p1 = L, *p2 = NULL; + + pc = (Cellule *) malloc(sizeof(Cellule)); + pc->valeur = e; + pc->suivant = NULL; + + if (!L) /* liste vide */ + return pc; + while (p1 && (e >= p1->valeur)) { + p2 = p1; + p1 = p1->suivant; + } + + if (!p2) { /* insertion en tete */ + pc->suivant = L; + L = pc; + } else { /* insertion entre p2 et p1 */ + p2->suivant = pc; + pc->suivant = p1; + } + + return L; } - int longueur_iter(Liste L) { - int res = 0; - while(L) - { - res = res + 1; - L=L->suivant; - } - return res; + int res = 0; + while (L) { + res = res + 1; + L = L->suivant; + } + return res; } - int longueur_rec(Liste L) { - if(!L) return 0; - return 1+longueur_rec(L->suivant); + if (!L) + return 0; + return 1 + longueur_rec(L->suivant); } - void visualiser_iter(Liste L) { - while (L) - { - printf("%d ",L->valeur); - L = L->suivant; - } - printf("\n"); + while (L) { + printf("%d ", L->valeur); + L = L->suivant; + } + printf("\n"); } - void visualiser_aux(Liste L) { - if(L) - { - printf("%d ",L->valeur); - visualiser_aux(L->suivant); - } + if (L) { + printf("%d ", L->valeur); + visualiser_aux(L->suivant); + } } - void visualiser_rec(Liste L) { - visualiser_aux(L); - printf("\n"); + visualiser_aux(L); + printf("\n"); } - int rechercher_iter(element e, Liste L) { - while(L) - { - if(e == L->valeur) return 1; - L = L->suivant; - } - return 0; + while (L) { + if (e == L->valeur) + return 1; + L = L->suivant; + } + return 0; } - int rechercher_rec(element e, Liste L) { - if(L == NULL) return 0; - if(e==L->valeur) return 1; - return rechercher_rec(e,L->suivant); + if (L == NULL) + return 0; + if (e == L->valeur) + return 1; + return rechercher_rec(e, L->suivant); } - Liste rechercher_rec2(element e, Liste L) { - if(!L || e==L->valeur) return L; - else return rechercher_rec2(e,L->suivant); + if (!L || e == L->valeur) + return L; + else + return rechercher_rec2(e, L->suivant); } - Liste ajouter_rec(element e, Liste L) -{ - if(!L) - { - L=(Cellule *)malloc(sizeof(Cellule)); /* liste vide */ - L->valeur=e;L->suivant=NULL; - } - else if(e < L->valeur) /* ajouter DEVANT la tete */ - { - Cellule *p=(Cellule *)malloc(sizeof(Cellule)); - p->valeur=e; p->suivant=L; - L=p; /* nouvelle tete de liste */ - } - else L->suivant=ajouter_rec(e,L->suivant); /* ajouter DERRIERE la tete */ - return L; +{ + if (!L) { + L = (Cellule *) malloc(sizeof(Cellule)); /* liste vide */ + L->valeur = e; + L->suivant = NULL; + } else if (e < L->valeur) { /* ajouter DEVANT la tete */ + Cellule *p = (Cellule *) malloc(sizeof(Cellule)); + p->valeur = e; + p->suivant = L; + L = p; /* nouvelle tete de liste */ + } else + L->suivant = ajouter_rec(e, L->suivant); /* ajouter DERRIERE la tete */ + return L; } - Liste supprimer_iter(element e, Liste L) { - Liste prec = NULL; - while(L) - { - if(e == L->valeur) { - prec->suivant = L->suivant; /* le suivant de prec devient le suivant de L */ - free(L); /* liberation memoire pour L */ - return prec; - } - prec = L; - L = L->suivant; - } - return L; + Liste prec = NULL; + while (L) { + if (e == L->valeur) { + prec->suivant = L->suivant; /* le suivant de prec devient le suivant de L */ + free(L); /* liberation memoire pour L */ + return prec; + } + prec = L; + L = L->suivant; + } + return L; } - Liste supprimer_rec(element e, Liste L) { - if(!L) ; /* element absent - on ne fait rien */ - else if(L->valeur==e) - { - Cellule *p=L; - L=L->suivant; - free(p); - } - else L->suivant=supprimer_rec(e,L->suivant); - return L; + if (!L) ; /* element absent - on ne fait rien */ + else if (L->valeur == e) { + Cellule *p = L; + L = L->suivant; + free(p); + } else + L->suivant = supprimer_rec(e, L->suivant); + return L; } - Liste inverser_iter(Liste L) { - Liste cell=NULL; /* une cellule temporaire */ - Liste inv=NULL; /* la liste inversee */ - - while(L!=NULL) - { - cell=L; /* on prend la premiere cellule de la liste */ - L=L->suivant; /* le debut de la liste devient l'element suivant */ - cell->suivant=inv; /* on libere l'element de la liste et on le place en debut de la liste a renvoyer*/ - inv=cell; /* l'element qu'on vient de mettre en debut de liste devient le debut de la liste de a renvoyer */ - } - return inv; + Liste cell = NULL; /* une cellule temporaire */ + Liste inv = NULL; /* la liste inversee */ + + while (L != NULL) { + cell = L; /* on prend la premiere cellule de la liste */ + L = L->suivant; /* le debut de la liste devient l'element suivant */ + cell->suivant = inv; /* on libere l'element de la liste et on le place en debut de la liste a renvoyer */ + inv = cell; /* l'element qu'on vient de mettre en debut de liste devient le debut de la liste de a renvoyer */ + } + return inv; } - - Liste inserer_fin(element e, Liste L) { - Cellule *pc, *p1=L, *p2=NULL; - pc = (Cellule *)malloc(sizeof(Cellule)); - pc->valeur=e;pc->suivant=NULL; - if (!L) return pc; - while (p1) - { - p2 = p1; - p1 = p1->suivant; - } - p2->suivant = pc; - pc->suivant = p1; - return L; + Cellule *pc, *p1 = L, *p2 = NULL; + pc = (Cellule *) malloc(sizeof(Cellule)); + pc->valeur = e; + pc->suivant = NULL; + if (!L) + return pc; + while (p1) { + p2 = p1; + p1 = p1->suivant; + } + p2->suivant = pc; + pc->suivant = p1; + return L; } - Liste inverser_rec(Liste L) { - if(L != NULL) { - return inserer_fin(L->valeur, inverser_rec(L->suivant)); - } - else return L; + if (L != NULL) { + return inserer_fin(L->valeur, inverser_rec(L->suivant)); + } else + return L; } - -/****************************************************************************/ +/****************************************************************************/ int main() { - Liste L=NULL; - printf("liste vide\n"); - visualiser_iter(L); - visualiser_rec(L); - - printf("longueur=%d\n",longueur_iter(L)); - printf("longueur=%d\n",longueur_rec(L)); - - printf("ajout de 3\n"); - L=ajouter_iter(3,L); - printf("ajout de 6\n"); - L=ajouter_iter(6,L); - printf("ajout de 1\n"); - L=ajouter_iter(1,L); - printf("ajout de 10\n"); - L=ajouter_iter(10,L); - printf("ajout de 6\n"); - L=ajouter_iter(6,L); - visualiser_iter(L); - visualiser_rec(L); - - printf("longueur=%d\n",longueur_iter(L)); - printf("longueur=%d\n",longueur_rec(L)); - - printf("recherche de %d = %d\n",3,rechercher_iter(3,L)); - printf("recherche de %d = %d\n",3,rechercher_rec(3,L)); - printf("recherche de %d = %d\n",4,rechercher_iter(4,L)); - printf("recherche de %d = %d\n",4,rechercher_rec(4,L)); - - printf("ajout (rec) de 4\n"); - L=ajouter_rec(4,L); - visualiser_iter(L); - printf("ajout (rec) de 8\n"); - L=ajouter_rec(8,L); - visualiser_iter(L); - - printf("suppression (iter) de 4\n"); - supprimer_iter(4,L); - visualiser_iter(L); - printf("suppression (rec) de 6\n"); - supprimer_rec(6,L); - visualiser_iter(L); - - printf("liste inversee (iter)\n"); - Liste inv = inverser_iter(L); - visualiser_iter(inv); - - printf("Liste inversee (rec)\n"); - Liste inv2 = inverser_rec(inv); - visualiser_iter(inv2); - - /* il faut aussi tester chaque fonction (visualiser, supprimer, rechercher, inverser, ...) sur tous les cas : liste vide, liste avec un seul element, operation sur le premier element, operation sur le dernier element, ... */ + Liste L = NULL; + printf("liste vide\n"); + visualiser_iter(L); + visualiser_rec(L); + + printf("longueur=%d\n", longueur_iter(L)); + printf("longueur=%d\n", longueur_rec(L)); + + printf("ajout de 3\n"); + L = ajouter_iter(3, L); + printf("ajout de 6\n"); + L = ajouter_iter(6, L); + printf("ajout de 1\n"); + L = ajouter_iter(1, L); + printf("ajout de 10\n"); + L = ajouter_iter(10, L); + printf("ajout de 6\n"); + L = ajouter_iter(6, L); + visualiser_iter(L); + visualiser_rec(L); + + printf("longueur=%d\n", longueur_iter(L)); + printf("longueur=%d\n", longueur_rec(L)); + + printf("recherche de %d = %d\n", 3, rechercher_iter(3, L)); + printf("recherche de %d = %d\n", 3, rechercher_rec(3, L)); + printf("recherche de %d = %d\n", 4, rechercher_iter(4, L)); + printf("recherche de %d = %d\n", 4, rechercher_rec(4, L)); + + printf("ajout (rec) de 4\n"); + L = ajouter_rec(4, L); + visualiser_iter(L); + printf("ajout (rec) de 8\n"); + L = ajouter_rec(8, L); + visualiser_iter(L); + + printf("suppression (iter) de 4\n"); + supprimer_iter(4, L); + visualiser_iter(L); + printf("suppression (rec) de 6\n"); + supprimer_rec(6, L); + visualiser_iter(L); + + printf("liste inversee (iter)\n"); + Liste inv = inverser_iter(L); + visualiser_iter(inv); + + printf("Liste inversee (rec)\n"); + Liste inv2 = inverser_rec(inv); + visualiser_iter(inv2); + + /* il faut aussi tester chaque fonction (visualiser, supprimer, rechercher, inverser, ...) sur tous les cas : liste vide, liste avec un seul element, operation sur le premier element, operation sur le dernier element, ... */ } - -/****************************************************************************/ +/****************************************************************************/ /* trace d'execution : liste vide - longueur=0 longueur=0 ajout de 3 @@ -295,4 +277,3 @@ liste inversee (iter) Liste inversee (rec) 1 3 6 8 10 */ - diff --git a/TP6/arbres/arbre_n_aire/dictionnaire b/TP6/arbres/arbre_n_aire/dictionnaire index c87770f..7149996 100644 --- a/TP6/arbres/arbre_n_aire/dictionnaire +++ b/TP6/arbres/arbre_n_aire/dictionnaire @@ -1,5 +1,8 @@ -4 +7 salut salutations cela ceci +saluts +zazou +attendre -- 2.34.1