Liste chainée et suppression

Version imprimable

Bonjour,
j'ai fait un programme de liste chaînée et je voudrais supprimer un élément en fonction d'un nom que j'entre mais quoi que je rentre ça ne supprime pas l'élément mais ça supprime toujours le dernier élément de ma liste. Alors voici mon code.
Merci de votre aide

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
void supprimer(Maliste* Liste)
{
	Contact* tmp;
	tmp= Liste->Premier;
	string qui;
	cout << "Qui voulez-vous supprimer ? ";
	cin >> qui;
 
	while (tmp != 0)
	{
		if (tmp->Suivant == 0)
		{
			Liste->Dernier = tmp->Precedant; //on fait pointer le dernier de la liste vers le precedent du contact a supp
			Liste->Dernier->Suivant = 0; //suivant du dernier contact=0
		}
		else
		{
			tmp->Precedant->Suivant - tmp->Suivant; //tmp->precedant->suivant c'est le tmp qu'on a rentré 
			tmp->Suivant->Precedant = tmp->Precedant;
 
		}
		if (qui == tmp->Nom)
		{
			tmp->Suivant = tmp->Suivant->Suivant;
		}
		tmp = tmp->Suivant;
	}
 
 
}

C'est quand même un exercice trivial qu'on résout simplement et en premier lieu au papier/ crayon :mrgreen: :mrgreen:

Et de plus ton code est susceptible d'être hautement plantogène avec les doubles déférencements X->X1->.

Non testé, non compilé :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// list should be a pointer of the fist element
bool supprimer(Maliste* list, string name) {
    if (liste == NULL) { return false; }
 
    Contact* element;
 
//  First Element
    if ((*list)->Nom == name) { element = (*list)->Suivant; delete (*liste); (*list) = element; return true; }
 
    element = (*list)->Suivant;
 
    Contact* precedent = NULL;
    bool not_found = true;
 
    while ((element != NULL) && not_found ) {
        if (element->Nom == name) {
            if (precedent != NULL)  {
                precedent->Suivant = element->Suivant;
            }
 
            delete element;
 
            not_found = false;
        } else {
            precedent = element;
            element   = element->Suivant;
        }
    }
 
    return !not_found;
}

11/07/2015, 22h10
trainingevth

Merci de ta réponse, mais je ne comprend pas

Code:

if ((*list)->Nom == name) { element = (*list)->Suivant; delete(*liste); (*list) = element; return true; }

le pointeur list est de type structure MaListe alors que list->Nom, Nom se trouve dans une autre structure.

Modifies un peu alors :mrgreen: (*)

Tu n'as pas donné tes structures

* Si ta structure Maliste contient le premier et le dernier élément, on peut juste la passer en référence et tester le nom du premier élément ... s'il n'est pas NULL

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool supprimer(Maliste& list, string name) {
    if (liste.premier == NULL) { return false; }
 
    Contact* element;
 
//  First element
    if (list.premier->Nom == name) {
        element = list.premier->Suivant;
 
        if ((list.premier == list.dernier) || (list.premier->Suivant == NULL)) { list.dernier = NULL; element = NULL; }
 
        delete list.premier;
        list.premier = element;
 
        return true;
    }
 
//  ...

rebonjour, j'ai passé toute la journée à essayer de le compiler mais rien à faire toujours une erreur. Donc voici mon code "complet". Si tu peux essayer de m'expliquer le code car j'ai compris le principe (j'ai pris la feuille et le stylo) comme quoi si on veut supprimer le contact2 il faut juste faire pointer le suivant du contact1 sur le précédant du contact3.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
struct Contact
{
	string Nom;
	string Tel;
	Contact* Suivant; //propriété qui garde l'adresse du suivant
	Contact* Precedant; //pour revenir et voir y a qui a coté
};
 
struct MaListe
{
	Contact* Premier; //adresse du premier element
	Contact* Dernier;
	int NombreElement;
};
 
void supprimer(Maliste* Liste)
{
	Contact* tmp;
	tmp= Liste->Premier;
	string qui;
	cout << "Qui voulez-vous supprimer ? ";
	cin >> qui;
 
	while (tmp != 0)
	{
		if (tmp->Suivant == 0)
		{
			Liste->Dernier = tmp->Precedant; //on fait pointer le dernier de la liste vers le precedent du contact a supp
			Liste->Dernier->Suivant = 0; //suivant du dernier contact=0
		}
		else
		{
			tmp->Precedant->Suivant - tmp->Suivant; //tmp->precedant->suivant c'est le tmp qu'on a rentré 
			tmp->Suivant->Precedant = tmp->Precedant;
 
		}
		if (qui == tmp->Nom)
		{
			tmp->Suivant = tmp->Suivant->Suivant;
		}
		tmp = tmp->Suivant;
	}
 
 
}

Citation:

