TP5 exo4: implement more functions

[Algorithmic_C.git] / TP5 / exo4 / liste_chainee.c

/********************************************************************/
/*   Implantation d'une liste triee d'entiers                       */
/********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int element;

typedef struct cellule {
	element valeur;
	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 = creer_maillon(e, 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 longueur = 0;

	while (L != NULL) {
		L = L->suivant;
		longueur++;
	}
	return longueur;
}

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);
}

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)
{
	/* ... */
}

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);
	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 */