X-Git-Url: https://git.piment-noir.org/?p=Algorithmic_C.git;a=blobdiff_plain;f=TP5%2Fexo_c4%2Fliste_correction.c;h=5c219e755d0fb31aa693f4d2092f72354d69a32a;hp=7f9d0c631fc050302cde7b768bad6e15bb9bf5ea;hb=c31b68a4e24e74a20f09aa1d7b9906b58d4aa255;hpb=915495850ca055b20497568512c3e70a6b61a13c 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 */ -