+ps:

+ make -f Makefile.doc ps

+

+clean:

+ make -f Makefile.doc clean

+

+distclean:

+ make -f Makefile.doc clean

+

+EXTRA_DIST = bib.tex conclusion.tex description.tex intro.tex manuel.tex outils.tex polynom.tex

+PROJET=polynom

+

+all: $(PROJET).dvi

+

+$(PROJET).dvi: bib.tex conclusion.tex description.tex intro.tex manuel.tex outils.tex polynom.tex source.tex

+ echo

+ echo pass1

+ echo

+ latex $(PROJET)

+ echo

+ echo pass2

+ echo

+ latex $(PROJET)

+

+source.tex:

+ echo '\section{Includes}' > source.tex

+ for i in `find ../include -name *.h` ; do echo "\subsection{`basename $$i`}"; echo "\lstinputlisting{$$i}"; done >> source.tex

+ echo '\section{Sources de la librairie}' >> source.tex

+ for i in `find ../lib -name *.c` ; do echo "\subsection{`basename $$i`}"; echo "\lstinputlisting{$$i}"; done >> source.tex

+ echo '\section{Sources du frontend}' >> source.tex

+ for i in `find ../src -name *.c` ; do echo "\subsection{`basename $$i`}"; echo "\lstinputlisting{$$i}"; done >> source.tex

+

+ps: $(PROJET).ps

+

+$(PROJET).ps: $(PROJET).dvi

+ dvips $(PROJET)

+

+clean:

+ rm -f *.dvi *.aux *.toc *.ps *.log source.tex

+

+\begin{thebibliography}{WWW99}

+% pour citer le Tanenbaum : \cite{Tanenbaum}

+% pour citer le Tanenbaum page 238 : \cite[page 238]{Tanenbaum}

+

