Algorithmique 3
L1 informatique-mathématiques
V.Marion
1
Organisation du module
Volume horaire
6h CM : pile/file/liste, listes chaînées, récursivité, tris
6h TD + 15h TP : application des notions en C.
Evaluation
C.C. : TPs notés + évaluations sur les TPs + DS
Note finale = 2/3 Exam + 1/3 CC
Organisation du module
Bibliographie
Concepts fondamentaux de l’informatique, A.Aho - J.Ullman,
DUNOD
Conception d’algorithmes, P.Bosc - M.Guyomard - L.Miclet,
EYROLLES
Algorithmes et structures de données génériques, M.Divay,
DUNOD
Programmation. Principes et pratique en C++, B.Stroustrup,
PEARSON Education
Les listes - Définitions
Liste
Liste : séquence finie de 0 ou plusieurs éléments d’un type donné.
Exemples :
I liste des nombres premiers inférieurs à 20 : (2, 3, 5, 7, 11, 13, 17, 19)
I liste de caractères : baba
I liste des sommets du cube unité : ((0,0,0), (1,0,0), (1,1,0), (0,1,0),
(0,1,1), (0,0,1), (1,0,1), (1,1,1))
Longueur d’une liste
Longueur d’une liste : nombre d’occurrences des éléments de la liste.
Liste vide : liste de longueur nulle. Notations : (),
Longueur des listes vues précédemment :
I liste des nombres premiers inférieurs à 20 : 8
I liste de caractères : 4
I liste des sommets du cube unité : 8
4
Parties d’une liste - Exemple : L = abc
Composition d’une liste
Tête : premier élément d’une liste non vide
5
Parties d’une liste - Exemple : L = abc
Composition d’une liste
Tête : premier élément d’une liste non vide => a
6
Parties d’une liste - Exemple : L = abc
Composition d’une liste
Tête : premier élément d’une liste non vide => a
Queue : le reste de la liste (liste privée de son premier élément)
7
Parties d’une liste - Exemple : L = abc
Composition d’une liste
Tête : premier élément d’une liste non vide => a
Queue : le reste de la liste (liste privée de son premier élément) =>
bc
8
Parties d’une liste - Exemple : L = abc
Composition d’une liste
Tête : premier élément d’une liste non vide => a
Queue : le reste de la liste (liste privée de son premier élément) =>
bc
Sous-liste et sous-séquence d’une liste
Sous-liste de L : liste formée d’éléments de L consécutifs entre 2
positions.
9
Parties d’une liste - Exemple : L = abc
Composition d’une liste
Tête : premier élément d’une liste non vide => a
Queue : le reste de la liste (liste privée de son premier élément) =>
bc
Sous-liste et sous-séquence d’une liste
Sous-liste de L : liste formée d’éléments de L consécutifs entre 2
positions. => vide, a, b, c, ab, bc, abc
10
Parties d’une liste - Exemple : L = abc
Composition d’une liste
Tête : premier élément d’une liste non vide => a
Queue : le reste de la liste (liste privée de son premier élément) =>
bc
Sous-liste et sous-séquence d’une liste
Sous-liste de L : liste formée d’éléments de L consécutifs entre 2
positions. => vide, a, b, c, ab, bc, abc
Sous-séquence de L : liste formée en éliminant 0 ou plusieurs
éléments à L. Les éléments constituant la sous-séquence apparaissent
dans le même ordre que dans L.
11
Parties d’une liste - Exemple : L = abc
Composition d’une liste
Tête : premier élément d’une liste non vide => a
Queue : le reste de la liste (liste privée de son premier élément) =>
bc
Sous-liste et sous-séquence d’une liste
Sous-liste de L : liste formée d’éléments de L consécutifs entre 2
positions. => vide, a, b, c, ab, bc, abc
Sous-séquence de L : liste formée en éliminant 0 ou plusieurs
éléments à L. Les éléments constituant la sous-séquence apparaissent
dans le même ordre que dans L. => sous-listes + ac
12
Parties d’une liste - Exemple : L = abc
Composition d’une liste
Tête : premier élément d’une liste non vide => a
Queue : le reste de la liste (liste privée de son premier élément) =>
bc
Sous-liste et sous-séquence d’une liste
Sous-liste de L : liste formée d’éléments de L consécutifs entre 2
positions. => vide, a, b, c, ab, bc, abc
Sous-séquence de L : liste formée en éliminant 0 ou plusieurs
éléments à L. Les éléments constituant la sous-séquence apparaissent
dans le même ordre que dans L. => sous-listes + ac
Remarque : la liste vide et la liste L elle-même sont des sous-listes et
des sous-séquences de L.
Parties d’une liste (suite) - Exemple : L = abc
Préfixe et suffixe d’une liste
Préfixe de L : n’importe quelle sous-liste qui commence au début de
la liste.
Parties d’une liste (suite) - Exemple : L = abc
Préfixe et suffixe d’une liste
Préfixe de L : n’importe quelle sous-liste qui commence au début de
la liste. => vide, a, ab, abc
Parties d’une liste (suite) - Exemple : L = abc
Préfixe et suffixe d’une liste
Préfixe de L : n’importe quelle sous-liste qui commence au début de
la liste. => vide, a, ab, abc
Suffixe de L : n’importe quelle sous-liste qui se termine à la fin de la
liste.
Parties d’une liste (suite) - Exemple : L = abc
Préfixe et suffixe d’une liste
Préfixe de L : n’importe quelle sous-liste qui commence au début de
la liste. => vide, a, ab, abc
Suffixe de L : n’importe quelle sous-liste qui se termine à la fin de la
liste. => c, bc, abc, vide
Parties d’une liste (suite) - Exemple : L = abc
Préfixe et suffixe d’une liste
Préfixe de L : n’importe quelle sous-liste qui commence au début de
la liste. => vide, a, ab, abc
Suffixe de L : n’importe quelle sous-liste qui se termine à la fin de la
liste. => c, bc, abc, vide
Remarque : la liste vide et la liste elle-même sont à la fois préfixe et
suffixe de n’importe quelle liste.
Représentations des listes - statique
Utilisation d’un tableau statique - Caractéristiques
taille max : fixe pour toutes les listes,
taille réelle : de la liste sauvegardée
Tête Fin Max
Structure
struct Liste {
type_elt Tab[Max] ;
int taille ; // taille <= Max
};
Opérations sur les listes
Opérations possibles
rechercher : un élément dans la liste
modifier : un élément de la liste
insérer : un élément à n’importe quel endroit de la liste
supprimer : n’importe quel objet de la liste en la mettant à jour
ensuite (en fonction de sa valeur ou de sa position)
afficher : la liste
concaténer : 2 listes (exemple : concaténer L1 = abc et L2 = ca
donnera une liste L = abcca)
est_vide : indique si la liste est vide
est_pleine : indique si la liste est pleine
Opérations sur les listes
Opérations possibles
rechercher : un élément dans la liste
modifier : un élément de la liste
insérer : un élément à n’importe quel endroit de la liste
supprimer : n’importe quel objet de la liste en la mettant à jour
ensuite (en fonction de sa valeur ou de sa position)
afficher : la liste
concaténer : 2 listes (exemple : concaténer L1 = abc et L2 = ca
donnera une liste L = abcca)
est_vide : indique si la liste est vide
est_pleine : indique si la liste est pleine
Attention toutes les opérations doivent mettre à jour la liste
Liste statique - est_vide
fonction est_vide - renvoie vrai si la liste est vide et faux sinon
bool est_vide(Liste L1)
{
if (L1.taille == 0)
return true ;
return false ;
}
Liste statique - est_vide
fonction est_vide - renvoie vrai si la liste est vide et faux sinon
bool est_vide(Liste L1)
{
if (L1.taille == 0)
return true ;
return false ;
}
fonction est_vide - simplifiée
bool est_vide(Liste L1)
{
return (L1.taille == 0) ;
}
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
24
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
if (est_vide(L1)) //la liste est vide, pas de valeur possible
return false ;
25
Liste statique - modifier
26
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
if (est_vide(L1)) //la liste est vide, pas de valeur possible
return false ;
27
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
if (est_vide(L1)) //la liste est vide, pas de valeur possible
return false ;
while ( )
}
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
if (est_vide(L1)) //la liste est vide, pas de valeur possible
return false ;
while ( (L1.Tab[i] != valeur))
}
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
if (est_vide(L1)) //la liste est vide, pas de valeur possible
return false ;
while ( (i < L1.taille) (L1.Tab[i] != valeur))
}
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
if (est_vide(L1)) //la liste est vide, pas de valeur possible
return false ;
while ( (i < L1.taille) and (L1.Tab[i] != valeur))
}
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
if (est_vide(L1)) //la liste est vide, pas de valeur possible
return false ;
while ( (i < L1.taille) and (L1.Tab[i] != valeur))
i = i+1 ;
}
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
int i = 0 ;
if (est_vide(L1)) //la liste est vide, pas de valeur possible
return false ;
while ( (i < L1.taille) and (L1.Tab[i] != valeur))
i = i+1 ;
}
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
int i = 0 ;
if (est_vide(L1)) //la liste est vide, pas de valeur possible
return false ;
while ( (i < L1.taille) and (L1.Tab[i] != valeur))
i = i+1 ;
*pos = i ; //on est sorti car L1.Tab[i] == valeur
}
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
int i = 0 ;
if (est_vide(L1)) //la liste est vide, pas de valeur possible
return false ;
while ( (i < L1.taille) and (L1.Tab[i] != valeur))
i = i+1 ;
*pos = i ; //on est sorti car L1.Tab[i] == valeur
return true ;
}
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
int i = 0 ;
if (est_vide(L1)) //la liste est vide, pas de valeur possible
return false ;
while ( (i < L1.taille) and (L1.Tab[i] != valeur))
i = i+1 ;
if (i == L1.taille) //on n’a pas trouvé l’élément "valeur"
*pos = i ; //on est sorti car L1.Tab[i] == valeur
return true ;
}
Liste statique - rechercher
fonction rechercher - renvoie la position "pos" de l’élément si trouvé
bool rechercher(Liste L1, type_element valeur, int * pos)
{
int i = 0 ;
if (est_vide(L1)) //la liste est vide, pas de valeur possible
return false ;
while ( (i < L1.taille) and (L1.Tab[i] != valeur))
i = i+1 ;
if (i == L1.taille) //on n’a pas trouvé l’élément "valeur"
return false ;
*pos = i ; //on est sorti car L1.Tab[i] == valeur
return true ;
}
Représentations des listes - dynamique
Utilisation d’un tableau dynamique - Caractéristiques
pointeur : début de la liste,
taille réelle : de la liste sauvegardée
Structure
struct Liste {
type_elt *Tab ; // adresse du 1er élément
int taille ;
};
Avantage/Inconvénient de cette solution
avantage : pas de perte mémoire.
inconvénient : opérations de MAJ plus longues (réallocation de la
mémoire)
38
Types de données basées sur les listes - LA PILE
Caractéristiques
Tableau : même représentation que la liste.
Opérations : toutes effectuées à une extrémité de la liste = sommet.
Structure
struct Pile {
type_elt Tab[Max] ;
int sommet ; // sommet (< Max), indice de l’élément à empiler
};
Opérations sur les piles
Opérations possibles
empiler (ou push) : déposer un élément au sommet de la pile
dépiler (ou pop) : supprimer un élément du sommet de la pile
afficher : la pile
est_vide : indique si la pile est vide
est_pleine : indique si la pile est pleine
vider : initialise la pile à vide
PILE = liste LIFO
La pile est une liste Last In First Out
40
Opérations sur les piles
Opérations possibles
empiler (ou push) : déposer un élément au sommet de la pile
dépiler (ou pop) : supprimer un élément du sommet de la pile
afficher : la pile
est_vide : indique si la pile est vide
est_pleine : indique si la pile est pleine
vider : initialise la pile à vide
PILE = liste LIFO
La pile est une liste Last In First Out
Attention toutes les opérations doivent mettre à jour la pile
41
Pile - est_vide
fonction est_vide - renvoie vrai si la pile est vide et faux sinon
bool est_vide(Pile L1)
{
if (L1.sommet == 0)
return true ;
return false ;
}
Pile - est_vide
fonction est_vide - renvoie vrai si la pile est vide et faux sinon
bool est_vide(Pile L1)
{
if (L1.sommet == 0)
return true ;
return false ;
}
fonction est_vide - simplifiée
bool est_vide(Pile L1)
{
return (L1.sommet == 0) ;
}
Types de données basées sur les listes - LA FILE
Caractéristiques
Tableau et taille : même représentation que la liste.
Opérations : différentes.
Structure
struct File {
type_elt Tab[Max] ;
int taille ; // taille <= Max)
};
44
Opérations sur les files
Opérations possibles
enqueue : ajoute un élément en queue de liste
dequeue : supprime l’élément de tête de la liste
afficher : la file
est_vide : indique si la file est vide
est_pleine : indique si la file est pleine
vider : initialise la file à vide
FILE = liste FIFO
La file est une liste First In First Out
45
Opérations sur les files
Opérations possibles
enqueue : ajoute un élément en queue de liste
dequeue : supprime l’élément de tête de la liste
afficher : la file
est_vide : indique si la file est vide
est_pleine : indique si la file est pleine
vider : initialise la file à vide
FILE = liste FIFO
La file est une liste First In First Out
Attention toutes les opérations doivent mettre à jour la file
46
Opérations sur les files - enqueue
Fonction enqueue - File avec tableau linéaire
bool enqueue(File *L1, type_element valeur)
{
}
Opérations sur les files - enqueue
Fonction enqueue - File avec tableau linéaire
bool enqueue(File *L1, type_element valeur)
{
if (est_pleine(*L1)) //la file est pleine, pas d’ajout de valeur possible
}
Opérations sur les files - enqueue
Fonction enqueue - File avec tableau linéaire
bool enqueue(File *L1, type_element valeur)
{
if (est_pleine(*L1)) //la file est pleine, pas d’ajout de valeur possible
return false ;
}
Opérations sur les files - enqueue
Fonction enqueue - File avec tableau linéaire
bool enqueue(File *L1, type_element valeur)
{
if (est_pleine(*L1)) //la file est pleine, pas d’ajout de valeur possible
return false ;
L1->Tab[L1->taille] = valeur ; //1er element est à l’indice 0
}
Opérations sur les files - enqueue
Fonction enqueue - File avec tableau linéaire
bool enqueue(File *L1, type_element valeur)
{
if (est_pleine(*L1)) //la file est pleine, pas d’ajout de valeur possible
return false ;
L1->Tab[L1->taille] = valeur ; //1er element est à l’indice 0
L1->taille = L1->taille+1 ; //on a un element de plus
}
Opérations sur les files - enqueue
Fonction enqueue - File avec tableau linéaire
bool enqueue(File *L1, type_element valeur)
{
if (est_pleine(*L1)) //la file est pleine, pas d’ajout de valeur possible
return false ;
L1->Tab[L1->taille] = valeur ; //1er element est à l’indice 0
L1->taille = L1->taille+1 ; //on a un element de plus
return true ;
}
LA FILE : autre représentation
Caractéristiques
Tableau circulaire : avec une taille fixée N, on ne pourra mettre que
N-1 éléments dans la file.
2 variables "avant" et "arrière" : pour repérer l’emplacement de
l’élément à supprimer, et celui de l’élément à ajouter.
Structure
struct File {
type_elt Tab[Max] ; //Max-1 éléments possibles
int avant ;
int arriere ;
53
LA FILE : représentation avec tableau circulaire
Propriétés spécifiques
Taille du tableau : fixée à N+1 pour contenir N éléments.
54
LA FILE : représentation avec tableau circulaire
Propriétés spécifiques
Taille du tableau : fixée à N+1 pour contenir N éléments.
file vide : avant = arriere.
55
LA FILE : représentation avec tableau circulaire
Propriétés spécifiques
Taille du tableau : fixée à N+1 pour contenir N éléments.
file vide : avant = arriere.
file pleine : avant = arriere + 1.
56
LA FILE : représentation avec tableau circulaire
Propriétés spécifiques
Taille du tableau : fixée à N+1 pour contenir N éléments.
file vide : avant = arriere.
file pleine : avant = arriere + 1.
Structure
struct File {
type_elt Tab[Max] ; //Max-1 éléments possibles
int avant ; // =0 au départ
int arriere ; // =0 au départ
};
Opérations sur les files - enqueue
Fonction enqueue - File avec tableau circulaire
bool enqueue(File *L1, type_element valeur)
{
}
Opérations sur les files - enqueue
Fonction enqueue - File avec tableau circulaire
bool enqueue(File *L1, type_element valeur)
{
if (est_pleine(*L1)) //la file est pleine, pas d’ajout de valeur possible
}
Opérations sur les files - enqueue
Fonction enqueue - File avec tableau circulaire
bool enqueue(File *L1, type_element valeur)
{
if (est_pleine(*L1)) //la file est pleine, pas d’ajout de valeur possible
return false ;
}
Opérations sur les files - enqueue
Fonction enqueue - File avec tableau circulaire
bool enqueue(File *L1, type_element valeur)
{
if (est_pleine(*L1)) //la file est pleine, pas d’ajout de valeur possible
return false ;
L1->Tab[L1->arriere] = valeur ; //file non pleine
}
Opérations sur les files - enqueue
Fonction enqueue - File avec tableau circulaire
bool enqueue(File *L1, type_element valeur)
{
if (est_pleine(*L1)) //la file est pleine, pas d’ajout de valeur possible
return false ;
L1->Tab[L1->arriere] = valeur ; //file non pleine
L1->arriere = (L1->arriere+1)%Max ; //prochain emplacement
}
Opérations sur les files - enqueue
Fonction enqueue - File avec tableau circulaire
bool enqueue(File *L1, type_element valeur)
{
if (est_pleine(*L1)) //la file est pleine, pas d’ajout de valeur possible
return false ;
L1->Tab[L1->arriere] = valeur ; //file non pleine
L1->arriere = (L1->arriere+1)%Max ; //prochain emplacement
return true ;
}
