(C] liste chainée

Je t'en prie :)

Bon courage @+

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

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

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)

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

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

up

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

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

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 ?

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;
}

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 )

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

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;

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

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

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

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 ?

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

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