[email protected]

C o u r s   d e   s t r u c t u r e s   d e  d o n n é e s

 

Pr.  Z E G O U R   DJAMEL EDDINE

 

E  S  I : École Supérieure d'Informatique

 

 

DOCUMENTATION

 

LOGICIEL PÉDAGOGIQUE

  • Khawarizm II (Niveau 2, Version Windows )
     

  • Khawarizm II+         Avec traduction automatique vers Pascal et C      (Niveau 2, Version Windows )
     

COMPLÉMENT

 

AUTRES

PRE-REQUIS

AUTRES LIENS 

Références bibliographiques 

 


PARTIE 1 : STRUCTURES DE DONNÉES

 

Les listes linéaires chaînées

Notion d'allocations statique et dynamique 
Définition d'une liste linéaire chaînée
Modèle sur les listes linéaires chaînées
Exemple d'introduction
Algorithmes sur les listes
Listes linéaires chaînées particulières
Implémentation des listes linéaires chaînées avec la représentation contiguë
Les listes en Pascal

Les files d'attente

Définition, principe, domaine d'application
Modèle
Implémentation 

Les piles

Définition, principe, domaine d'application
Modèle
Implémentation 

Récursivité

Exemples d'introduction 
Conception d'algorithmes récursifs
Sémantique de la récursivité
Passage d'algorithmes récursifs en algorithme itératifs
Récursivité en pascal

Les arbres

Définitions
Terminologie
Les arbres binaires
Modèle sur les arbres binaires
Parcours des arbres binaires
Arbres de recherche binaire
Application des arbres binaires
Implémentation des arbres binaires

Arbres AVL
Les arbres m-aires

Les arbres de recherche m-aires

Arbres B, Arbres 2-3 ,Arbres 2-3-4

Arbres Red-Black

Implémentation des arbres de recherche m-aires

 

Les graphes

Graphes orientés et non orientés
Modèle sur les graphes
Parcours des graphes : DFS & BFS
Quelques applications sur les graphes
Implémentation

Hachage

Introduction, définitions 
Fonctions de hachage
Méthodes de résolution des collisions
Comparaison entre les différentes méthodes
Étude de la distribution des données

Hachage dynamique

 

PARTIE 2 : STRUCTURES DE FICHIERS


Une introduction aux structures de fichiers

Raisons de l'utilisation de l'espace secondaire 
Problèmes avec le stockage externe 
Différence entre la RAM et la mémoire secondaire
Fichier 
Bloc d'en-tête 
Fichiers statique et dynamique 
Méthode d'accès 

Organisation du fichier 
Adressage 
Critère de mesure d'une méthode d'accès 
Dans les langages de programmation 
Algorithmes 
Objectifs du cours

Structures simples de fichiers

Fichier vu comme un tableau 
Fichier vu comme une liste linéaire chaînée
Remarques 
Récapitulatif 
Utilisation 
Exemple : recherche dichotomique 

Les méthodes d'index

Des structures simples aux méthodes d'index 
Index à un niveau 
Index à 2 niveaux 
Opérations de base 
Remarques
Avantages des méthodes d'index

Indexation pour l'accès multi-clés

Introduction
Organisation d'un index secondaire 
Exemple de combinaison de clés secondaires
Remarque

Les méthodes d'arbres

Des méthodes d'index aux méthodes d'arbres

Arbres de recherche m-aire

Les B-arbres

Variantes des B-arbres

Les méthodes de hachage

Introduction 
Chaînage avec des listes séparées 
Adressage ouvert
Avantages et inconvénients