X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=TP5%2Fexo4%2Fliste_correction.c;fp=TP5%2Fexo4%2Fliste_correction.c;h=eff60c44928e498d2b25b1caab743810c8c10fd8;hb=f5904379c91a724dcc5818fcb80e7b111dc6cf0d;hp=0000000000000000000000000000000000000000;hpb=0146cff3db3fd5c445da626bf0786e2c74a4ecaa;p=Algorithmic_C.git diff --git a/TP5/exo4/liste_correction.c b/TP5/exo4/liste_correction.c new file mode 100644 index 0000000..eff60c4 --- /dev/null +++ b/TP5/exo4/liste_correction.c @@ -0,0 +1,298 @@ +/********************************************************************/ +/* Implantation d'une liste triee d'entiers */ +/********************************************************************/ +#include +#include + +typedef int element; + +typedef struct cellule { + 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; +} + + +int longueur_iter(Liste L) +{ + 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); +} + + +void visualiser_iter(Liste L) +{ + 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); + } +} + + +void visualiser_rec(Liste L) +{ + 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; +} + + +int rechercher_rec(element e, Liste L) +{ + 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); +} + + +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; +} + + +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 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; +} + + +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 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; +} + + +Liste inverser_rec(Liste L) +{ + if(L != NULL) { + return inserer_fin(L->valeur, inverser_rec(L->suivant)); + } + else return L; +} + + +/****************************************************************************/ + +int main() +{int x; + 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 +ajout de 6 +ajout de 1 +ajout de 10 +ajout de 6 +1 3 6 6 10 +1 3 6 6 10 +longueur=5 +longueur=5 +recherche de 3 = 1 +recherche de 3 = 1 +recherche de 4 = 0 +recherche de 4 = 0 +ajout (rec) de 4 +1 3 4 6 6 10 +ajout (rec) de 8 +1 3 4 6 6 8 10 +suppression (iter) de 4 +1 3 6 6 8 10 +suppression (rec) de 6 +1 3 6 8 10 +liste inversee (iter) +10 8 6 3 1 +Liste inversee (rec) +1 3 6 8 10 +*/ +