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
58
59
60
61
62
63
64
|
\chapter{Structures de données}
\section{Files de priorités}
Pour l'implémentation des files de priorités, nous avons remarqué que, comme pour des arbres ou des listes
chaînées, la structure est (dans le cas des tas Binomiaux et des tas de Fibonacci) récursive. Nous avons donc
choisi comme structure de données de base C++ une classe récursive. Qu'importe si les informations de récursivités
ne sont pas utilisés dans les autres dérivés de file de priorité. La classe implémentée est la suivante:
\begin{lstlisting}{}
class PriorityList {
protected:
class GeneralException;
int type;
Key_t Key;
Datas_t Datas;
PriorityList(Key_t IKey, Datas_t const &IDatas);
public:
PriorityList(void);
virtual ~ PriorityList(void);
virtual Key_t ReadKey(Cell C);
virtual Datas_t ReadDatas(Cell C);
virtual int n(void);
virtual int rn(void) = 0;
virtual void Dump(ostream & os) = 0;
virtual bool IsEmpty(void) = 0;
virtual Cell Min(void) = 0;
virtual Cell Insert(Key_t IKey, Datas_t const &IDatas) = 0;
virtual Key_t Extract_Min(Datas_t & Datas) = 0;
virtual PriorityList *Union(PriorityList * P) = 0;
virtual bool Lower_Key(Cell x, Key_t NKey) = 0;
virtual Key_t Delete(Datas_t & Datas, Cell x) = 0;
PriorityList *GenericUnion(PriorityList * P);
int GetType(void);
};
\end{lstlisting}
Les types Key\_t, Datas\_t et Cell sont définis dans un include, et n'influencent en rien le comportement des algorithmes.
Il suffit que Key\_t soit un type "comparable" (nous avons mis int), et que Datas\_t et Cell soient capables de véhiculer
des informations. Pour ces deux derniers types, nous avons mis void *. A partir de cette classe de base, nous allons
dériver toutes les classes suivantes pour permettre l'implémentation des files de priorités.
\section{Huffman}
Pour l'implémentation de l'algorithme de Huffman, nous avons eu besoin d'écrire une petite structure d'arbre toute simple:
\begin{lstlisting}{}
class HTree {
private:
HTree * left, *right;
int freq;
char *objet;
public:
HTree(int n_freq, char *n_objet);
HTree(HTree * n_left, HTree * n_right);
~HTree();
ostream & Trace(ostream & os, int d = 0);
int ReadFreq(void);
char *ReadObj(void);
};
\end{lstlisting}
Notez au passage que la sturcture de données possède une fonction "trace" qui nous sert à générer visuellement le résultat de la compression.
|
