algorithme et programmation 2

Un algorithme est une méthode de résolution de problème énoncée sous la forme d'une série d'opérations à effectuer. La mise en œuvre de l'algorithme consiste en l'écriture de ces opérations dans un langage de programmation et constitue alors la brique de base d'un programme informatique.

Cours de algorithme et programmation 2 

Le type TableHC

Si on veut pouvoir effectuer des destructions, il faut distinguer 3 états : libre, occupé, ou détruit. Un élément est déclaré ne pas appartenir à la table si l’entrée proposée par la résolution est libre. En cas de retrait d’un élément, il ne faut pas rompre cette liste implicite des éléments occupés. L’entrée est marquée détruite (et non libre), ce qui permet une insertion, mais n’arrête pas la recherche d’un élément. Les cas de retraits ne sont pas envisagés dans la suite des algorithmes, mais laissés en exercice.

remarques 

L’opérateur + commence par créer un emplacement temporaire pouvant recevoir un nombre comportant un chiffre de plus que le plus grand de ses deux opérandes (on ne sait pas encore combien de chiffres comportera exactement le résultat). On y calcule la somme suivant un algorithme calqué sur le processus manuel d’addition. Puis on crée un objet de type big_int en utilisant un constructeur particulier : big_int (int, int). 

En fait, nous avons besoin d’un constructeur créant un big_int comportant un nombre de chiffres donné, ce dont nous ne disposons pas dans les constructeurs publics. De plus, nous ne pouvons pas utiliser un constructeur de la forme big_int (int) car, alors, les additions mixtes faisant intervenir des entiers chercheraient à l’employer pour effectuer une conversion ! C’est pourquoi nous avons prévu un constructeur à deux arguments, le second étant fictif ; de plus, nous l’avons rendu privé, car il n’a nullement besoin d’être accessible à un utilisateur de la classe

La fonction : static int resolution (TableHC* table, int h) ; cherche une entrée libre dans la table pour un élément de hash-code h. Cette fonction fournit la place (entier) attribuée à l’élément en collision ou –1 si la table est saturée. Si la résolution est pseudo-aléatoire, il faut réinitialiser le générateur de nombres, de façon à recommencer au début de la séquence de nombres. L’algorithme est simple : tant qu’on n’a pas effectué nMax-1 tentatives et tant qu’on n’a pas trouvé une entrée libre (ou détruite), on appelle la fonction de résolution (passée en paramètre lors de l’appel de creerTableHC()) pour connaître la prochaine entrée à tester. Cet algorithme est le même quelles que soient les fonctions de hachage et de résolution.

Un algorithme est une méthode de résolution de problème énoncée sous la forme d'une série d'opérations à effectuer. La mise en œuvre de l'algorithme consiste en l'écriture de ces opérations dans un langage de programmation et constitue alors la brique de base d'un programme informatique.

Cours de algorithme et programmation 2 

Le type TableHC

Si on veut pouvoir effectuer des destructions, il faut distinguer 3 états : libre, occupé, ou détruit. Un élément est déclaré ne pas appartenir à la table si l’entrée proposée par la résolution est libre. En cas de retrait d’un élément, il ne faut pas rompre cette liste implicite des éléments occupés. L’entrée est marquée détruite (et non libre), ce qui permet une insertion, mais n’arrête pas la recherche d’un élément. Les cas de retraits ne sont pas envisagés dans la suite des algorithmes, mais laissés en exercice.

remarques 

L’opérateur + commence par créer un emplacement temporaire pouvant recevoir un nombre comportant un chiffre de plus que le plus grand de ses deux opérandes (on ne sait pas encore combien de chiffres comportera exactement le résultat). On y calcule la somme suivant un algorithme calqué sur le processus manuel d’addition. Puis on crée un objet de type big_int en utilisant un constructeur particulier : big_int (int, int). 

En fait, nous avons besoin d’un constructeur créant un big_int comportant un nombre de chiffres donné, ce dont nous ne disposons pas dans les constructeurs publics. De plus, nous ne pouvons pas utiliser un constructeur de la forme big_int (int) car, alors, les additions mixtes faisant intervenir des entiers chercheraient à l’employer pour effectuer une conversion ! C’est pourquoi nous avons prévu un constructeur à deux arguments, le second étant fictif ; de plus, nous l’avons rendu privé, car il n’a nullement besoin d’être accessible à un utilisateur de la classe

La fonction : static int resolution (TableHC* table, int h) ; cherche une entrée libre dans la table pour un élément de hash-code h. Cette fonction fournit la place (entier) attribuée à l’élément en collision ou –1 si la table est saturée. Si la résolution est pseudo-aléatoire, il faut réinitialiser le générateur de nombres, de façon à recommencer au début de la séquence de nombres. L’algorithme est simple : tant qu’on n’a pas effectué nMax-1 tentatives et tant qu’on n’a pas trouvé une entrée libre (ou détruite), on appelle la fonction de résolution (passée en paramètre lors de l’appel de creerTableHC()) pour connaître la prochaine entrée à tester. Cet algorithme est le même quelles que soient les fonctions de hachage et de résolution.