(C] liste chainée

Question

Bonjour j'ai un petit problème de C.
Soit la struct suivant :
typedef struct element *Element
typdef struct element
{
 int entier;
 int decimal ;
 Element next ;
} ;

après j'ai :
Element element = malloc(sizeof(struct Element));

void ajouter(Element a,int b,int c)
{
  Element node = a ;
  while(node ->suivant != null)
     node  = node ->suivant ;
  Element nouveau = malloc(sizeof(struct Element));
  nouveau->entier = b ; nouveau->decimal = c ;
  node->suivant = nouveau ;
}

void supprimer_element(Element a,int b,int c)
{
    Element node = a ;
    while( node ->entier != b && node->decimal != c && node->suivant != null )
       node = node ->suivant ;
   
   /* LA je bloque */
  Comment faire pour libérer la mémoire et affecter a la node_precedente la valeur de la node_suivante ( par rapport a celle que nous voulons supprimer ?
}

PIERRE · Answer

Dsl je reposte, je n'arrive pas à éditer.

En effet si nous avons deux elements elem_1 et elemt_2 et elem_3.
l'adresse mémoire de elem_1->suivant = elem_2 et elem_2->suivant = elem_3 ?

donc comment faire pour affecter à élem_1 l'adresse de elem_3 par exemple et supprimer elem_2 ensuite sachant que 
elem ( ou node dans mon code )
sont des pointeurs sur une structure de type element

Neoxeo78 · Answer

Bonjour,

Je te donne la voie à suivre :

Pour supprimer un élément d'une liste chaînée tu dois :
1 - isoler l'élément à supprimer.
     Petit exemple : 
     Si tu as trois éléments qui se suivent elem1 elem2 et elem3
     On veut supprimer element 2
     tu casse le lien entre elem1 et elem2 en fasant elem1->suivant = elem3
2 - tu libère la mémoire de l'élément à supprimer en faisant un free ( )

Neoxeo78 · Answer

petite précision
Lorsque tu casse le lientu dois plutot faire elem1->suivant = elem2->suivant 
pour gerer le cas ou elem2 est le dernier élément de ta liste chaînée

lami20j · Answer

Salut,

tu dois penser a plusieurs choses

1. sauvegarder la tete et la queue de la liste (en utilisant deux pointeur)
Ca te permettre d'avoir un contrôle sur ta liste, et si jamais tu dois faire des opérations à la fin de la liste tu ne seras pas obligé de réparcourir la lite de la tete à la fin
2. tu peux aussi sauvegarder la taille de la liste qui pourras toujours servir pour les opérations d'insertion ainsi que pour la comptabilité des éléments
3. pour l'insertion d'un élément on a 3 possibilités
- insertion au début de la liste
- insertion ailleurs dans la liste
- insertion à la fin de la liste
4. pour la suppression d'un élément on a
- suppression au début de la liste
- suppresson ailleurs dans la liste
La supression de dernier élément n'est pas optimale vu qu'il n'y a pas de pointeur vers l'élément précedent

L'utilisation des listes doublement chaînées offre plusieurs possibilités.

Justement je suis en train de préparé 2 tutos avec les listes simplement et doublement chaînées, ça sera pour la semaine prochaine.

PIERRE · Answer

D'accord. Donc dans mon cas je doit faire : ( sans les tests de null etc... )
void supprimer_element(Element a,int b,int c)
{
Element node = a ;
while( node ->entier != b && node->decimal != c && node->suivant != null )
   node = node ->suivant ;

  Element supprimer = node ;
  node = node->suivant ;
  free(node ) ?
}
 ou encore 
void supprimer_element(Element a,int b,int c)
{
Element node = a ;
Element precedent ;
while( node ->entier != b && node->decimal != c && node->suivant != null ) {
   precedent = node ; 
   node = node ->suivant ;
  }
  precedent->suivant = node->suivant ;
  free(node) ; 
}

Par contre je ne comprend pas. sachant que :
precedent->suivant et node on la même adresse mémoire ? ( je ne me trompe pas ? )
precedent->suivant = node->suivant ; /*  node = node->suivant  ca revient au même */
Après si on fais un free(node); /* ca reviendrais a faire free(precedent->suivant); non ? */ 


dsl je débute avec les structures et pointeurs, donc j'aimerais bien comprendre...
( le prof nous impose cette structure... sinon )

w1sm3rhi11 · Answer

En gros tu dois procéder ainsi : tu dois faire une sauvegarde de l'adresse du noeud suivant du noeud à supprimer

void supprimer (Element* tete, int b, int c)
{
Element* cuseur = (Element*)malloc(sizeof(Element));
curseur=tete;

Element* prec = (Element*)malloc(sizeof(Element));
prec=tete;

Element* save;

while( (curseur->entier!=b || curseur->decimal!=c) && (curseur!=NULL) )
{
prec=curseur;
curseur=curseur->suivant;
}

//Cas différents de la tete de liste
if (curseur && prec!=curseur)
{
save=curseur->suivant;
prec->suivant=save;
free(curseur);
}

//Cas tête de liste
if(prec==curseur && curseur)
{
free(curseur);
}

}

Je n'ai pas pu testé mais il ne s'agit la que des idées, ca peut fonctionner tel quel comme foirer tel quel ^^

PS : fais attention à la condition d'arrêt du while qui a changé :p


Voia j'éspère que ca t'aidera @+

PIERRE · Answer

D'accord. donc  mon code était bon ?

Par contre un truc que je ne comprend pas ma structure est la suivante :

typedef struct element *Element
typdef struct element
{
int entier;
int decimal ;
Element next ;
} ;

Moi je fais ca :
Element element = malloc(sizeof(struct element)); 
et toi ca :
Element* cuseur = (Element*)malloc(sizeof(Element)); 

Qu'elle est la différence au niveau du programme ? Est-ce que c'est moi qui me trompe ou les deux sont corrects ?

w1sm3rhi11 · Answer

le malloc te retourne un void*, il t'alloue un emplacement mémoire pour une instance de ta structure. C'est pour ca qu'il faut caster le résultat de ton malloc en (Element*)

Je n'ai pas testé ta version de la déclaration, mais je ne suis pas sur que ca marche as tu testé ?

Dans tous les cas ma version fonctionne car c'est celle que j'utilisais :)

