1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
| #include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
typedef struct s_noeud {
int valeur;
struct s_noeud *suivant;
} t_noeud;
typedef struct {
t_noeud *premier;
size_t size;
} t_liste;
void liste_init(t_liste *liste)
{
printf("liste_init (%p)\n", liste);
liste->premier=NULL;
liste->size=0;
}
void liste_affiche(t_liste *liste)
{
t_noeud *courant;
printf("liste_affiche (%p)\n", liste);
if (liste->size == 0)
{
printf("liste vide\n");
return;
}
printf("taille liste: %zu, premier=%p\n", liste->size, liste->premier);
for (courant=liste->premier; courant != NULL; courant=courant->suivant)
printf("noeud %p, valeur=%d, suivant=%p\n", courant, courant->valeur, courant->suivant);
}
t_noeud *noeud_ajout(int valeur)
{
t_noeud *noeud;
// Allocation mémoire
if ((noeud=malloc(sizeof(t_noeud))) == NULL) return NULL;
// Remplissage
noeud->valeur=valeur;
noeud->suivant=NULL;
return noeud;
}
t_liste *liste_insere(t_liste *liste, t_noeud *noeud)
{
t_noeud *courant;
// Check paramètres entrés
if (noeud == NULL) return NULL;
// Un élément de plus
liste->size++;
// Liste vide
if (liste->premier == NULL)
{
liste->premier=noeud;
return liste;
}
// Premier élément
if (noeud->valeur < liste->premier->valeur)
{
// Le noeud mémorise le premier comme étant son successeur et prend sa place en tant que premier
noeud->suivant=liste->premier;
liste->premier=noeud;
return liste;
}
// Remontée de la liste en s'arrêtant sur le dernier noeud inférieur à la valeur à insérer
// Le cas "premier élément" étant déjà traité, on peut alors regarder un noeud "plus loin" que le noeud courant ce qui placera le noeud courant toujours un noeud "en arrière" de l'endroit où la valeur devient plus grande
for (courant=liste->premier; courant->suivant != NULL && courant->suivant->valeur < noeud->valeur; courant=courant->suivant);
// Le courant est maintenant juste avant le point où le noeud doit s'insérer
noeud->suivant=courant->suivant;
courant->suivant=noeud;
return liste;
}
void liste_free(t_liste *liste)
{
t_noeud *courant;
printf("liste_free (%p)\n", liste);
courant=liste->premier;
while (courant != NULL)
{
liste->premier=courant;
courant=courant->suivant;
printf("free(%p)\n", liste->premier);
free(liste->premier);
}
}
int main()
{
t_liste liste;
// Initialisation
liste_init(&liste);
// Petits tests de bon fonctionnement sur liste vide
liste_affiche(&liste);
liste_free(&liste);
// Insertion
liste_insere(&liste, noeud_ajout(5));
liste_insere(&liste, noeud_ajout(7));
liste_insere(&liste, noeud_ajout(8));
liste_insere(&liste, noeud_ajout(6));
liste_insere(&liste, noeud_ajout(2));
liste_insere(&liste, noeud_ajout(4));
liste_insere(&liste, noeud_ajout(1));
liste_insere(&liste, noeud_ajout(3));
// Affichage
liste_affiche(&liste);
// Libération
liste_free(&liste);
} |
Partager