X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=TP5%2Fexo4%2Fliste_chainee.c;h=851e35428f6d63f1ad12b2805500501bbb79effd;hb=c31b68a4e24e74a20f09aa1d7b9906b58d4aa255;hp=7d550819392e5824b797f24f78b988e38c912710;hpb=43bff44a320b5da23600d46768a2fc2d8815f647;p=Algorithmic_C.git

diff --git a/TP5/exo4/liste_chainee.c b/TP5/exo4/liste_chainee.c
index 7d55081..851e354 100644
--- a/TP5/exo4/liste_chainee.c
+++ b/TP5/exo4/liste_chainee.c
@@ -3,6 +3,7 @@
 /********************************************************************/
 #include <stdio.h>
 #include <stdlib.h>
+#include <stdbool.h>
 
 typedef int element;
 
@@ -11,13 +12,18 @@ typedef struct cellule {
 	struct cellule *suivant;
 } Cellule, *Liste;
 
+Cellule *creer_maillon(element e, Cellule * suivant)
+{
+	Cellule *pnouveau = malloc(sizeof(Cellule));
+	pnouveau->valeur = e;
+	pnouveau->suivant = suivant;
+	return pnouveau;
+}
+
 Liste ajouter_iter(element e, Liste L)
 {
 	Cellule *pc, *p1 = L, *p2 = NULL;
-
-	pc = (Cellule *) malloc(sizeof(Cellule));
-	pc->valeur = e;
-	pc->suivant = NULL;
+	pc = creer_maillon(e, NULL);
 
 	if (!L)			/* liste vide */
 		return pc;
@@ -42,8 +48,7 @@ int longueur_iter(Liste L)
 {
 	int longueur = 0;
 
-	while (L->suivant != NULL)
-	{
+	while (L != NULL) {
 		L = L->suivant;
 		longueur++;
 	}
@@ -52,42 +57,122 @@ int longueur_iter(Liste L)
 
 int longueur_rec(Liste L)
 {
-	/* ... */
+	if (L != NULL) {
+		return 1 + longueur_rec(L->suivant);
+	} else {
+		return 0;
+	}
 }
 
 void visualiser_iter(Liste L)
 {
-	/* ... */
+	int compteur = 0;
+
+	printf("--Debut--\n");
+	while (L != NULL) {
+		printf("L[%d]->value=%d\n", compteur, L->valeur);
+		L = L->suivant;
+		compteur++;
+	}
+	printf("--Fin--\n");
+}
+
+void _visualiser_rec(Liste L, int compteur)
+{
+	if (L != NULL) {
+		/* FIXME: suboptimal printing to stdout, put this code path outside the recursion */
+		if (compteur == 0)
+			printf("--Debut--\n");
+		printf("L[%d]->value=%d\n", compteur, L->valeur);
+		compteur++;
+		_visualiser_rec(L->suivant, compteur);
+		if (compteur == (longueur_rec(L) - 1))
+			printf("--Fin--\n");
+	}
+
 }
 
 void visualiser_rec(Liste L)
 {
-	/* ... */
+	int compteur = 0;
+
+	_visualiser_rec(L, compteur);
 }
 
-int rechercher_iter(element e, Liste L)
+bool rechercher_iter(element e, Liste L)
 {
-	/* ... */
+	bool rt_val = false;
+
+	while (L != NULL) {
+		if (L->valeur == e) {
+			rt_val = true;
+			break;
+		}
+		L = L->suivant;
+	}
+	return rt_val;
 }
 
 Liste rechercher_rec(element e, Liste L)
 {
-	/* ... */
+	if (L->valeur != e && L->suivant != NULL) {
+		return L = rechercher_rec(e, L->suivant);
+	}
 }
 
 Liste ajouter_rec(element e, Liste L)
 {
-	/* ... */
+	if (!L || !(L->valeur < e)) {
+		return creer_maillon(e, L);
+	}
+
+	L->suivant = ajouter_rec(e, L->suivant);
+
+	return L;
 }
 
 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 */
+		} else if (L->valeur == e && pavant == NULL) {
+			Cellule *pcourant = L;
+			free(L);
+			return pcourant->suivant;
+			/* supprimer au mileu de la liste */
+		} else if (L->valeur == e) {
+			Cellule *pcourant = L;
+			free(L);
+			L = pavant;
+			L->suivant = pcourant->suivant->suivant;
+			return pdebut;
+		}
+		pavant = L;
+		L = L->suivant;
+	}
 }
 
 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)
@@ -100,16 +185,61 @@ Liste inverser_rec(Liste L)
 	/* ... */
 }
 
+void liberer_iter(Liste L)
+{
+	while (!L) {
+		Cellule *pcourant = L;
+		free(L);
+		L = pcourant->suivant;
+	}
+}
+
+void liberer_rec(Liste L)
+{
+	if (!L) {
+		liberer_rec(L->suivant);
+		free(L);
+	}
+}
+
 /****************************************************************************/
 int main()
 {
 	int x;
 	Liste L = NULL;
+	L = ajouter_iter(2, L);
+	L = ajouter_iter(1, L);
+	L = ajouter_iter(3, L);
+	L = ajouter_iter(4, L);
+	printf("Saisir un entier a chercher dans la liste L\n");
 	scanf("%d", &x);
-	L = ajouter_iter(x, L);
-	printf("longueur=%d\n", longueur_iter(L));
+	printf("L a pour longueur %d\n", longueur_rec(L));
+	visualiser_iter(L);
+	visualiser_rec(L);
+	if (rechercher_iter(x, L))
+		printf("L'element %d est present dans L\n", x);
+	else
+		printf("L'element %d n'est pas present dans L\n", x);
+	if (rechercher_rec(x, L) != NULL)
+		printf("L'element %d est present dans L\n", x);
+	else
+		printf("L'element %d n'est pas present dans L\n", x);
+	L = ajouter_rec(6, L);
+	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_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);
 	/* ... */
 }
 
 /****************************************************************************/
+/* vim:noet:ts=8:sw=8:textwidth=80 */