Structures de données en langage C

• Cours IA-S3 sur les structures de données en langage C
• Année universitaire : 2024/2025
• Instructeur : Pr. Hamza Alami
• Le cours a lieu tous les mercredis de 8h30 à 10h30
• Contact : [email protected]

Objectif du Cours

• Connaître et mettre en œuvre différentes structures en C
• Liste chaînée
• Piles et files
• Arbres binaires
• Graphes
• Utiliser les structures pour répondre aux besoins du monde réel

Structure de Données

• Une structure de données est un ensemble d'éléments regroupés sous un nom unique.
• Sert à stocker et organiser les données dans un ordinateur.
• Permet une utilisation efficace des données.
• Les structures de données sont utilisées dans les bibliothèques d'analyse numérique, l'intelligence artificielle, les systèmes d'exploitation, la simulation et les systèmes de gestion de bases de données (SGBD).
• L'utilisation de structures de données permet aux programmeurs de gérer de grandes quantités de données de manière simple et efficace.
• Processus de sélection d'une structure de données pour résoudre un problème :
• Analyser le problème pour déterminer les opérations de base nécessaires (insertion, suppression, recherche, etc.).
• Quantifier les contraintes de ressources pour chaque opération.
• Sélectionner la structure de données qui répond le mieux aux exigences.
• Différents types de structures de données ont des caractéristiques différentes.
• Certains types autorisent l'ajout de nouveaux éléments uniquement au début, tandis que d'autres autorisent l'ajout à n'importe quelle position.
• Certaines structures permettent un accès séquentiel, tandis que d'autres permettent un accès aléatoire.
• Le choix approprié d'une structure de données a un impact majeur sur les performances du programme.

Types de Structures de Données

• Structure de données primitives :
• Entier
• Réel
• Character
• Structures de données non primitives :
• Linéaire :
• Tableau
• Liste chaînée
• Pile
• File
• Non linéaire :
• Arbre
• Graphe

Tableau

• Un tableau est une collection d'éléments similaires.
• Les éléments d'un tableau sont stockés de manière consécutive.
• Déclaration d'un tableau en C : type marks[0]
• Exemple : int marks[10]

Listes Chaînées

• Une liste chaînée est une structure de données flexible et dynamique.
• Les éléments (nœuds) forment une liste séquentielle.
• Chaque nœud contient deux éléments :
• La valeur du nœud
• Un pointeur vers le nœud suivant

Piles

• Une pile est une structure de données linéaire.
• L'insertion et la suppression d'éléments se font à une seule extrémité appelée le sommet de la pile (top).
• C'est une structure LIFO (Last In, First Out) : le dernier élément ajouté est le premier à être supprimé.

Filles

• Une file est une structure de données FIFO (First In, First Out).
• L'élément inséré en premier est également le premier à être retiré.
• Les éléments sont ajoutés à l'arrière (rear) et retirés de l'avant (front).
• Les les peuvent être implémentées à l'aide de tableaux ou de listes chaînées.

Des Arbres

• Un arbre est une structure de données non linéaire.
• Il est constitué d'une collection de nœuds organisés hiérarchiquement.
• Un nœud est désigné comme la racine.
• Les nœuds restants sont répartis en ensembles disjoints, formant chacun un sous-arbre de la racine.

Graphes

• Un graphe est une structure de données non linéaire constituée d'une collection de sommets et d'arêtes qui relient ces sommets.
• Un graphe généralise la structure d'arbre en autorisant tout type de relation complexe entre les nœuds, au lieu d'une relation parent-enfant stricte.

Opérations sur les Structures de Données

• Parcours
• Recherche
• Insertion
• Suppression
• Tri
• Fusion

Langage De Programmation C

• Le langage C a été développé au début des années 1970 par Dennis Ritchie aux Laboratoires Bell.
• Il a été initialement développé pour écrire des logiciels système, mais est maintenant utilisé dans une grande variété de logiciels.
• Il peut être facilement utilisé sur différents types d'ordinateurs.

Structure D'un Programme C

