Problème sur les listes chaînées

Ilioo Messages postés 42 Date d'inscription Statut Membre Dernière intervention -
mamiemando Messages postés 33772 Date d'inscription Statut Modérateur Dernière intervention - 16 déc. 2015 à 16:53

Bonjour,

Je suis sur un projet en C, et c'est un langage que je ne maîtrise pas. J'utilise les listes chaînées de type :

typedef struct TListePers{
 struct TListePers *suivant;
 PPers pers;
 } TListePers;

typedef struct TListePers *PListePers;

Où PPers est un pointeur vers une structure représentant une personne.

Le problème c'est que je ne parviens pas à insérer un maillon au début de ma liste, alors que je sais très bien que c'est la base.

Voici les fonctions impliquées :

//ajouter un maillon "vide" en début de liste
PListePers fix_maillon_liste(PListePers liste)
{
 PListePers maillon=malloc(sizeof(TListePers));
 maillon->pers = NULL;
 maillon->suivant = liste;
 return maillon;
}

//ajouter une personne à un maillon en écrasant la précédente
void fix_pers_liste_ecraser_maillon(PListePers liste, PPers pers)
{
 liste->pers = pers;
}

//ajouter un maillon avec une personne
void fix_pers_liste_nouveau_maillon(PListePers liste, PPers pers)
{
 liste = fix_maillon_liste(liste);
 fix_pers_liste_ecraser_maillon(liste,pers);
}

La première fois que j'appelle fix_pers_liste_nouveau_maillon, c'est avec une liste = NULL. Elle doit ensuite se remplir petit à petit mais ma liste reste nulle éternellement...

Merci d'avance pour vos réponses et pour avoir pris le temps de me lire.

Afficher la suite

A voir également:

Problème sur les listes chaînées
Comment faire une liste déroulante sur excel - Guide
Comment cacher sa liste d'amis sur facebook - Guide
Listes déroulantes en cascade excel - Guide
Lister les disques cmd - Guide
Problème liste de diffusion whatsapp - Guide

1 réponse

Réponse 1 / 1

mamiemando Messages postés 33772 Date d'inscription Statut Modérateur Dernière intervention 7 882

Bonjour

Le plus simple c'est dessiner sur un papier et de garder à l'esprit que toute variable non initialisée en C contient a priori une valeur indéterminée. Tu peux représenter un pointeur (= adresse mémoire) par une flèche qui part de la case dans laquelle vers le début de l'objet considéré (dans ton cas, le début d'une cellule).

La structure d'un maillon de liste chaînée est normalement défini (ici ma valeur est un entier) :

typedef struct _cell_t {
  int value;
  struct _cell_t * next;
} cell_t;

Supposons que j'ai une liste b - c - e - f. Note que dans ce qui suit, pour manipuler des cellules je ne vais utiliser que des adresses mémoires (appelées aussi pointeur). C'est beaucoup plus efficace, car ça évite de faire des recopies non seulement inutiles, mais qui pourraient aussi conduire à ne pas faire ce qu'on croit.

push_front (= insérer un maillon a devant b)

1) Allouer cell_t
2) Initialiser sa valeur (ce que as appelé "pers")
3) Initialiser son pointeur vers le maillon suivant à &B (ce que tu as appelé pers). Si je n'ai pas de successeur, par convention j'aurais utilisé NULL.

cell_t * cell_create(int value, cell_t * next) {
  cell_t * c = malloc(sizeof(cell_t));
  c->value = value;
  c->next = next;
  return c;
}

int main() {
    cell_t * a = cell_create(1, NULL);
    return 0;
}

Qui dit

malloc

dit

free

, donc on prévoit le terrain pour désallouer une cellule :

void cell_free(cell_t * cell) {
  free(cell);
}

// cell_create ...

int main() {
    cell_t * a = cell_create(1, NULL);
    free_cell(a);
    return 0;
}

