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);
}
} |