Par ailleurs tu ne peut pas affecter une adresse à une valeur c('est incompatible donc dans tous les cas pour utiliser malloc il te faut un pointeur

PIERRE · Answer

Element element = malloc(sizeof(struct element));  passe à la compilation. donc je doit faire ca plutot :
Element element = (Element)malloc(sizeof(struct element)); 

D'accord ils ont la même adresse mais le fait de faire :
precedent->suivant = node->suivant ; // affecter à precedent->suivant l'adresse de node->suivant ?
free(node) ; // libération de node

w1sm3rhi11 · Answer

non tu dosi vraiment passer par des pointeurs pour ca puisque de toute facon avec 

Element element = (Element)malloc(sizeof(struct element)); 

tu ne pourras pas faire des indirections du type element->suivant mais seuelemnt element.suivant qui t'obligeront à travailler sur des copies de varaible et non  las variables elles memes et lorsque la fonction supprimer sera terminée, cette variable sera detrutie automatiquement

EElement* cuseur = (Element*)malloc(sizeof(Element));   tu accedes directement à l'adresse de ta variable et non à sa valeur et tu modifie le contenu en mémoire

w1sm3rhi11 · Answer

Sinon pour precedent->suivant = node->suivant ; // affecter à precedent->suivant l'adresse de node->suivant ? 

Si tu fais ca, lors de la libération de node, precedent->suivant va pointer sur NULL do'u l'interet de sauvegarde l'adresse du noeud suivant du noeud à supprimer Oo ^^

PIERRE · Answer

Oui mais je ne comprend vraiment pas Element est déjà un pointeur sur une structure de type element.

save = node->suivant ; 
free(node);
precedent->suivant = save  ;

Donc en faite je doit utiliser des pointeurs qui pointe sur un pointeur de stucture ( c'est assez compliqué comme truc :s ) il n'y a pas plus simple ?

w1sm3rhi11 · Answer

Un pointeur c'est une variable qui contient une adresse. Jusque la j'pense que tu es d'accord.

Connaitre l'adresse d'une variable veut dire avoir la possibilité d'accéder au contenu mémoire à cette adresse.

Ta structure sera ca : 

typedef struct Element
{
int entier;
int decimal;
Element* suivant;
} Element;

Ca veut dire qu'un noeud possède l'adresse de son successeur et pas seulement une copie de sa valeur.

Dans Element* suivant tu vas pouvoir mettre n'importe quelle adresse d'un noeud et c'est uniquement cela qui te permet de faire du chaînage.

Imagine si tu utilises Element suivant au lieu de Element* suivant

Dans suivant tu ne pourras mettre que des copies de valeurs d'un noeud deja existant et non pas son emplacement mémoire comme tu le souhaites

w1sm3rhi11 · Answer

Le fait d'utiliser 

save = node->suivant ;
free(node);
precedent->suivant = save ; 

te permets de retrouver l'adresse (comme une adresse postale finalement) du noeud suivant du noeud que tu veut supprimer.

Si tu ne le fais pas il ya une rupture du chaînage puisque le noeud suivant du neoud a supprimmer est detaché des neouds avant lui

PIERRE · Answer

Attend :
Toi tu utilise 
typedef struct Element
{
int entier;
int decimal;
Element* suivant;
} Element; 

et moi 

typedef struct element *Element
typedef struct element
{
int entier;
int decimal;
Element suivant;
} ; 

...
donc je peux faire ca :
precedent->suivant= node->suivant ; // remplacer l'adresse de node par node->suivant...
free(node); // libération de node...

w1sm3rhi11 · Answer

Exemple (je reprends le tiens) : 

typedef struct element *Element
typedef struct element
{
int entier;
int decimal;
Element suivant;
} ; 

tu peux faire Element->suivant; mais pas Element->suivant->suivant;

Le chainage dans ton cas ne marchera pas et ta boucle while plantera;

lami20j · Answer

tu peux faire Element->suivant; mais pas Element->suivant->suivant; 

si on consider que TETE c'est un pointeur vers le 1er élément de la liste alors

TETE->suivant pointe vers le 2ème élément
TETE->suivant->suivant pointe vers 3ème élément
TETE->suivant->suivant->suivant pointe vers 4ème élément
.
.
jusqu'à quand TETE->suivant...............->suivant point vers NULL

donc on peut faire Element->suivant->suivant

PIERRE · Answer

D'accord, merci de je comprend mieux.
Une dernière question que je me pose et après je part :
typedef struct element *Element
typedef struct element
{
int entier;
int decimal;
Element suivant;
}  elem ; 

Au moment de faire le malloc je doit faire :
elem e1 = (elem *)malloc(sizeof(elem )); // d'accord.

Element e2 = (Element)malloc(sizeof(elem)); // je doit faire ca ou je réserve un espace xx octect = a la taille de la structure
Element e2 = (Element)malloc(sizeof(Element)); // je réserce un espace de 4 octect ( car pointeur )

lami20j · Answer

Re, Voici un exemple purement didactic pour comprendre les opérations sur une liste chaînée /* ---------- liste.h ----------- */ typedef struct ElementListe { char *donnee; struct ElementListe *suivant; } Element; typedef struct ListeRepere { Element *debut; Element *fin; int taille; } Liste; /* initialisation de la liste */ void initialisation (Liste * liste); /* INSERTION */ /* insertion dans une liste vide */ int ins_dans_liste_vide (Liste * liste, char *donnee); /* insertion au début de la liste */ int ins_debut_liste (Liste * liste, char *donnee); /* insertion Ã a fin de la liste */ int ins_fin_liste (Liste * liste, Element * pilote, char *donnee); /* insertition ailleurs */ int ins_liste (Liste * liste, char *donnee, int pos); /* fonction globale d'insertion */ int insertion (Liste * liste, Element * pilote, char *donnee); /* SUPPRESSION */ int supp_debut (Liste * liste); int supp_dans_liste (Liste * liste, int pos); void affiche (Liste * liste); void detruire (Liste * liste); /* -------- FIN liste.h --------- */ Les fonctions/***************************\ * liste_function.h * \***************************/ void initialisation (Liste * liste) { liste->debut = NULL; liste->fin = NULL; liste->taille = 0; } /* insertion dans une liste vide */ int ins_dans_liste_vide (Liste * liste, char *donnee){ Element *nouveau_element; if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) return -1; if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->suivant = NULL; liste->debut = nouveau_element; liste->fin = nouveau_element; return 0; } /* insertion au début de la liste * * les éléments seront decalé de la façon suivante * * le 1er passe en position 2, le 2Ã¨ en position 3, ... * */ int ins_debut_liste (Liste * liste, char *donnee){ Element *nouveau_element; if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) return -1; if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->suivant = liste->debut; liste->debut = nouveau_element; return 0; } /*insertion à la fin de la liste */ int ins_fin_liste (Liste * liste, Element * pilote, char *donnee){ Element *nouveau_element; if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) return -1; if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); pilote->suivant = nouveau_element; nouveau_element->suivant = NULL; liste->fin = nouveau_element; return 0; } /* insertion à la position desirée * la position sera demandé */ int ins_liste (Liste * liste, char *donnee, int pos){ if (liste->taille < 2) return -1; if (pos < 1 || pos >= liste->taille) return -1; Element *courant; Element *nouveau_element; int i; if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) return -1; if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) == NULL) return -1; courant = liste->debut; for (i = 1; i < pos; ++i) courant = courant->suivant; if (courant->suivant == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->suivant = courant->suivant; courant->suivant = nouveau_element; liste->taille++; return 0; } /* fonction globale d'insertion * * en fonction d'élément pilote * * - l'insertion se fera : * * - dans une liste vide * * - au début de la liste * * - à la fin de la liste * */ int choix_insertion (Liste * liste, Element * pilote, char *donnee){ if (pilote == NULL && liste->taille == 0) ins_dans_liste_vide (liste, donnee); else if (pilote == NULL && liste->taille != 0) ins_debut_liste (liste, donnee); else if (liste->taille != 0 && pilote != NULL && pilote->suivant == NULL) ins_fin_liste (liste, pilote, donnee); liste->taille++; return 0; } /* suppression en début de la liste * * cette fonction sera utiliser dans une boucle * * pour detruire la liste (voir la fonction "detruire" ) * */ int supp_debut (Liste * liste){ if (liste->taille == 0) return -1; Element *element_supp; element_supp = liste->debut; liste->debut = liste->debut->suivant; if (liste->taille == 1) liste->fin = NULL; free (element_supp->donnee); free (element_supp); liste->taille--; return 0; } /* supprimer un element après la position donnée * la suppresion à la fin de la liste sera interdite * pour la suppression dans une liste avec un seul élément * utiliser la fonctionn "supp_debut" * */ int supp_dans_liste (Liste * liste, int pos){ if (liste->taille <= 1 || pos < 1 || pos >= liste->taille) return -1; int i; Element *courant; Element *supp_element; courant = liste->debut; for (i = 1; i < pos; ++i) courant = courant->suivant; supp_element = courant->suivant; courant->suivant = courant->suivant->suivant; if(courant->suivant == NULL) liste->fin = courant; free (supp_element->donnee); free (supp_element); liste->taille--; return 0; } /* affichage de la liste */ void affiche (Liste * liste){ Element *courant; courant = liste->debut; while (courant != NULL){ printf ("%p - %s ", courant, courant->donnee); courant = courant->suivant; } } /* detruire la liste */ void detruire (Liste * liste){ while (liste->taille > 0) supp_debut (liste); } /* -------- FIN liste2.h --------- */ liste.c/**********************\ * liste.c * \**********************/ #include #include #include #include "liste.h" #include "liste_function.h" int main (void) { char choix; char *nom; Liste *liste; Element *pilote; if ((liste = (Liste *) malloc (sizeof (Liste))) == NULL) return -1; if ((nom = (char *) malloc (50)) == NULL) return -1; pilote = NULL; choix = 'o'; initialisation (liste); int pos; while (choix == 'o'){ printf ("Entrez un element : "); scanf ("%s", nom); getchar (); choix_insertion (liste, pilote, nom); pilote = liste->fin; /* insertion à la fin */ printf ("Vous voulez continuer [o/n] : "); choix = getchar (); } printf ("%d ", liste->taille); affiche (liste); printf ("%s - ", liste->debut->donnee); printf ("%s ", liste->fin->donnee); printf ("Entrez la position apres laquelle le nouveau element sera installer : "); scanf ("%d", &pos); printf ("Entrez un element : "); scanf ("%s", nom); getchar (); ins_liste (liste, nom, pos); printf ("%d ", liste->taille); affiche (liste); printf ("Entrez la position apres laquelle l'element sera supprime : "); scanf ("%d", &pos); getchar (); supp_dans_liste (liste, pos); printf ("%d ", liste->taille); affiche (liste); printf ("%s - ", liste->debut->donnee); printf ("%s ", liste->fin->donnee); printf ("Voulez-vous detruire la liste [o - detruire;n - afficher] : "); if ((choix = getchar ()) == 'o'){ detruire (liste); printf ("La liste a ete detruite! "); } else affiche(liste); return 0; }