+\bibitem[COR]{Cormen} T. Cormen, C. Leiserson, R. Rivest \textit{Introduction � l'algorithmique}, Dunod.

+

+\end{thebibliography}

+\chapter*{Conclusion}

+\addcontentsline{toc}{chapter}{Conclusion}

+\markboth{CONCLUSION}{CONCLUSION}

+

+Ce projet a �t� men� � terme, et l'ensemble des conditions du sujet ont �t� respect�es.

+L'effort de recherche men� sur la mani�re d'impl�menter les algorithmes en C++ a

+sans aucun doute �t� profitable pour notre connaissance personnelle. De plus, les algorithmes

+impl�ment�s sont "durables": ils peuvent nous resservir dans n'importe quel autre projet n�cessitant

+des structures de files de priorit�s, ce qui porte un int�r�t quant au d�veloppement de ce projet.

+\chapter{Description}

+\paragraph{}

+Nous allons d�crire dans cette premi�re partie tous ce que nous avons effectu� comme travail de r�flexion afin de

+programme ce projet. Il y a beaucoup de d�tails relatifs � l'impl�mentation dont nous ne parlerons pas, comme les structures

+sur les listes cha�n�es, ou l'initialisation du terminal pour g�rer le menu du programme de test. En revanche, nous appuyerons

+sur les d�tails d'impl�mentation purement algorithmiques qui nous ont pos� probl�me.

+\paragraph{}

+En ce qui concerne le langage de programmation, nous avons choisi le C++, car c'est le langage qui nous semblait le plus

+adapt� pour cr�er les structures de donn�es n�cessaire � la programmation de ce projet.

+\paragraph{}

+Nous avons impl�ment� les algorithmes de files de priorit�s suivants:

+\begin{itemize}

+\item Tas Binaire

+\item Tas Binomial

+\item Tas de Fibonacci

+\item Liste cha�n�e tri�e

+\end{itemize}

+\paragraph{}

+L'algorithme utilisant les files de priorit� impl�ment� est l'algorithme de compression de dictionnaire Huffman.

+\chapter*{Introduction}

+\addcontentsline{toc}{chapter}{Introduction}

+\markboth{INTRODUCTION}{INTRODUCTION}

+

+\paragraph{}

+Ce projet a pour but d'une part l'impl�mentation d'algorithmes de files de priorit�s et l'impl�mentation d'un algorithme

+utilisant ces files de priorit�s d'autre part.

+

+\paragraph{}

+Ce pr�sent document va tenter de d�crire en totalit� la progression de la

+mise en forme de ce projet. Nous vous souhaitons bonne lecture.

+\chapter{Manuel d'utilisation}

+\paragraph{}

+Ce projet g�n�re deux binaire. Le premier appel� testTas n'est qu'une petite application nous permettant d'utiliser l'API

+C++ g�n�r�e par notre classe de file de priorit�s. Voici un exemple d'ex�cution:

+\begin{verbatim}

+Priority list type: 0 - Binary Heap

+Choice: Please select an action

+a - Add a key into the priority list

+c - Change priority list type

+d - Delete a Key from the priority list

+e - Extract Min onto the priority list

+l - Lower Key onto a key of the priority list

+p - Print the current priority list on the screen

+r - Remove the whole priority list

+t - Test the priority list algorithms

+q - Quit

+\end{verbatim}

+

+A partir de cet instant, le programme nous propose un menu nous permettant d'effectuer plusieurs actions sur le tas. La

+fonction 'a' permet d'ajouter une clef dans le tas en cours. Comme il est impossible d'effectuer une recherche sur un tas

+pour y retrouver le pointeur d'un �l�ment, le programme nous propose de sauvegarder le pointeur r�sultat dans un tableau:

+

+\begin{verbatim}

+Choice: Please select a slot to save the cell

+0 - Empty slot

+1 - Empty slot

+2 - Empty slot

+3 - Empty slot

+4 - Empty slot

+5 - Empty slot

+6 - Empty slot

+7 - Empty slot

+8 - Empty slot

+9 - Empty slot

+n - Don't store

+c - Cancel

+\end{verbatim}

+

+Ce tableau apparaitra r�guli�rement dans toutes les fonctions du menu afin de choisir une cellule sur laquelle agir. Toutes

+les fonctions du menu parlent d'elles m�mes. La fonction 't' va lancer une batterie de tests sur les algorithmes de la

+file de priorit� s�lectionn�e.

+

+\paragraph{}

+Le deuxi�me binaire g�n�r� est 'Huffman'. Il sert � utiliser l'algorithme d'huffman impl�ment�. Voici sa ligne d'aide:

+\begin{verbatim}

+$ ./Huffman -h

+Huffman [{-f|-i} file] {type}

+Huffman -h

+This will encode the input file with the Huffman code

+using the priority list defined by type.

+Type is a number taken from this list:

+ 0 : Binary Heap (default)

+ 1 : Binomial Heap

+ 2 : Fibonacci Heap

+ 3 : Sorted chained list

+-f file means that you specify a dictionnary file which is

+ structured as described into the README file.

+-i file means that you specify a file to encode. It will

+ built a quiet dumb dictionnary.

+By default, a dictionnary will be built from stdin.

+-h prints this help and exit.

+\end{verbatim}

+

+La structure d'un dictionnaire est la suivante:

+\begin{verbatim}

+Mot1 : Fr�quence1

+Mot2 : Fr�quence2

+...

+\end{verbatim}

+

+Chaque mot est une cha�ne de caract�res servant � identifier la fr�quence associ�e. Voici un exemple complet de dictionnaire

+et d'utilisation du programme avec ce dictionnaire:

+

+\begin{verbatim}

+Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ cat dict.sample

+MOT1 : 2000

+MOT2 : 1234

+MOT3 : 15987

+MOT4 : 1203

+MOT5 : 192837

+MOT6 : 12987

+Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ ./Huffman -f dict.sample

+MOT3 (15987) = 00

+MOT1 (2000) = 0100

+MOT4 (1203) = 01010

+MOT2 (1234) = 01011

+MOT6 (12987) = 011

+MOT5 (192837) = 1

+Bitstream length : 283957 bits (= 35495 bytes)

+Real size input : 7239936 bits (= 904992 bytes)

+Size squeezed by : 96.0779 percents

+Dictionnary size : 336 bits (= 42 bytes)

+Total bitstream length : 284293 bits (= 35537 bytes)

+Real gain (4 bytes header) : 96.0728 percents

+\end{verbatim}

+

+Il est indiqu� que le programme est capable de g�n�rer un dictionnaire � partir d'un fichier. Il s'agit simplement de compter

+les caract�res provenant de l'entr�e et d'en g�n�rer un dictionnaire. Exemple:

+

+\begin{verbatim}

+$ cat dict.sample | Huffman

+\32 (12) = 00

+6 (1) = 01000

+4 (2) = 01001

+3 (4) = 0101

+0 (4) = 0110

+5 (2) = 01110

+7 (3) = 01111

+1 (6) = 1000

+M (6) = 1001

+: (6) = 1010

+\10 (6) = 1011

+O (6) = 1100

+8 (3) = 11010

+9 (3) = 11011

+2 (6) = 1110

+T (6) = 1111

+Bitstream length : 294 bits (= 37 bytes)

+Real size input : 608 bits (= 76 bytes)

+Size squeezed by : 51.6447 percents

+Dictionnary size : 512 bits (= 64 bytes)

+Total bitstream length : 806 bits (= 101 bytes)

+Real gain (4 bytes header) : -38.1579 percents

+\end{verbatim}

+\chapter{Outils utilis�s}

+\paragraph{}

+Pour d�velopper ce projet, nous avons choisi d'utiliser une s�rie d'outils GNU pour nous simplifier la t�che.

+Nous utilisons entre-autres, GNU autoconf \& automake pour g�rer notre arborescence de d�veloppement. Ainsi le

+pr�sent projet est d�coup� en ces r�pertoires:

+\begin{itemize}

+\item src contenant les sources des programmes ex�cutables. C'est notemment dans ce r�pertoire que seront stoqu�s

+les binaires des ex�cutables produit par la compilation du projet.

+\item lib contenant tous les sources purement algorithmiques, dont ne d�pend pas l'impl�mentation finale.

+\item include contenant tous les fichiers .h

+\item doc contenant le source \LaTeX\ de cette pr�sente documentation

+\item po contenant les fichiers d'internationalisation (traduction fran�aise)

+\item intl contenant le code source n�cessaire au support de l'internationalisation.

+\end{itemize}

+En dehors de autoconf \& automake, nous avons utilis� un serveur CVS (Concurrent Version System) qui nous a permis

+de travailler � plusieurs sur ce projet, sans avoir � nous soucier de rapatrier et de fusionner les codes sources

+de tout le monde.

+\paragraph{}

+Enfin, pour pouvoir compiler ce projet, il suffit de taper la commande './configure' au shell et de suivre les instructions.

+Les binaires seront plac�s dans le r�pertoire src. Pour g�n�rer cette documentation, il suffit d'aller dans le r�pertoire doc

+et de taper 'make ps'.

+%initialisations----------------------------------------------------------------

+\documentclass[french,11pt,a4paper,twoside,openright]{report}

+\usepackage[T1]{fontenc}

+\usepackage[latin1]{inputenc}

+\usepackage[francais]{babel}

+\usepackage{a4}

+\usepackage{ulem}

+\usepackage{multirow}

+\usepackage[dvips]{graphics}

+\usepackage{vmargin}

+\usepackage{fancyhdr}

+\usepackage{oldstyle}

+\usepackage{listings}

+\usepackage{verbatim}

+%fin des initialisations--------------------------------------------------------

+

+\pagestyle{fancyplain}

+\addtolength{\headwidth}{\marginparsep}

+\addtolength{\headwidth}{\marginparwidth}

+% titre de chapitre

+\renewcommand{\chaptermark}[1]{\markboth{#1} {}}

+% titre de section

+\renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}}

+

+\lhead[\fancyplain{}{\bfseries\textos{\thepage}}]{\fancyplain{}{\bfseries\rightmark}}

+\rhead[\fancyplain{}{\bfseries\leftmark}]{\fancyplain{}{\bfseries\textos{\thepage}}}

+\cfoot{\fancyplain{\textos{\thepage}}{}}

+

+\newcommand{\clearemptydoublepage}{\newpage{\pagestyle{empty}\cleardoublepage}}

+

+\def\addcontentsline#1#2#3{%

+ \addtocontents{#1}{\protect\contentsline{#2}{#3}{\textos{\thepage}}}}

+% \setmargrb{leftmargin}{topmargin}{rightmargin}{bottommargin}

+\setmargrb{1.5cm}{2cm}{1.5cm}{4cm}

+

+\begin{document}

+\renewcommand{\chaptername}{Section}

+\newcommand{\bracebits}{$\underbrace{\hspace{2cm}}$}

+

+%page de garde

+\title{Projet de C\\

+ Rapport \vspace{1.0cm}}

+\author{Vagner Alain, Noble Nicolas\vspace{2.0cm}}

+\date{\textit{derni�re r�vision: \today}}

+\maketitle

+\strut\thispagestyle{empty}

+\vfill

+\pagebreak

+\setcounter{page}{1}

+

+

+

+\tableofcontents

+

+\clearemptydoublepage

+

+\input{intro}

+\clearemptydoublepage

+\part{Analyse}

+\input{description}

+\clearemptydoublepage

+\part{Synth�se}

+\input{manuel}

+\clearemptydoublepage

+\input{outils}

+\clearemptydoublepage

+

+\chapter{Code source}

+\lstset{language=C++,basicstyle=\scriptsize,stringspaces=false}

+\input{source}

+

+\clearemptydoublepage

+\input{conclusion}

+\clearemptydoublepage

+\input{bib}

+\clearpage

+\strut\thispagestyle{plain}

+\begin{tiny}

+\begin{center}

+Cette documentation a �t� r�alis�e sous Linux Slackware 7.1 � l'aide de \LaTeX\ et cvs.

+\end{center}

+\end{tiny}

+\end{document}

+ sprintf(temp, "%s%s%c ", rat, mute, 178);

+ sprintf(temp, "%s%s%c ", rat, mute, 179);