Discussion :

[Twice22]

Bonjour à tous.

Voilà j'ai créé une structure de liste doublement chaînée circulaire dans laquelle je voulais connaître le nombre d'éléments de ma liste pour après avoir un temps d'accès aux nombres d'éléments de ma liste en O(1) et pas en O(n) où n est le nombre d'éléments de ma liste.

Voici la structure :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#ifndef LISTE_H
#define LISTE_H
 
#include <stdio.h>
 
typedef char nomSom[20]; // nomSom de type char[20];
 
typedef struct e
{
    nomSom nomS; // nom des sommets
    struct e* prec;
    struct e* suiv;
} element;
 
typedef struct
{
    element *racine;      // pointeur sur la racine de la liste
    size_t nbElements;
} liste;
 
 
liste* creerListe (void);
void viderListe (liste* maListe);    //pas tester
void supprimerListe (liste** maListe);    //pas tester
 
void ajouterAvant (liste* maListe, nomSom nomSommetS, nomSom nomSommet);
void ajouterApres (liste* monElement, nomSom nomSommetA, nomSom nomSommet);
void ajouterEnTete (liste* racine, nomSom nomSommet);
void ajouterEnQueue (liste* racine, nomSom nomSommet);
void supprimerElement (liste* maListe, nomSom nomSommet);   //problème
 
 
 
#endif

Je test chacune de mes fonctions mais j'ai un problème pour la fonction supprimerElement. Celle-ci prend ma liste d'éléments en entrée et le nom d'un élément de ma liste (les éléments de ma liste sont des sommets d'où nomSommet) et supprime cette élément de ma liste.

Voilà comment j'ai codé ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
// Supprime un élement de la liste
void supprimerElement (liste* maListe, nomSom nomSommet)
{
    int i;
    element* it = (element *) malloc ( sizeof *it );
    it = maListe->racine;   // maListe->racine contient le premier élément de ma liste
 
// si l'allocation a fonctionné ET que ma liste n'est pas vide.
    if (it != NULL && maListe->nbElements != 0)
        {
            // on cherche l'élément nommé it à supprimer
            while (strcmp(it->nomS, nomSommet) != 0 && i < maListe->nbElements + 1)
            {
                it = it->suiv;
                i++;
            }
        }
    // si on a trouvé l'élément it à supprimer
    if (i != maListe->nbElements + 1 && maListe->nbElements != 0)
    {
        //on raccorde l'élt avant it avec l'élt après et inversemment
        it->prec->suiv = it->suiv;
        it->suiv->prec = it->prec;
 
        /* on libère la mémoire allouée */
        free(it);
 
        //on décrémente le nb d'élt de la liste
		maListe->nbElements -= 1;
 
    }
 
 
}

Je vois pas d'où vient le problème. La seule source d'erreur qui me semble probable c'est le fait que je change la racine de ma liste dans la boucle de recherche d'un élément dans ma liste. Pourtant je fais : it = maListe->racine au début et comme dans la boucle j'agis sur it et pas maListe->racine, la valeur de ma racine de maListe reste inchangée... par ailleurs comme j'agis sur des pointeurs. Travailler sur mes éléments it au lieu de ma liste maListe revient au même ? Je suis un peu perdu

Merci à vous.
Bonne soirée

[Médinoc]

Déjà, pourquoi allouer un élément dans ta fonction de suppression?

Aussi, assure-toi de gérer les "edge cases" lors des modifications: Si tu changes le premier élément de ta liste, alors non seulement il n'a pas d'élément précédent, mais tu dois aussi changer le pointeur racine qui lui pointe dessus.

[Twice22]

Oui c'est vrai que l'allocation de sert à rien.

Pour ce qui est des "edges cases" vu que ma liste est circulaire il n'y en a pas (non ?) car mon premier élément à un élément précédent qui est en quelque sorte (je dis quelque sorte car la liste est circulaire) la queue de ma liste.

Mais outre les cas particuliers cette fonction ne... fonctionne pas sur les éléments en 'milieu de liste'.

Edit : Ah non oui je comprends. Si je supprime mon premier élément il faut que ma racine pointe sur le second élément. Merci

[Médinoc]

J'avais mal lu en effet qu'elle était circulaire, mais comme tu t'en es rendu compte, ça ne change pas le fait de devoir changer le pointeur racine.

Attention aussi au cas où la liste ne comprend qu'un seul élément (sauf si tu as toujours une racine dans la liste, un peu comme le \0 d'une chaîne vide).

[Twice22]

Vu que ça marche pas sans savoir pourquoi j'ai enlevé le nombre d'éléments de ma liste doublement chaînée. Du coup j'ai plus qu'une structure et c'est bien plus simple même si j'aurai bien voulu savoir comment faire.

[Médinoc]

J'ai surtout des problèmes avec le fait que la liste soit circulaire: C'est plus dur de savoir où s'arrêter quand on la parcoure.

Pour la suppression, j'ai trouvé ceci:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <string.h>
#include <stdlib.h>
#include <assert.h>
 
element* trouverElement(liste* maListe, nomSom nomSommet)
{
	element* it = maListe->racine;
	if(it!=NULL)
	{
		do
		{
			assert(it->suiv != NULL);
			assert(it->suiv->prec == it);
 
			if(strcmp(it->nomS, nomSommet)==0)
				return it;
 
			it = it->suiv;
		}
		while(it != maListe->racine); //Si on est retourné sur la racine, on arrête.
	}
	return NULL;
}
 
void detruireElement(element* pDel)
{
	free(pDel);
}
 
// Supprime un élement de la liste
void supprimerElement (liste* maListe, nomSom nomSommet)
{
	element *pDel = trouverElement(maListe, nomSommet);
 
	// si on a trouvé l'élément à supprimer
	if (pDel != NULL)
	{
		//Cas spécial n°1: L'élément est tout seul
		if(pDel->suiv == pDel)
		{
			//Si on est dans ce cas, normalement ce qui suit est forcément vrai
			assert(maListe->racine == pDel);
			assert(maListe->nbElements == 1);
			assert(pDel->prec == pDel);
 
			maListe->racine = NULL;
		}
		else
		{
			//Cas spécial n°2: L'élément est le premier de la liste (mais pas seul)
			if(maListe->racine == pDel)
				maListe->racine = pDel->suiv;
 
			//on raccorde l'élt avant it avec l'élt après et inversemment
			pDel->prec->suiv = pDel->suiv;
			pDel->suiv->prec = pDel->prec;
		}
 
		/* on libère la mémoire allouée */
		detruireElement(pDel);
 
		//on décrémente le nb d'élt de la liste
		maListe->nbElements -= 1;
	}
}

Je n'ai pas testé, par contre.

Note: Les assertions servent à vérifier des choses qui ne peuvent jamais être fausses, sauf erreur de programmation (ce qu'on appelle des invariants). Je m'en sers ici pour vérifier la cohérence de la liste chaînée circulaire.