[Cours 05] Liste chainees

Bonjour a tous et bienvenue a ce nouveau cours de C

Nous allons aborder une notion tres importantes (presque autant que les pointeurs, sauf qu'il se sert des pointeurs ), mais qui n'est pas tres complique a mettre en place. Du moins je vais essayer de faire en sorte que vous comprenniez facilement .

A savoir, il est completement inutile de poursuivre plus loin si vous n'avez pas assimile les notions du Cours 03, a savoir, les pointeurs, ainsi que le Cours 04, sur les tableaux et surtout, les structures, car nous allons nous amuser a voyager dans la memoire grace a ces pointeurs . Cependant, pour ceux qui n'ont pas compris le fonctionnement des pointeurs, il n'est pas trop tard pour poser vos questions dans les sections appropriees .

Let's go !

Code:

typedef   struct   s_list
{
  void      *data;
  struct s_list   *next;
}      t_list;

Presentation

Encore une nouvelle chose a apprendre ? C'est quoi cette fois

A savoir, ce n'est pas un notion excessivement difficile a comprendre compare aux derniers cours. C'est quelque chose qui va vous faciliter la gestion de donnees de vos programmes, notamment si vous ne savez pas jusqu'a ou la base de donnee s'etendra.

Exemple :

-Vous devez gerer la gestion d'objet que possedent votre groupe de heros. Comment faites-vous ?

Je pense que certains utiliserons les tableaux ou une enorme structure avec tout les objets existants. Normal, vu que je ne vous ai appris que ca .

Mais plusieurs problemes apparaissent : deja, pour le tableau, quelle taille allez-vous lui donner ? Vu que vous ne pouvez pas savoir ce que le joueur possede a X moment du jeu. Donc aucun moyen d'allouer de maniere universelle le tableau. ensuite pour la structure, je n'en parle meme pas car a moins que vous ne definissiez toute la structure des le debut, vous ne pourrez plus modifier les differents elements qui la composent. Ainsi, vous prendrez toute la memoire pour du vide .

Code:

typedef   struct   s_obj
{
  int    potion;
  int   ether;
  int   herbe;
  int   dague;
  ...;
}      t_obj;

Bref, on va adopter cette methode pour stocker nos objets. On va mettre la quantite d'objet par element contenu, puis, dans le menu d'objet du joueur, on va afficher ce qu'il possede. Supposons que l'on limite a 20 le nombre d'objet differents que le joueur peut porter, et que l'on possede 1500 objets differents (un petit RPG en gros ), on voit devoir parcourir les 1500 elements de la structure pour afficher l'objet qui correspond si jamais sa quantite est au dessus de 0. Non seulement on va perdre enormement de temps en faisant ca, de plus il nous faudra un autre tableau avec le nom de l'element correspondant, car celui-ci n'est stocke nul part. Et enfin c'est nul car pour limiter le nombre d'iobjet a 20, c'est presque du suicide...


Autre exemple :

Vous faites un jeu avec la possibilite d'enroler dans votre aventure des nouveaux personnages.

Donc structure presques obliges, qui contiendront les caracteristiques des personnages. Cependant, vu qu'on n'est pas oblige d'enrouler tel ou tel personnages, c'est la meme galere pour savoir combien de "fiche" on prepare.


Dernier exemple :

Pour mon portage de mon jeu Space Invasion, quand je rafraichie l'image, je redessinne les missiles tires par mon vaisseau a l'ecran. Pour cela, dans ma boucle de jeu, j'appelle une fonction qui s'occupe de ca. Cependant, contrairement au jeu original, on peut tirer autant de missile que notre doigt permet .

Ainsi, comment dois-je m'y prendre pour appeler autant de fois la fonction temps qu'il me reste de missile ? A savoir, j'ai une structure de ce genre :

Code:

typedef   struct   s_mis
{
  void   *image;
  int   x;
  int   y;
}      t_mis;

Classique .

Je ne vais pas m'amuser a trouver plein de cas de figure irrealisable niveau gain de performance/memoire, mais vous dire tout de suite que j'utilise les Listes Chainees

Creation

Je vous conseille de reutilisez les codes que je vous donne ci-dessous, car ce sont des codes generiques permettant la manipulation des listes chainees. Bien entendu, il vous faudra les readapter en fonction de vos besoins et de donnees contenues dans la structure.

Code:

typedef   struct   s_list
{
  void      *data;
  struct s_list   *next;
}      t_list;

A savoir, la presentation de la structure est obligatoirement celle ci-dessus. Sauf pour le nom de la structure, le nom des variables et le

Code:

void    *data

qui peut-etre remplace par toutes les informations que vous souhaitiez.
En fait il n'y a que

Code:

struct s_list *next

qui est obligatoire .


Commencons par l'initialisation de la liste chainee

Code:

typedef   struct   s_list
{
  void      *data;
  struct s_list   *next;
}      t_list;

int      main()
{
  t_list   *liste;

  liste = 0;
  return (0);
}

Apres avoir creer la structure, je la declare comme d'habitude et je lui assigne la valeur de '0'.
Pourquoi, me direz-vous, tout simplement car cela va marquer la fin de la liste. Et oui, il faut bien s'arreter un jour .


Ensuite, pour l'ajout d'un nouveau maillon (les maillons qui constituent une chaine ), il faut proceder comme ce qui suit :

Code:

typedef   struct   s_list
{
  void      *data;
  struct s_list   *next;
}      t_list;

void      my_put_in_list(t_list **liste, void *data)
{
  t_list   *new_elem;

  new_elem = malloc(sizeof(*new_elem));
  new_elem->data = data;
  new_elem->next = *liste;
  *liste = new_elem;
}

int      main()
{
  t_list   *liste;

  liste = 0;
  my_put_in_list(&liste, "Je suis le premier element.");
  my_put_in_list(&liste, "Je suis le deuxieme element");
  return (0);
}

Explication : apres avoir declare ma liste, et l'avoir initialisee, j'ai decide de lui ajouter deux maillons contenant les phrases ci-dessus. Pour cela, j'ai une fonction "my_put_in_list", qui va s'occuper de cela. Je lui envoi donc l'adresse de ma liste, histoire que toutes les modifications que j'apporte a ma liste, accompagnent ma liste a son retour, et la phrase que je veux rentrer.
Puis, ma fonction cree un nouveau maillon, attribue une plage memoire (qui va prendre autant de place que la sturcture aura besoin en fonction des parametres qui la composent et penser a free-er a la fin ), puis, ce nouveau element recoit ma chaine de caractere, attribue a son "next (j'expliquerai son utilite juste apres), le contenu de "liste" (soit 0), puis j'assigne un nouveau pointage a "liste", qui ne pointera plus vers 0, mais vers le nouveau element.

Puis, je souhaite ajouter un deuxieme maillon a ma liste. La, meme histoire : j'envoi mes elements a ma fonction, je cree un nouveau maillon, j'atttribue les valeurs, je fait pointer "next" sur ce que pointe "liste" (soit 0.... et non sur le premier maillon, car "liste" ne pointe plus sur 0, mais sur le premier element que l'on a cree precedement . C'est le "next" du premier element qui contient 0 ), puis je repointe "liste" sur ce nouveau maillon.

Ainsi, ma chaine contient desormais 2 maillons . Je peux rappeler autant de fois ma fonction, et les elements s'ajouteront petit a petit .

Mais si on suit ton raisonnement, les nouveaux elements se placeront au debut

Et oui, quel bon sens de l'observation .
Ca peut paraitre stupide, mais c'est comme ca ! C'est pour vous faire travailler un peu .
Comment ? Vous ne comprennez pas ? Ben, c'est simple ! Ce sera dans les exercices a faire a l'issue de ce cours .

Deplacement

Apres avoir cree votre liste chainee, il faut pouvoir se deplacer dedans, sinon ca ne sert a rien .

Code:

typedef   struct   s_list
{
  void      *data;
  struct s_list   *next;
}      t_list;

void      my_put_in_list(t_list **liste, void *data)
{
  t_list   *new_elem;

  new_elem = malloc(sizeof(*new_elem));
  new_elem->data = data;
  new_elem->next = *liste;
  *liste = new_elem;
}

int      main()
{
  t_list   *liste;
  t_list   *start;

  liste = 0;
  my_put_in_list(&liste, "Je suis le premier element.");
  my_put_in_list(&liste, "Je suis le deuxieme element");
  start = liste;
  while (liste != 0)
    {
      my_putstr(liste->data);
      liste = liste->next;
    }
  liste = start;
  return (0);
}

Deja, a savoir, la fonction "my_putstr", est une fonction personnelle qui me permet d'afficher un message a l'ecran. Il n'y a rien de surprenant ici .
En gros, je ne fais qu'afficher le contenu de ma liste .

Treve de bavardage et place aux explications .
Pour commencer, nous avons creer un pointeur pour sauvegarder la position de depart de la liste. Je l'ai stockee dans ma variable "*start".
Ensuite, je fais une boucle, qui dit que tant que je ne suis pas a la fin de ma liste, j'affiche le contenu de "data" et je passe au maillon suivant.
Donc, effectivement, j'affiche le contenu de "data" avec

Code:

my_putstr(liste->data);

puis je passe a l'element suivant

Code:

liste = liste->next

.

En effet, vu que le fameux "next" contient l'adresse du maillon suivant, il suffit que je donne le pointeur de "next" a "liste" pour le faire avancer au maillon suivant .
Donc il va continuer ainsi, tant qu'il reste des elements, jusqu'au moment ou "next" vaudra 0 !

Et oui !, vu que le premier maillon se retrouve a la fin de la liste et que je lui avais donne la valeur de 0, vu que "liste" vaut 0, on sort de la boucle .

Mais sacre probleme ! Comment fait-on pour retrouver notre position d'origine vu qu'il n'y a plus de "next" pour nous ramener au debut ? Tout simplement grace a la variable "start" qui possede l'adresse du premier maillon .

Liste chainee en images

Ca peut paraitre confus, cette histoire de "je te passe mon adresse" et de "mais avant tu te souviens de la mienne", etc...


On va commencer par une petite histoire .
Deja, rappelez-vous (et si ce n'est pas le cas, je vous invite a relire les anciens cours ), que les pointeurs pointent comme leur nom l'indiquent, sur des cases de memoire. C'est partit !

[Histoire]

Il etait une fois, une petite liste chainee du nom de "Lista" (jolieee ). Un jour, son ecole decida d'organiser un voyage de reve, mais assez couteux (dur dur les reves !)

Elle decida alors de faire une collecte dans sa ville : elle vendrait des chocolats contre un peu d'argent.

Elle prit avec elle son chien "start" (vous l'auriez devine ), car elle avait mauvaise memoire et ne pourrait pas retrouver le chemin de ma maison. Ainsi, elle sorti de chez elle, et alla chez sa voisine "data". Pour cela, elle traversa le quartier "next" (). Elle sonna alors chez Madame "data" et lui fit son commerce. Puis elle reprit le chemin "next", pour aller voir chez "data2".

Cependant, apres avoir epuise son stock, elle commenca a s'inquieter : elle ne savait plus ou elle etait !
Mais fort heuresement, son chien "start" savait ou ils se trouvaient et la ramena chez elle, ou elle put enfin se reposer de son dur labeur.

[/histoire]

Histoire emouvante, non ?

C'etait la schematisation en histoire des listes chainees . ("Lista, la petite liste chainee", de Sekoda, Edition Gallimard ).



Maintenant, je vous vous montrer en images ce qui se passe :

Voous pouvez voir ici que chaque "next" pointe sur le maillon suivant, jusqu'à ce que vous arriviez à 0, et dans ce cas là, grâce à "start", vous pouvez repartir au début. Car dites-vous bien qu'autant les listes chainées savent où se trouvent le prochain maillon, autant il ne savent pas où se trouvent le maillon précedent.

Voyons ce qui se passe au niveau de la mémoire :


C'est plus ou moins la même chose.

Je tiens à rappeler que ce ne sont que des schémas, et que ce n'est pas exactement comme ça. Mais pour la compréhension général, ça devrait suffire .

Les formes de listes chaînées

Les listes chaînées sont donc super utiles et leur utilisation est recommandé dans le cas où vous avez besoin de faire une liste, mais dont vous ne connaissez pas la longueur de cette liste.

Cependant, on remarque que la façon dont ils sont utilisés peut-être assez problématique. Il éxiste donc des formes de listes chaînées, pouvant simplifier la vie et éviter bien des problèmes, notamment si la liste arrive en fin de parcourt sans avoir au préalable, sauvegarder sa position de départ.

-Liste chaînée simple : c'est ce que je vous ai montré plus haut.

-Liste chaînée circulaire : c'est justement ce que je vous ai dit. En gros, au dernier maillon, au lieu que "next" point sur 0, il pointera sur le premier maillon. Ce qui permet de revenir à sa position de départ. Celà permet aussi d'éviter de taper dans la mémoire dans le cas où la liste ne s'arrête pas au maillon 0. Cependant, gare au boucle infinie, car la liste ne sait plus où s'arreter !

-Liste chaînée double : Au lieu de n'avoir que "next" pour se déplacer dans la liste chaînée, on a aussi :

Code:

t_list    *before

ce qui permet de revenir en arrière. Ainsi, selon les opérations voulue, on n'est plus obligé de repassé par le premier maillon pour faire les modifications que l'on veut.

-Liste chaînée double circulaire : c'est un mélange total. On se déplace en avant, en arrière, et en plus c'est circulaire. Mais même excuse : pas de boucle non contrôlée, autrement on ne s'arrête pas.


Cependant, il est plus difficile de mettre en place les 3 derniers cas, que le premier. Il y a deux conditions pour s'en servir :
-avoir bien compris le fonctionnement des pointeurs, structures et listes chaînées.
-avoir une bibliotèque de fonction solide.

Une fois que vous avez remplis ces deux conditions, ça devient un jeu d'enfants .

Conclusion


Et voilà, le cours sur les Listes Chaînées est terminée .

Comme les autres cours, la théorie ne suffit pas à comprendre le principe des listes chaînées et seules la pratique et l'expérience permettra de vous faire progresser.

Pour cela, je vous invite vivement à faire les exos.

Puis plus tard, quand vous developperez vos applications, ne pensez surtout pas qu'il faut utiliser à tout bout de champs les listes chaînées. C'est uniquement dans des cas précis, car mine de rien, bien qu'il gère mieux la mémoire car elle n'alloue que ce qui lui faut et non du surplus, elle prends pas mal de mémoire vue qu'on doit allouer de la mémoire pour une structure complète (donc de la place pour chaque élément qui la compose).

Sachant que la DS ne possède pas beaucoup de RAM, il faudra y aller doucement et surtout ne pas oublier de free-er. Par contre sur pc, il y a moins d'inquiétude à avoir

Mais ne prennons pas de mauvaise habitude et faisons bien les choses

Bon courage pour la suite .

Prochain cours : Fichier Header, Macro et Librairie.