PIERRE · Answer

D'accord merci, je viens de teste ton code est tout est bcp plus clair.
Par contre une question que je me pose.
  supp_element = courant->suivant;
  courant->suivant = courant->suivant->suivant;
Peut aussi s'écrire ( mais moi lisible )
  supp_element = courant->suivant;
  courant->suivant =  supp_element->suivant; si j'ai bien compris ?

lami20j · Answer

courant->suivant = supp_element->suivant; si j'ai bien compris ?
Non.
supp_element c'est un pointeur que j'utilise pour avoir une référence vers l'élément que je doit supprimer
ça me permettre de faire free() sur supp_element

donc à eviter cette interpretation, même si ça pourrait être valable

je fait courant->suivant = courant->suivant->suivant  justement pour montrer l'enchaînement ;-)

PIERRE · Answer

De plus, tu utilise souvant :

typedef struct ElementListe
{
char *donnee;
struct ElementListe *suivant;
} Element;
Element *elem ;
... /* du code */
elem->suivant->suivant

peut se remplacer par si je suis là logique :

typedef struct ElementListe *PElement ;
typedef struct ElementListe
{
char *donnee;
PElement suivant;
} Element;
PElement elem ;
elem->suivant-suivant

? Element *elem ~= PElement elem reviens a la même :s normalement

