Algorithmes de base
Factorielle
Complexité : \( C_n = \mathcal{O}(n) \)
let rec factorielle n = if n = 0 then 1 else n * (factorielle (n - 1))
HR : "Si \( n \) désigne l'entrée, factorielle n termine et renvoie \( n! \)"
int factorielle(int n) {
int res = 1;
for (int i = 1; i <= n; i += 1) {
res *= i;
}
return res;
}
Variant : \( n + 1 - i \)
Invariant : \( res = i! \)
Expo rapide
Complexité : \( C_n = \mathcal{O}(log(n)) \)
let rec expo_rapide x n = if n = 0 then 1
else if n mod 2 = 0 then expo_rapide (x*x) (n/2)
else x * (expo_rapide (x*x) ((n - 1) / 2))
HR : Par récurence sur \( n \) : "expo_rapide x n termine et renvoie \( x^n \)"
int expo_rapide(int x, int n) {
int resultat = 1;
while (n > 0) {
if (n % 2 == 0) {
n = n/2;
} else {
resultat *= x;
n = (n - 1)/2;
}
x = x*x;
}
return resultat;
}
Variant : \( n \)
Invariant : En notant \( N \) la valeur initiale de \( n \) et \( X \) la valeur initiale de \( x \), on prend \( X^N = resultat \cdot (x^n) \)
Euclide
Complexité : Pas au programme, nous n'avons pas les outils pour la calculer
let rec euclide a b = if b = 0 then a else euclide b (a mod b)
HR : Récurrence sur \( b \). "euclide a b termine et renvoie \( pgcd(a,b) \)"
int euclide(int a, int b) {
while (b > 0) {
int tmp = a;
a = b;
b = tmp % b;
}
return a;
}
Variant : \( b \)
Invariant : En notant \( A \) et \( B \) les valeurs originales de \( a \) et \( b \) on prend \( pgcd(a,b) = pgcd(A,B) \)
PS : Pour la récurrence/l'invariant voir le cours de maths pour la relation entre pgcd de deux nombres et division euclidienne.
Recherche dichotomique
Complexité : \( C_n = \mathcal{O}(log(n)) \)
let rec recherche_dicho_interne tab value imin imax = if imin > imax then false
else let imoy = (imin + imax) / 2 in let vmoy = t.(imoy) in
if vmoy = value then true
else if vmoy < value then recherche_dicho_interne tab value (imoy + 1) imax
else recherche_dicho_interne tab value imin (imoy - 1)
let recherche_dicho tab value = recherche_dicho_interne tab value 0 (Array.length tab - 1)
HR (pour recherche_dicho_interne) : Sur \( imax - imin \), "recherche_dicho_interne et renvoie vrai si et seulement si la valeur \( val \) est dans le tableau entre les indices \( imin \) et \( imax \)"
bool recherche_dichotomique(int tab[], int taille_tab, int val) {
int imin = 0;
int imax = taille_tab - 1;
while (imin <= imax) {
int imoy = (imin + imax) / 2;
int vmoy = tab[imoy];
if (vmoy == val) {
return true;
} else if (vmoy < val) {
imin = imoy + 1;
} else {
imax = imoy - 1;
}
}
return false;
}
Variant : \( imax - imin \)
Invariant : "Si tab contient val c'est entre les indices imin et imax"
Nombre de chiffre d'un entier naturel
Complexité : \( C_n = \mathcal{O}(k) \) où \( k \) désigne le nombre de chiffres de \( n \)
let rec nb_chiffres n = if n < 10 then 1 else
1 + (nb_chiffres (n / 10))
HR : "nb_chiffres(n) termine et renvoie le nombre de chiffre de n"
int nb_chiffres(int n) {
int nb = 1;
while (n > 9) {
nb += 1;
n = n / 10;
}
return nb;
}
Variant : \( n \)
Invariant : En notant \( N \) la valeur initiale de \( n \), et \( l(a) \) le nombre de chiffres de \( a \), on pose \( l(N) = l(n) + nb \)
Fonctions du module List (Ocaml)
(* Longueur d'une liste ie List.length *)
let rec length lst =
match lst with
| [] -> 0
| _ :: t -> 1 + length t
(* Vérifie si un élément est dans la liste ie List.mem *)
let rec mem x lst =
match lst with
| [] -> false
| h :: t -> h = x || mem x t
(* Vérifie si un élément satisfait le prédicat ie List.exists *)
let rec exists p lst =
match lst with
| [] -> false
| h :: t -> p h || exists p t
(* Vérifie si tous les éléments satisfont le prédicat ie List.for_all *)
let rec for_all p lst =
match lst with
| [] -> true
| h :: t -> p h && for_all p t
(* Filtre les éléments qui satisfont le prédicat ie List.filter *)
let rec filter p lst =
match lst with
| [] -> []
| h :: t ->
if p h then h :: filter p t
else filter p t
(* Applique une fonction à chaque élément ie List.map *)
let rec map f lst =
match lst with
| [] -> []
| h :: t -> f h :: map f t
(* Concaténation de deux listes ie l'opérateur @ *)
let rec concat l1 l2 =
match l1 with
| [] -> l2
| h :: t -> h :: (concat t l2)
Fonctions du module Array (Ocaml)
Les fonctions Array.length et Array.make ne sont pas réécrivables.
Array.filter n'existe pas.
(* Copie d'un tableau ie Array.copy *)
let copy a =
let n = Array.length a in
let r = Array.make n a.(0) in
for i = 0 to n - 1 do
r.(i) <- a.(i)
done;
r
(* La copie créée est indépendante de l'original *)
(* Création d'une matrice m x n remplie avec x ie Array.make_matrix *)
let make_matrix m n x =
let r = Array.make m [||] in
for i = 0 to m - 1 do
r.(i) <- Array.make n x
done;
r
(* Initialise un tableau avec f ie Array.init *)
let init n f =
if n < 0 then invalid_arg "init";
let r = Array.make n (f 0) in
for i = 0 to n - 1 do
r.(i) <- f i
done;
r
(* Test si un élément est présent ie Array.mem *)
let mem x a =
let n = Array.length a in
let rec loop i =
i < n && (a.(i) = x || loop (i + 1))
in
loop 0
(* Test si au moins un élément satisfait p ie Array.exists *)
let exists p a =
let n = Array.length a in
let rec loop i =
i < n && (p a.(i) || loop (i + 1))
in
loop 0
(* Test si tous les éléments satisfont p ie Array.for_all *)
let for_all p a =
let n = Array.length a in
let rec loop i =
i >= n || (p a.(i) && loop (i + 1))
in
loop 0
(* Sous-tableau de a à partir de i de longueur len ie Array.sub *)
let sub a i len =
if i < 0 || len < 0 || i + len > Array.length a then invalid_arg "sub";
let r = Array.make len a.(i) in
for k = 0 to len - 1 do
r.(k) <- a.(i + k)
done;
r
(* Applique f à chaque élément ie Array.iter *)
let iter f a =
let n = Array.length a in
for i = 0 to n - 1 do
f a.(i)
done
Fonctions du module String (C)
#include <stdio.h>
/* Longueur d'une chaîne (comme strlen) */
int len(const char *s) {
int n = 0;
while (s[n] != '\0') {
n += 1;
}
return n;
}
/* Copie d'une chaîne (comme strcpy) */
char* cpy(char* dest, char* src) {
int i = 0;
while (src[i] != '\0') {
dest[i] = src[i];
i += 1;
}
dest[i] = '\0'; // Ajout de la sentinelle
return dest;
}
/* La copie créée est indépendante de l'original */
/* Concaténation de deux chaînes (comme strcat) */
char* cat(char* dest, char* src) {
int i = 0;
int j = 0;
while (dest[i] != '\0') {
i += 1;
}
while (src[j] != '\0') {
dest[i + j] = src[j];
j += 1;
}
dest[i + j] = '\0'; // Ajout de la sentinelle
return dest;
}
/* Comparaison lexicographique (comme strcmp) */
int cmp(const char* s1, char* s2) {
int i = 0;
while (s1[i] != '\0' && s2[i] != '\0') {
if (s1[i] != s2[i]) {
return (unsigned char)s1[i] - (unsigned char)s2[i];
}
i += 1;
}
return (unsigned char)s1[i] - (unsigned char)s2[i];
}
Méthodes de résolution de problèmes
Programmation dynamique
Top-down
FCT TOP_DOWN(n) :
memo <- structure de mémoïsation (tableau ou table de hachage)
FCT REMPLIR(memo, i) :
[Relation de récurence de la fonction sans mémoïsation sous forme récursive]
RENVOYER memo_i
FIN FCT
RENVOYER REMPLIR(memo, n)
FIN FCT
Bottom-up
FCT BOTTOM_UP(n) :
memo <- structure de mémoïsation (tableau ou table de hachage)
[Initialisation des valeurs initiales ie les cas de base]
[Relation de récurence de la fonction sans mémoïsation sous forme itérative (boucle)]
RENVOYER memo_n
FIN FCT
Note : On doit connaître le nombre d'itérations à réaliser pour faire du bottom-up
Backtracking
On suppose avoir :
- une fonction racine() qui renvoie la construction initiale vide
- une fonction fils(construction partielle) qui renvoie la liste des constructions avec 1 élément en plus que celle en paramètre
- une fonction est_feuille(construction) qui détermine si la construction est complétée
FCT BACKTRACKING(construction) :
SI est_feuille(construction) ALORS : //On vérifie si la construction est complète
SI P(construction) ALORS : // On vérifie si la construction satisfait la propriété voulue
S'arrêter avec cette construction comme solution
SINON
POUR CHAQUE construction_suivante dans fils(construction) FAIRE
BACKTRACKING(construction_suivante)
FIN SI
FIN SI
FIN FCT
FCT RESOLUTION():
BACKTRACKING(racine())
FIN FCT
Note : cette fonction ne comprend pas l'élagage de l'arbre
Représentation des nombres
Ecriture (petit-boutiste)
Complexité : \( C_n = \mathcal{O}(log(n)) \)
let rec ecriture n b = match n with
| 0 -> []
| _ -> let q, r = (n / b, n mod b) in r::(ecriture q b)
HR : Par récurence sur \( n \) : "ecriture n b termine et renvoie l'écriture de n en base b"
#include <math.h>
int* ecriture(int n, int b){
// Ecriture de n en base b
if (n == 0){
return NULL;
}
else{
int* res = malloc((log_base(n, b) + 1) * sizeof(int));
int i = 0;
while (n != 0){
int r = n % b;
n = n / b;
res[i] = r;
i += 1;
}
return res;
}
}
Variant : \( n \)
Invariant : En notant \( N_0 \) la valeur initiale de \( n \). Les indices de 0 à i-1 contiennent les i premiers chiffres de poids faible de \( N_0 \) et \(n = N_0 / b^i \)
Hörner (petit-boutiste)
Complexité : \( C_n = \mathcal{O}(n) \) où n désigne la taille de l
let horner l b = match l with
| [] -> 0
| h::t -> h + b * (horner t b)
HR : Par récurence sur \( n \), taille de la liste : "horner l b termine et renvoie l'écriture de l en base décimale"
int horner(int* ecr, int taille_ecr, int b){
int res = 0;
for (int i = taille_ecr - 1; i >= 0; i -= 1){
res = ecr[i] + b * res;
}
return res;
}
Variant : \( i \)
Invariant : Pour tout \(i \), \(res = \sum_{k = i + 1}^{taille\_ecr - 1} ecr_k \cdot b^{k-i-1} \)
Fonctions sur les arbres
Parcours d'arbres
Parcours préfixe
FCT PROFONDEUR_PREFIXE(A : arbre binaire strict) :
SI A est une feuille ALORS :
TRAITER(A)
SINON A est un noeud interne de la forme N(e,g,d) :
TRAITER(e)
PROFONDEUR_PREFIXE(g)
PROFONDEUR_PREFIXE(d)
FIN SI
FIN FCT
Parcours infixe
FCT PROFONDEUR_INFIXE(A : arbre binaire strict) :
SI A est une feuille ALORS :
TRAITER(A)
SINON A est un noeud interne de la forme N(e,g,d) :
PROFONDEUR_INFIXE(g)
TRAITER(e)
PROFONDEUR_INFIXE(d)
FIN SI
FIN FCT
Parcours postfixe
FCT PROFONDEUR_POSTFIXE(A : arbre binaire strict) :
SI A est une feuille ALORS :
TRAITER(A)
SINON A est un noeud interne de la forme N(e,g,d) :
PROFONDEUR_POSTFIXE(g)
PROFONDEUR_POSTFIXE(d)
TRAITER(e)
FIN SI
FIN FCT
Parcours largeur
FCT PARCOURS_LARGEUR(A : arbre binaire strict) :
a_traiter <- file vide
a_traiter <- enfiler A
TANT QUE a_traiter non vide FAIRE :
a <- defiler(a_traiter)
SI a est une feuille ALORS :
TRAITER(a)
SINON a est un noeud interne de la forme N(e,g,d) :
TRAITER(e)
a_traiter <- enfiler(g)
a_traiter <- enfiler(d)
FIN Si
FIN FCT
Binarisation
FCT AUX(foret : liste d'arbres frères) :
SI foret est vide ALORS :
RENVOYER ⊥
SINON foret est de la forme N(e,fils) :
RENVOYER(e, AUX(fils), AUX(queue de foret))
FIN SI
FIN FCT
FCT BINARISE(A : arbre d'arité quelconque non vide) :
RENVOYER AUX([A])
FIN FCT
Rappel : Un arbre d'arité quelconque est stocké sous la forme N(e,[a1,...,an]) où e est l'étiquette et an,...,an sont des arbres d'arité quelconque placés dans une liste
Débinarisation
FCT AUX(A) :
SI A est vide ALORS :
RENVOYER ⊥
SINON A est de la forme N(e,g,d) :
lc <- AUX(g)
rs <- AUX(d)
RENVOYER N(e,lc)::rs
FIN SI
FIN FCT
FCT DEBINARISE(A : arbre binaire correspondant à une représentation LCRS) :
RENVOYER tete de AUX(A)
FIN FCT
Parcours de graphes
Parcours profondeur
FCT PARCOURS_PROFONDEUR(graphe G, sommet dep) :
vus <- {}
FONCTION EXPLORER(sommet s) :
SI s ∉ vus ALORS :
TRAITER(s)
vus <- ajouter s
POUR chaque voisin/successeur v de s :
EXPLORER v
FIN POUR
FIN SI
FIN FCT
EXPLORER dep
FIN FCT
Parcours largeur
FCT PARCOURS_LARGEUR(graphe G, sommet dep) :
a_traiter <- file vide
a_traiter <- enfiler dep
vus <- {dep}
TANT QUE a_traiter non vide FAIRE :
s <- defiler(a_traiter)
TRAITER(s)
POUR chaque voisin/successeur de v de s :
SI v ∉ vus ALORS :
a_traiter <- enfiler v
vus <- ajouter v
FIN SI
FIN POUR
FIN TANT QUE
FIN FCT
Parcours générique
FCT PARCOURS_GENERIQUE(graphe G, sommet dep) :
a_traiter <- structure de données
a_traiter <- ajouter dep
vus <- {}
TANT QUE a_traiter non vide FAIRE :
s <- extraire(a_traiter)
SI s ∉ vus ALORS :
TRAITER(s)
vus <- ajouter(s)
POUR chaque voisin/successeur v de s FAIRE :
a_traiter <- ajouter(v)
FIN POUR
FIN SI
FIN TANT QUE
FIN FCT
Algorithmes de recherche dans un graphe pondéré
Floyd-Warshall
Complexité : \( C_n = \mathcal{O}(|S|^3) \)
FCT FLOYD_WARSHALL(M : matrice d'adjacence d'un graphe pondéré) :
POUR k ALLANT de 0 A |S| - 1 FAIRE :
POUR i ALLANT DE 0 A |S| - 1 FAIRE :
POUR j ALLANT de 0 A |S| - 1 FAIRE :
M_{i,j} <- min(M_{i,j}, M_{i,k} + M_{k,j})
FIN POUR
FIN POUR
FIN POUR
FIN FCT
Dijkstra
Complexité : \( C_n = \mathcal{O}((|S| + |A|)log(|S|)) \)
FCT DIJKSTRA(G : graphe pondéré, dep : sommet de départ) :
vus <- {}
a_traiter <- file de priorité vide
a_traiter <- enfiler dep de priorité 0
distance <- structure qui associe à dep 0 et aux autres sommets +∞
TANT QUE a_traiter non vide FAIRE :
s <- defiler de a_traiter le sommet de priorité minimale
SI s ∉ vus ALORS :
vus <- vus U {s}
POUR chaque voisin v de s dans G FAIRE :
SI distances[v] > distances[s] + ω(s,v) ALORS :
disntaces[v] <- distances[s] + ω(s,v)
a_traiter <- enfiler v
FIN SI
FIN POUR
FIN SI
FIN TANT QUE
FIN FCT
Fonctions de base sur les tableaux
Max / Min
Complexité : \( C_n = \mathcal{O}(n) \) où \( n \) désigne la taille de l
let rec max l = match l with
| [] -> failwith "Pas de maximum"
| [p] -> p
| p::q -> let max_reste = max q in if p > max_reste then p else max_reste
let rec min l = match l with
| [] -> failwith "Pas de minimum"
| [p] -> p
| p::q -> let min_reste = min q in if p < min_reste then p else min_reste
HR : Récurrence sur \( n \), la taille de l : "Pour toute liste l de taille \( n \) : max l (resp. min l) termine et renvoie le maximum (resp. le minimum) de l"
// On suppose le tableau non-vide
int max(int tab[], int taille_tab) {
int max_actuel = tab[0];
for (int i = 0; i < taille_tab; i += 1) {
if (tab[i] > max_actuel) {
max_actuel = tab[i];
}
}
return max_actuel;
}
int min(int tab[], int taille_tab) {
int min_actuel = tab[0];
for (int i = 0; i < taille_tab; i += 1) {
if (tab[i] < min_actuel) {
min_actuel = tab[i];
}
}
return min_actuel;
}
Variant : \( taille\_tab - i \)
Invariant : \( max\_actuel \) (resp. \( min\_actuel \) ) contient le maximum (resp. le minimum) des valeurs de tab d'indice inférieur à \( i \)
Indice max/Indice min
Complexité : \( C_n = \mathcal{O}(n) \) où \( n \) désigne la taille de l
let rec max_avec_indice l = match l with
| [] -> failwith "Pas de maximum"
| [p] -> (p, 0) (* valeur, indice *)
| p::q -> let (max_reste, indice_max_reste) = max_avec_indice q in
if p > max_reste then (p, 0) else (max_reste, 1 + indice_max_reste)
let rec indice_max l = snd (max_avec_indice l)
let rec min_avec_indice l = match l with
| [] -> failwith "Pas de minimum"
| [p] -> (p, 0) (* valeur, indice *)
| p::q -> let (min_reste, indice_min_reste) = min_avec_indice q in
if p < min_reste then (p, 0) else (min_reste, 1 + indice_min_reste)
let rec indice_min l = snd (min_avec_indice l)
HR (pour max_avec_indice et min_avec_indice) : Sur la taille \( n \) de l : "max_avec_indice (resp. min_avec_indice) termine et renvoie un tuple contenant la valeur du max (resp. min) et son indice"
// On suppose le tableau non-vide
int indice_max(int tab[], int taille_tab) {
int indice_max_actuel = 0;
for (int i = 0; i < taille_tab; i += 1) {
if (tab[i] > tab[indice_max_actuel]) {
indice_max_actuel = i;
}
}
return indice_max_actuel;
}
int indice_min(int tab[], int taille_tab) {
int indice_min_actuel = 0;
for (int i = 0; i < taille_tab; i += 1) {
if (tab[i] < tab[indice_min_actuel]) {
indice_min_actuel = i;
}
}
return indice_min_actuel;
}
Variant : \( taille\_tab - i \)
Invariant : \( indice\_max\_actuel \) (resp. \( indice\_min\_actuel \) contient l'indice du maximum (resp. du minimum) des valeurs de tab d'indice inférieur à \( i \)
Nombre d'occurences
Complexité : \( C_n = \mathcal{O}(n) \) où \( n \) désigne la taille de l
let rec nombre_occurences l v = match l with
| [] -> 0
| p::q -> if p = v then 1 + (nombre_occurences q v) else (nombre_occurences q v)
HR : Sur la taille \( n \) de l : "Pour toute liste l de taille \( n \), nombre_occurences l v termine et renvoie le nombre d'occurences de v dans l"
int nombre_occurences(int tab[], int taille_tab, int val) {
int nb_occ = 0;
for (int i = 0; i < taille_tab; i += 1) {
if (tab[i] == val) {
nb_occ += 1;
}
}
return nb_occ;
}
Variant : \( taille\_tab - i \)
Invariant : \( nb\_occ \) contient le nombre d'occurences de val dans tab d'indice inférieur à \( i \)
Indice première/dernière occurence
Complexité : \( C_n = \mathcal{O}(n) \) où \( n \) désigne la taille de l
(* Pas obligatoire mais TRES PRATIQUE DANS BEAUCOUP DE CAS *)
let fmap_option f o = match o with
| None -> None
| Some v -> Some (f v)
let rec indice_premiere_occurence l v = match l with
| [] -> None
| p::q -> if p = v then Some 0 else fmap_option (fun i -> i + 1) (indice_premiere_occurence q v)
let rec indice_derniere_occurence l v = match l with
| [] -> None
| p::q -> match indice_derniere_occurence q v with
| None -> if p = v then Some 0 else None
| Some i -> Some (i + 1)
HR : Sur \( n \) la taille de l : "Pour toute liste l de taille \( n \), indice_premiere_occurence l v (resp. indice_derniere_occurence l v) renvoie None si la valeur n'est pas dans la liste et Some i avec \( i \) l'indice de la première (resp. dernière) occurence de v dans l sinon"
int indice_premiere_occurence(int tab[], int taille_tab, int val) {
for (int i = 0; i < taille_tab; i += 1) {
if (tab[i] == val) {
return i;
}
}
return -1;
}
int indice_derniere_occurence(int tab[], int taille_tab, int val) {
for (int i = taille_tab - 1; i >= 0; i -= 1) {
if (tab[i] == val) {
return i;
}
}
return -1;
}
Variant : \( taille\_tab - i \) et \( i + 1 \) respectivement.
Invariant : tab ne contient pas la valeur val pour des indices inférieurs (resp. supérieurs) à \( i \)
Est-trié dans l'ordre croissant
Complexité : \( C_n = \mathcal{O}(n) \) où \( n \) désigne la taille de l
let rec est_croissant l = match l with
| [] | [_] -> true
| p1::p2::q -> (p1 <= p2) && (est_croissant (p2::q))
HR : Sur la taille \( n \) de l : "Pour toute liste l de taille \( n \), est_croissant l renvoie vrai si et seulement si l est trié dans l'ordre croissant"
bool est_croissant(int tab[], int taille_tab) {
for (int i = 0; i < taille_tab - 1; i += 1) {
if (tab[i+1] < tab[i]) {
return false;
}
}
return true;
}
Variant : \( taille\_tab - i \)
Invariant : Les valeurs de tab d'indices inférieurs à \( i \) sont triées dans l'ordre croissant.
Somme des valeurs
Complexité : \( C_n = \mathcal{O}(n) \) où \( n \) désigne la taille de l
let rec somme l = match l with
| [] -> 0
| p::q -> p + (somme q)
HR : Sur \( n \) la taille de l : "Pour toute liste l de taille \( n \), somme l termine et renvoie la somme des éléments de l"
int somme(int tab[], int taille_tab) {
int s = 0;
for (int i = 0; i < taille_tab; i += 1) {
s += tab[i];
}
return s;
}
Variant : \( taille\_tab - i \)
Invariant : \( s = \sum_{k = 0}^{i} tab_i \) où \( tab_i \) désigne l'élément d'indice \( i \) dans tab
Algorithmes de tri
Tri par sélection
Complexité : \( C_n = \mathcal{O}(n^2) \) où \( n \) désigne la taille de l
let rec extrait_minimum l = match l with
| [] -> failwith "Pas de minimum"
| [a] -> (a, [])
| p::q -> let (min_q, reste_q) = extrait_minimum q in
if p < min_q then (p, min_q::reste_q) else (min_q, p::reste_q)
let rec tri_selection l = match l with
| [] -> []
| [a] -> [a]
| _ -> let min, reste = extrait_minimum l in
min::(tri_selection reste)
void tri_selection(int tab[], int taille_tab) {
for (int i = 0; i < taille_tab; i += 1) {
int imin = i;
for (int j = i; j < taille_tab; j += 1) {
if (tab[j] < tab[imin]) {
imin = j;
}
}
int tmp = tab[i];
tab[i] = tab[imin];
tab[imin] = tmp;
}
}
Tri à bulles
Complexité : \( C_n = \mathcal{O}(n^2) \) où \( n \) désigne la taille de l
let rec un_tour l = match l with
| [] -> []
| [p] -> [p]
| p1::p2::q -> if p1 < p2 then p1::(un_tour p2::q) else p2::(un_tour p1::q)
let rec tri_a_bulle l = let apres_un_tour = un_tour l in if l = apres_un_tour then l else tri_bulles apres_un_tour
void tri_a_bulles(int tab[], int taille_tab){
for (int i = 0; i < taille_tab; i += 1){
for (int j = 0; j < taille_tab - i - 1; j += 1){
if (tab[j + 1] < tab[j]){
int tmp = tab[j];
tab[j] = tab[j + 1];
tab[j + 1] = tmp;
}
}
}
}
Tri par insertion
Complexité : \( C_n = \mathcal{O}(n^2) \) où \( n \) désigne la taille de l
let rec insere l e = match l with
| [] -> [e]
| p::q -> if e < p then e::p::q else p::(insere q e)
let tri_insertion l = match l with
| [] -> []
| p::q -> insere (tri_insertion q) p
void tri_insertion(int tab[], int taille_tab){
for (int i = 0; i < taille_tab; i += 1){
int j = i;
while (j > 0 && tab[j] < tab[j - 1]){
int temp = tab[j];
tab[j] = tab[j - 1];
tab[j - 1] = temp;
j -= 1;
}
}
}
Tri fusion
Complexité : \( C_n = \mathcal{O}(n\log(n)) \) où \( n \) désigne la taille de l
Sur des listes
let diviser l =
let rec aux l l1 l2 = match l with
| [] -> (l1, l2)
| h::[] -> (h::l1, l2)
| h1::h2::q -> aux q (h1::l1) (h2::l2)
in
aux l [] []
let rec fusion l1 l2 = match l1, l2 with
| [], [] -> failwith "PAS POSSIBLE"
| [], a | a, [] -> a
| h1::q1, h2::q2 ->
if h1 < h2 then h1::(fusion q1 (h2::q2))
else h2::(fusion (h1::q1) q2)
let rec tri_fusion l = match l with
| [] | [_] -> l
| _ ->
let tri1, tri2 = diviser l in
fusion (tri_fusion tri1) (tri_fusion tri2)
void divise(liste l, liste* pairs, liste* impairs){
if (!est_vide(l)){
ajoute(tete(l), pairs);
if (!est_vide(queue(l))){
ajoute(tete(queue(l)), impairs);
divise(queue(queue(l)), pairs, impairs);
}
}
}
liste fusion(liste l1, liste l2){
if (est_vide(l1)){
return copie(l2);
}
else if (est_vide(l2)){
return copie(l1);
}
else{
liste res;
if (tete(l1) < tete(l2)){
res = fusion(queue(l1), l2);
ajoute(tete(l1), &res);
}
else{
res = fusion(l1, queue(l2));
ajoute(tete(l2), &res);
}
return res;
}
}
liste tri_fusion(liste l){
if (est_vide(l) || est_vide(queue(l))){
return copie(l);
}
else{
liste temp1 = creer ();
liste temp2 = creer ();
divise(l, &temp1, &temp2);
liste tri1 = tri_fusion(temp1);
liste tri2 = tri_fusion(temp2);
liste res = fusion(tri1, tri2);
detruire(temp1);
detruire(temp2);
detruire(tri1);
detruire(tri2);
return res;
}
}
Sur des tableaux
let sous_tableau a i j =
let res = Array.make (j - i + 1) a.(0) in
for k = i to j do
res.(k - i) <- a.(k)
done;
res
let fusion_tableaux a1 a2 =
let s1 = Array.length a1 in
let s2 = Array.length a2 in
let res = Array.make (s1 + s2) a1.(0) in
let i = ref 0 in
let j = ref 0 in
for k = 0 to s1 + s2 - 1 do
if !j >= s2 || (!i < s1 && a1.(!i) < a2.(!j)) then
begin
res.(k) <- a1.(!i);
incr i;
end
else
begin
res.(k) <- a2.(!j);
incr j
end
done;
res
let rec tri_fusion_tableaux a =
let s = Array.length a in
if s = 0 || s = 1 then a
else
let tri1 = sous_tableau a 0 (s/2 - 1) in
let tri2 = sous_tableau a (s/2) (s - 1) in
fusion_tableaux (tri_fusion_tableaux tri1) (tri_fusion_tableaux tri2)
int* sous_tableau(int a[], int i, int j){
int* res = malloc((j - i + 1) * sizeof(int));
for (int k = i; k < j + 1; k += 1){
res[k - i] = a[k];
}
return res;
}
int* fusion_tableaux(int a1[], int a2[], int s1, int s2){
int* res = malloc((s1 + s2) * sizeof(int));
int i = 0;
int j = 0;
for (int k = 0; k < s1 + s2; k += 1){
if (j >= s2 || (i < s1 && a1[i] < a2[j])){
res[k] = a1[i];
i += 1;
}
else{
res[k] = a2[j];
j += 1;
}
}
return res;
}
int* tri_fusion_tableaux(int a[], int s){
if (s == 0){
return NULL;
}
else if (s == 1){
int* res = malloc(sizeof(int));
res[0] = a[0];
return res;
}
else {
int* temp1 = sous_tableau(a, 0, s/2 - 1);
int* temp2 = sous_tableau(a, s/2, s - 1);
int* tri1 = tri_fusion_tableaux(temp1, s/2);
int* tri2 = tri_fusion_tableaux (temp2, s - s/2);
int* res = fusion_tableaux(tri1, tri2, s/2, s - s/2);
free(temp1);
free(temp2);
free(tri1);
free(tri2);
return res;
}
}
Tri rapide
Complexité : \( C_n = \mathcal{O}(n^2) \) mais \( \Theta(n\log(n))\) où \( n \) désigne la taille de l
Sur des listes
let partition l p =
let rec aux l l1 l2 = match l with
| [] -> (l1, l2)
| h::t ->
if h < p then aux t (h::l1) l2
else aux t l1 (h::l2)
in
aux l [] []
let rec tri_rapide l = match l with
| [] -> []
| h::t ->
let tri1, tri2 = partition t h in
(tri_rapide tri1)@(h::(tri_rapide tri2))
void partition(liste l, int pivot, liste* inf, liste* sup){
if (!est_vide(l)){
if (tete(l) < pivot){
ajoute(tete(l), inf);
}
else{
ajoute(tete(l), sup);
}
partition(queue(l), pivot, inf, sup);
}
}
liste tri_rapide(liste l){
if (est_vide(l)){
return creer();
}
else{
liste temp1 = creer ();
liste temp2 = creer ();
partition(queue(l), tete(l), &temp1, &temp2);
liste tri1 = tri_rapide(temp1);
liste tri2 = tri_rapide(temp2);
ajoute(tete(l), &tri2);
liste res = concat(tri1, tri2);
detruire(temp1);
detruire(temp2);
detruire(tri1);
detruire(tri2);
return res;
}
}
Sur des tableaux
let partition a deb fin =
let k = ref deb in
let pivot = a.(fin) in
for i = deb to fin - 1 do
if a.(i) < pivot then
begin
let temp = a.(i) in
a.(i) <- a.(!k);
a.(!k) <- temp;
incr k
end
done;
let temp = a.(fin) in
a.(fin) <- a.(!k);
a.(!k) <- temp;
!k
let rec tri_rapide_aux a deb fin =
let k = partition a deb fin in
if k > deb then tri_rapide_aux a deb (k-1);
if k < fin then tri_rapide_aux a (k+1) fin
let tri_rapide a = tri_rapide_aux a 0 (Array.length a - 1)
int partition_lomuto(int t[], int debut, int fin){
int k = debut;
int pivot = t[fin];
for (int i = debut; i < fin; i += 1){
if (t[i] < pivot){
int temp = t[i];
t[i] = t[k];
t[k] = temp;
k += 1;
}
}
int temp = t[fin];
t[fin] = t[k];
t[k] = temp;
return k;
}
void tri_rapide_aux(int tab[], int debut, int fin){
int k = partition_lomuto(tab, debut, fin);
if (k > debut){
tri_rapide_aux(tab, debut, k-1);
}
if (k < fin){
tri_rapide_aux(tab, k+1, fin);
}
}
void tri_rapide(int tab[], int taille_tab){
tri_rapide_aux(tab, 0, taille_tab - 1);
}
Structures
Ce fichier ne contient que les implémentations des structures en C et des fonctions de leur interface, autrement dit, les parcours d'arbres et autres ne sont pas ici
Structure générale
(utilisée pour les listes, piles, files)
typedef int contenu;
struct maillon_s {
contenu valeur;
struct maillon_s* suivant;
};
typedef struct maillon_s maillon;
Listes chaînées
typedef maillon* liste;
Fonctions
liste creer_liste(void){
return NULL;
}
bool est_vide_liste(liste l){
return (l == NULL);
}
void ajouter_tete_liste(contenu elt, liste* l){
maillon* nouveau_maillon = malloc(sizeof(maillon));
nouveau_maillon->valeur = elt;
nouveau_maillon->suivant = *l;
*l = nouveau_maillon;
}
contenu tete_liste(liste l){
assert(l != NULL);
return l->valeur;
}
liste queue_liste(liste l){
assert(l != NULL);
return l->suivant;
}
void detruire_liste(liste l){
if (l != NULL){
detruire_liste(queue_liste(l));
free(l);
}
}
Pas obligatoire mais pratique (pour les tris par exemple)
liste copie(liste l) {
if (est_vide_liste(l)) {
return NULL;
}
liste nouveau_maillon = malloc(sizeof(maillon));
assert(nouveau_maillon != NULL)
nouveau_maillon->valeur = l->valeur;
nouveau_maillon->suivant = copie(l->suivant);
return nouveau_maillon;
}
void concat_aux(liste* l1, liste l2){
if (est_vide(queue(*l1))){
(*l1)->suivant = l2;
}
else{
concat_aux(&(*l1)->suivant, l2); //Je sais la syntaxe est étrange
}
}
liste concat(liste l1, liste l2){
if (est_vide(l1)){
return copie(l2);
}
else if (est_vide(l2)){
return copie (l1);
}
else{
liste c1 = copie(l1);
liste c2 = copie(l2);
concat_aux(&c1, c2);
return c1;
}
}
Piles
Structure spécifique
struct pile_s {
maillon* sommet;
};
typedef struct pile_s* pile;
Fonctions
pile creer_pile(void){
return NULL;
}
bool est_vide_pile(pile p){
return p == NULL;
}
void empiler(pile p, contenu elt){
maillon* nouveau_maillon = malloc(sizeof(maillon));
nouveau_maillon->valeur = elt;
nouveau_maillon->suivant = p->sommet;
p->sommet = nouveau_maillon;
}
contenu depiler(pile p){
assert(!est_vide_pile(p));
contenu tete = p->sommet->valeur;
maillon* temp = p->sommet->suivant;
free(p->sommet);
p->sommet = temp;
return tete;
}
contenu sommet_pile(pile p){
assert(!est_vide_pile(p));
return p->sommet->valeur;
}
void detruire_pile(pile p){
if (!est_vide_pile(p)){
depiler(p);
detruire_pile(p);
}
}
Files
Structure spécifique
struct file_s {
maillon* premier;
maillon* dernier;
};
typedef struct file_s* file;
Fonctions
file creer_file(void){
file file_res = malloc(sizeof(struct file_s));
file_res->premier = NULL;
file_res->dernier = NULL;
return file_res;
}
bool est_vide_file(file f){
return (f->premier == NULL && f->dernier == NULL);
}
void enfiler(file f, contenu elt){
maillon* nouveau_maillon = malloc(sizeof(maillon));
nouveau_maillon->valeur = elt;
nouveau_maillon->suivant = NULL;
if (est_vide_file(f)){
f->premier = nouveau_maillon;
f->dernier = nouveau_maillon;
}
else{
f->dernier->suivant = nouveau_maillon;
f->dernier = nouveau_maillon;
}
}
contenu defiler(file f){
assert(!est_vide_file(f));
contenu tete = f->premier->valeur;
maillon* temp = f->premier->suivant;
free(f->premier);
if (temp == NULL){
f->premier = NULL;
f->dernier = NULL;
}
else{
f->premier = temp;
}
return tete;
}
void detruire_file(file f){
if (!est_vide_file(f)){
defiler(f);
detruire_file(f);
}
else{
free(f);
}
}
contenu tete_file(file f){
assert(!est_vide_file(f));
return f->premier->valeur;
}
Merci Thibaud pour tout ce qui suit
Arbres
Structure spécifique
typedef int etiq;
struct noeud_s {
etiq etiquette;
struct noeud_s* gauche;
struct noeud_s* droit;
};
typedef struct noeud_s* ab;
Fonctions
ab vide(void) {
return NULL;
}
ab noeud(etiq e, ab sag, ab sad) {
ab a = malloc(sizeof(struct noeud_s));
assert(a != NULL);
a->etiquette = e;
a->gauche = sag;
a->droit = sad;
return a;
}
void libere_ab(ab a) {
if (a != NULL) {
libere_ab(a->gauche);
libere_ab(a->droit);
free(a);
}
}
bool est_vide_ab(ab a) {
return a == NULL;
}
etiq etiq_racine(ab a) {
assert(!est_vide_ab(a));
return a->etiquette;
}
ab sous_arbre_gauche(ab a) {
assert(!est_vide_ab(a));
return a->gauche;
}
ab sous_arbre_droit(ab a) {
assert(!est_vide_ab(a));
return a->droit;
}
Graphes
typedef int mat_adjacence[900]; // matrice (30,30) linéarisée
struct graphe_s {
int nb_sommets; // nombre de sommets du graphe, toujours <= 30
mat_adjacence mat;
};
typedef struct graphe_s graphe;
typedef int lst_adjacence[30][31];
struct graph_s {
int nb_sommets;
lst_adjacence liste;
};
typedef struct graph_s graph;
La liste est implémentée par un tableau contenant les voisins du sommet i où i est le numéro de la ligne.
Deux possibilités : liste[i][0] contient le nombre de voisins du sommet i ou alors liste[i] contient une sentinelle (-1) pour marquer la fin des voisins
Arbres binaires de recherche (ABR)
Structure spécifique
struct noeud_s {
int etiq;
struct noeud_s* gauche;
struct noeud_s* droit;
struct noeud_s* pere;
};
typedef struct noeud_s* abr;
Fonctions
abr construit(int e, abr g, abr d) {
abr racine = malloc(sizeof(struct noeud_s));
assert(racine != NULL);
racine->etiq = e;
racine->gauche = g;
racine->droit = d;
racine->pere = NULL;
if (g != NULL) {
g->pere = racine;
}
if (d != NULL) {
d->pere = racine;
}
return racine;
}
void detruit(abr a) {
if (a != NULL) {
detruit(a->gauche);
detruit(a->droit);
free(a);
}
}
bool recherche_abr(abr a, int e) {
if (a == NULL) {
return false;
}
else if (a->etiq == e) {
return true;
}
else if (a->etiq < e) {
return recherche_abr(a->droit, e);
}
else {
return recherche_abr(a->gauche, e);
}
}
void insertion_abr(abr* a, int e) {
// si l'arbre était vide, il devient une feuille d'étiquette e
if (*a == NULL) {
*a = construit(e, NULL, NULL);
}
// si l'insertion de e doit se faire à droite
else if ((*a)->etiq < e) {
// si (*a) n'a pas de sous-arbre droit, on insère ici
if ((*a)->droit == NULL) {
(*a)->droit = construit(e, NULL, NULL);
(*a)->droit->pere = *a;
}
// sinon on insère récursivement dans le sous-arbre droit
else {
insertion_abr(&(*a)->droit, e);
}
}
// si l'insertion de e doit se faire à gauche
else if ((*a)->etiq > e) {
if ((*a)->gauche == NULL) {
(*a)->gauche = construit(e, NULL, NULL);
(*a)->gauche->pere = *a;
}
else {
insertion_abr(&(*a)->gauche, e);
}
}
}
// suppression par la méthode de la fusion dans un ABR
abr fusion(abr x1, abr x2) {
if (x1 == NULL) {
return x2;
}
else if (x2 == NULL) {
return x1;
}
else {
// on suit le schéma
abr f = fusion(x1->droit, x2->gauche);
x1->droit = x2;
x2->pere = x1;
x2->gauche = f;
if (f != NULL) {
f->pere = x2;
}
return x1;
}
}
abr noeud_a_supprimer(abr a, int e) {
// on est arrivé au bon endroit
if (a == NULL || a->etiq == e) {
return a;
}
// le nœud à supprimer est à droite
else if (a->etiq < e) {
return noeud_a_supprimer(a->droit, e);
}
// le nœud à supprimer est à gauche
else {
return noeud_a_supprimer(a->gauche, e);
}
}
void suppression_abr_fusion(abr* a, int e) {
// on récupère le nœud à supprimer
abr a_supprimer = noeud_a_supprimer(*a, e);
if (a_supprimer != NULL) {
abr pere_du_noeud_supprime = a_supprimer->pere;
// on fusionne ses fils, et on les raccroche dans l'arbre
abr f = fusion(a_supprimer->gauche, a_supprimer->droit);
if (f != NULL) {
f->pere = pere_du_noeud_supprime;
}
// si on a supprimé la racine, la fusion des fils devient notre nouvelle racine
if (pere_du_noeud_supprime == NULL) {
*a = f;
}
else {
// sinon on rattache la fusion des fils au père du bon côté
if (pere_du_noeud_supprime->etiq < e) {
pere_du_noeud_supprime->droit = f;
}
else {
pere_du_noeud_supprime->gauche = f;
}
}
// on libère le nœud
free(a_supprimer);
}
}
Arbres bicolores
Structure spécifique
enum couleur_e {rouge, noir};
typedef enum couleur_e couleur;
struct arn_s {
int etiq;
couleur coul;
struct arn_s* gauche;
struct arn_s* droit;
};
typedef struct arn_s* arn;
Fonctions
arn construit_arn(int e, couleur c, arn g, arn d) {
arn racine = malloc(sizeof(struct arn_s));
assert(racine != NULL);
racine->etiq = e;
racine->coul = c;
racine->gauche = g;
racine->droit = d;
return racine;
}
void detruit_arn(arn a) {
if (a != NULL) {
detruit_arn(a->gauche);
detruit_arn(a->droit);
free(a);
}
}
// les rotations
arn rotation_droite(arn x) {
arn y = x->gauche;
x->gauche = y->droit;
y->droit = x;
return y;
}
arn rotation_gauche(arn y) {
arn x = y->droit;
y->droit = x->gauche;
x->gauche = y;
return x;
}
// insertion
arn corrige_rouge(arn a) {
arn y = a;
// je traite les 4 cas problématiques dans le même ordre
// que celui du schéma présenté dans le TP
if (a != NULL && a->coul == noir) {
if (a->gauche != NULL && a->gauche->coul == rouge) {
if (a->gauche->gauche != NULL && a->gauche->gauche->coul == rouge) {
y = rotation_droite(a);
}
else if (a->gauche->droit != NULL && a->gauche->droit->coul == rouge) {
y = rotation_gauche(a->gauche);
a->gauche = y;
y = rotation_droite(a);
}
}
else if (a->droit != NULL && a->droit->coul == rouge) {
if (a->droit->gauche != NULL && a->droit->gauche->coul == rouge) {
y = rotation_droite(a->droit);
a->droit = y;
y = rotation_gauche(a);
}
else if (a->droit->droit != NULL && a->droit->droit->coul == rouge) {
y = rotation_gauche(a);
}
}
}
// une fois les rotations faites il suffit de mettre les bonnes couleurs
if (y != a) {
y->coul = rouge;
y->gauche->coul = noir;
y->droit->coul = noir;
}
return y;
}
void insere_en_corrigeant_rouge(arn* a, int e) {
// insère une feuille rouge
if (*a == NULL) {
*a = construit_arn(e, rouge, NULL, NULL);
}
// on insère à droite et on corrige les couleurs
else if ((*a)->etiq < e) {
insere_en_corrigeant_rouge(&(*a)->droit, e);
*a = corrige_rouge(*a);
}
// idem à gauche
else if ((*a)->etiq > e) {
insere_en_corrigeant_rouge(&(*a)->gauche, e);
*a = corrige_rouge(*a);
}
}
void insertion_arn(arn* a, int e) {
// on insère puis on remet la racine en noir
insere_en_corrigeant_rouge(a, e);
(*a)->coul = noir;
Tas
Structure spécifique
typedef int contenu_file_prio;
struct file_prio_s {
int* priorites; // tableau des priorité
contenu_file_prio* elements; // tableau des éléments
int nb_elements; // nombre d'éléments dans la file de priorité
int capacite_maximale; // taille de la zone allouée pour 'priorites' et 'elements'
};
typedef struct file_prio_s file_de_priorite;
Fonctions
const int CAPACITE_MAX_INITIALE = 2;
void echange(int* t, int i, int j) {
int tmp = t[i];
t[i] = t[j];
t[j] = tmp;
}
// fonction pour la réallocation de zones plus grandes / plus petites
void realloue(file_de_priorite* fp, int nouvelle_capacite) {
// allocation des nouvelles zones
fp->capacite_maximale = nouvelle_capacite;
int* nouvelle_zone_priorites = malloc(fp->capacite_maximale * sizeof(int));
contenu_file_prio* nouvelle_zone_elements = malloc(fp->capacite_maximale * sizeof(contenu_file_prio));
// recopie du contenu actuel de la file de priorité
for (int i = 0; i < fp->nb_elements; i += 1) {
nouvelle_zone_priorites[i] = fp->priorites[i];
nouvelle_zone_elements[i] = fp->elements[i];
}
// libération des anciennes zones
free(fp->elements);
free(fp->priorites);
fp->elements = nouvelle_zone_elements;
fp->priorites = nouvelle_zone_priorites;
}
void percolation_vers_le_haut(file_de_priorite* fp, int indice_mal_place) {
int pere = (indice_mal_place - 1) / 2;
if (indice_mal_place != 0 && fp->priorites[indice_mal_place] < fp->priorites[pere]) {
echange(fp->priorites, indice_mal_place, pere);
echange(fp->elements, indice_mal_place, pere);
percolation_vers_le_haut(fp, pere);
}
}
void percolation_vers_le_bas(file_de_priorite* fp, int indice_mal_place) {
int fils_gauche = 2*indice_mal_place + 1;
int fils_droit = 2*indice_mal_place + 2;
int indice_avec_lequel_echanger = indice_mal_place;
if (fils_gauche < fp->nb_elements && fp->priorites[indice_mal_place] > fp->priorites[fils_gauche]) {
indice_avec_lequel_echanger = fils_gauche;
}
if (fils_droit < fp->nb_elements && fp->priorites[indice_avec_lequel_echanger] > fp->priorites[fils_droit]) {
indice_avec_lequel_echanger = fils_droit;
}
if (indice_avec_lequel_echanger != indice_mal_place) {
echange(fp->priorites, indice_avec_lequel_echanger, indice_mal_place);
echange(fp->elements, indice_avec_lequel_echanger, indice_mal_place);
percolation_vers_le_bas(fp, indice_avec_lequel_echanger);
}
}
file_de_priorite* fp_creer(void) {
file_de_priorite* fp = malloc(sizeof(file_de_priorite));
fp->capacite_maximale = CAPACITE_MAX_INITIALE;
fp->nb_elements = 0;
fp->priorites = malloc(fp->capacite_maximale * sizeof(int));
fp->elements = malloc(fp->capacite_maximale * sizeof(contenu_file_prio));
return fp;
}
bool fp_est_vide(file_de_priorite* fp) {
return fp->nb_elements == 0;
}
void fp_enfiler(file_de_priorite* fp, contenu_file_prio element, int priorite) {
// si on doit enfiler un élément et que la zone allouée est pleine,
// on réalloue une zone deux fois plus grande
if (fp->nb_elements == fp->capacite_maximale) {
realloue(fp, 2 * fp->capacite_maximale);
}
// on insère tout en bas à droite puis percolation vers le haut
fp->elements[fp->nb_elements] = element;
fp->priorites[fp->nb_elements] = priorite;
fp->nb_elements += 1;
percolation_vers_le_haut(fp, fp->nb_elements-1);
}
contenu_file_prio fp_defiler(file_de_priorite* fp) {
assert(fp->nb_elements != 0);
// l'élément de priorité minimale se trouve à la racine
contenu_file_prio a_renvoyer = fp->elements[0];
// on échange la racine avec l'élément tout en bas à droite puis percolation vers le bas
fp->nb_elements -= 1;
if (fp->nb_elements != 0) {
echange(fp->elements, 0, fp->nb_elements);
echange(fp->priorites, 0, fp->nb_elements);
percolation_vers_le_bas(fp, 0);
}
// si on défile un élément et que moins d'un quart de la zone est utilisée,
// on réalloue une zone deux fois plus petite
if (fp->nb_elements < fp->capacite_maximale / 4) {
realloue(fp, fp->capacite_maximale / 2);
}
return a_renvoyer;
}
void fp_detruire(file_de_priorite* fp) {
free(fp->elements);
free(fp->priorites);
free(fp);
}
Tas
Structure spécifique
struct tas_s {
int* elements; // tableau représentant le tas
int nb_elements; // nombre actuel de nœuds dans le tas
int capacite_maximale; // nombre maximal de nœuds que peut contenir le tas
bool est_tas_min; // true s'il s'agit d'un tas-min, false s'il s'agit d'un tas-max
};
typedef struct tas_s tas;
Fonctions
int fils_gauche(int i, int taille_tas) {
assert(0 <= i && i < taille_tas);
if (2*i + 1 >= taille_tas) {
return -1;
}
return 2*i + 1;
}
int fils_droit(int i, int taille_tas) {
assert(0 <= i && i < taille_tas);
if (2*i + 2 >= taille_tas) {
return -1;
}
return 2*i + 2;
}
int pere(int i, int taille_tas) {
assert(0 <= i && i < taille_tas);
if (i == 0) {
return -1;
}
return (i - 1) / 2;
}
tas* tas_vide(int capacite, bool type_de_tas) {
tas* t = malloc(sizeof(tas));
assert(t != NULL);
t->elements = malloc(capacite * sizeof(int));
assert(t->elements != NULL);
t->nb_elements = 0;
t->capacite_maximale = capacite;
t->est_tas_min = type_de_tas;
return t;
}
void tas_detruit(tas* t) {
free(t->elements);
free(t);
}
void tas_initialise(tas* t, int n, int tableau[n]) {
assert(t->nb_elements == 0 && n <= t->capacite_maximale);
for (int i = 0; i < n; i += 1) {
t->elements[i] = tableau[i];
}
t->nb_elements = n;
}
void percolation_vers_le_haut_tas(int* t, int taille_t, int indice_noeud_mal_place, bool tas_min) {
int p = pere(indice_noeud_mal_place, taille_t);
if (p != -1 && ((tas_min && t[indice_noeud_mal_place] < t[p])
||
(!tas_min && t[indice_noeud_mal_place] > t[p]))) {
echange(t, indice_noeud_mal_place, p);
percolation_vers_le_haut_tas(t, taille_t, p, tas_min);
}
}
void percolation_vers_le_bas_tas(int* t, int taille_t, int indice_noeud_mal_place, bool tas_min) {
int fg = fils_gauche(indice_noeud_mal_place, taille_t);
int fd = fils_droit(indice_noeud_mal_place, taille_t);
int indice_avec_lequel_echanger = indice_noeud_mal_place;
// on regarde si l'échange doit se faire avec le fils gauche du nœud mal placé
if (fg != -1 && ((tas_min && t[indice_noeud_mal_place] > t[fg])
||
(!tas_min && t[indice_noeud_mal_place] < t[fg]))) {
indice_avec_lequel_echanger = fg;
}
// ou bien avec son fils droit
if (fd != -1 && ((tas_min && t[indice_avec_lequel_echanger] > t[fd])
||
(!tas_min && t[indice_avec_lequel_echanger] < t[fd]))) {
indice_avec_lequel_echanger = fd;
}
// si un échange est nécessaire, on le fait et on continue la percolation vers le bas depuis ce nœud
if (indice_noeud_mal_place != indice_avec_lequel_echanger) {
echange(t, indice_noeud_mal_place, indice_avec_lequel_echanger);
percolation_vers_le_bas_tas(t, taille_t, indice_avec_lequel_echanger, tas_min);
}
}
int tas_lecture_minimum_ou_maximum(tas t) {
assert (t.nb_elements > 0);
return t.elements[0];
}
void tas_insertion(tas* t, int etiquette_a_inserer) {
assert(t->nb_elements < t->capacite_maximale);
t->elements[t->nb_elements] = etiquette_a_inserer;
t->nb_elements += 1;
percolation_vers_le_haut_tas(t->elements, t->nb_elements, t->nb_elements - 1, t->est_tas_min);
}
int tas_extraction_racine(tas* t) {
assert(t->nb_elements > 0);
t->nb_elements -= 1;
if (t->nb_elements != 0) {
echange(t->elements, 0, t->nb_elements);
percolation_vers_le_bas_tas(t->elements, t->nb_elements, 0, t->est_tas_min);
}
return t->elements[t->nb_elements];
}