TP5 exo4: implement more functions

[Algorithmic_C.git] / TP5 / exo_c4 / liste_correction.c

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