Envoyé par trainingevth

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
		if (tmp->Suivant == 0)
		{
			Liste->Dernier = tmp->Precedant; //on fait pointer le dernier de la liste vers le precedent du contact a supp
			Liste->Dernier->Suivant = 0; //suivant du dernier contact=0
		}
		else
		{
			tmp->Precedant->Suivant - tmp->Suivant; //tmp->precedant->suivant c'est le tmp qu'on a rentré 
			tmp->Suivant->Precedant = tmp->Precedant;
 
		}

Pourquoi tu modifies ta liste avant même d'avoir trouvé l'élément qui correspond à ta recherche?

Citation:

Envoyé par dragonjoker59

Pourquoi tu modifies ta liste avant même d'avoir trouvé l'élément qui correspond à ta recherche?

Parce-qu'il fait trois choses dans une fonction :

Demander un nom à l'utilisateur
Rechercher le contact par son nom
Supprimer le contact

Un conseil : Faire trois fonctions séparées
Code:

1 2 3 4 5 6 7 /** * Demande à l'utilisateur de saisir une chaîne de caractères */ std::string prompt(){ // TODO }
Code:

1 2 3 4 5 6 7 /** * Trouve un contact par son nom, NULL si non trouvé */ Contact * recherche( Maliste& liste, const std::string & nom ){ // TODO }
Code:

1 2 3 4 5 6 7 /** * Supprime contact dans la liste chaînée */ void supprimer(Maliste& liste, Contact * contact){ // TODO }
Chaîne ensuite le tout :
Code:

1 2 3 4 5 6 7 8 9 std::string nom = prompt() ; Contact * contact = recherche(liste, nom); if ( NULL != contact ) { std::cout << "suppression du contact..." << std::endl; supprimer( liste, contact ) ; }else{ std::cout << "contact non trouvé" << std::endl; }
EDIT : supprimer a besoin de liste pour mettre à jour le premier et dernier.

13/07/2015, 15h27
foetus

Sauf que c'est un petit bête de faire une recherche avant la suppression :mrgreen: :mrgreen:

Parce qu'on a va faire 2 fois le même parcours.

Moi, je préfère fusionner la recherche/ suppression en retournant un booléen pour indiquer s'il y a eu découverte/ suppression.

Édit: Quoique avec sa liste doublement-chaînée, si on retourne le maillon contenant le contact, on peut refaire les branchements [... mais avec des doubles déférencements]
13/07/2015, 16h10
bretus

Citation:

Envoyé par foetus

Édit: Quoique avec sa liste doublement-chaînée, si on retourne le maillon contenant le contact, on peut refaire les branchement [... mais avec des doubles déférencements]

D'où l'itérateur dans erase de la std::list ;)

Salut,

Citation:

Envoyé par foetus

Sauf que c'est un petit bête de faire une recherche avant la suppression :mrgreen: :mrgreen:

Parce qu'on a va faire 2 fois le même parcours.

Si ta fonction de recherche renvoie un pointeur sur l'élément trouvé, il n'est absolument pas question de faire deux fois le parcours ;) (à moins, que tu n'aies une liste simplement chainée, je dois l'admettre ;) )
Mais sinon :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* found : pointeur sur l'élément recherché */
if(found){ // si on a trouvé l'élément qu'on cherchait
    if(found->previous){ // s'il y a un élément précédant
        found->previous->next = found->next; // on relie l'élément précédant à "ce qui suit"
    }
    if(found->next){ // s'il y a un élément suivant
        found->next->previous = found->previous; // on relie l'élément suivant à "ce qui précède"
    }
    if(found == liste->end){
        liste->end = found->previous;
    }
    if(found == liste->begin){
        liste->begin = found->next;
    }
    delete found; // on libère la mémoire de l'élément trouvé
}

Ce code fonctionnera quelle que soit la position de l'élément trouvé ;)

Maintenant, en effet, si tu travailles avec une liste simplement chainée, tu as peut etre intérêt à renvoyer une structure qui te permette de récupérer deux pointeurs :
un pointeur sur l'élément précédant (s'il existe) et l'élément recherché, sous une forme proche de

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
struct SearchResult{
    SearchResult(Element * previous, Element * found):
        previous(previous), found(found){}
    Element * previous;
    Element * found;
};
SearchResult findElement(std::string const & name, List * list){
    Element * previous = list->first;
    if(previous->name == name){
        return SearchResult(nullptr,previous);
    }
    Element * found;
    while(previous->next && previous->next->name != name){
        previous = previous->next;
    }
    if(!previous->next){
        return SearchResult(nullptr,nullptr);
    }
    return SearchResult(previous, found);
}
void removeElement(std::string const & name, List * list){
    SearchResult found = findElement(name, list);
    if(found->found){
        if(!found->previous){
            assert(found->found = list->first);
            list->first = found->next;
        }
        if(!found->found->next){
            assert(list->last == found->found);
            list->last = found->previous;
        }
        if(found->previous)
            found->previous->next = found->found->next;
        delete found->found;
    }
}

14/07/2015, 17h43
trainingevth

Merci pour vos réponses je vais voir si je peux le faire compiler.