CommentCaMarche
Recherche
Posez votre question Signaler

Algorithme Avancé

Flaiso - Dernière réponse le 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!
Lire la suite 
Réponse
+1
moins plus
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 ...
Ajouter un commentaire
Réponse
+0
moins plus
Flaiso- 20 janv. 2010 à 09:22
Merci pour la reponse, c'est juste pour donner l'algorithme simple, pas pour le transcrire dans un quelconque langange.
Répondre
Ajouter un commentaire
Réponse
+0
moins plus
En quel langage?
Ajouter un commentaire
Réponse
+0
moins plus
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
Ajouter un commentaire
Réponse
+0
moins plus
Ce n'est pas un tableau mais plutot une liste et c'est exactement comme MoodZy l'a expliqué.
Michel- 21 janv. 2010 à 00:50
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.
Répondre
Ajouter un commentaire
Réponse
+0
moins plus
En fait, c'est la redaction qui pose problème
Ajouter un commentaire
Réponse
+0
moins plus
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)
MoodZy 1004Messages postés lundi 2 juin 2008Date d'inscription 28 juillet 2014Dernière intervention - 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?
Répondre
Ajouter un commentaire
Réponse
+0
moins plus
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
MoodZy 1004Messages postés lundi 2 juin 2008Date d'inscription 28 juillet 2014Dernière intervention - 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...
Répondre
Ajouter un commentaire
Réponse
+0
moins plus
alors on a bien la même vision du problème, l'algo que j'ai écris fait exactement ca
Ajouter un commentaire
Réponse
+0
moins plus
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?
Ajouter un commentaire
Réponse
+0
moins plus
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.
Ajouter un commentaire
Réponse
+0
moins plus
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.
Ajouter un commentaire
Réponse
+0
moins plus
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
Ajouter un commentaire
Réponse
+0
moins plus
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;
		}
	}
}
Michel- 21 janv. 2010 à 17:14
bjr;
ça parait bien !
Les souvenirs du passé qui remontent à la surface - C'est un peu ça la nostalgie
a+
Michel
Répondre
Ajouter un commentaire
Réponse
+0
moins plus
é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
Flaiso- 27 janv. 2010 à 09:38
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
Répondre
Ajouter un commentaire
Réponse
+0
moins plus
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)
tibobo_77 1371Messages postés mardi 21 avril 2009Date d'inscription 27 juillet 2012Dernière intervention - 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.
http://www.limsi.fr/Individu/cecile/Enseignement/coursAlgo_V4.pdf

Sinon il y a d'autre point ou ton algo flanche,Flaiso , try again ;-)
Répondre
Ajouter un commentaire
Réponse
+0
moins plus
Ajouter un commentaire
Ce document intitulé «  Algorithme Avancé  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes.

Le fait d'être membre vous permet d'avoir des options supplémentaires.