Partie 4
Structures de données
LISTES CHAÎNÉES 19
19.1 QU’EST-CE QU’UNE LISTE CHAÎNÉE ?
Une liste chaînée (voir figure 19.1) est un ensemble de cellules liées entre elles par
des pointeurs. Chaque cellule est une structure contenant les champs suivants :
une ou plusieurs données comme dans n’importe quelle structure ;
un pointeur suivant sur la cellule suivante.
•
•
On accède à la liste par un pointeur L sur la première cellule, puis en parcourant
la liste d’une cellule à l’autre en suivant les pointeurs suivant. Le dernier pointeur
suivant vaut NULL, ce qui indique la fin de la liste.
cellules
L
donnée 1
donnée 2
donnée 3
donnée 4
pointeur sur
cellule de tˆete
pointeurs suivant
pointeur NULL
Figure 19.1– Exemple de liste chaînée avec 4 cellules
19.2 DÉCLARER UNE LISTE CHAÎNÉE
Pour créer une liste chaînée, il faut déclarer une nouvelle structure de données : la
structure qui représentera une cellule.
/ exemple : les données dans les cellules sont des float /
typedef float TypeDonnee;
/* définition du type cellule :
*/
typedef struct Cell
.
t
i
l
é
d
n
u
t
s
e
e
é
s
i
r
o
t
u
a
n
o
n
e
i
p
o
c
o
t
o
h
p
a
L
.
d
o
n
u
D
©
185
Chapitre 19 • Listes chaînées
{
TypeDonnee donnee;
/ on peut mettre ce qu’on veut comme donnée /
/ définition des données /
struct Cell suivant; / pointeur sur la structure suivante */
/ (de même type que celle qu’on est en train de définir) /
}TypeCellule;
La structure TypeCellule contient un pointeur sur TypeCellule. En fait, on ne peut
pas déclarer directement un pointeur sur le type TypeCellule qui est en cours de
définition. Par contre, le langage C permet de définir un pointeur sur une structure
non encore définie en employant le mot struct (voir Chapitre 7). De cette manière,
le compilateur accepte que le code “se morde la queue”.
On déclare ensuite le pointeur qui donne l’adresse de la première cellule (NULL si la
liste est vide) :
TypeCellule L; / déclaration d’une liste */
Ici, nous avons déclaré une liste chaînée de float. Nous aurions pu déclarer une
liste chaînée d’entiers, ou d’autres types de données, ou même contenant plusieurs
types de données. En fait, la cellule n’est rien d’autre qu’une structure C dans laquelle
on met des données dans des champs. Ici, nous avons défini un type TypeDonnee par
un typedef. Dans la suite, nous écrirons le code des fonctions en utilisant l’identi-
ficateur TypeDonnee. Cela permet d’adapter facilement le code pour d’autres types
de données (int, char, int, structure...) en changeant simplement la définition
de TypeDonnee au niveau du typedef et les fonctions d’entrée-sortie (saisie et af-
fichage). On parle d’un code générique pour parler d’un code qui peut fonctionner
pour différents types de données.
Voici les fonctions d’entrée-sortie de TypeDonnée (dont l’implémentation dépend du
type) :
void AfficheDonnee(TypeDonnee donnee)
{
printf("%f ", donnee); / ici donnée est de type float /
}
TypeDonnee SaisieDonnee(void)
{
TypeDonnee donnee;
scanf("%f", &donnee); / ici donnée est de type float /
return donnee;
}
186
19.3. Insertion en tête de liste
19.3 INSERTION EN TÊTE DE LISTE
La fonction suivante prend en paramètre une liste et une donnée, et ajoute la don-
née en tête de liste. La fonction renvoie la nouvelle adresse de la tête de liste (voir
figure 19.2).
TypeCellule InsereEnTete(TypeCellule ancienL,
TypeDonnee donnee)
{
}
TypeCellule nouveauL; / nouvelle tête de liste */
/ création d’une nouvelle cellule /
nouveauL = (TypeCellule*)malloc(sizeof(TypeCellule));
nouveauL->donnee=donnee;
/ on met la donnée à ajouter /
/ dans la cellule /
nouveauL->suivant=ancienL; / chaînage /
return nouveauL; / on retourne la nouvelle tête de liste /
ancienL
donnée 1
etc.
donnée n
nouveauL
nouv. donnée
Figure 19.2 – Insertion en tête de liste
Ne pas confondre l’utilisation du point . et l’utilisation de la flèche -> pour accéder
aux champs d’une structure. On utilise le point pour une variable de type structure,
et une flèche pour une variable de type pointeur sur structure.
19.4 CONSTRUCTION D’UNE LISTE CHAÎNÉE
Les listes chaînées se construisent par des insertions sucessives. La fonction suivante
réalise la saisie d’une liste chaînée au clavier.
TypeCellule* SaisieListeEnvers()
{
char choix;
TypeDonnee donnee;
/ déclaration d’une liste vide : /
TypeCellule L=NULL; / initialisation obligatoire ! */
puts("Voulez-vous entrer une liste non vide ?");
.
t
i
l
é
d
n
u
t
s
e
e
é
s
i
r
o
t
u
a
n
o
n
e
i
p
o
c
o
t
o
h
p
a
L
.
d
o
n
u
D
©
187
Chapitre 19 • Listes chaînées
choix = getchar();
getchar();
while (choix == ’o’)
{
}
puts("Entrez une donnée");
donnee = SaisieDonnee(); / saisie au clavier /
getchar();
L = InsereEnTete(L, donnee); / insertion en tête /
/ ne pas oublier de récupérer la nouvelle tête dans L /
puts("Voulez-vous continuer ?");
choix = getchar();
getchar();
return L;
}
Remarque
Avec des insertions en tête de liste, la liste obtenue est classée à l’ envers, le dernier
élément saisi étant le premier élément de la liste. Pour obtenir les éléments à l’ endroit,
il faurait faire les insertions en queue de liste (voir la section 19.6).
Remarque
Nous avons fait une fonction InsereEnTete qui retourne la nouvelle tête de liste (type
de retour TypeCellule*) pour éviter de faire un passage de pointeur par adresse. En
effet, nous voulons modifier l’ adresse de la tête de liste, donc modifier la valeur du
pointeur L. Nous aurions pu, en utilisant un double pointeur (TypeCellule**) modifier
cette valeur par un passage du pointeur par adresse (passage de &L). Nous avons jugé
plus simple de faire retourner la nouvelle valeur par la fonction. Pour un exemple de
passage de pointeur par adresse, voir la section 19.7.
19.5 PARCOURS DE LISTE
L’idée du parcours de liste chaînée est de prendre un pointeur auxiliaire p. On fait
pointer p sur la première cellule, puis le pointeur p passe à la cellule suivante (par une
affectation p=p->suivant), etc. (voir la figure 19.3). Le parcours s’arrête lorsque p
vaut le suivant de la dernière cellule, c’est-à-dire lorsque p vaut NULL.
(
donnée 1
donnée 2
donnée 3
donnée 4
Figure 19.3 – Parcours de liste chaînée
!"#$%&’
!"#$%&’
188
19.5. Parcours de liste
Exemple
La fonction suivante réalise l’affichage d’une liste chaînée.
void Affichage(TypeCellule* L)
{
TypeCellule *p;
p = L;
while (p != NULL)
/ on pointe sur la première cellule /
/ tant qu’il y a une cellule /
{
}
AfficheDonnee(p->donnee); / on affiche la donnée /
p = p->suivant; / on passe à la cellule suivante /
puts(""); / passage à la ligne /
}
Lors du parcours, on s’arrête lorsque p vaut NULL, et non pas lorsque p->suivant
vaut NULL. En effet, p->suivant vaut NULL lorsque p pointe sur la dernière cellule
(voir la figure 19.4). Il faut traiter cette dernière.
!
"#$%&’(
)*
!" # $%& ’%
donnée 1
donnée 2
donnée 3
donnée 4
Figure 19.4 – Le pointeur p pointe sur la dernière cellule
!
On pourra par exemple avoir le programme principal suivant :
int main(void)
{
/ déclaration du pointeur sur tête de liste : /
TypeCellule *L;
L = SaisieListeEnvers(); / on récupère l’adresse /
/ de la première cellule /
Affichage(L); / on affiche la liste saisie /
return 0;
}
.
t
i
l
é
d
n
u
t
s
e
e
é
s
i
r
o
t
u
a
n
o
n
e
i
p
o
c
o
t
o
h
p
a
L
.
d
o
n
u
D
©
189
Chapitre 19 • Listes chaînées
On peut aussi faire le parcours de liste chaînée avec une boucle for :
void AffichageBis(TypeCellule* L)
{
TypeCellule *p;
/ tant qu’il y a une cellule /
for (p=L ; p!=NULL ; p=p->suivant)
AfficheDonnee(p->donnee); / on affiche la donnée /
puts(""); / passage à la ligne /
}
19.6 INSERTION EN QUEUE DE LISTE
L’ajout d’une cellule en queue de liste est un peu plus compliquée que l’insertion
en tête de liste. Notamment, elle nécessite un parcours de la liste pour rechercher
l’adresse du dernier élément (voir la figure 19.5).
donnée
donnée 1
donnée 2
donnée 3
donnée 4
Figure 19.5 – Insertion en queue d’une liste chaînée
TypeCellule InsereEnQueue(TypeCellule L, TypeDonnee donnee)
{
TypeCellule p, nouveau;
/ allocation d’une nouvelle cellule : /
nouveau = (TypeCellule*)malloc(sizeof(TypeCellule));
nouveau->donnee = donnee; / donnée de la nouvelle cellule /
nouveau->suivant = NULL; / la nouvelle dernière cellule /
if (L == NULL) / cas particulier si la liste est vide /
L = nouveau;
else
{
/ recherche de la dernière cellule /
for (p = L ; p->suivant!=NULL ; p=p->suivant)
{}
190
19.7. Libération de mémoire
p->suivant = nouveau; / chaînage /
}
return L;
}
Ici, on a une condition d’arrêt p->suivant !=NULL parce que nous cherchons
l’adresse de la dernière cellule. C’est un cas différent du parcours de liste chaînée,
où il faut traîter la dernière cellule comme les autres (condition p !=NULL).
L’insertion en queue de liste permet de saisir une liste chaînée à l’endroit :
TypeCellule* SaisieListeEndroit()
{
char choix;
TypeDonnee donnee;
/ déclaration d’une liste vide : /
TypeCellule L=NULL; / initialisation obligatoire ! */
puts("Voulez-vous entrer une liste non vide ?");
choix = getchar();
getchar();
while (choix == ’o’)
{
}
puts("Entrez une donnée");
donnee = SaisieDonnee();
getchar();
L = InsereEnQueue(L, donnee); / insertion en queue /
puts("Voulez-vous continuer ?");
Publicité
choix = getchar();
getchar();
return L;
}
Compléments
√ La création d’une liste chaînée par insertions en queue de liste telle que décrite
ici prend un nombre d’opérations quadratique (O(n2)) par rapport au nombre
de cellules. On peut éviter cela et écrire un algorithme linéaire (O(n)) en main-
tenant tout au long de l’algorithme un pointeur sur la dernière cellule, sans le
rechercher à chaque fois par un parcours de liste.
19.7 LIBÉRATION DE MÉMOIRE
Pour libérer la mémoire d’une liste chaînée, il faut détruire chacune des cellules
avec la fonction free. Pour éviter les éventuels bugs, il vaut mieux que la fonction
.
t
i
l
é
d
n
u
t
s
e
e
é
s
i
r
o
t
u
a
n
o
n
e
i
p
o
c
o
t
o
h
p
a
L
.
d
o
n
u
D
©
191
Chapitre 19 • Listes chaînées
réinitialise la tête de liste à NULL (liste vide). Pour cela, la fonction doit modifier le
pointeur de tête de liste, et il faut donc passer ce pointeur par adresse.
void Liberation(TypeCellule **pL)
/ passage d’un pointeur par adresse : /
*/
/* pointeur sur pointeur
{
}
TypeCellule *p;
while (pL != NULL) / tant que la liste est non vide */
{
}
/ mémorisation de l’adresse de la cellule /
p = *pL;
pL = (pL)->suivant; / cellule suivante /
free(p); / destruction de la cellule mémorisée /
pL = NULL; / on réinitialise la liste à vide */
int main(void)
{
/ déclaration du pointeur sur tête de liste : /
TypeCellule *L;
L = SaisieListeEndroit(); / on récupère l’adresse /
/ de la première cellule /
Affichage(L); / on affiche la liste saisie /
Liberation(&L); / passage de l’adresse du pointeur /
return 0;
}
Après l’appel de la fonction Liberation, la liste est vide (pointeur NULL).
Exercices
19.1 (
) Écrire une fonction qui calcule la somme des éléments d’une liste chaînée
∗
d’entiers.
19.2 (
) (recherche d’un élément) Écrire une fonction qui prend en paramètre une
∗
liste chaînée d’entiers et un nombre entier n, et qui renvoie l’adresse de la première
cellule dont la donnée vaut n. La fonction renverra NULL si l’élément n n’est pas
présent dans la liste.
192
Exercices
19.3 (
)
∗
a) Écrire une fonction qui prend en paramètre un tableau et son nombre d’éléments,
et qui crée une liste chaînée dont les éléments sont les mêmes que les éléments du
tableau.
b) Écrire une fonction qui prend en paramètre une liste chaînée, et qui crée un tableau
dont les éléments sont les mêmes que les éléments du tableau.
19.4 (
) Écrire une fonction qui prend en paramètre une liste chaînée et renvoie une
∗
autre liste ayant les mêmes éléments, mais dans l’ordre inverse.
19.5 (
) Écrire une fonction de recopie d’une liste chaînée.
∗
19.6 (
) (suppression dans une liste chaînée)
∗
a) Écrire une fonction qui prend en paramètre une liste chaînée et une donnée, et qui
supprime la première occurrence de cette donnée dans la liste.
b) Écrire une fonction qui supprime toutes les occurrences d’une donnée (passée en
paramètre) dans une liste chaînée. Quelle est la complexité de l’algorithme ?
c) Même question qu’au b) mais pour un tableau au lieu d’une liste chaînée.
19.7 (
) Écrire une fonction de concaténation de deux listes chaînées. La fonction
∗
prend en entrée deux listes et ressort une seule liste réunion l’une à la suite de l’autre
des deux listes. On donnera deux versions de cette fonction, l’une destructrice (c’est-
à-dire qu’on ne conservera pas les listes chaînées d’entrée), l’autre non destructrice
(c’est-à-dire que l’on préservera les listes chaînées d’entrée).
19.8 (
) (tri d’une liste chaînée)
∗∗
a) Écrire une fonction qui prend en paramètre une liste chaînée d’entiers et vérifie
qu’elle est triée dans l’ordre croissant.
b) Écrire une fonction qui insère un élément dans une liste chaînée triée. La liste re-
tournée doit être triée. Pour cela, on recherchera l’adresse de la cellule (si elle existe)
juste avant l’emplacement de l’insertion.
c) Même question qu’au b) mais avec un tableau au lieu d’une liste chaînée.
d) Donner un algorithme quadratique de tri d’une liste chaînée (on calculera le
nombre d’opérations).
.
t
i
l
é
d
n
u
t
s
e
e
é
s
i
r
o
t
u
a
n
o
n
e
i
p
o
c
o
t
o
h
p
a
L
.
d
o
n
u
D
©
193
Chapitre 19 • Listes chaînées
19.9 (
) Écrire une fonction qui prend en entrée deux listes chaînées de même lon-
∗
gueur, et qui crée une liste chaînée fusion alternée des deux listes. La liste fusion doit
être la réunion des deux listes, mais les éléments de la liste fusion doivent être alter-
nativement de l’une et de l’autre des deux listes. Si les listes ne sont pas de même
longueur, la liste fusion se terminera comme la plus longue des deux listes en entrée.
On fera une version destructrice et une version non destructrice de la fonction.
19.10 (
) (interclassement et tri par interclassement)
∗∗
a) Écrire une fonction Interclassement qui prend en paramètre deux listes chaî-
nées supposées triées, et qui retourne une liste qui est la réunion des deux listes triées.
La liste retournée doit être triée. Quelle est la complexité de l’interclassement ?
b) Écrire une fonction de tri de liste chaînée TriInterclassement qui fonctionne
comme suit ;
•
•
Si la liste est vide ou n’a qu’un seul élément, la fonction renvoie la liste elle même.
Sinon, la fonction partage la liste en deux sous-listes L1 et L2 d’égales longueurs
(plus ou moins 1) et
1. trie
les
listes L1 et L2 par un appel
récursif
à
la
fonction
TriInterclassement ;
2. effectue l’interclassement de L1 et L2 et retourne le résultat.
Quelle est la complexité de ce tri ?
c) Même question qu’au a) mais avec des tableaux au lieu de listes chaînées. La
fonction retournera un tableau.
d) Même question qu’au b) mais avec des tableaux au lieu des listes chaînées.
19.11 (
) Écrire une fonction qui prend en entrée une liste chaînée d’entiers et qui
∗
ressort deux listes chaînées, l’une avec les nombres pairs, l’autre avec les nombres
impairs de la liste d’entrée. On détruira la liste d’entrée.
)
∗∗
19.12 (
(Listes doublement chaînées) On s’intéresse à des listes doublement
chaînées, pour lesquelles chaque cellule à un pointeur suiv vers la cellule suivante,
et un pointeur preced vers la cellule précédente. Voici une exemple ci-dessous :
L
D1
D2
D3
D4
Figure 19.6 – Une liste doublement chaînée
a) Déclarer le type de données correspondant à une liste doublement chaînée d’en-
tiers.
194
Corrigés
b) Écrire une fonction d’insertion en tête de liste dans une liste doublement chaînée.
c) Écrire une fonction d’insertion en queue de liste dans une liste doublement chaînée.
d) Écrire une fonction d’insertion dans une liste triée doublement chaînée. La liste
doit rester triée.
e) Écrire une fonction qui supprimme la première occurence (si elle existe) d’un en-
tier n dans une liste doublement chaînée.
f) Écrire une fonction qui supprimme la dernière occurence (si elle existe) d’un entier
n dans une liste doublement chaînée.
g) Écrire une fonction qui supprimme l’avant-dernière occurence (si elle existe) d’un
entier n dans une liste doublement chaînée.
h) Écrire une fonction qui supprime toutes les occurences d’un nombre n dans une
liste doublement chaînée.
i) Écrire une fonction non conservative qui réalise la concaténation de deux listes
doublement chaînées.
j) Écrire une fonction de recopie d’une liste doublement chaînée à l’identique.
Corrigés
19.1
int Somme(TypeCellule * L)
{
TypeCellule *p;
int somme = 0;
p = L;
while (p != NULL)
{
}
somme += p->donnee;
p = p->suivant;
return somme;
}
19.2
TypeCellule Recherche(TypeCellule L, TypeDonnee n)
{
TypeCellule *p;
195
.
t
i
l
é
d
n
u
t
s
e
e
é
s
i
r
o
t
u
a
n
o
n
e
i
p
o
c
o
t
o
h
p
a
L
.
d
o
n
u
D
©
Chapitre 19 • Listes chaînées
p = L;
while (p != NULL && p->donnee != n)
p = p->suivant;
if (p == NULL)
return NULL;
return p;
}
19.3
a)
TypeCellule CreerListeduTableau(TypeDonnee tab, int n)
{
int i;
TypeDonnee donnee;
TypeCellule *nouvelleListe = NULL;
for (i = 0; i < n; i++)
nouvelleListe = InsereEnQueue(nouvelleListe, tab[i]);
return nouvelleListe;
}
b)
TypeDonnee CreerTableaudelaListe(TypeCellule L, int *n)
{
int i = 0;
TypeDonnee *tab;
TypeCellule *p;
p = L;
*n = 0;
/ compter le nb d’éléments à partir de zéro /
/ compter le nombre d’éléments dans la liste /
while (p != NULL)
{
}
(*n)++;
p = p->suivant;
tab = (TypeDonnee ) malloc((n) * sizeof(TypeDonnee));
p = L;
while (p != NULL)
/ retourner au début de la liste /
/ remplir le tableau /
{
}
tab[i] = p->donnee;
p = p->suivant;
i = i + 1;
return tab;
}
196
Corrigés
19.4
TypeCellule CreerListeEnvers(TypeCellule L)
{
TypeCellule p, nouveauL = NULL;
p = L;
while (p != NULL)
{
}
nouveauL = InsereEnTete(nouveauL, p->donnee);
p = p->suivant;
return nouveauL;
}
19.5
TypeCellule RecopieListe(TypeCellule L)
{
TypeCellule p, nouveauL = NULL;
p = L;
Publicité
while (p != NULL)
{
}
nouveauL = InsereEnQueue(nouveauL, p->donnee);
p = p->suivant;
return nouveauL;
}
19.6
a)
TypeCellule Supprime1occur(TypeCellule L, TypeDonnee donnee)
{
TypeCellule p, suivant, *pL;
p = L;
if (p == NULL)
return L;
/Si la première occurrence est le premier élément de L/
if (p->donnee == donnee)
{
}
pL = p->suivant;
free(p);
return pL;
/*Pour les autres cas, on maintient 2 pointeurs: un vers
la cellule courante et un vers la cellule suivante*/
suivant = p->suivant;
.
t
i
l
é
d
n
u
t
s
e
e
é
s
i
r
o
t
u
a
n
o
n
e
i
p
o
c
o
t
o
h
p
a
L
.
d
o
n
u
D
©
197
Chapitre 19 • Listes chaînées
while (suivant->suivant != NULL && suivant->donnee != donnee)
{
}
p = p->suivant;
suivant = p->suivant;
if (suivant->donnee == donnee)
{
}
free(suivant);
p->suivant = suivant->suivant;
return L;
}
b)
TypeCellule Supprimetouteoccur(TypeCellule L, TypeDonnee donnee)
{
TypeCellule p, suivant, *pL;
p = L;
if (p == NULL)
return L;
while (p->suivant != NULL && p->donnee == donnee)
{
}
pL = p;
p = p->suivant;
free(pL);
if (p->donnee == donnee)
{
}
pL = p;
L = p->suivant;
free(pL);
/*Pour les autres cas, on maintient 2 pointeurs: un vers
la cellule courante et un vers la cellule suivante*/
suivant = p->suivant;
while (suivant->suivant != NULL)
{
if (suivant->donnee == donnee)
{
p->suivant = suivant->suivant;
free(suivant);
}
else
p = p->suivant;
198
Corrigés
suivant = p->suivant;
}
if (suivant->donnee == donnee)
{
}
p->suivant = NULL;
free(suivant);
return L;
}
La complexité est O(n)
c)
void Supprimetouteoccurtab(TypeDonnee tab, TypeDonnee donnee, int nb)
{
int i = 0, j = 0;
while (i < *nb)
{
}
if (tab[i] == donnee)
i++;
else
{
tab[j] = tab[i];
i++;
j++;
}
*nb = j;
}
La complexité est de O(n)
19.7
TypeCellule Concatenationdestructrice(TypeCellule L1,
TypeCellule * L2)
{
}
TypeCellule *p;
p = L1;
while (p->suivant != NULL)
{
}
p = p->suivant;
p->suivant = L2;
return L1;
.
t
i
l
é
d
n
u
t
s
e
e
é
s
i
r
o
t
u
a
n
o
n
e
i
p
o
c
o
t
o
h
p
a
L
.
d
o
n
u
D
©
199
Chapitre 19 • Listes chaînées
TypeCellule Concatenationnondestructrice(TypeCellule L1,
TypeCellule * L2)
{
TypeDonnee donnee;
TypeCellule p, L3 = NULL;
p = L1;
while (p != NULL)
{
}
L3 = InsereEnQueue(L3, p->donnee);
p = p->suivant;
p = L2;
while (p != NULL)
{
}
L3 = InsereEnQueue(L3, p->donnee);
p = p->suivant;
return L3;
}
19.8
a)
/*la fonction retourne 0 si la liste est triée,
-1 si elle est vide et 1 si elle n’est pas triée */
int Verifietrie(TypeCellule * L)
{
TypeCellule p, suivant;
if (L == NULL)
{
puts("La liste est vide");
return -1;
}
p = L;
suivant = p->suivant;
if (suivant == NULL) / la liste contient un seul élément /
return 0;
while (suivant->suivant != NULL && p->donnee < suivant->donnee)
{
}
p = p->suivant;
suivant = p->suivant;
if (suivant->suivant == NULL) / on arrive au dernier élément /
200
Corrigés
{
}
if (p->donnee < suivant->donnee)
return 0;
/la liste est triée /
else
return 1;
return 1;
}
b)
TypeCellule InsereElement(TypeCellule L, TypeDonnee donnee)
{
TypeCellule p, nouveau, *suivant;
nouveau = (TypeCellule *) malloc(sizeof(TypeCellule));
nouveau->donnee = donnee;
nouveau->suivant = NULL;
if (L == NULL)
return nouveau;
p = L;
suivant = p->suivant;
/Si la première donnée est < que la donnée à insérer /
if (p->donnee < donnee)
{
if (suivant == NULL)
{
}
}
else
{
p->suivant = nouveau;
return L;
/ Si la première donnée est > à la donnée à insérer /
nouveau->suivant = p;
return nouveau;
}
while (suivant->suivant != NULL && suivant->donnee < donnee)
{
}
p = p->suivant;
suivant = p->suivant;
if (suivant->donnee > donnee)
{
}
p->suivant = nouveau;
nouveau->suivant = suivant;
.
t
i
l
é
d
n
u
t
s
e
e
é
s
i
r
o
t
u
a
n
o
n
e
i
p
o
c
o
t
o
h
p
a
L
.
d
o
n
u
D
©
201
Chapitre 19 • Listes chaînées
else
suivant->suivant = nouveau;
return L;
}
c)
void InsereElementTabTriee(TypeDonnee tab, TypeDonnee donnee, int nb)
{
int i = 0, j = 0;
while (i < *nb && tab[i] < donnee)
i++;
/Augmenter de 1 la taille du tableau alloué /
tab = realloc(tab, (nb + 1) sizeof(int));
if (i == *nb)
tab[i] = donnee;
else
{
for (j = (*nb) + 1; j > i; j--)
tab[j] = tab[j - 1];
/insérer la donnée à son emplacement i /
tab[i] = donnee;
}
nb = nb + 1;
}
d)
TypeCellule TriListe(TypeCellule L)
{
TypeCellule p, Listetriee = NULL;
p = L;
while (p != NULL)
{
}
Listetriee = InsereElement(Listetriee, p->donnee);
p = p->suivant;
return Listetriee;
}
19.9
/Fusion destructrice/
TypeCellule FusionDestructrice(TypeCellule L1, TypeCellule * L2)
202
Corrigés
{
TypeCellule p1, p2, suivant_p1, suivant_p2;
p1 = L1;
p2 = L2;
while (p1->suivant != NULL && p2->suivant != NULL)
{
/mémoriser le suivant de p1 /
suivant_p1 = p1->suivant;
Publicité
/mémoriser le suivant de p2 /
suivant_p2 = p2->suivant;
p1->suivant = p2;
p2->suivant = suivant_p1;
p1 = suivant_p1;
p2 = suivant_p2;
}
/ L1 est plus longue que L2 /
if (p1->suivant != NULL && p2->suivant == NULL)
{
}
suivant_p1 = p1->suivant;
p1->suivant = p2;
p2->suivant = suivant_p1;
/ L1 et L2 ont la même longueur ou L2 est plus longue que L1 /
else
p1->suivant = p2;
return L1;
}
/Fusion non destructrice /
TypeCellule FusionNonDestructrice(TypeCellule L1, TypeCellule * L2)
{
TypeCellule p1, p2, *L3 = NULL;
p1 = L1;
p2 = L2;
/si la fin d’aucune des listes n’est atteinte /
while (p1 != NULL && p2 != NULL)
{
}
L3 = InsereEnQueue(L3, p1->donnee);
L3 = InsereEnQueue(L3, p2->donnee);
p1 = p1->suivant;
p2 = p2->suivant;
/si L1 est plus longue que L2 et fin de L2 atteinte /
while (p1 != NULL)
{
L3 = InsereEnQueue(L3, p1->donnee);
.
t
i
l
é
d
n
u
t
s
e
e
é
s
i
r
o
t
u
a
n
o
n
e
i
p
o
c
o
t
o
h
p
a
L
.
d
o
n
u
D
©
203
Chapitre 19 • Listes chaînées
p1 = p1->suivant;
}
/L2 est plus longue que L1 et la fin de L1 est atteinte /
while (p2 != NULL)
{
}
L3 = InsereEnQueue(L3, p2->donnee);
p2 = p2->suivant;
return L3;
/retourner la nouvelle liste /
}
19.10
a)
TypeCellule Interclassement(TypeCellule Liste1, TypeCellule * Liste2)
{
TypeCellule tmp, debut;
if (Liste1->donnee <= Liste2->donnee)
{
tmp = Liste1;
debut = Liste1;
Liste1 = Liste1->suivant;
}
else
{
tmp = Liste2;
debut = Liste2;
Liste2 = Liste2->suivant;
}
while (tmp->suivant != NULL)
{
if (Liste1->donnee <= Liste2->donnee)
{
tmp->suivant = Liste1;
tmp = Liste1;
Liste1 = Liste1->suivant;
}
else
{
tmp->suivant = Liste2;
tmp = Liste2;
Liste2 = Liste2->suivant;
}
}
204
Corrigés
if (Liste1 != NULL)
tmp->suivant = Liste1;
if (Liste2 != NULL)
tmp->suivant = Liste2;
return debut;
}
b)
TypeCellule TriInterclassement(TypeCellule Liste)
{
TypeCellule debutliste, tmp, res1, res2;
if (Liste == NULL || Liste->suivant == NULL)
return Liste;
debutliste = Liste;
tmp = Liste->suivant->suivant;
while (tmp != NULL && tmp->suivant != NULL)
{
}
tmp = tmp->suivant->suivant;
Liste = Liste->suivant;
tmp = Liste->suivant;
Liste->suivant = NULL;
res1 = TriInterclassement(debutliste);
res2 = TriInterclassement(tmp);
return Interclassement(res1, res2);
}
c)
void Interclassement(TypeDonnee tab, TypeDonnee tmptab,
int debut, int m, int fin)
int i, j, k;
for (i = m + 1; i > debut; i--)
tmptab[i - 1] = tab[i - 1];
for (j = m; j < fin; j++)
tmptab[fin + m - j] = tab[j + 1];
for (k = debut, i = debut, j = fin; k <= fin; k++)
tab[k] = (tmptab[i] < tmptab[j]) ? tmptab[i++] : tmptab[j--];
{
}
d)
void TriInterclassement(TypeDonnee tab, TypeDonnee tmptab,
int debut, int fin)
{
int m;
205
.
t
i
l
é
d
n
u
t
s
e
e
é
s
i
r
o
t
u
a
n
o
n
e
i
p
o
c
o
t
o
h
p
a
L
.
d
o
n
u
D
©
Chapitre 19 • Listes chaînées
int i, j, k;
if (fin > debut)
m = (debut + fin) / 2;
TriInterclassement(tab, tmptab, debut, m);
TriInterclassement(tab, tmptab, m + 1, fin);
Interclassement(tab, tmptab, debut, m, fin);
{
}
}
La complexité est O(nlog2n)
19.11
void Pairimpair(TypeCellule * L, TypeCellule L1, TypeCellule L2)
{
TypeCellule p, p1, *p2;
*L1 = NULL;
*L2 = NULL;
p = L;
while (p->suivant != NULL)
{
if ((p->donnee) % 2 == 0)
{
if (*L1 == NULL)
{
*L1 = p;
p1 = *L1;
}
else
{
p1->suivant = p;
p1 = p1->suivant;
}
}
else
{
if (*L2 == NULL)
{
*L2 = p;
p2 = *L2;
}
else
{
p2->suivant = p;
206
Corrigés
p2 = p2->suivant;
}
}
p = p->suivant;
}
}
19.12
a)
typedef struct Cell
{
TypeDonnee donnee;
struct Cell * precedent;
struct Cell * suivant;
} TypeCellule;
b)
TypeCellule InsereEnTete(TypeCellule ancienL, TypeDonnee donnee)
{
TypeCellule *nouveauL;
nouveauL=(TypeCellule*)malloc(sizeof(TypeCellule));
nouveauL->donnee=donnee;
nouveauL->suivant=ancienL;
nouveauL->precedent=NULL;
if (ancienL!=NULL)
ancienL->precedent=nouveauL;
return nouveauL;
}
c)
TypeCellule InsereEnQueue(TypeCellule L,TypeDonnee donnee)
{
TypeCellule p,nouveau;
nouveau=(TypeCellule*)malloc(sizeof(TypeCellule));
nouveau->donnee=donnee;
nouveau->suivant=NULL;
if (L==NULL)
{
nouveau->precedent=NULL;
return nouveau;
}
else
{
for(p=L; p->suivant!=NULL; p=p->suivant)
.
t
i
l
é
d
n
u
t
s
e
e
é
s
i
r
o
t
u
a
n
o
n
e
i
p
o
c
o
t
o
h
p
a
L
.
d
o
n
u
D
©
207
Chapitre 19 • Listes chaînées
{}
p->suivant=nouveau;
nouveau->precedent=p;
}
return L;
}
d)
TypeCellule InsereDonnee(TypeCellule L,TypeDonnee donnee)
{
TypeCellule precedent,nouveau,*suivant;
nouveau=(TypeCellule*)malloc(sizeof(TypeCellule));
nouveau->donnee=donnee;
if (L==NULL) / si la liste est vide /
{
}
nouveau->suivant=NULL;
nouveau->precedent=NULL;
return L;
else if (L->donnee>donnee) / si l’élément à insérer est /
/le plus petit élément de la liste /
/ et doit donc être insérer en tête /
{
}
nouveau->precedent=NULL;
nouveau->suivant=L;
L->precedent=nouveau;
return nouveau;
else / dans tous les autres cas /
{
precedent=L; / precedent est celui qui precède le suivant /
suivant=precedent->suivant;
while(suivant!=NULL && suivant->donnee<donnee)
/ tant que le suivant est plus petit que l’élément à /
/ insérer et tant qu’on n’est pas à la fin de la liste /
{
precedent=suivant;
suivant=suivant->suivant;
}...