Remerciez-le!

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

Langages et Concepts de Programmation Structures de données et algorithmes en C

Langages et Concepts de Programmation Structures de données et algorithmes en C Cours 1A 2010-2011 Jean-Jacques Girardot, Marc Roelens girardot@emse.fr, roelens@emse.fr Octobre 2010 École Nationale Supérieure des Mines de Saint-Etienne 158 Cours Fauriel 42023 SAINT-ÉTIENNE CEDEX 2 Version du 6 octobre 2010. Première partie Cours 3 Introduction Avant-Propos Ce cours [2] fait suite au cours d’Introduction à l’Informatique [1]. Comme le précédent, ce cours se veut aussi bien une continuation de l’apprentissage de l’algorithmique et de la program- mation, qu’une poursuite de l’étude du langage C. En parallèle à ce cours, les élèves ont à réaliser un mini-projet de programmation, destiné à mettre en œuvre de façon pratique les concepts et techniques abordées dans le cours. Dans le cadre du pôle de modélisation mathématique, les élèves suivent en parallèle le cours de Recherche opérationnelle. Ce cours se termine par deux séances de travaux pratiques, consis- tant à implémenter grâce aux compétences acquises dans le présent cours un algorithme de résolution d’un problème « classique » de recherche opérationnelle. Déroulement du cours Séances 1 et 2 But Savoir écrire des programmes accédant à leurs données en-dehors du programme lui- même. Théorie La représentation externe des données. Entrées-sorties en C. Fichiers texte et ﬁchiers binaires. Pratique Lire des données simples (entiers, ﬂottants, chaînes de caractères), des tableaux. Formater des données en sortie, lire des données formatées en entrée. Séances 3 et 4 But Savoir manipuler des structures de données du langage C. Théorie Notion d’enregistrement (regroupement de données de types différents), champs d’un enregistrement. Structures de données comme paramètres ou résultat de procédures. 5 6 Pratique Construire une structure de données adaptée à un problème posé. Spéciﬁer les pro- cédures de manipulation de cette structure de données. Implémenter ces procédures. Séances 5, 6 et 7 But Initiation au traitement des listes Théorie Algorithmes sur listes. Allocation dynamique de structures de données, pointeurs. Pratique Programmes de recherche en liste, d’interclassement, de tri de listes. Chapitre 1 Entrées-sorties en C 1.1 Cours Ce cours va nous permettre d’aborder les entrées-sorties, qui sont les opérations permettant à nos programmes de communiquer avec le monde extérieur. Dans ces opérations, nous nous intéresserons entre autres à celles qui permettent de lire et d’écrire des données sur les ﬁchiers. Enﬁn, nous proﬁterons de l’occasion pour introduire le traitement des erreurs à l’exécu- tion d’un programme au travers de la variable globale errno et de la fonction de bibliothèque perror. 1.1.1 Introduction Les données que nous avons manipulées jusqu’à présent résidaient uniquement en mémoire centrale. Créées par le programme en cours d’exécution, elles étaient traitées, éventuellement imprimées, puis disparaissaient lorsque le programme se terminait. Certaines données informa- tiques, une fois créées, doivent au contraire être conservées pour une utilisation ultérieure : un jeu se souvient des high scores et des noms de joueurs, les données comptables d’une entreprise sont préservées pendant des années, les pages du web sont gardées pour pouvoir être fournies à la demande, etc. Nous avons déjà décrit brièvement la structure des systèmes de ﬁchiers, et la désignation des ﬁchiers eux-mêmes. Nous avons utilisé jusqu’à présent ces ﬁchiers pour la seule représentation des programmes, qu’ils soient en source, objet, ou exécutables. Nous allons aborder maintenant l’utilisation des ﬁchiers pour la représentation et la conservation des données manipulées par les programmes. 1.1.2 Représentation des données dans un ﬁchier Il faut bien distinguer à ce niveau deux représentations différentes des données de nos pro- grammes : 7 8 CHAPITRE 1. ENTRÉES-SORTIES EN C ◦la représentation interne, c’est-à-dire la forme sous laquelle ces données sont manipu- lées par le programme lui-même ; cette représentation est donc totalement dépendante du langage de programmation ; ◦la représentation externe, c’est-à-dire le codage de ces données dans le but de les conserver dans un ﬁchier ; cette représentation peut dépendre des moyens fournis par le système d’exploitation. Nous avons vu, par exemple, que les données de nos programmes étaient accessibles sous forme de variables, ayant chacune un nom et un type. Ces déclarations de variables sont partie in- tégrante du langage de programmation, et le programmeur n’a donc que peu de choix (divers formats d’entiers et de nombres ﬂottants, noms des variables). A contrario, le langage C ne connaît pas la notion de ﬁchier (ce n’est pas une notion propre au langage) ; les données stockées dans un ﬁchier externe n’ont aucun format imposé par le lan- gage lui-même : il est de la responsabilité totale du programmeur de préciser sous quel(s) format(s) ses données sont représentées dans les ﬁchiers externes. Ces données utiles pour un programme peuvent ainsi être représentées, sous une forme éventuellement différente (com- pactée, codée. . .) de celle qui est utilisée par le programme. C’est toujours au programmeur de garantir que l’utilisation de ces données se fait à bon escient ! On rappelle qu’au niveau du système d’exploitation, un ﬁchier est une simple suite d’octets, en général physiquement enregistrés sur des supports magnétiques, opto-électroniques, etc. Ces ﬁchiers ont un nom externe (et une « position » : les répertoires), des propriétés (ou attributs : peut-on le lire, le modiﬁer ? quand a-t-il été créé, etc) et un contenu, les données elles-mêmes. Sous cette forme, les données ne sont pas directement accessibles par le processeur. Le système d’exploitation permet, grâce aux primitives d’entrées-sorties, d’avoir accès à un ﬁchier, d’en lire et éventuellement d’en modiﬁer le contenu, et de libérer l’accès à ce ﬁchier, aﬁn qu’il puisse être utilisé par d’autres programmes. 1.1.3 Bibliothèque standard des entrées-sorties Ainsi que cela a été indiqué, le langage C ne contient pas la notion de ﬁchier (rappelons que le langage C est un langage simple, voire simpliste... mais néanmoins extrêmement puissant). Cependant, comme ce sont des objets incontournables pour bien des programmes, on a dé- ﬁni pour ce langage des bibliothèques de structures de données et de procédures permettant de réaliser les fonctions d’entrées-sorties : cette bibliothèque, standardisée, est souvent appelée bi- bliothèque standard des entrées-sorties ou encore STanDard Input-Output library, d’où le nom du ﬁchier d’en-tête contenant les structures de données et prototypes des procédures, à savoir le ﬁchier stdio.h déjà maintes fois signalé. Il serait possible à tout un chacun de ne pas vouloir utiliser cette bibliothèque stan- dard des entrées-sorties, mais on perdrait alors tout avantage de la standardisation : universalité, performance éprouvée... Remarque : l’un des avantages de cette bibliothèque est aussi le fait que le langage C s’af- franchit presque totalement des problèmes de portabilité entre systèmes d’exploitation différents 1.1. COURS 9 (Windows et Unix, notamment). On trouvera ainsi des versions spécialisées de la bibliothèque sur chaque environnement utilisé. 1.1.4 Déﬁnition des ﬂots Les mécanismes d’entrées-sorties en C font appel à la notion de ﬂot. Un ﬂot est une sé- quence d’octets, accessibles séquentiellement, qui peut être lue et/ou écrite par le programme. Les programmes C manipulent en particulier : ◦un ﬂot d’entrée, dit entrée standard, accessible par l’intermédiaire d’un objet nommé stdin ; ◦un ﬂot de sortie, dit sortie standard, accessible par l’intermédiaire d’un objet nommé stdout ; ◦un ﬂot de gestion des erreurs, accessible par l’intermédiaire d’un objet nommé stderr. Ces trois ﬂots sont habituellement associés au terminal (clavier, écran) de l’utilisateur. Par exemple, la fonction printf déjà présentée réalise toutes ses sorties sur le ﬂot stdout. Les objets stdin, stdout et stderr sont déclarés dans le ﬁchier d’inclusion stdio.h, que nous connaissons bien. Les déclarations précises de ces objets sont : extern FILE *stdin; extern FILE *stdout; extern FILE *stderr; Le mot-clef extern indique que ces données ne sont pas déﬁnies dans le programme source lui-même, mais dans un module externe (la bibliothèque standard du C), qui sera inclus lors de la phase d’édition des liens. Les objets sont de type FILE *, ce qui veut dire qu’ils sont des adresses (l’étoile) de structures spéciﬁques (de nom FILE) décrivant les caractéristiques des ﬂots correspondants. Nous n’avons pas besoin de savoir précisément ce que contiennent ces structures, car le seul traitement que nous leur appliquerons sera de les utiliser comme paramètres de procédures d’entrées-sorties qui, elles, connaissent lesdites structures. Retenons simplement que, comme toute adresse, l’adresse 0 déﬁnie dans stdio.h par la macro-déﬁnition NULL, représente une adresse incorrecte, et sera toujours utilisée lorsqu’une procédure de manipulation de ﬁchier vou- dra indiquer qu’elle a échoué. Outre ces ﬂots « standard », nous allons voir que des mécanismes du système permettent d’accéder, sous la forme de ﬂots, au contenu des ﬁchiers gérés par le système d’exploitation. 1.1.5 Flots et ﬁchiers 1.1.5.1 Création d’un ﬂot à partir d’un ﬁchier La construction d’un ﬂot à partir d’un ﬁchier externe se fait par la fonction fopen(3) 1. On notera que dans la suite, on parlera d’ouverture de ﬁchier pour désigner la construction d’un 1. Cette notation particulière indique que la fonction fopen fait partie de la section 3 du manuel en ligne : la section 3 contient en fait toutes les bibliothèques de fonctions, et en particulier les opérations d’entrées-sorties du C. On peut consulter la documentation, sous Linux, par la commande man 3 fopen 10 CHAPITRE 1. ENTRÉES-SORTIES EN C uploads/Ingenierie_Lourd/ algorithme-en-c.pdf