Slt tout d'abord voici mon code

#include <stdio.h>
#include <stdlib.h>
#include "simple.h"

/*---------------------------------------------------------------*/
Liste *initialisation(void)
{
	Liste *liste = malloc(sizeof(Liste));
	
	if(liste == NULL)
		exit(EXIT_FAILURE);
	
	liste->premier = NULL;
	
	return liste;
}

/*---------------------------------------------------------------*/
Bool est_ce_vide(Liste *lst)
{
	if(lst->premier == NULL)
			return vrai;
	
	return faux;
}

/*---------------------------------------------------------------*/
void ajout_en_tete(Liste *lst, int nvnbr)
{
	Element *nouveau = malloc(sizeof(Element));
	
	if(lst == NULL || nouveau == NULL)
		exit(EXIT_FAILURE);
	
	nouveau->nombre = nvnbr;
	nouveau->suivant = lst->premier;
	lst->premier = nouveau;
}

/*---------------------------------------------------------------*/
void ajout_en_fin(Liste *lst, int nvnbr)
{
	Element *nouveau = malloc(sizeof(*nouveau));
	
	if(nouveau == NULL || lst == NULL)
		exit(EXIT_FAILURE);
	
	if(est_ce_vide(lst))
		ajout_en_tete(lst, nvnbr);

	else
	{
		Element *tmp = lst->premier;
		nouveau->nombre = nvnbr;
		nouveau->suivant = NULL;
		
		while(tmp->suivant != NULL)
			tmp = tmp->suivant;
		
		tmp->suivant = nouveau;
	}
}

/*---------------------------------------------------------------*/
void affiche_liste(Liste *lst)
{
	if(lst == NULL)
		exit(EXIT_FAILURE);

	if(est_ce_vide(lst))
	{
		printf("\nLa Liste est vide.\n");
		exit(EXIT_SUCCESS);
	}
	
	Element *actuel = lst->premier;
	
	while(actuel != NULL)
	{
		printf("[%d] ", actuel->nombre);
		actuel = actuel->suivant;
	}
	
	printf("\n");
}

/*---------------------------------------------------------------*/
void suppression_en_tete(Liste *lst)
{
	if(lst == NULL)
		exit(EXIT_FAILURE);

	else if(!(est_ce_vide(lst)))
	{
		Element *elementASupprimer = lst->premier;
		lst->premier = lst->premier->suivant;
		free(elementASupprimer);
	}
}

/*---------------------------------------------------------------*/
void suppression_en_fin(Liste *lst)
{
	if(lst == NULL)
		exit(EXIT_FAILURE);

	if(!(est_ce_vide(lst)))
	{
		Element *elementASupprimer = lst->premier;
		Element *precedent;
			
		while(elementASupprimer->suivant != NULL)
		{
			precedent = elementASupprimer;
			elementASupprimer = elementASupprimer->suivant;
		}
		
		precedent->suivant = NULL;
		free(elementASupprimer);
	}
}

/*---------------------------------------------------------------*/
Element *recherche_element(Liste *lst, int valeur)
{
	if(lst == NULL)
		exit(EXIT_FAILURE);

	Element *tmp = lst->premier;
	
	while(tmp != NULL)
	{
		if(tmp->nombre == valeur)
			return tmp;
			
		tmp = tmp->suivant;
	}

	return NULL;
}

/*---------------------------------------------------------------*/
int nombre_occurence(Liste *lst, int valeur)
{
	int i = 0;
	Element *element = lst->premier;
	
	if(lst == NULL)
		exit(EXIT_FAILURE);
	
	while(element != NULL)
	{
		if(element->nombre == valeur)
			i++;
			
		element = element->suivant;
	}
	
	return i;
}

/*---------------------------------------------------------------*/
void affiche_premier_element(Liste *lst)
{
	printf("\nLe premier element de la liste : [%d]\n", lst->premier->nombre);
}

