IN101 - cours 10 - 20 novembre 2009

IN 101 - Cours 1025 novembre 2011pr´esent´e parMatthieu FiniaszUn probleme concretLa recherche en tableLe probl`eme : retrouver une information `a partir d’une clef qui luiest associ´ee.Par exemple :dictionnaire : mot_ d´efinition,annuaire : nom_ adresse, t´el´ephone,biblioth`eque : num´ero_ ouvrage.Il faut les fonctionnalit´es suivantes :recherche,insertion,suppression.Quelle structure de donn´ees utiliser?_1Le probleme de larecherche en tableNotationsLes clefs forment un ensemble de m ´el´ements index´es de 0 `a m−110 47pour des mots de 10 lettres : m = 26 ≈ 2 .On veut g´erer n paires de la forme (clef,information)jamais deux clefs identiques,n≤ m mais en g´en´eral n≪ m.Nous allons voir plusieurs solutions. On s’int´eresse `a :la complexit´e spatiale du stockage,la´e temporelle de chaque op´erationinsertion, recherche, suppression._2Table a adressage direct0 1 2 3 4 5 6 m-1info info info2 3 6On utilise un tableau tab de taille mcomplexit´e spatiale en(m).en fait m×taille info ou m+n×taille info avec des pointeurs.Recherche return tab[clef];_complexit´e(1).Insertion tab[clef] = info;_complexit´e(1).Suppression tab[clef] = NULL;_complexit´e(1).3Table a adressage direct0 1 2 3 4 5 6 m-1info info info2 3 6On utilise un tableau tab de taille mcomplexit´e spatiale en(m).en fait m×taille info ou m+n×taille info avec des pointeurs.47mots de 10 lettres : m = 2mˆeme avec un seul bit d’information 16 To de stockage.. ...