summaryrefslogtreecommitdiff
path: root/doc/structures.tex
blob: c6c70136d235da5b70ff4c9386e71568b40b1180 (plain)
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.