Liste doublement chaînée.
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:
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:
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
