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

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 ( )

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

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.


lami20j

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 )

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 @+

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 ?

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

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

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

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 ^^

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 ?

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

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

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...

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;

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 lami20j

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 )

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 --------- */

/***************************\
 *     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\n", 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        *
\**********************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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\n", liste->taille);

  affiche (liste);
  printf ("%s - ", liste->debut->donnee);
  printf ("%s\n", 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\n", 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\n", liste->taille);
  affiche (liste);

  printf ("%s - ", liste->debut->donnee);
  printf ("%s\n", 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!\n");
  } else
          affiche(liste);
  return 0;
}