(C] liste chainée

Fermé
PIERRE - 21 sept. 2007 à 10:48
w1sm3rhi11 Messages postés 372 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 30 mars 2009 - 24 sept. 2007 à 11:45
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 ?
}
A voir également:

29 réponses

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
0
Neoxeo78 Messages postés 107 Date d'inscription mercredi 5 septembre 2007 Statut Membre Dernière intervention 12 novembre 2007 1
21 sept. 2007 à 11:14
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 ( )
0
Neoxeo78 Messages postés 107 Date d'inscription mercredi 5 septembre 2007 Statut Membre Dernière intervention 12 novembre 2007 1
21 sept. 2007 à 11:15
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
0
lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019 3 569
21 sept. 2007 à 11:30
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.


0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
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 )
0
w1sm3rhi11 Messages postés 372 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 30 mars 2009 53
21 sept. 2007 à 11:49
En effet ils ont la meme adresse regarde le code que je t'ai mis
0
w1sm3rhi11 Messages postés 372 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 30 mars 2009 53
21 sept. 2007 à 11:43
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 @+
0
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 ?
0
w1sm3rhi11 Messages postés 372 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 30 mars 2009 53
21 sept. 2007 à 11:51
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
0
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
0
w1sm3rhi11 Messages postés 372 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 30 mars 2009 53
21 sept. 2007 à 11:58
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
0
w1sm3rhi11 Messages postés 372 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 30 mars 2009 53
21 sept. 2007 à 11:59
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 ^^
0
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 ?
0
w1sm3rhi11 Messages postés 372 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 30 mars 2009 53
21 sept. 2007 à 12:10
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
0
w1sm3rhi11 Messages postés 372 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 30 mars 2009 53
21 sept. 2007 à 12:13
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
0
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...
0
w1sm3rhi11 Messages postés 372 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 30 mars 2009 53
21 sept. 2007 à 12:18
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;
0
lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019 3 569
21 sept. 2007 à 12:28
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
0
w1sm3rhi11 Messages postés 372 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 30 mars 2009 53
21 sept. 2007 à 13:36
Non pas dans le cas ou sa structure est

typedef struct Element
{
int entier;
int decimal;
Element suivant;
} Element;

ca ne marche que si elle est comme ca :

typedef struct Element
{
int entier;
int decimal;
Element* suivant;
} Element;
0
lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019 3 569 > w1sm3rhi11 Messages postés 372 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 30 mars 2009
21 sept. 2007 à 13:41
Non pas dans le cas ou sa structure est
je n'ai pas fait référence à un cas particulier ou déclaration.

il s'agit tout simplement de principe, ensuite en fonction de la façon dont les structures sont definies, bien sûr que la notation change, mais le principe et toujours le même ;-) (le pointeur suivant de l'élément permet d'accèder au élément suivant dans la liste)
0
w1sm3rhi11 Messages postés 372 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 30 mars 2009 53 > lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019
21 sept. 2007 à 13:44
ah la oui c'est sur, dans le principe (et heureusement que tu peux le faire) tu peux faire elem->suivant->suivant c'est le fondement d'une liste chaînée ^^
0
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 )
0
lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019 3 569
21 sept. 2007 à 13:17
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\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
/**********************\
 *     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;
}
0
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
0
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 ?
0