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
|
\chapter{Algorithmes}
\section{Tas Binomial}
\paragraph{}
L'implémentation de certaines parties des algorithmes sur les tas binomiaux ont nécessité quelques changements, notemment
en ce qui concerne la gestion des cellules. En effet, il se pose un grave problème lors de l'implémentation de "DIMINUER-CLÉ",
car nous effectuons des changements dans les cellules. Et si l'appelant a gardé des pointeurs sur les cellules elles-mêmes, alors
leur contenu ne correspondra plus à la valeur d'insertion. Il faudrait pouvoir modifier aussi les pointeurs sur les cellules
qui ont été renvoyés à l'appelant, ce qui est impossible, vu que ces variables ne font pas partie de l'espace de données de notre
structure.
\paragraph{}
Pour résoudre ce problème, nous avons une table de pointeurs "tampon" qui vont stoquer les vrais pointeurs sur
les cellules du tas binomial. Comme ces pointeurs sont conservés dans la structure
de données, nous pouvons les modifier à loisir, lors d'une opération diminuer clef. Ainsi les pointeurs renvoyés à l'appelant
ne sont pas les pointeurs sur le tas directement, mais des pointeurs sur cette structure tampon, qui joue le role d'intermédiaire.
\paragraph{}
Cette structure est une liste doublement chaînée non triée (afin de pouvoir libérer la mémoire correctement
à la fin du programme), et vu que les deux seules opérations que nous effectuons dessus sont "INSERER" et "SUPPRIMER", nous ne
faisons que des opérations en $O(1)$ ce qui n'aura aucune influence sur le déroulement des algorithmes eux-mêmes.
\paragraph{}
L'implémentation de l'algorithme "FUSIONNER-TAS-BINOMIAUX" a été réalisé différemment de l'idée du cormen. En effet, le livre
suggérait de créer un troisième tas, et d'y placer les éléments de T1 et de T2 pour effacer T1 et T2 ensuite. Nous nous contentons
d'effectuer une fusion "sur place". C'est à dire nous vidons le tas T2 et nous insérons ses éléments à la bonne place dans le tas
T1. Ceci a pour but d'éviter la copie des cellules, pour la même raison que ci-dessus. Autant limiter les opérations et nous
contenter d'utiliser les blocs mémoires déjà alloués.
\paragraph{}
L'implémentation de l'algorithme "UNION" ne diffère que très légèrement de l'algorithme proposé, et nous obtenons un algorithme
légèrement plus simple. En effet, dans l'algorithme proposé, nous avons un cas particulier dans le cas où nos pointeurs se
trouvent en début de liste. Nous résolvons le problème directement car notre structure de données est récursive et le tas est
aussi une cellule de tas binomial. Ainsi, physiquement, nous ne commençons pas à la première, mais à la deuxième cellule du tas.
Le problème du cas particulier est donc réglé.
\section{Tas de Fibonacci}
\paragraph{}
Le tas de Fibonacci, quique d'allure complexe, n'a pas posé de problèmes d'implémentations particuliers. La seule particularité
fut d'implémenter certaines des phrases "en français dans le texte" telles que "parcourir la liste des pointeurs de base". Nous avons
aussi inversé en général l'ordre des choses lors de l'implémentation, ceci afin d'eviter de complexifier le code C++. En effet,
deux opérations consécutives peuvent influencer l'une sur l'autre, et mener à des situations de programmation délicates. Les
inverser peut présenter un aventage d'un point de vue conception, et n'influencer en rien le déroulement de l'algorithme. Le code
source des tas de Fibonacci est commenté de manière à pouvoir suivre les changements effectués lors de l'implémentation.
\paragraph{}
La seule restriction que nous avons posé fut sur l'algorithme "CONSOLIDER" pour lequel le tableau A possède une taille fixe.
En effet, nous ne pouvons évaluer à l'avance le nombre de case dont nous aurons besoin, sachant que certaines branches du
tas peuvent être dégénérées.
\section{Liste chaînée triée}
\paragraph{}
Cette implémentation n'a posé aucun problèmes particuliers, la structure étant extrèmement simple. La seule particularité qu'il
peut être amusant de souligner, est que l'algorithme "UNION" est en fait la partie "FUSION" de l'algorithme de tri fusion.
\section{Tas Binaire}
\paragraph{}
Comme pour le tas binomial, les cellules pouvant être échangées, nous ne pouvons renvoyer directement de pointeur sur le
tableau lui-même. De ce fait, nous avons utilisé exactement la même structure "tampon" que pour le tas binomial.
\paragraph{}
Le tableau dans lequel nous stoquons les valeurs n'est en aucun cas limité en revanche. Nous avons inclus un mécanisme qui
va redimentionner le tableau automatiquement en fonction des indices demandés, ce qui nous permet d'effectuer des tests
comme si la structure avait une dimension infinie.
\paragraph{}
Le reste de l'implémentation n'a posé aucun problème. Il est à noter en revanche qu'il a fallu inverser les conditions par rapport
à ce qui est décrit dans le livre. En effet, le tas binaire du livre nous donne une structure permettant d'effectuer "EXTRAIRE-MAX".
|
