TP5: fix the iterative search function in linked list

[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;

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

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

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