Algorithme Avancé Fermé

Question

Bonjour,
J'aimerais tout d'abord vous remercier pour ce que vous faites, tous autant que vous êtes pour aider dans la mesure du possible. Je ne suis pas tellement un habitué de ce forum mais on m'en a dit beaucoup de bien.
Voilà mon problème: Ecrire une fonction supprimer_x qui supprime dans une liste L, toutes les occurences d'un élément x et retourne la liste L privé de X.
J'espère pouvoir rapidement avoir une reponse à ce problème que je traine depuis un bon moment. Merci d'avance!

lami20j · Answer

Salut,

Quel langage?

MoodZy · Answer

En quel langage?

MoodZy · Answer

Juste un algorithme...
Hmmm...

Dans le genre de :

On parcourt la liste L. On compare chaque élément avec X au fur et à mesure qu'on passe en revue la liste.
Si l'élément est égal à X on appelle une fonction qui supprime X dans la liste et qui rappelle la première fonction supprimer_x avec la nouvelle liste. (de cette manière on ira à chaque fois plus loin dans la liste)
Si l'élément n'est pas égal à X on passe au suivant.
A la fin de la fonction tu renvoies L ...

garion28 · Answer

fonction supprimer (tableau:tableau de chaine, elemsuppr: chaine):tableau de chaine
i : entier
tabretourne:tableau de chaine
i=0
tant que tableau[i]<>""
si tableau [i]<>elemsuppr alors
tabretourne=tableau[i]
i=i+1
fin tant que

retourner tabretourne

ca devrai le faire, donc en faite ca veut dire qu'on parcours le tableau original et si la valeur a l'index i est différent de l'élément supprimé alors on l'ajoute dans le tableau a retourner

Flaiso · Answer

Ce n'est pas un tableau mais plutot une liste et c'est exactement comme MoodZy l'a expliqué.

Flaiso · Answer

En fait, c'est la redaction qui pose problème

garion28 · Answer

moodzy: le seul truc c'est que ta liste devra etre trié avant d'etre renvoyé
et un algorithme n'est pas qu'une suite de phrase, c'est aussi du pseudo code (aucun language précis)

garion28 · Answer

ben je ne sais pas si dans ton texte tu prend en compte qu'une nouvelle liste est généré après chaque suppression mais selon moi, ta suppression est sensé laisser des trous a la place de la valeur
genre avec la valeur c a supprimer
i1: a
i2: b
i3: c
i4: d

ca ferai 
i1: a
i2: b
i3: 
i4: d
au lieu de faire
i1: a
i2: b
i3: d

garion28 · Answer

alors on a bien la même vision du problème, l'algo que j'ai écris fait exactement ca

Flaiso · Answer

Vous avez tous, d'une manière ou d'une autre, raison! En fait, on aura une liste principale qu'on sauvera dans une nouvelle liste tierce pour pouvoir la modifier à souhait; On aura aussi des listes intermédiaires pour la sauvegarde de la liste après suppression de l'élément X. Avec ces éléments, quelqu'un peut-il me proposer une redaction?

lami20j · Answer

Salut,

Souvent pour pouvoir 'supprimer' un élément, il faut recopier la liste dans une nouvelle sans l'élément incriminé... 

Ce n'est pas obligatoire.
Ca dépends ce qu'on comprends pas une liste.
L'implémentation de l'algo peut être différent en fonction de langage. (Un exemple avec les listes chaînées
C'est c'est un tableau alors il faudra penser décaler les termes après la suppréssion, pas vraiment besoin d'une recopie.
Si c'est une liste chaînée il suffit de garder la liaison entre les termes après la suppression.

tibobo_77 · Answer

En fait en algo une liste est composé de cellules.
Chaque cellule comporte 2(ou+) éléments:
---une/des données.
---l'adresse de la cellule suivante.

Exemple en C:
struct Cell{
int a;
struct Cell *suivante;
}

Donc pour trouver les valeurs X dans une Liste il faut la parcourir de bout en bout.

Lorsque l'on efface une cellule il faut faire attention a ne pas perdre la suivante.

Supposons une liste ou les cellule s'appelleraient cell1,cell2 et cell3

Si on supprime cell2 brutalement ==> cell1->suivante vaux toujours cell2... ce qui pose problème! 

Donc le plus simple ,pour supprimer cell2 de la liste est de faire cela:
cell1->suivant=cell2-suivant
Même plus  besoin de se soucier de ce qu'est devenu la cellule 2 ( faire attention a la place mémoire d'un ordi, le plus propre c'est de faire un "free(Cell2)" avant de sortir)

Donc pour ton problème, il faut que tu garde en mémoire 2 cellules: celle que tu regarde et celle d'avant (car on ne peux pas revenir en arrière) et c'est tout.

Si tu as besoin de plus de détails répond direct au post.

Flaiso · Answer

Je vous remercie pour toutes ces informations très utiles. Je comprend l'exo mais j'ai des difficultés au niveau de la redaction de la solution. Si je pouvais avoir un exemple... Merci d'avance

tibobo_77 · Answer

Un essaie en C, mais ne m'en veux pas si c'est pas super bien codé..
Je suppose la liste déja faite.

typedef struct Cell{
	int val;
	struct Cell *suivante;
}cell;

//Tu fera attention au cas particulier de l'initialisation (que je te laisse faire si tu reprend ce bout de code), car cette méthode demande une mémoire de 2 cellules(evite de reparcourir n fois la boucle)

void rechercherEtSupprimer (&cellA,&cellB,valCherche){
	//Fait un dernier test
	if(cellB->suivant == null){
		if(cellB->val=valCherche)
			cellA->suivant=NULL;
	}
	//Passe en revue toutes les cellules de la liste Sauf la derniere faiete ci dessus
	while(cellB->suivant != null){
		//si la valeur est trouvée, on la "supprime" et on avance.
		if(cellB->val=valCherche){
			cellA->suivant=cellB->suivant;
			*cellB=cellB->suivant;
		}
		// si elle n'est pas trouvée, on avance
		else{
			*cellA=cellA->suivant; // ou cellA=cellB
			*cellB=cellB->suivant;
		}
	}
}

garion28 · Answer

écrit ici l'algo de ce que tu as compris (l'ordre d'execution de toutes les taches) on te dira si c'est correct ou pas

garion28 · Answer

avec le systeme du lien suivant, c'est a tibobo de t'aider ^^'

mais apparament ca a l'air faux:
tu remplace L1 par L1.lien
ca fait genre: camion=camion.porte_gauche
donc tu remplace le camion par sa propre porte
ca serai plutot L1.valeur=L1.lien

bon après une recherche sur les listes j'ai trouvé 2 type de liste(exemple en perl) mais le principe est qu'une liste et un tableau c'est pareil, c'est juste des synonyme

donc mon algo devrai t'aller (le principe c'est de remplacer la valeur de l'indice i par la valeur de l'indice i+1, afin de "remonter" les valeurs)

Flaiso · Answer

Merci les gars!

Algorithme Avancé

17 réponses

Discussions similaires