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 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
| #include <stdio.h>
#include <stdlib.h>
struct maillon
{
int donnee;
struct maillon * suivant;
};
typedef struct maillon Maillon;
/* Les prototypes des fonctions */
Maillon * nouveau_maillon(int, struct maillon *);
Maillon * inserer(Maillon * , int);
Maillon * saisir(void);
void ecrire_liste(Maillon *);
Maillon * inverser(Maillon *);
void liberer(Maillon *);
int main(int argc, char ** argv)
{
Maillon * debut;
debut = saisir();
printf("liste croissante \n");
ecrire_liste(debut);
debut = inverser(debut);
printf("liste decroissante \n");
ecrire_liste(debut);
liberer(debut);
return 0;
}
/*
Crée un nouveau maillon en mettant la valeur cle dans le champ donnee et
la valeur deb dans le second champ.
.*/
Maillon * nouveau_maillon(int cle, struct maillon * deb)
{
Maillon * nouveau = (Maillon *) malloc(sizeof(Maillon));
nouveau -> donnee = cle;
nouveau -> suivant = deb;
return nouveau;
}
/*
Insère la valeur cle dans la liste triée par valeurs croissantes
de début "debut" en respectant l'ordre.
On insère la nouvelle valeur même si elle figurait déjà.
Renvoie le début de la liste après insertion.
On distingue d'abord le cas où la liste serait vide et le cas où cle serait
inférieure à la première donnée de la liste.
On cherche ensuite la place de cle en utilisant deux pointeurs p et q et en
faisant en sorte que, au moment de l'insertion, p et q pointent sur deux maillons
consécutifs, le premier maillon contenant une donnée < cle et le suivant une donnée > cle.
*/
Maillon * inserer(Maillon * debut, int cle)
{
Maillon * p, * q;
if ((debut == NULL) || (cle < debut -> donnee))
debut = nouveau_maillon(cle, debut);
else
{
p = debut;
q = p -> suivant;
while ((q != NULL) && (cle > q -> donnee))
{
p = q;
q = q -> suivant;
}
p -> suivant = nouveau_maillon(cle, q);
}
return debut;
}
/*
Demande à l'utilisateur les données et les insère au fur et à mesure
dans la liste chaînée, de telle sorte que la liste soit triée.
Utilise la fonction inserer.
L'utilisateur indique la valeur -1 pour indiquer qu'il n'y a plus de données
*/
Maillon * saisir()
{
Maillon * debut = NULL;
int cle;
printf("vos données, indiquez la fin avec la valeur -1 ? \n");
scanf("%d", &cle);
while (cle != -1)
{
debut = inserer(debut, cle);
scanf("%d", &cle);
}
return debut;
}
/*
Ecrit sur la sortie standard les données de la liste chainée
de début "debut" .
*/
void ecrire_liste(Maillon * debut)
{
Maillon * p = debut;
while (p != NULL)
{
printf("%d ", p -> donnee);
p = p-> suivant;
}
printf("\n");
}
/*
Prend un à un les maillons de la liste chainée de début "debut" pour
construire une nouvelle liste chaînée qui est dans l'ordre inverse.
Renvoie le début de la liste après inversion.
La liste doit être inversée sans faire d'allocation dynamique (aucun malloc).
*/
Maillon * inverser(Maillon * debut)
{
Maillon * debut_inverse = NULL, * p;
while (debut != NULL)
{
p = debut;
debut = debut -> suivant;
p -> suivant = debut_inverse;
debut_inverse = p;
}
return debut_inverse;
}
/*
Libère la liste chaînée.
*/
void liberer(Maillon * debut)
{
Maillon * p = debut;
while (debut != NULL)
{
debut = debut -> suivant;
free(p);
}
} |
Partager