Généralités sur les SD

  • Utilités d'une structure de données
    Pour bien créer les algorithmes de résolution de problèmes, il n'est pas suffisant de bien manier les structures de contrôle( séquentielle, itérative, alternative), il faut en plus bien choisir la structure de données.
    Pour définir une structure de données, il faut préciser :

    • leur spécification fonctionnelle ( les opérateurs et leurs propriétés)
    • leur description logique
    • leur représentation ( ou implémentation) physique en mémoire
    1. Types de données
  • Turbo-Pascal
  • Caml
  • Prédéfinis scalaires
  • Byte
  • Prédéfinis scalaires
  • Shortint
  • Integer
  • Int -230;;230 - 1
  • Word
  • Longint
  • Boolean
  • bool
  • Char
  • Prédéfinis réels
  • Prédéfinis réels
  • Real
  • float
  • Single
  • Double
  • Extended
  • Comp
  • Prédéfinis structurés
  • Prédéfinis structurés
  • String
  • string
  • n-uplets
  • Array of
  • Tableau ou vecteur
  • Record
  • (enregistrement)
  • Enregistrement avec éventuellement des champs mutables { }
  • Set  of
  • liste
  • Prédéfinis fichiers
  • type fonctionnel
  • File of
  • (fichier d'articles)
  • type Produit cartésien
  • Text
  • File
  • (fichiers sans type)
  • Prédéfinis pointeurs
  • Prédéfinis  spécial          le type rien ()
  • Unit
  • ^
    variable dynamique typée)
  • Pointer
  • (variable dynamique sans type)
  • Définis par l'utilisateur
  • Définis par l'utilisateur
  • énumération
  • type construit
  • intervalle
  • type somme générique
 

 
  • Structures de données
    • non linéaires :
      On relie un élément à plusieurs suivants et non plus à un seul

      • les graphes
      • les arbres
    • linéaires : 
       il existe entre les éléments une notion de "séquence" : 1er, 2ème, …, dernier.
    • les tableaux :
      On peut alors regrouper un nombre fixe de données de même type.
      Un vecteur est construit en une seule fois.En Turbo-Pascal
      Program gestiontableau ;
      uses winCrt ;
      const Nmax   = 5 ;
      type tableau = array[1..Nmax] of integer ;
      var             v : tableau ;
      begin
      or i := 1 to Nmax do begin
      write(‘v[‘,i,’] = ’) ;
      readln(v[i]) ;
      end ;En Caml 
      let n = 5 and v =[|0;0;0;0;0|] in
      begin
      for i = 0 to ( n – 1 )
      do
      print_string "entrez v[" ;
      print_int i ;
      print_string "]= ";
      v.(i) <- read_int() ;
      done ;
      v ;
      end ;;

      L’accès à un élément de vecteur se fait en un temps constant et indépendant du rang.
      L’accès aux éléments se fait par le rang.

      En Turbo Pascal

      v[3] := 8 ;
      for i := 1 to Nmax do  writeln(‘v[‘,i,’] = ’,v[i]) ;

      En Caml
      v.(0) ; ;
      v.(1) <- 4 ; ;
      v ; ;

  • les listes chaînées
    On peut alors regrouper un nombre quelconque et variable de données de même type.
    C’est une structure de donnée efficace  en informatique.
    On distingue

    • la liste chaînée classique
    • les listes chaînées particulières :
      • les piles (LIFO : Last    In,    First  Out)
      • les files (FIFO : First  In,     First  Out)