Algorithme Avancé

Fermé
Flaiso - 20 janv. 2010 à 08:43
 Flaiso - 28 janv. 2010 à 08:24
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!

17 réponses

MoodZy Messages postés 976 Date d'inscription lundi 2 juin 2008 Statut Membre Dernière intervention 28 juillet 2014 841
20 janv. 2010 à 09:27
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 ...
1
Salut,

Quel langage?
0
Merci pour la reponse, c'est juste pour donner l'algorithme simple, pas pour le transcrire dans un quelconque langange.
0
MoodZy Messages postés 976 Date d'inscription lundi 2 juin 2008 Statut Membre Dernière intervention 28 juillet 2014 841
20 janv. 2010 à 09:12
En quel langage?
0
garion28 Messages postés 1543 Date d'inscription mardi 16 juin 2009 Statut Membre Dernière intervention 3 avril 2011 404
20 janv. 2010 à 09:45
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
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Flaiso Messages postés 4 Date d'inscription mercredi 20 janvier 2010 Statut Membre Dernière intervention 20 janvier 2010
20 janv. 2010 à 10:56
Ce n'est pas un tableau mais plutot une liste et c'est exactement comme MoodZy l'a expliqué.
0
bjr;
Je me souviens !
Ta liste doit être une liste chainée avec en structure de données de type cellule qui contient un caractère (dans ton cas) et un pointeur sur l'adresse de la cellule suivante. on initie avec la cellule de début et celle de fin qui prend la valeur NULL
on lit la liste tant que le pointeur n'est pas fin
si caractère = x alors on récupère le pointeur de la cellule précédente et on lui donne la valeur de l'adresse de la cellule suivante, c à dire l'adresse qui est le pointeur de la cellule contenant x. La plupart des étudiants détestent les pointeurs mais c'est non seulement utile mais en plus ça peut être 'fun'. JE ne peux en dire plus car j'ai décroché depuis longtemps mais je suis sûr que quelqu'un va prendre le fil sinon j'essaierai de piocher dans ce qui me reste de notes cours de licence. Le mieux est de faire un petit dessin avec flèches pour les poineurs.
0
Flaiso Messages postés 4 Date d'inscription mercredi 20 janvier 2010 Statut Membre Dernière intervention 20 janvier 2010
20 janv. 2010 à 10:59
En fait, c'est la redaction qui pose problème
0
garion28 Messages postés 1543 Date d'inscription mardi 16 juin 2009 Statut Membre Dernière intervention 3 avril 2011 404
20 janv. 2010 à 11:19
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)
0
MoodZy Messages postés 976 Date d'inscription lundi 2 juin 2008 Statut Membre Dernière intervention 28 juillet 2014 841
20 janv. 2010 à 11:22
Tu as surement raison, j'y connais rien en algorithmes, j'ai juste écrit comment moi je coderais... ;)
Que veux tu dire en disant que la liste devra être triée?
0
garion28 Messages postés 1543 Date d'inscription mardi 16 juin 2009 Statut Membre Dernière intervention 3 avril 2011 404
20 janv. 2010 à 11:27
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
0
MoodZy Messages postés 976 Date d'inscription lundi 2 juin 2008 Statut Membre Dernière intervention 28 juillet 2014 841
20 janv. 2010 à 12:33
Souvent pour pouvoir 'supprimer' un élément, il faut recopier la liste dans une nouvelle sans l'élément incriminé... (à moins qu'il existe déjà une fonction remove ou quelque chose du genre) (je ne sais pas s'il existe des langages ou on peut avoir des éléments vides dans une liste)
Et donc il ne reste pas de trou... Enfin moi j'ai pas l'expérience d'énormément de langages informatiques donc ça doit en dépendre...
0
garion28 Messages postés 1543 Date d'inscription mardi 16 juin 2009 Statut Membre Dernière intervention 3 avril 2011 404
20 janv. 2010 à 12:35
alors on a bien la même vision du problème, l'algo que j'ai écris fait exactement ca
0
Flaiso Messages postés 4 Date d'inscription mercredi 20 janvier 2010 Statut Membre Dernière intervention 20 janvier 2010
20 janv. 2010 à 13:02
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?
0
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.
0
tibobo_77 Messages postés 1357 Date d'inscription mardi 21 avril 2009 Statut Membre Dernière intervention 27 juillet 2012 263
20 janv. 2010 à 13:25
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.
0
Flaiso Messages postés 4 Date d'inscription mercredi 20 janvier 2010 Statut Membre Dernière intervention 20 janvier 2010
20 janv. 2010 à 16:45
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
0
tibobo_77 Messages postés 1357 Date d'inscription mardi 21 avril 2009 Statut Membre Dernière intervention 27 juillet 2012 263
21 janv. 2010 à 09:49
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;
		}
	}
}
0
bjr;
ça parait bien !
Les souvenirs du passé qui remontent à la surface - C'est un peu ça la nostalgie
a+
Michel
0
garion28 Messages postés 1543 Date d'inscription mardi 16 juin 2009 Statut Membre Dernière intervention 3 avril 2011 404
21 janv. 2010 à 09:58
é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
0
Voici ce que j'ai fait:
Fonction supprimer_X
variable:
L1,L2: Liste
Debut
Tant que L1 <> Nil Faire
Debut
Si L1.val=X Alors
Debut
L1=L1.lien
Fin
Sinon
Debut
L2.val=L1.val
L1=L1.lien
Fin
L2.lien=L1
Fin
Retourner(L2)
Fin
0
garion28 Messages postés 1543 Date d'inscription mardi 16 juin 2009 Statut Membre Dernière intervention 3 avril 2011 404
27 janv. 2010 à 10:39
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)
0
tibobo_77 Messages postés 1357 Date d'inscription mardi 21 avril 2009 Statut Membre Dernière intervention 27 juillet 2012 263
27 janv. 2010 à 11:13
Remplacer L1 par L1.lien est juste si il suit mon exemple.

Regardez ça, il y a plein de dessins, c'est plus simple qu'à l'écrit.
https://perso.limsi.fr/ancien.html

Sinon il y a d'autre point ou ton algo flanche,Flaiso , try again ;-)
0
Merci les gars!
0