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".
|