PIERRE · Answer

up

lami20j · Answer

Salut,

typedef struct ElementListe *PElement ;
typedef struct ElementListe
{
char *donnee;
PElement suivant;
} Element;
PElement elem ; 

PElement c'est un pointeur du type ElementListe* , ce qui te permettra de definir le pointeur suivant dans la structure Element
En revanche elem c'est un pointeur de type Element*
donc il faut declaré

typedef struct ElementListe *PElement ;
typedef struct ElementListe
{
char *donnee;
PElement suivant;
} Element;
Element elem ; --
lami20j

w1sm3rhi11 · Answer

typedef struct ElementListe *PElement ;
typedef struct ElementListe
{
char *donnee;
PElement suivant;
} Element;
PElement elem ;

marche tout aussi bien ;)

Il suffira alors d'utiliser elem->suivant pour pointer sur l'élément suivant de la liste :)

lami20j · Answer

et que PIERRE comprend c'est le principal ;)
D'accord avec toi, c'est ça mon but ;-)
Et voici sa réponse
D'accord merci, je viens de teste ton code est tout est bcp plus clair. 

 juste que je trouve ton exemple un peu alambiqué 

Ben, justement il n'est pas alambique (ce qui ne vas changer pas ton avis ;-)
Au contraire j'ai crée le code dans le but didactic pour comprendre les opérations sur les listes chaînées.
Et je l'ai fait puisque à vrai dire je n'ai pas vu encore une présentation basique à la portée pour tout débutant.
Chaque fonction pourra être étudier sans se soucier d'une autre.
Si un structuration des opérations ne te semble pas organisée alors je suis désolé.

