![[Home]](http://fridim.org/oddmuse/logo.png){kind=logo}
Après avoir vu les pointeurs ainsi que les fonctions permettant l'allocation dynamique de mémoire, on s'interesse naturelement aux strucures complexes pouvant accueillir des données. Le but est d'allouer de manière dynamique des données à l'aide de la fonction malloc. Cette fonction se trouve dans la librairie standard stdlib qu'on inclura.
Nous allons essayer de faire une liste chainée simple, ou plutôt une pile de donnée du type "last in, first out". La structure
struct noeud {
int data;
struct noeud *prec;
}
La structure est en somme assez simple. Elle est composée d'une donnée quelconque, ici un entier qu'on appelle data, et d'un pointeur vers la structure précédente (N'oublions pas qu'on est dans une pile). Nous devons donc créer une fonction push qui s'occupera d'ajouter en haut de la pile la nouvelle donnée. Mais avant ça, créons plutot un type, Noeud, à l'aide de typedef pour la structure précédente.
typedef struct noeud {
int data;
struct noeud *prec;
} Noeud;
Note : l'operateur -> est un raccourci : foo->bar est strictement équivalent à (*foo).bar.
void push (Noeud **dernier, int data) {
Noeud *nouveau;
nouveau = malloc(sizeof(Noeud));
if (!nouveau) return; // En cas d'echec d'allocation
nouveau->data = data;
nouveau->prec = *dernier;
*dernier = nouveau; // C'est une pile, donc on s'interesse uniquement au dernier entré.
}
Tant qu'à faire, et surtout histoire de voir ce qu'il y a dans notre pile, on va faire une fonction qui va afficher les éléments qui sont dans la pile.
void view (Noeud *dernier) {
while (dernier) {
printf("La donnée : %d\n", dernier->data);
dernier = dernier->prec;
}
}
Ici on n'a pas besoin d'une variable temporaire de type pointeur sur type Noeud à cause de l'appel par valeur. En effet le pointeur dernier est copié et view n'y touche pas. C'est pour cette raison que dans la fonction push on a un double pointeur sur dernier, car on veut le modifier.
void clear (Noeud *dernier) {
Noeud *tmp;
while (dernier) {
tmp = dernier->prec;
free(dernier);
dernier = tmp;
}
}
Voici le programme en entier :
#include <stdio.h>
#include <stdlib.h>
typedef struct noeud {
int data;
struct noeud *prec;
} Noeud;
void push (Noeud **dernier, int data) {
Noeud *nouveau;
nouveau = malloc(sizeof(Noeud));
if (!nouveau) return;
nouveau->data = data;
nouveau->prec = *dernier;
*dernier = nouveau;
}
void view (Noeud *dernier) {
while (dernier) {
printf("La donnée : %d\n", dernier->data);
dernier = dernier->prec;
}
}
void clear (Noeud *dernier) {
Noeud *tmp;
while (dernier) {
tmp = dernier->prec;
free(dernier);
dernier = tmp;
}
}
int main(void) {
Noeud *pile = NULL;
push(&pile, 8);
push(&pile, 7);
push(&pile, 55);
view(pile);
clear(pile);
view(pile);
return 0;
}
[:ListeChaineeDouble?]
C'est quasiment la même chose que les listes chainées simples à part que chaque structure pointe vers la structure précedente ET la structure suivante, si cette dernière existe. Si elle n'existe pas, vous avez plusieurs choix possibles :
Etant donné que l'on travaille sur des choses très basiques, largement définies dans la glib, on peut faire à peu près n'importe quoi. A vous de voir.
############# -->############# # donnees # / # donnees # #-----------# / #-----------# # suivant #------/ # suivant #--------> etc #-----------# #-----------# # precedent # ------# precedent # #############<----/ #############
Pour changer un peu, nous allons prendre un type de données plus complexe que le simple entier data vu précédement. Je définis donc une structure data qui contient les données. Elle est suivie de la structure Noeud qui représente les briques de la future liste chainée.
Vu qu'on va travailler avec des pointeurs sur des tableaux de caractères (char *nom et char *prenom), il vaut mieux créer tout de suite une fonction qui va s'occuper de dupliquer les chaines, histoire qu'on puisse attribuer facilement des chaines aux pointeurs nom et prenom de la structures data.
Toujours dans le même soucis des données, viens la fonction qui va copier une structure data dans une autre.
On peut maintenant attaquer sans trop de mal la fonction push de tout à l'heure. J'ai décidé de ne pas déplacer le pointeur racine. Il pointera toujours sur la première brique. On aurait très bien pu, et ça aurait rejoint l'exemple de la liste chainée simple, copier l'adresse de la dernière brique ajoutée dans racine. Cependant, les fonctions clear et view auraient été différentes. Peu importe.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define taille sizeof(char)*256
typedef struct data {
char *nom;
char *prenom;
unsigned int age;
} Data;
typedef struct noeud {
Data fiche;
struct noeud *prev;
struct noeud *next;
} Noeud;
void push (Noeud **racine, Data fiche) {
Noeud *cursor = *racine;
Noeud *nouveau;
nouveau = malloc(sizeof(Noeud));
if (!nouveau) return;
// On met les données dans nouveau
nouveau->fiche = fiche;
// Si nouveau est le premier véritable élément de la liste
if (!*racine)
*racine = nouveau;
// sinon on link
else {
while (cursor->next)
cursor = cursor->next;
nouveau->prev = cursor;
cursor->next = nouveau;
}
}
void view (Noeud *racine) {
Data fiche;
while (racine) {
fiche = racine->fiche;
printf("Le nom: %s\tPrenom: %s\tAge: %d\n", fiche.nom, fiche.prenom, fiche.age);
printf("-----------\n");
racine = racine->next;
}
}
void clear (Noeud **racine) {
Noeud *tmp;
while (*racine) {
tmp = (*racine)->next;
free(((*racine)->fiche).nom);
((*racine)->fiche).nom = NULL;
free(((*racine)->fiche).prenom);
((*racine)->fiche).prenom = NULL;
free(*racine);
*racine = tmp;
}
}
char *lire_ligne(FILE *flux) {
char *p = malloc(taille);
char *final = NULL;
char *ret = NULL;
if (p != NULL) {
fgets(p, taille - 1, flux);
ret = strchr(p, '\n');
if (ret != NULL)
*ret = '\0';
final = malloc(sizeof(char)*(strlen(p)+1));
strcpy(final, p);
free(p);
p = NULL;
}
return final;
}
int main(void) {
Noeud *racine = NULL;
Data fiche;
// pour la saisie
char *c;
do {
free(c);
c = NULL;
printf("Entrez l'age :\n");
scanf("%d", &(fiche.age));
getchar(); // à cause du \n de scanf...
printf("Entrez un nom :\n");
fiche.nom = lire_ligne(stdin);
printf("Entrez un prenom :\n");
fiche.prenom = lire_ligne(stdin);
push(&racine, fiche);
printf("Voulez vous entrer une nouvelle entrée ? [o/n]\n");
c = lire_ligne(stdin);
} while (*c == 'o');
view(racine);
clear(&racine);
view(racine);
return 0;
}
