TP5: Implement linked list counting iteratively and recursively

[Algorithmic_C.git] / TP5 / exo4 / liste_chainee.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 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)
{
	/* ... */
}

void visualiser_rec(Liste L)
{
	/* ... */
}

int rechercher_iter(element e, Liste L)
{
	/* ... */
}

Liste rechercher_rec(element e, Liste L)
{
	/* ... */
}

Liste ajouter_rec(element e, Liste L)
{
	/* ... */
}

Liste supprimer_iter(element e, Liste L)
{
	/* ... */
}

Liste supprimer_rec(element e, Liste L)
{
	/* ... */
}

Liste inverser_iter(Liste L)
{
	/* ... */
}

Liste inverser_rec(Liste L)
{
	/* ... */
}

/****************************************************************************/
int main()
{
	int x;
	Liste L = NULL;
	L = ajouter_iter(2, L);
	L = ajouter_iter(1, L);
	L = ajouter_iter(3, L);
	printf("Saisir un entier a ajouter a la site\n");
	scanf("%d", &x);
	L = ajouter_iter(x, L);
	printf("longueur=%d\n", longueur_rec(L));
	visualiser_iter(L);
	/* ... */
}

/****************************************************************************/