Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours structures des donnees 3

Faculté des Sciences Département d ? Informatique Structures de Données SMI SMA S Pr Khalid HOUSNI https khalidhousni shost ca CObjectifs de cours Ce cours a pour objectifs Introduire la problématique de la structuration des données et les types abstraits Étudier les structures les plus classiques rencontrées en informatique pour organiser des données ?les piles arbres ? permettant la mise au point de programmes nécessitant la représentation de données complexes Le cours est structuré en parties Structures de données et types abstraits Structures linéaires listes ?les et piles Structures arborescentes arbres binaires arbres binaire de recherche tas hachage arbre équilibré Graphes terminologie représentation algorithmes de parcours Structures de données - SMA SMI S CIntroduction algorithme Qu'est-ce qu ? un algorithme Encha? nement d ? opérations destiné à résoudre un problème Spéci ?cation d ? un schéma de calcul sous forme d ? une suite ?nie d ? opérations élémentaires obéissant à un encha? nement déterminé L ? élaboration d ? un algorithme exige Description des données Description des méthodes Preuve de bon fonctionnement La complexité d ? un algorithme Temps de calcul Espace nécessaire Structures de données - SMA SMI S CDé ?nitions et Terminologie Type Un type de données ou simplement type dé ?nit le genre de contenu d'une donnée et les opérations pouvant être e ?ectuées sur la variable correspondante Le typage est l ? association à un objet ?? un ensemble de valeurs possibles ?? et un ensemble d ? opérations admissibles sur ces valeurs Structure de données Une structure de données est une manière particulière de stocker et d ? organiser des données dans un ordinateur de façon à pouvoir être utilisées e ?cacement On distingue ?? Structures de données du langage types primitifs Tableaux ? ?? Structures de données abstraites piles listes ? Structures de données - SMA SMI S C ? Dé ?nitions et Terminologie Structure de données abstraite Un type abstrait ou une structure de données abstraite est une spéci ?cation mathématique d'un ensemble de données et de l'ensemble des opérations qu'elles peuvent e ?ectuer On quali ?e d'abstrait ce type de données car il correspond à un cahier des charges qu ? une structure de données doit ensuite implémenter Structure dynamique Une structure dynamique est une structure dont la taille peut varier en fonction des besoins CCeeccoouurrsseexxigigeelalammaa? t? rtrisiseeddeessnnootitoionnssddeeppooinintteeuurrss eettddeeggeessttioionnddyynnaammiqiquueeddeelalamméémmooiriree Structures de données - SMA SMI S CClassi ?cation des structures de données On peut classer les structures de données en deux grandes catégories Les structures de données linéaires qui permettent de relier des données en séquence on peut numéroter les éléments ?? Tableaux ?? Piles ?? Simplement cha? nées ?? Listes ?? Files ?? Doublement cha? nées Tete suiv suiv suiv suiv Les structures de données non linéaires qui permettent de relier un élément à plusieurs autres éléments ?? Arbres ?? Graphes ??Binaire arbre binaire arbre binaire de recherche arbre équilibré tas ?? n- aire Structures de données - SMA SMI S CChapitre Rappel Tableaux Enregistrement structure Pointeurs Allocation dynamique Fonctions