Changes between Version 35 and Version 36 of CaoCourseTme2


Ignore:
Timestamp:
Feb 18, 2007, 7:54:01 AM (18 years ago)
Author:
franck
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • CaoCourseTme2

    v35 v36  
    1515 *  Ecrire un man sur l'outil.
    1616
    17 L'objectif de ce TME est double :
     17L'objectif de ce TME est triple :
    1818
    1919 1. Il doit d'une part vous permettre de complêtez l'auto-évaluation de vos connaissances des outils de developpement C que vous avez commencée dans le précédent TME, en vous posant des questions auxquelles vous devriez savoir répondre.  Si ce n'est pas le cas, vous '''devez''' trouver les réponses dans les documentations (man, web), ou auprès de vos camarades.
    2020 1. Il introduit de nouveaux outils permettant l'indentation automatique d'un programme source (outil ''indent''), la constructtion d'une bibliothèque C (outil ''ar''), ou l'écriture d'une documentation (outil ''man'').
     21 1. Il présente une structure de données, la table de hachage, très utile quelquesoit le type de programme.
    2122
    2223Il vous offre également un modèle de programme, avec Makefile et man pour vos futurs développements.
    … …  
    3839
    3940 *  {{{Makefile .......................}}} description du processus de construction de l'exécutable.
    40  *  {{{main.c, main.h .................}}} programme principal source et déclaration.
     41 *  {{{main.c, main.h .................}}} programme principal source et déclarations.
    4142 *  {{{count.c, count.h ...............}}} algorithme de parcours d'un fichier texte en vue de comptage.
    4243 *  {{{hte.c, hte.h ...................}}} fonction de création des tables de hachage et déclaration de toutes fonctions de gestion.
    … …  
    4647Une table de hachage est une structure de données permettant de stocker des
    4748ensembles contenant un nombre quelconque d'éléments, où chaque élément est un couple
    48 de la forme (clé, valeur).  Le plus souvent la clé est une chaîne de caractères.
    49 La valeur peut être un nombre ou une structure de données plus ou moins complexe.
     49de la forme (clé, data).  Le plus souvent la clé est une chaîne de caractères.
     50La donnée peut être un nombre ou une structure de données plus ou moins complexe, parfois la donnée est absente.
    5051Le principal objectif d'une table de hachage est d'accélérer la recherche d'un élément
    5152par sa clé.
    5253
    53 Pour représenter un ensemble de couple (clé, valeur) la méthode la plus simple
     54Pour représenter un ensemble de couple (clé, data) la méthode la plus simple
    5455consiste à les stocker dans une liste chainée.
    5556La recherche d'un élément se fait alors par un parcours de la liste, donc de
    56 l'ensemble des éléments, ce qui n'est pas très efficace si le nombre d'élément est grand.
     57l'ensemble des éléments, ce n'est pas très efficace si le nombre d'éléments est grand.
    5758
    5859Pour accélérer la recherche, on créé un tableau de listes chainées. Le nombre de
    … …  
    6162d'environ 1000 cases.     
    6263On définit ensuite une fonction, que l'on nomme '''fonction de hachage''',
    63 qui calcule un index à partir de la clé d'un élément.
     64qui calcule l'index d'une case à partir de la clé d'un élément.
    6465Un élément doit être rangé dans la liste chainée associée à la case du tableau
    6566définie par l'index calculé par la fonction de hachage.
    … …  
    7677qu'un tout petit nombre de listes contenant plus d'un élément.
    7778
    78 La propriété principale d'une table de hachage est que (si la taille de la table
    79 est du même ordre de grandeur que le nombre d'éléments), le temps de
    80 recherche est en O(1), c'est à dire indépendant du nombre d'éléments, (même pour
    81 un million d'éléments).
     79La propriété principale d'une table de hachage est que, si la taille de la table
     80est du même ordre de grandeur que le nombre d'éléments, alors le temps de
     81recherche est en O(1), c'est à dire indépendant du nombre d'éléments, même pour
     82un million d'éléments.
    8283 
    8384Les deux principales actions sont l'ajout d'un élément (add) et la recherche d'un élément (get).
    84   * La fonction get() prend en paramètre la clé de l'élément recherché. Si l'élément existe, elle rend la valeur associée.
    85   * La fonction add() prend en paramètre le couple (clé, valeur). Si l'élément existe, elle change sa valeur, sinon elle créé l'élément.
     85  * La fonction get() prend en paramètre la clé de l'élément recherché. Si l'élément existe, elle rend la donnée associée.
     86  * La fonction add() prend en paramètre le couple (clé, data). Si l'élément existe, elle change sa donnée, sinon elle créé l'élément.
    8687
    8788= Etape 1 : Questions sur le code fourni =