Passons à l'insertion proprement dite : cela revient à créer un maillon devant la tête d'une liste. Il faut donc créer une liste. De quoi avons nous besoin ? Au moins du premier maillon. Certains stockent aussi le nombre d'élément, le dernier maillon etc... C'est une question de choix : plus l'information est accessible facilement, moins ça coûte à l'exécution. Mais cette information additionnelle requiert plus de mémoire, et surtout, requiert de maintenir tout à jour correctement. Donc commençons simple et contentons-nous de :

typedef struct _list_t {
  cell_t * begin;
} list_t;

Encore une fois, je dois prévoir comment allouer une liste vide, on verra plus tard comment la désallouer. Je peux aussi facilement récupérer le premier élément de la liste :

list_t * list_create() {
  return calloc(1, sizeof(list_t));
}

cell_t * list_begin(list_t * list) {
  return list->begin;
}

Ok j'ai maintenant tous les éléments pour faire mon push_front. A priori on attend de cette fonction qu'elle dépende d'une liste list (que l'on modifie) et d'une cellule c (à insérer au début). Il faut :
- corriger la structure list
- corriger le maillon inséré pour qu'il pointe sur l'ancien début de liste (ça tombe bien l'adresse de l'ancienne tête est celle stockée dans la structure list_t).

void list_push_front(list_t * list, cell_t * c) {
  if (list && c) {
    c->next = list_begin(l);
    list->begin = c;
  }
}

Note bien qu'il faut agir dans cet ordre, car si on écrase list->begin par c avant d'avoir corrigé c->next, on ne va pas mettre la bonne adresse dans c->next ! Note aussi la présence du if qui vérifie que list est une adresse mémoire non nulle (et qu'on espère correctement initialisée !) ainsi que pour c.

Malheureusement à ce stade il faudrait créer une cellule (avec cell_create) à chaque fois qu'on ajoute une valeur dans la liste. Ce n'est pas très pratique à l'usage :

// ...

int main() {
   list_t * list = list_create();
   list_push_front(list, cell_create(1, NULL)); // list = {1}
   list_push_front(list, cell_create(2, NULL)); // list = {2, 1}
   return 0;
}

Donc on va ajouter un push_front un peu plus pratique :

void push_front(list_t * l, int value) {
  list_push_front(l, cell_create(value, NULL));
}

Du coup, on peut maintenant écrire :

// ...

int main() {
   list_t * list = list_create();
   push_front(list, 1); // list = {1}
   push_front(list, 2); // list = {2, 1}
   return 0;
}

insert (= insérer un maillon d entre c et e)

Le principe est quasiment le même, on dessine les maillons sur un papier et on regarde les "cases" à corriger :
- le pointeur next de c (qui ne doit plus pointer sur e, mais sur d)
- le pointeur next de d (qui doit désormais pointer sur e)
- la valeur stockée par d (si la cellule d n'est pas déjà initialisée).

Ensuite on réfléchit à ce dont on a besoin. L'adresse de e peut être retrouvée à partir de c (c'est c->next pour le moment). Il faut ensuite l'adresse de la cellule d (ou allouer la cellule d). Supposons que d soit initialisée :

void list_insert(list_t * list, cell_t * c, cell_t * d) {
  d->next = c->next; // l'adresse de e
  c->next = d;
}

... mais comme le paramètre list ne sert à rien on peut aussi écrire :

void list_insert(cell_t * c, cell_t * d) {
  d->next = c->next; // l'adresse de e
  c->next = d;
}

Quoi qu'il en soit, list_insert n'étant pas très pratique pour insérer une valeur (on devra encore utiliser cell_create) on écrit alors :

void insert(cell_t * c, int value) {
  cell_t d = cell_create(value, NULL);
  list_insert(c, d);
}

... ou encore mieux :

void insert(cell_t * c, int value) {
  cell_t d = cell_create(value, c->next);
  c->next = d;
}

Bonne chance

Discussions similaires

Toutes les combinaisons à 4 chiffres de 0000 a 9999

Tous les code possible de 0 à 9 (4 chiffres )

Tri les lettres d'un mot par ordre alphabétique

ordre alphabetique sous word

CMD - Lister les disques

Votre réponse

Discussions similaires