/*---------------------------------------------------------------*/
void affiche_dernier_element(Liste *lst)
{
	if(lst == NULL)
		exit(EXIT_FAILURE);
		
	Element *tmp = lst->premier;
	
	while(tmp->suivant != NULL)
	{
		tmp = tmp->suivant;
	}
	
	printf("\nLe dernier element de la liste : [%d]\n", tmp->nombre);
}

/*---------------------------------------------------------------*/
Element *trouver_nieme_element(Liste *lst, int indice)
{
	if(lst == NULL || indice >= (taille_liste(lst)))
		exit(EXIT_FAILURE);
		
	Element *tmp = lst->premier;
	int i = 0;
	
	if(lst == NULL)
			return NULL;

	while(i < indice)
	{
		tmp = tmp->suivant;
		i++;
	}
	
	return tmp;
}

/*---------------------------------------------------------------*/
int taille_liste(Liste *lst)
{
	int taille = 0;
	
	if(lst == NULL)
		exit(EXIT_FAILURE);
	
	if(est_ce_vide(lst))
			return 0;
			
	Element *tmp = lst->premier;
	
	while(tmp != NULL)
	{
		tmp = tmp->suivant;
		taille++;
	}
	
	return taille;
}

/*---------------------------------------------------------------*/
void vider_liste(Liste *lst)
{
	if(lst == NULL)
		exit(EXIT_FAILURE);
		
	int taille = taille_liste(lst);
	
	while(taille != 0)
	{
		suppression_en_tete(lst);
		taille--;
	}
}

/*---------------------------------------------------------------*/
void suppression_du_i_element(Liste *lst, int indice)
{
	if(indice == 0)
		exit(EXIT_FAILURE);

	if(lst == NULL || indice >= (taille_liste(lst)))
		exit(EXIT_FAILURE);
	
	Element *tmp = lst->premier;
	Element *precedent;
	
	for(int i = 0; i < indice; i++)
	{
		precedent = tmp;
		tmp = tmp->suivant;
	}
	
	precedent->suivant = tmp->suivant;
	free(tmp);
}

/*---------------------------------------------------------------*/
void ajout_au_milieu(Liste *lst, int indice, int valeur)
{
	Element *nouveau = malloc(sizeof(Element));
	
	if(lst == NULL || nouveau == NULL || indice >= (taille_liste(lst)))
		exit(EXIT_FAILURE);
	
	Element *tmp = lst->premier;
	Element *precedent;
	
	for(int i = 0; i < indice; i++)
	{
		precedent = tmp;
		tmp = tmp->suivant;
	}
	
	nouveau->nombre = valeur;
	nouveau->suivant = precedent->suivant;
	precedent->suivant = nouveau;
}

/*---------------------------------------------------------------*/
Liste *suppression_cible_valeur(Liste *lst, int valeur)
{
	if(lst == NULL)
		exit(EXIT_FAILURE);
		
	Element *tmp = lst->premier;
	Liste *nvliste = initialisation();
	
	while(tmp != NULL)
	{
		if(tmp->nombre != valeur)
			ajout_en_fin(nvliste, tmp->nombre);
			
		tmp = tmp->suivant;
	}
	
	vider_liste(lst);
	
	return nvliste;
}

/*Vous pouvez compléter votre bibliothèque avec des fonctions de tri,
de recherche de minimum, de maximum et bien d'autre choses...*/

Mon problème est que la fonction Liste *suppression_cible_valeur(Liste *lst, int valeur) si elle s'excecute très rapidement sur les listes de petites tailles , sur les grandes par contre le temps d'excecution est trop long (par exemple ~30s sur 100000). La fonction doit parcourir toute la chaine à la recherche de la valeur ciblé et en même temps copier les autres valeurs dans un autre liste et ensuite liberer l'ancienne liste avant de retourne la nouvelle . J'avoue je l'ai mal coder celle-là .Si vous pouvez m'aider à l'optimiser un peu se serait cool. 

Ça montre à l'évidence un problème de conception ! On ne fait pas n'importe quoi avec une liste chaînée, on peut s'en servir pour simuler des piles ou des files sinon, c'est inadapté.