C'est loin d'être une bonne implementation.
Une impléméntation se fait en fonction des besoins.


Bref, je le trouve plûtot organisé, quoi que assez long, ce qui est d'ailleurs normal vu que pour chaque opération j'ai crée une fonction.

Je pense que c'est essentiel de comprendre le principe et ensuite de comprendre les opérations qu'on peut effectuer sur une liste

- sauvegarder le début et la fin de la liste pour garder le contrôle
- incrementation ou decrementation de la taille en fonction des opérations d'insertion ou suppression
- allocation de la mémoire pour le nouveau élément
- insertion dans une liste vide
- insertion au début
- insertion à la fin
- insertion ailleurs dans la liste
- suppression au début
- suppression à la fin
- suppression ailleurs dans la liste
- affichage de la liste
- detruire la liste

J'ai fait aussi une représentation pour chaque opérations pour être encore plus clair.

On pourrait écrire une seule fonction qui groupe les opérations d'insertion ainsi qu'une seule fonction qui groupe les opérations de suppression (voir Maîtrise des algorithmes en C)

w1sm3rhi11 · Answer

Pour ma compréhension ca ira ^^ j'ai largement utilisé les listes chaînées et créé certaines du genre hétérogène ou des trucs comme ca.

Ce que je voulais dire est simplement que je trouvais la structure de la liste un peu compliquée pour les débutants qui se lancent la dedans. 
Apparemment j'ai eu tort ^^ en tout cas vu que c'est toi qui a fait ca c'est du beau travail :)

lami20j · Answer

que je trouvais la structure de la liste un peu compliquée pour les débutants qui se lancent la dedans. 
je vais tenir compte de ton opinion ;-) et je vais essayer de modifier.
Merci ;-)

w1sm3rhi11 · Answer

Je t'en prie :)

Bon courage @+

(C] liste chainée - Page 2

Newsletters