--- /dev/null
+/********************************************************************/
+/* Implantation d'une liste triee d'entiers */
+/********************************************************************/
+#include <stdio.h>
+#include <stdlib.h>
+
+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
+*/
+
repositories / Algorithmic_C.git / blobdiff