Ici tu t'en sers pour gérer des nombres.

Il faudrait qu'elle soit triée en fonction de "nombre".

Tu ajoutes un nombre en insérant un noeud  au bon endroit.

Tu supprimes une valeur en supprimant le/les noeuds concernés.

Jamais de recopies des bonnes valeurs, c'est justement ça l'intérêt des listes chaînées.

Dernière choses, pour le dernier élément, tu as tout à fait le droit d'avoir un pointeur sur ce dernier élément, ça gagne énormément de temps.

-
Edité par joel76 23 mars 2020 à 9:03:13

Ok merci beaucoup joel76 pour ta reponse.

Voilà j'ai remanié le code mais le probléme maintenant est que j'ai un 0 qui s'affiche à la place de la valeur supprimée.

Code:

void suppression_cible_valeur(Liste *lst, int valeur)
{
	if(lst == NULL)
		exit(EXIT_FAILURE);
		
	Element *tmp = lst->premier;
	Element *precedent;
	Element *suivant;
	
	while(tmp != NULL)
	{
		if(tmp->nombre == valeur)
		{
			precedent = tmp;
			suivant = tmp->suivant;
			free(tmp);
			tmp = suivant;
			precedent->suivant = suivant;
		}
		tmp = tmp->suivant;
	}
}

resultat:

Sur cette capture d'ecran j'ai supprimée la valeur 20 . Voyez le resultat.

-
Edité par BamAss 23 mars 2020 à 10:04:29

Quand on supprime un noeud, on doit mémoriser le "père" du noeud, et relier père->suivant à noeud->suivant   (je me demande si je suis clair ?!).

-
Edité par joel76 23 mars 2020 à 11:42:36

Je pense bien que c'est ce que j'ai fait dans mon precedent code. Cependant d'où vient l'erreur?

Ben non. Il faut tester  tmp->suivant->nombre et non pas tmp->nombre

-
Edité par PierrotLeFou 23 mars 2020 à 14:19:23

Oui mais comme je suis en apprentissage, je me dis que maitriser les listes simplement chainées avant de passer aux doublement chainées serait plus avantageux que je de sauter directement à la suite

-
Edité par PierrotLeFou 23 mars 2020 à 16:29:10

joel76 a écrit:

Ben non. Il faut tester  tmp->suivant->nombre et non pas tmp->nombre

Je cite cette phrase car c'est elle la clé du problème. Faire un petit dessin pour bien comprendre.

-
Edité par PierrotLeFou 24 mars 2020 à 1:29:01

Slt merci beaucoup pour vos explications et PierrotLeFou pour ton code je l'ai testé en il marche. Dites comment faites vous pour etre aussi bon en programmation ?

Il va me falloir alors pas mal de temps pour vraiment être un as et maitriser vraiment le langage. Ça tombe bien alors je suis passionné et motivé.

-
Edité par PierrotLeFou 25 mars 2020 à 4:44:10

Slt,

Pour ce qui est de ta première consigne il ne passe rien quand j'essaie de supprimer une liste vide , du moins en apparence.

Pour la seconde , en testant avec un seul élément celui si est simplement retiré de la liste et la fonction affiche_liste me signale que la liste est vide. Et pour ce qui est supprimer un élément qui ne se trouve pas dans la liste, j'ai pas non plus d'erreur de ce côté.

Pour les troisième et quatrième consignes , toutes les occurences de la valeur ciblée sont simplement retirées de la liste. Pour le premier cas , la fonction affiche_liste m'affiche ce qui reste de la liste et pour le deuxième elle me signale que la liste est vide.

-
Edité par BamAss 25 mars 2020 à 10:30:28

Je signale le site HackerRank qui propose des exercices d'algo à résoudre dans presque tous les langages. Ça peut être intéressant.

En C, il y a toute une série d'exo sur les listes chaînées.

J'y est jetté un coup d'oeil et il est super ce site. Je l'ajoute direct à mes favoris. Merci beaucoup.

-
Edité par BamAss 25 mars 2020 à 17:38:12