• Un programme C contient une ou plusieurs fonctions.
• Une fonction est un groupe d'instructions exécutant une tâche spécifique.
• L'exécution d'un programme C commence avec la fonction main().

Identificateur et Mots-Clés en C

• Un mot dans un programme C peut être un identificateur ou un mot-clé.
• Les identificateurs sont des noms donnés aux variables, tableaux et fonctions, et doivent respecter certaines règles.
• C a des mots réservés qui ne peuvent pas être utilisés comme identificateurs.

Types Primitifs en C

• Le langage C fournit quatre types de données de base :
• char : 1 octet, stocke des caractères (de -128 à 127).
• int : 2 octets, stocke des nombres entiers (-32768 à 32767).
• float : 4 octets, stocke des nombres à virgule flottante (3.4e-38 à 3.4e+38).
• double : 8 octets, stocke de grands nombres à virgule flottante (1.7e-308 à 1.7e+308).

Modificateurs de Type en C

• C fournit quatre modificateurs de type :
• short int : 2 octets, plage de -32768 à 32767.
• unsigned short int : 2 octets, plage de 0 à 65535.
• signed short int : 2 octets, plage de -32768 à 32767.
• long int : 4 octets, plage de -2147483648 à 2147483647.
• unsigned long int : 4 octets, plage de 0 à 4294967295.
• signed long int : 4 octets, plage de -2147483648 à 2147483647.
• float : 4 octets, plage de 3.4e-38 à 3.4e+38.
• double : 8 octets, plage de 1.7e-308 à 1.7e+308.
• long double : 10 octets, plage de 3.4E-4932 à 1.1E+4932.

Variables et Constantes

• Une variable est un nom significatif donné à un emplacement de stockage de données dans la mémoire de l'ordinateur.
• Les constantes sont des identificateurs dont les valeurs ne changent pas.

Opérateurs et Expressions

• Le langage C prend en charge différents types d'opérateurs 
• Les opérateurs peuvent être utilisés avec des variables et des constantes pour former des expressions

Types D'Opérateurs

• Arithmétiques
• Addition (+) : a + b.
• Soustraction (-) : a - b.
• Multiplication (*) : a * b.
• Division (/) : a / b.
• Modulo (%) : a % b.

Opérateurs de Comparaison

• Comparent deux valeurs ou expressions, renvoyant une valeur vraie ou fausse.
• < inférieur à : 11 < 12 donne 1.
• > supérieur à : 11 > 12 donne 0.
• <= inférieur ou égal à : 11 <= 11 donne 1.
• >= supérieur ou égal à : 11 >= 12 donne 0.

Opérateurs d'Égalité

• Comparent les opérandes pour une égalité ou une inégalité stricte.
• == Renvoie 1 si les deux opérandes sont égaux, 0 sinon.
• != Renvoie 1 si les opérandes n’ont pas la même valeur, 0 sinon.

Opérateurs Logiques

• ET logique (&&) : a && b
• OU logique (||) : a || b
• NON logique (!) : !a

Opérateurs Unaires

• Agissent sur un seul opérande
• - Inverse la valeur.
• ++ Incrémente la valeur de l'opérande de 1.
• -- Décrémente la valeur de l'opérande de 1.

Opérateur Conditionnel

• (exp1 ? exp2 : exp3)
• exp1 est évalué en premier. Si c'est vrai, alors exp2 est évalué et devient le résultat sinon exp3 est évalué et devient le résultat

Opérateurs Bit à Bit

• Effectuent des opérations au niveau du bit.
• AND bit à bit &, OR bit à bit |, XOR bit à bit ^, NOT bit à bit~.
• Décalage à droite >>, Décalage à gauche<<

Opérateurs D'affectation

• Simple =, Affecte les valeurs des opérandes de droite à
• Compound +=, -=, *=, /=, %=.

Instructions de Contrôle

• Permettent aux programmeurs d'exécuter un bloc de code particulier de manière conditionnelle.
• Décision (branchement)
• Itératives (boucle)
•  Saut