Sommaire: Structures de données dynamiques langage c
1 Introduction
1.1 Pourquoi modéliser des données ?
1.2 Pourquoi des structures de données dynamiques ?
1.3 Quel langage ?
1.4 Quel programme (du cours☺) ?
2. Le langage C
2.1 Introduction
2.2 Bonjour
2.2.1 Avec le compilateur « gcc » de cygwin
2.2.2 Avec l’environnement « Visual C++ 2008 Express Edition »
2.3 Calcul de factorielle
2.4 Trier un tableau
2.5 Échanger deux variables
2.6 Concaténer deux chaines
2.7 Les nombres complexes
3. Structure de Donnée Abstraite
3.1 C’est quoi une SDA ?
3.2 Spécification et implémentation d’une SDA
3.3 La liste linéaire
3.3.1 Spécifications
3.3.1.1 Le Vecteur
3.3.1.2 Le Tirage
3.3.2 Implémentations
3.3.2.1 Le Vecteur
3.3.2.2 Le Tirage
3.3.3 Spécifications algébriques
4. Structures Classiques
4.1 Structures dérivées des listes
4.1.1 La pile
4.1.1.1 Spécification, implémentation et test en C
4.1.1.2 Les tours de Hanoï : « des tours » récursif ☺
4.1.2 La file
4.1.3 Autres structures ensemblistes linéaires
4.2 Arbres
4.2.1 Principe, forme générale
4.2.2 Arbres binaires
4.2.2.1 Spécification algébrique
4.2.2.2 Spécification et implémentation en C
4.2.2.3 Fonctions simples sur l’arbre
4.2.2.4 Parcours en profondeur
4.2.2.5 Parcours en largeur
4.3 Autres formes d’arbres
4.3.1 Arbres généralisés
4.3.2 Structures dérivées
4.4 Les graphes
4.4.1 Intérêt
4.4.2 Modélisation d’un graphe
Extrait du cours structures de données dynamiques langage c
1 Introduction
1.1 Pourquoi modéliser des données ?
Programme = algorithme + données
• Pour réaliser un « bon » programme (i.e. rapide et faible en mémoire), le choix de la structure de données est aussi important que celui de l’algorithme.
• La structure de données doit modéliser au mieux les informations à traiter pour en faciliter le traitement.
• L’utilisation de structures de données abstraites (S.D.A.) associées à des fonctions de manipulation facilite la conception d’un algorithme.
1.2 Pourquoi des structures de données dynamiques ?
• La spécification d’une S.D.A. permet de décrire des objets au niveau fonctionnel / logique tout en cachant leur implémentation.
• L’implémentation (ou réalisation physique) peut-être statique (taille fixée) ou dynamique (taille variable) pour optimiser certaines fonctions (par ex : insérer une donnée)
• Pour pouvoir faire varier la taille des données, le langage doit permettre la création / destruction de zone mémoire : les pointeurs.
1.3 Quel langage ?
• Le langage C est très utilisé, possède de nombreux environnements de développement (MS Visual C++) et est à la base de C++ et JAVA.
Il oblige le concepteur à maîtriser les allocations dynamiques de mémoire.
1.4 Quel programme (du cours☺) ?
• Nous allons d’abord nous familiariser avec le langage C
• Nous verrons dans le chapitre Structure de Donnée Abstraite comment spécifier puis réaliser une SDA grâce à un exemple simple : la liste
• Nous étudierons alors au chapitre Structures Classiques les structures suivantes :
o Linéaires (piles, files, listes ordonnées, chaînées, ensemble, dictionnaire)
o Hiérarchiques (arbres binaires, arbres de recherche, arbre n-aires)
o Graphes (notions générales)
Une bibliographie sur le WEB est en dernière page du polycopié ainsi que la table des figures.
………
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Structures de données dynamiques langage c (1.1 MO) (Cours PDF)
