cours 511 - partie 2

DéfinitionAlgorithmes complexes Une table est une structure de Partie 2Clé Infosdonnées telle que l’accès à un élément est déterminé à partir de 0sa clé. Une clé permet d’identifier un élément de manière unique : la clé 1est dite discriminante. L’allocation d’un table est 2 Dupond …Les tablesgénéralement contiguë. La partie infos contient les 3informations spécifiques àl’application.N-1Algorithmes complexes : Les 1 Algorithmes complexes : Les 2TablesTablesIndex Rappel sur les clés Sorte Clé Si une structure données (Infos) contient plusieurs éléments Utilise Booléendiscriminants, il est possible alors de créer une table servant d’index et utilisant comme clé l’élément discriminant choisi.Opérations : Un index permet d’accélérer les traitements de recherche.≤ : Clé ⊗ Clé Booléen ; Exemple := : Clé ⊗ Clé Booléen ; Index sur Nom Tableau de donnéesAvec :Nom Pos Pos Nom Prénom Adresse Numérox , y , z : CléHenri 0Henri Arthur Rue là 04789232100 Axiomes :Dupond 25…x ≤ y= vraiDupond Michel Rue Ici 0630302456( x ≤ y ) ∧ ( y ≤ x ) ⇒ x = y25( x ≤ y ) ∧ ( y ≤ z ) ⇒ x ≤ zIndex sur NuméroOn appelle clé l’application, qui à chaque éléments associe sa clé :Numéro PosClé: Elément Clé0630302456 00630302456 25Algorithmes complexes : Les 3 Algorithmes complexes : Les 4Tables Tables1Spécification du type Spécification du type Sorte Table AxiomesUtilise Elément, Clé, Entier, Booléen Taille(Créer-Table(i)) = 0 ...