From 47e2da7929c9fad9a97c2a6ceea76f00e4a25321 Mon Sep 17 00:00:00 2001
From: Pixel <>
Date: Tue, 17 Apr 2001 22:29:10 +0000
Subject: Pouet (doc)

---
 doc/structures.tex | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 64 insertions(+)
 create mode 100644 doc/structures.tex

(limited to 'doc/structures.tex')

diff --git a/doc/structures.tex b/doc/structures.tex
new file mode 100644
index 0000000..c6c7013
--- /dev/null
+++ b/doc/structures.tex
@@ -0,0 +1,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.
-- 
cgit v1.2.3

