[email protected] - Université de Montpellier · 2014. 9. 1. · Notes de Cours : « Génie ... grand volume horaire de Travaux Pratiques encadrés (environ 2/3 du module),

DEPARTEMENT D'ENSEIGNEMENT

ELECTRONIQUE - ELECTROTECHNIQUE - AUTOMATIQUE

Notes de Cours :« Génie Informatique »GLEE302 - Licence EEA - Semestre 3

Mikhaë[email protected]

13 septembre 2011

mailto:[email protected]

2

Table desmatières

1 Introduction Générale : Développement de Logiciels 71.1 Architecture Générale des Calculateurs . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.1.1 Le MicroProcesseur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.1.2 Exemple de Mapping : structure de l’IBM PC (1980) . . . . . . . . . . . . . 91.1.3 Bus d’Adresses, Bus de Données . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Développement Bas Niveau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3 Développement au Niveau Système . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3.1 Notion de Système d’Exploitation . . . . . . . . . . . . . . . . . . . . . . . . 111.3.2 Stratégie de Développement sous Système d’Exploitation . . . . . . . . . . 12

1.4 Et Maintenant ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Rappels du Langage C : Pointeurs et Compilation 152.1 Les Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.1 Les Types de Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.1.2 Utilité de ces Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2 Les Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.2.1 Vie d’une fonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3 Les Pointeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.3.1 Notions élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.3.2 Typage des pointeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.3.3 Vie d’un pointeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.3.4 Notation ”Tableau” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.3.5 Opérateur Adresse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.3.6 Conclusion intermédiaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.4 Préprocesseur et Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.4.1 Schéma de Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.4.2 Commandes Pré-Processeur usuelles . . . . . . . . . . . . . . . . . . . . . . . 28

2.5 Conclusion du Chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3 Développement en Bas Niveau 313.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2 Affichage en Mode Texte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.2.1 Ecriture d’un texte en haut de l’écran . . . . . . . . . . . . . . . . . . . . . . 323.2.2 Ecriture d’un texte n’importe ou à l’écran . . . . . . . . . . . . . . . . . . . . 35

3.3 Utilisation de la RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3

TABLE DES MATIÈRES

4 Développement au niveau Système 394.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.2 Gestion Standard de la RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.2.1 La problématique et sa Solution Système . . . . . . . . . . . . . . . . . . . . 404.2.2 Application au Langage C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2.3 Confrontation Allocation Statique/Allocation Dynamique . . . . . . . . . 47

4.3 Gestion des Fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.3.1 Aspect Système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.3.2 Accès aux fichiers en Langage C . . . . . . . . . . . . . . . . . . . . . . . . . 494.3.3 Gestion du Curseur sur Fichiers . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5 Utilisation Avancée des Pointeurs 555.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.2 Pointeur sur variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.3 Passage de Paramètres d’entrée/sortie à des fonctions . . . . . . . . . . . . . . . . 57

5.3.1 Rappel : Passage de Paramètres à une Fonction . . . . . . . . . . . . . . . . 575.3.2 Rappel : Valeur Renvoyée par une Fonction . . . . . . . . . . . . . . . . . . 595.3.3 Passage par Adresse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.4 Renvoi de Pointeur par une Fonction . . . . . . . . . . . . . . . . . . . . . . . . . . 625.5 Tableaux de Pointeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655.6 Pointeurs de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6 Structures de Données Simples 756.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756.2 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6.2.1 Utilité des Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756.2.2 Définition de Nouvelles Structures . . . . . . . . . . . . . . . . . . . . . . . . 776.2.3 Utilisation de Nouvelles Structures . . . . . . . . . . . . . . . . . . . . . . . . 78

6.3 Nouveaux Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 856.4 Les Unions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

7 Structures de Données Avancées 897.1 Listes Chaînées Simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

7.1.1 Limitation des Tableaux - Utilité des Listes Chaînées . . . . . . . . . . . . . 897.1.2 Fonctionnement des Listes Chaînées . . . . . . . . . . . . . . . . . . . . . . 907.1.3 Les Listes Chaînées en Langage C . . . . . . . . . . . . . . . . . . . . . . . . 917.1.4 Problème du Premier Element . . . . . . . . . . . . . . . . . . . . . . . . . . 1017.1.5 Discussion : Tableaux ou Listes Chaînées . . . . . . . . . . . . . . . . . . . . 103

7.2 Listes Chaînées Doubles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1047.2.1 Limite des Listes Chaînées Simples . . . . . . . . . . . . . . . . . . . . . . . 1047.2.2 Les Listes Doublement Chaînées en Langage C . . . . . . . . . . . . . . . . 104

4

Objectifs et Documents Utiles

Ce module a plusieurs objectifs :– vous permettre de « mettre au propre »des notions abordées en première année mais mal

maîtrisées, notamment en ce qui concerne les pointeurs et la gestion de la mémoire,– vous sensibiliser au développement sur « machine embarquée »par opposition au déve-

loppement sur ordinateur,– enfin, vous rendre opérationnel en Langage C, c’est à dire vous donner un niveau suffi-

samment robuste pour vous permettre de programmer en introduisant un minimum debugs dans vos programmes ainsi que d’aborder n’importe quel domaine de la program-mation (réseau, interface graphique, video, musique

Soyez tout de même conscient que suivre les enseignements théoriques proposés dans cemodule est très insuffisant pour atteindre l’objectif qui est fixé ici, à savoir vous rendre opé-rationnels en programmation en Langage C. Pour atteindre cet objectif assez ambitieux etaborder les différentes sessions d’examen de ce module avec succès, il faut obligatoirementpasser par un grand volume d’heures de pratique sur ordinateur. Ce module comporte déjà ungrand volume horaire de Travaux Pratiques encadrés (environ 2/3 du module), mais ceci restetrès insuffisant et vous aurez à progresser par vous-mêmes.

Pour cela, j’ai écrit un ensemble de tutoriaux pour vous permettre d’installer un langage Cet / ou un linux chez vous et sans risque. Ces tutoriaux sont disponibles à l’URL ci-dessous, surle site du département EEA :

http://www.eea.univ-montp2.fr/spip.php?rubrique79

Dans tous les cas, ma boite email est disponible pour toute question relative à ce langage :[email protected]

Vous pouvez aussi m’envoyer des morceaux de programmes que vous auriez écrits et qui nefonctionneraient pas pour une raison à déterminer.

5

http://www.eea.univ-montp2.fr

http://www.eea.univ-montp2.fr/spip.php?rubrique79

[email protected]

6

Chapitre 1

Introduction Générale :Développement de Logiciels

Sommaire1.1 Architecture Générale des Calculateurs . . . . . . . . . . . . . . . . . . . . . . . 8

1.1.1 Le MicroProcesseur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.1.2 Exemple de Mapping : structure de l’IBM PC (1980) . . . . . . . . . . . 91.1.3 Bus d’Adresses, Bus de Données . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Développement Bas Niveau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3 Développement au Niveau Système . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3.1 Notion de Système d’Exploitation . . . . . . . . . . . . . . . . . . . . . . 111.3.2 Stratégie de Développement sous Système d’Exploitation . . . . . . . . 12

1.4 Et Maintenant ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Ce cours a pour vocation d’introduire le développement de logiciels sur les calculateurs engénéral, c’est à dire essentiellement deux familles de machines :

– Ordinateurs : machines dottées notamment d’un microprocesseur et d’un systèmed’exploitation, notions que nous introduisons par la suite. Ce sont des machines quevous cotoyez tous les jours et dont vous connaissez deja les applications.

– Machines Embarquées : machines généralement dépourvues de système d’exploitation.Vous cotoyez également ces machines tous les jours sans forcément savoir qu’il s’agit demachines embarquées. Les applications vont de la simple montre digitale au tableau debord d’un avion, en passant par le pilotage d’automates en robotique, les programmateursde machine à laver ou encore les baladeurs MP3. Les applications sont donc extrèmementdiverses.

La présence ou l’absence d’un système d’exploitation va complètement changer la tech-nique du développement de logiciels 1. Nous parlerons plus précisément du système dans lasuite de ce cours.

Le langage qui servira de support sera ici le langage C, mais les notions qui sont introduitessont extrapolables à d’autres langages type Pascal ou Fortran même si en règle générale lelangage C reste le plus adapté au développement d’applications efficaces.

1. Notons qu’il existe aussi des machines embarquées utilisant un système d’exploitation réduit.

7

1 • Introduction Générale : Développement de Logiciels

1.1 Architecture Générale des CalculateursQuoi qu’il en soit, les calculateurs ont généralement tous la même structure. Le schéma

simplifié de la figure 1.1 montre les organes principaux qui composent une telle machine.

Divers Périphériques

HDCD-Rom

SourisClavier

Réseau EcranImprimante

Bus d’Adresses

Bus de Données

µpRAM ROM

Figure 1.1 – Schéma global d ’un Calculateur

Ils sont généralement composés de 4 entités :– un MicroProcesseur qui est chargé à la fois des calculs et ainsi que des échanges de

données avec les autres organes (RAM, ROM, Périphériques) composant le calculateur.C’est le composant électronique qui va exécuter les programmes.

– de la RAM : ”Random Access Memory” (par opposition aux mémoires à bande). C’est lamémoire de travail de la machine. Notez que l’on parle ”d’accès aléatoire” par oppositionavec les mémoires à bandes : l’ordre d’accès des cases mémoire avec une RAM n’a pasbeaucoup d’influence (à quelques optimisations hardware près) sur le temps de calcul,contrairement aux mémoires à bande.

– une ROM : ”Read Only Memory” qui contient généralement le premier programmelancé par la machine. Dans le cas d’une machine embarquée, la ROM contient en généraltout le programme à exécuter. Dans le cas d’un ordinateur, la ROM peut contenir soit lesystème d’exploitation complet (ce que l’on ne fait plus depuis les années 1990 environpour des raisons de taille et de souplesse), soit une séquence de démarrage permettantde charger le système à partir d’un disque dur.

– des Périphériques : typiquement les points d’entrée/sortie. Dans le cas d’un ordina-teur, il pourra s’agir d’un contrôleur de souris, de clavier, de disque dur ou d’une cartevideo pour l’affichage. Dans le cas d’une machine embarquée, il peut s’agir de convertis-seurs analogiques/numeriques ou numériques/analogiques permettant de piloter diverscapteurs (sonde de température, détecteur de lumière, etc ...) ou actionneurs (émetteurde lumière, moteur, etc ...), ou encore d’afficheurs simples, etc ...

1.1.1 LeMicroProcesseurLe MicroProcesseur est le composant qui va exécuter le programme que nous aurons à

écrire. Il est donc essentiel pour nous de se placer du point de vue du microprocesseur. Pour cecomposant, la notion de RAM, de ROM ou de Périphérique n’existe pas. Pour communiqueravec les divers composants, tout ce que sait faire le Microprocesseur c’est lire ou écrire uneDonnée (toujours sous forme de chiffre) à un certain endroit, appelé ”Adresse”.

Ainsi, du point de vue du MicroProcesseur (ou CPU pour ”Central Processing Unit”), tousles organes (RAM, ROM, Périphériques) sont simplement des cases mémoire organisées dansun tableau. Le CPU n’a ainsi absolument aucune idée de ”quel composant” se situe à quelleadresse : c’est au développeur de savoir ”où taper” (à quelle adresse) pour accéder à tel ou telpériphérique. Le recencement de toutes ces plages d’adresses est ”le mapping”. Il est câblé au

8

1.1 • Architecture Générale des Calculateurs

niveau électronique, un ensemble de composants non représentés sur la figure 1.1 servant àl’aiguillage des diverses adresses vers certains composants.

Ainsi, pour un développeur en bas niveau, le Mapping de la machine sur laquelleil développe est une donnée indispensable.

1.1.2 Exemple deMapping : structure de l’IBMPC (1980)Nous donnons, à titre d’exemple (fig. 1.2), le Mapping de l’IBM-PC tel qu’il fut défini dans

les années 1980 et qui est aujourd’hui celui sur lequel se basent tous les micro-ordinateurs PCgrand public de la famille Intel et AMD pour la partie basse du moins. Ce schéma appelle unensemble de remarques :

– Les microprocesseurs Intel/AMD exécutent, lors de leur mise sous tension, du code situéen fin de mémoire puisque le BIOS, qui contient la séquence de démarrage, se situe àcet endroit.

– Si l’on souhaite par exemple accéder au port série (RS-232) principal, souvent noté ”COM1”,il faudra taper dans la plage d’adresses située entre $3F8 et $3FF inclus. Cette plage de8 octets permet non seulement de placer la valeur à envoyer mais également de lire ladonnée reçue ainsi que de configurer les paramètres de la liaison (parité, CRC, etc ...).

– Pour ”savoir l’heure qu’il est”, il suffit de lire la donnée à l’adresse $40,– Si l’on souhaite allumer ou éteindre des pixels à l’écran, il faut s’intéresser à la RAM vidéo,

et donc taper entre $A0000 et $C0000, soit un espace de 128 ko. Notons que cette plaged’adresses ne permet d’obtenir que des résolutions video assez modestes, notamment unmode usuel à cette époque, à savoir 640 × 400 en 16 couleurs : 16 couleurs = 4 bit/pixel(24 = 16), soit 640 × 480 × 4 = 1024000bits = 128000octets < 128ko. Il est donc clairque les modes video disponibles aujourd’hui utilisent d’autres plages de mémoire, ce quimontre quelque part l’aspect obsolète de ce mapping, qui reste malgré tout en vigueurpour des raisons de compatibilité.

1.1.3 Bus d’Adresses, Bus de DonnéesSur la figure 1.1, nous constatons deux choses :– Tous les composants sont à la fois reliés au bus d’adresse et au bus de données. C’est ce

qui permet notamment au microprocesseur d’envoyer ou de récupérer l’information pré-sente sur le bus de données en fonction de l’adresse du composant avec lequel il dialogue.

– Chaque bus fait sur cette figure ”4 fils”.Chacun de ces fils électrique est simplement un bit du bus considéré. Ainsi, avec 4 fils pour

le bus d’adresses, nous avons 4bits et donc 24 adresses possibles, soit 16 adresses. Si le bus dedonnées fait également 4bit, chaque adresse peut correspondre au plus à un demi octet, ce quinous donne un espace adressable de 8 octets en tout. Une telle structure n’est bien entendu pasdu tout réaliste au jour d’aujourd’hui pour un ordinateur. Toutefois, on peut noter que certainsmicrocontrôleurs dédiés aux machines embarquées peuvent disposer de bus d’adresses et dedonnées assez réduits.

A ce jour, nous venons de vivre la transition entre les CPU 32 bit et les CPU 64 bit. Qu’est ceque cela signifie vraiment ? CPU ”32 bit” signifie que le bus d’adresses et le bus de données font32 bit chacun. Ainsi, le processeur dispose de 232 = 4Giga-adresses. Sur ordinateur, les casesmémoire sont usuellement d’un octet, on a donc un maximum de 4Giga-octets de mémoireau maximum. En considérant que le mapping n’est pas constitué à 100% de RAM, ceci mèneà 2Go de RAM environ au maximum. Les machines d’aujourd’hui - les ordinateurs pour le

9


0

Hex

adéc

imal

Hex

adéc

imal

Déc

imal

Déc

imal

40Réservé

Horloge44

Réservé60

Clavier64

RS232 secondaire300

Réservé320

Réservé378

Réservé3D0

Réservé3F0

Contrôleur Disque Dur330

Imprimante380

Ecran Monochrome3C0

Ecran Couleur3E0

Lecteur de Disquettes3F8

RS232 principal400

Réservé2F8

00

400

A 0000

0

64

68

96

100

768

800

888

976

1008

816

896

960

992

1016

1024

760

Entrées/Sorties

ZOOM E/SMapping Général

1024

655 360 (640 ko)

640 ko RAMenviron

C 0000 786 432 (768 ko)

128 koRAM Video

10 0000 1 048 576 (1 Mo)

256 koBIOS (ROM)

Adresses Adresses

Adresses Adresses

Figure 1.2 – Mapping de l’IBM PC

traitement d’images, video, ou encore les serveurs de calcul - sont très près de cette quantité,ce qui suppose que l’on a besoin d’étendre la taille du bus d’adresses, donc de passer à desstructures 64 bit.

De plus, si l’on a 32bit sur le bus de données, celà signifie que le CPU est capable d’échanger4 octets d’un seul coup avec n’importe quel composant, notamment avec la RAM. Le débitd’information du bus, exprimé en octets par secondes, faut donc 4 fois la fréquence de pilotagedu bus.

Avec un CPU 64 bit, on augmente énormément la quantité de RAM max possible (264 ≈20× 106To ...), et on double la vitesse d’échange des données avec la RAM notamment.

1.2 Développement Bas NiveauDe nos jours, le développement Bas Niveau ne concerne que les machines embarquées :

le développement sur ordinateur devenant de plus en plus ambitieux quant aux applicationsvisées, il n’est plus vraiment concevable aujourd’hui de développer en bas niveau sur un ordi-nateur (exception faite du développement de drivers ...).

Lors d’un développement en bas niveau, le programmeur est ”seul maître à bord”. Ceci peutsembler avantageux au sens où le programmeur fait ce qu’il veut. La contrepartie est qu’aucunoutil n’est là pour l’aider. Lorsque l’on opte pour une telle stratégie de développement, il fautgarder à l’esprit que :

– L’accès aux périphériques se fait directement en tapant aux bonnes adresses dans lemapping. Ainsi, le programmeur est directement tributaire du mapping et du protocoled’accès aux différents composants.

– La RAM est gérée par le programmeur lui-même. Si l’on prend par exemple le mapping del’IBM-PC, le programmeur peut choisir de travailler à n’importe quelle adresse mémoire

10

1.3 • Développement au Niveau Système

située entre $400 et $A0000. Si il faut gérer plusieurs tableaux, c’est au programmeur querevient encore une fois l’attribution des zones de mémoire nécessaires au travail.

– Siette façon de programmer est toujours possible sur une machine ne disposant pas desystème d’exploitation, elle est généralement impossible sur les machines disposant desystèmes modernes, et parfois possible sur des systèmes plus anciens ou plus laxistes.

Le critère qui permet de savoir si le développement en bas niveau est possible avec une machinedottée d’un système d’exploitation est la notion de ”protection mémoire”. Dans tous les or-dinateurs récents, une puce appelée ”MMU” (Memory Management Unit) permet au systèmed’exploitation de faire un contrôle en temps réel des accès aux différentes zones du mappinget donc interdire les accès qui lui semblent dangereux. Sur d’anciens systèmes - typiquementMS-DOS - la MMU n’est pas gérée et la protection mémoire est donc indisponible. Ceci faitque n’importe quelle application peut accéder à toutes les zones sensibles de la machine sansrestriction, ce qui permet donc un développement en bas niveau.

Notez que la protection mémoire n’est pas un handicap, bien au contraire : c’est typique-ment ce qui fait que l’ordinateur ne peut plus ”planter” lorsqu’une tâche réalise des opérations”annormales”. C’est donc quelque chose de complètement indispensable sur les systèmes mul-titâches, pour rendre les différentes tâches indépendantes les unes des autres.

Nous donnons sur la figure 1.3 une classification des systèmes d’exploitation les plus ren-contrés aujourd’hui par rapport à leur gestion de la protection mémoire. Ainsi :

– On remarque qu’aucun système d’exploitation moderne ne permet le développement enbas niveau. A noter que les Unix gèrent la protection mémoire depuis leur création dansles années 1980 ...

– Le système qui permet totalement un développement bas niveau est MS-DOS. Atten-tion, ouvrir une session ”Terminal” sous Windows n’est pas équivalent à fonctionner sousMS-DOS.

– Les anciens systèmes d’exploitation Microsoft permettaient, en fonction du type d’application,un accès direct à certaines ressources sans que cela soit très bien documenté.

Système "sécurisé"

Système "laxiste"

MS-DOS Windows 3.x Windows 9x

MacOs < 10 MacOs 10Unix/Linux

Windows NT/2000/XP

Figure 1.3 – Classification des Systèmes d ’Exploitation les plus connus

1.3 Développement au Niveau Système

1.3.1 Notion de Système d’ExploitationSi l’on se contente d’une machine constituée de son processeur, sa RAM, sa ROM et ses

périphériques, tout ce que l’on peut faire c’est en gros du calcul et de la communication avecdes périphériques. Prenons le cas concret des disques : Si l’on connecte un disque dur sur unordinateur, initialement, tout ce que la machine peut faire c’est accéder aux cases mémoire dudisque, et y inscrire ou lire des informations. La notion de fichier ou de répertoire par exemple

11


n’existe absolument pas. De même, lorsque l’on tape une touche au clavier, tout ce que connaitla machine c’est la position de la touche sur le clavier et pas le caractère qui lui est associé. Demême, tous les protocoles réseau permettant de naviguer sur internet ou encore les protocolesde communication avec les imprimantes sont eux aussi inexistants. Si l’on va plus loin, lesnotions d’interface graphique que nous manipulons tous les jours (interactions à la souris avecdes fenêtres, des boutons, des boites de dialogue, etc ...) sont totalement inconnues.

Pour que l’ordinateur ne se limite pas simplement à produire du calcul et de l’échanged’information, on le dotte d’un ”système d’exploitation” (noté ”SE” ou ”OS” pour ”OperatingSystem”). Un système d’exploitation est donc un assez gros programme qui va gérer pour leprogrammeur les notions de fichiers et de répertoire pour les disques, un accès facile au cla-vier, une gestion des éléments de base des interfaces graphiques, etc. En absence de système,quiconque voudrait utiliser ces concepts serait obligé de réinventer la roue à chaque fois qu’ilproduit une nouvelle application. Le système représente donc, pour un développeur, un gainde temps substantiel.

Ceci dit, son rôle ne se limite pas à cela. Depuis maintenant une quinzaine d’années, lesutilisateurs exigent des systèmes capables d’exécuter plusieurs tâches à la fois - alors que lesmachines ne disposent en général que d’un seul processeur. On dit alors que les machines sont”multitaches”, et le programme qui permet de gérer les tâches est encore une fois le systèmed’exploitation : l’ordinateur est alors équivalent à plusieurs ordinateurs (”machines”) fonction-nant sur le même processeur. Ces machines sont voulues bien entendu aussi indépendantes quepossible (d’ou la protection mémoire permise par la MMU dont nous avons parlé plus haut),et l’on dit alors que chacune d’elle est une ”machine virtuelle”, au sens ou ce sont de ”faussesmachines”.

1.3.2 Stratégie de Développement sous Système d’Exploitation

Etant donné le contrôle qu’a le système sur la machine et les possibilités qu’il offre, il estclair que le développement d’applications va beaucoup changer par rapport à ce que l’on faiten absence de système. Ainsi, il faut suivre quelques règles :

– Dans un tel développement, le Mapping n’est plus du tout une donnée fondamentale etpeut être ignoré. Mieux, il est totalement interdit d’accéder directement aux portsd’entrée/sortiee de l’ordinateur.

– C’est le système qui a le contrôle de l’occupation de la RAM. Ainsi, si vous avez besoinde mémoire pour faire un certain calcul, vous ne pouvez pas choisir le lieu où vousallez travailler en RAM, c’est le système qui va décider pour vous.

– L’accès aux différentes possibilités du système se fait via les API (Application ProgramInterface), qui sont propres à chaque système d’exploitation. Pour les systèmes Micro-soft, cette API s’appelle ”API Win32”, elle est décrite dans les MSDN (MicroSoft De-velopper Network), disponible en ligne sur le site de Microsoft. Notez que dans le casdu langage C, l’appel aux API est inutile en ce qui concerne l’accès à la mémoire et auxdisques durs car le C intègre cette gestion en faisant lui-même appel à l’OS. En revanche,pour tout ce qui concerne l’interface graphique, il faut attaquer directement les API etdonc connaître la structure de l’OS sur lequel vous travaillez. Nous y reviendrons.

12

1.4 • Et Maintenant ?

1.4 EtMaintenant ?Maintenant que nous avons posé le contexte de ce cours, nous allons pouvoir rentrer dans

le développement et l’application de ces concepts au langage C.Nous commencerons par un chapitre de rappels sur la notion de pointeur en langage C

ainsi que sur l’utilisation du pré-processeur.Nous aurons ensuite un second chapitre concernant le développement en absence de sys-

tème.Toute la suite du cours sera consacrée au développement sur ordinateur avec OS en déve-

loppant les différents concepts offerts par les systèmes d’exploitation.

13

14

Chapitre 2

Rappels du Langage C : Pointeurs etCompilation

Sommaire2.1 Les Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.1 Les Types de Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.1.2 Utilité de ces Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2 Les Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.2.1 Vie d’une fonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3 Les Pointeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.3.1 Notions élémentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.3.2 Typage des pointeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.3.3 Vie d’un pointeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.3.4 Notation ”Tableau” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.3.5 Opérateur Adresse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.3.6 Conclusion intermédiaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.4 Préprocesseur et Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.4.1 Schéma de Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.4.2 Commandes Pré-Processeur usuelles . . . . . . . . . . . . . . . . . . . . . 28

2.5 Conclusion du Chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.1 Les TypesEn C, toute variable doit être déclarée en indiquant son type : aucune variable ne peux

exister sans type. Exemples :

1 int i; /* Le type Entier */

float k; /* Le type Reel */

2.1.1 Les Types de BaseIl existe en C d’autres types de base, qui sont d’autres sortes d’entiers et d’autres sortes de

réels :

15

2 • Rappels du Langage C : Pointeurs et CompilationType Valeurs possibleschar entier sur 8 bit. Permet de stocker par exemple un carac-

tère ou un pixel niveau de gris.short entier 16 bit.int entier 16 ou 32 bit (selon les machines)long entier sur 32 bit.float flottant (nombre à virgule) simple précisiondouble flottant double précision

Intéressons nous aux types entiers. Dire que l’on a un nombre entier codé sur par exemple16 bits signifie que l’on a 216 possibilités d’arrangements de bits. A partir de là, on a notammentdeux possibilités :

– considérer que l’entier est toujours positif. Dans ce cas, on utilise les 16 bit pour coderle nombre, et on obtient un nombre situé entre 0 et 216−1 (puisqu’on a 216 possibilités).

– considérer que l’entier peut etre soit positif soit négatif. Dans ce cas, on utilise un bit (lebit de poids le plus fort en général) pour représenter le signe et les 15 bits restants pourcoder le nombre lui-même. Les nombres obtenus sont donc situés entre −215 et 215 − 1.

Par défaut, il existe une ambiguité : on ne peut pas dire sans se documenter sur ce quefait le compilateur. Généralement, les nombres sont implicitement signés : ca n’est pas uneobligation, c’est le cas sur la majorité des compilateurs et ce sera le cas en TP. Si toutefois il ya une ambiguité, on peut utiliser le modificateur signed :

Type Valeurs possiblessigned char -128 à +127signed short -32768 à +32767signed int entier 16 ou 32 bit (selon les machines)signed long entier sur 32 bit. valeur entre -2 milliards et +2 milliards

De la meme facon, et c’est plus souvent utile, on peut forcer un entier à être non signé enutilisant le modificateur unsigned :

Type Valeurs possiblesunsigned char 0 à +255unsigned short 0 à +65536unsigned int entier 16 ou 32 bit (selon les machines)signed long entier sur 32 bit. valeur entre 0 milliards et 4 milliards

2.1.2 Utilité de ces TypesReste donc une question importante : pourquoi a-t-on besoin d’autant de types de don-

nées ? Comment choisit-on le type dont nous avons besoin ? Nous montrons ici, sur quelquesexemples concrets, pourquoi il est utile de disposer de tous ces types.

2.1.2.1 Le type Char

De par l’expérience que vous avez acquis, vous avez dejà une partie de la réponse avecl’utilisation du type char : Comme nous l’avons déjà dit, tout ce que l’on peut gérer avec un

16

2.1 • Les Types

ordinateur, ce sont des tableaux de chiffres. La notion de ”caractère” n’a pas d’existance en soi,un caractère est un entier pouvant prendre une valeur située entre 0 et 255, conformément àla table ASCII. On voit donc qu’on a besoin du type char, qui est un type de nombre entier,pour représenter des caractères : il serait stupide de représenter les caractères par des long parexemple, puisqu’on a besoin d’atteindre des valeurs toujours inférieures à 255.

Le char trouve bien entendu une autre utilité, par exemple en imagerie. En effet, une image”niveaux de gris” utilise typiquement 8 bit pour chaque pixel. Une valeur faible (proche de 0)définit un point sombre, une valeur forte (proche de 255) représente un point clair. Entre lesdeux valeurs extrêmes, les points sont interprétés en différents niveaux de gris :

0

0

1

2

3

4

5

6

7

1 2 3 4 5 6 255 255 223 187 239 255 255 255

255 255 85 0 138 255 255 255

255 239 0 0 0 255 255 255

255 154 0 154 0 207 255 255

255 49 85 255 17 118 255 255

233 0 33 69 17 33 255 255

138 0 138 138 102 0 207 255

49 85 255 255 239 0 118 255

On utilisera donc des unsigned char. Ce codage représente une limite, puisqu’on a uneprécision un peu meilleure que 0.5 % (1/256) sur l’amplitude, ce qui suffit toutefois en généralà satisfaire l’oeil.

2.1.2.2 Le type Short

Nous donnons ici trois utilités :– La première concerne le codage du texte : les normes évoluent actuellement vers un

nouveau standard, ”unicode”, successeur de l’ASCII, codé sur 16 bit, permettant doncde coder 65536 caractères différents. Outre les caractères latins, les caractères associés àl’ensemble des langues mondiales sont représentés.

– La seconde concerne l’imagerie : il se peut que l’on ait besoin de plus de précision que 8 bitsur l’amplitude. Ce nouveau codage permet alors d’avoir une précision de 15 millionièmes(1/216) au lieu de quelques millièmes.

– Le codage de chaque amplitude d’un son se fait typiquement sur 16 bit en qualité HiFi.Un codage sur 8bit ajouterait un souffle perceptible à l’oreille.

On peut en effet voir sur la figure suivante comment le nombre de bits de codage influencela précision, ici sur respectivement 3 bits (soit 23 = 8 niveaux) et 4 bits. Il est clair qu’avec4 bits on va pouvoir se rapprocher plus du signal réel puisqu’on dispose de plus de niveaux :

0Vtemps temps

1V

8 niveaux = 3 bit

erreur max = 1/8

0V

1V

16 niveaux = 3 bit

erreur max = 1/16

2.1.2.3 Le Type Long

Le type long sert typiquement à représenter un compteur ou l’indice d’un tableau, puisqu’ona besoin d’atteindre de grandes valeurs entières. Notez que dans le cas d’un tableau, on a en

17

2 • Rappels du Langage C : Pointeurs et Compilation

général intérêt à opter pour unsigned long dans la mesure où un indice n’est jamais négatif.

2.1.2.4 Les type oat ou double

Ces types servent typiquement à du calcul scientifique, et le choix du type se fait en fonc-tion d’un compromis sur la précision à atteindre et la place mémoire utilisée (Notammentproblème des exponentielles) http://www.cs.princeton.edu/introcs/91float /

2.2 Les FonctionsLe rôle principal d’une fonction est de produire un certain travail à partir de paramètres

d’entrée et de fournir éventuellement un résultat :FONCTION

TRAVAIL

(Morceau de Programmeappelé

"Corps de la Fonction")

ENTREES SORTIE

paramètre 1

résultat(retour)

paramètre 2

paramètre 3

paramètre n

Toute fonction a donc :– un nom qui la représente. Typiquement, en mathématique, une fonction s’appelle f oug, alors qu’en C on essaiera de donner un nom indiquant le rôle de la fonction.

– des paramètres qui sont les informations sur laquelle la fonction va s’appuyer pour réa-liser son travail. Il peut éventuellement n’y avoir aucun paramètre. En math, les fonctionsont usuellement un seul paramètre, x.

– un résultat ou retour qui est généralement le résultat du calcul si la fonction produitun calcul, mais pas nécessairement

– un corps, qui est simplement une suite d’insctructions en C qui décrivent la tâche àréaliser.

2.2.1 Vie d’une fonction

Il y a trois étapes dans la vie d’une fonction :– la déclaration de la fonction : c’est l’étape où l’on indique le nom de la fonction, ce

qu’elle prend pour paramètres, et le type de son retour. De plus, si l’on n’utilise pascertaines astuces, une fonction C n’a qu’une et une seule valeur de sortie aumaximum. Nous apprendrons comment détourner cette limitation du langage C, maisà ce stade, nous ne disposons que d’une et une seule sortie pour une fonction donnée.

– la définition de la fonction : Dans cette étape, on répète le prototype de la fonction eton ajoute son corps, c’est à dire le morceau de programme qui décrit ce qu’elle doit faire.Une fonction, identifiée par son nom, ne peut être définie qu’une et une seulefois. Ceci signifie qu’on ne peut pas définir deux fonctions dont le nom serait identique.

– l’appel à la fonction : dans cette étape, on fournit à la fonction les valeurs des paramètressur lesquels elle va travailler. On a tout à fait le droit (et c’est même un des buts)de faire plusieurs appels à la même fonction.

18

2.2 • Les Fonctions

2.2.1.1 Déclaration d’une fonction

La déclaration d’une fonction se fait en respectant rigoureusement la syntaxe suivante (icipour trois paramètres) :type_de_retour nom (type1 param1, type2 param2, type3 param3);

On retrouve bien le nom et les paramètres (chacun avec son type). Pour le résultat ou retour,le C n’a besoin ici que du type de la valeur de retour. Prenons un exemple. Définissons lafonction Puissance qui calcule ab avec a réel et b entier positif. On peut donc dire que :

– le nom sera par exemple puissance,– la fonction a deux entrées :• la variable a qui sera soit un réel, donc float soit un double, nous choisirons float,• la variable b qui sera un entier positif, donc un unsigned char, unsigned short, un-

signed int ou unsigned long. Nous choisirons unsigned int. Choisir int ne seraitpas une erreur mais serait moins rigoureux par rapport aux possibilités offertes par lafonction. Choisir char limiterait la fonction à l’exposant 255 ce qui serait dommage.

– la fonction a pour sortie un réel, puisque le résultat mathématique de ab est un réel. Parsoucis d’homogénéité, nous choisirons encore une fois le type float.

La déclaration de la fonction puissance serait donc :1 float Puissance(float a, unsigned int b) ;

2.2.1.2 Dé nition d’une fonction

La définition de la fonction se fait, à peu de choses près, en décrivant par un morceau deprogramme en C, le calcul qu’elle doit faire à partir des paramètres pour fournir la sortie. Ladéfinition d’une fonction se fait en respectant rigoureusement la syntaxe suivante (ici pourtrois paramètres) :

1 type_de_retour nom (type1 param1, type2 param2, type3 param3)

{

3 /*Corps de la fonction*/

}

Toujours pour le cas de la fonction puissance, nous donnons le programme correspondant :float Puissance(float a, unsigned int b)

2 {

float c = 1;

4

while(b!=0)

6 {

c = c * a;

8 b = b - 1;

}

10

return c;

12 }

Le principe est simplement de multiplier c par a autant de fois qu’il faut, c’est à dire b fois,pour arriver au résultat. Le résultat du calcul est donc contenu dans la variable locale c à la findu calcul. Pour indiquer que c est le résultat, on précise à la fin de la fonction return c;.

19


Remarquons que c est de type float, c’est à dire du même type que le retour de la fonction,ce qui est obligatoire puisque c’est la variable retournée par la fonction !

2.2.1.3 Appel à une fonction

L’appel à une fonction se fait en fournissant des valeurs à la fonction lui permettant d’effectuerle calcul. Voici sur un premier exemple :

Puissance(5.0 , 3);

Si on tape cette ligne de programme, par exemple dans la fonction main, la fonction puissanceest effectivement exécutée. En revance, impossible d’obtenir le résultat : rien n’a été fait pourqu’il soit affiché, et de puis ce résultat n’est stocké nulle part au moment de l’appel. Voici surun nouvel exemple :

1 float z;

z = Puissance(5.0 , 3);

Sur cet exemple, z vaut bien 125 : la variable z a récupéré le résultat contenu dans la variable c.On pourrait également écrire :

float x,z;

2 unsigned int y;

x = 5.0;

4 y = 3

z = Puissance(x , y);

Note Importante : y vaut toujours 3 et pas 0 à la fin de ce programme ! !. Si la valeurde y changeait, celà signifierait que y est une sortie or c’est impossible puisque les paramètressont TOUJOURS des entrées. Plus techniquement, ceci est dû au fait que les paramètres sontpassés par recopie aux fonctions : b de la fonction Puissance est une copie de y. Cette re-copie a lieu AUTOMATIQUEMENT au lieu de l’appel, et fait partie du fonction-nement normal du Langage C pour l’appel de fonctions.

Ecrivons maintenant le programme complet :

1 /*definition de la fonction Puissance*/

float Puissance(float a, unsigned int b)

3 {

float c = 1;

5

while(b!=0)

7 {

c = c * a;

9 b = b - 1;

}

11

return c;

13 }

15 /*definition de la fonction main*/

int main(void)

17 {

20

2.2 • Les Fonctions

float x,z;

19 unsigned int y;

x = 5.0;

21 y = 3

z = Puissance(x , y); /*appel a la fonction Puissance*/

23 printf(”%f␣a␣la␣puissance␣%d␣vaut␣%f”,x,y,z);}

2.2.1.4 Le symbole void

Le symbole void est utile dès lors que l’on veut définir une fonction qui ne prend aucunparamètre, qui n’a aucune sortie ou les deux à la fois. Prenons quelques exemples.

Fonction sans paramètre : Quel genre de fonction peut ne prendre aucun paramètre ? Parexemple une fonction qui ne fait que produire un résultat, sans avoir besoin de paramètre.C’est le cas d’une fonction qui effectuerait le calcul de la constante π, en utilisant par exemplele calcul suivant :

π ≈ 4×(1

1− 1

3+

1

5− 1

7+

(−1)k

2k + 1

)Voici un programme avec déclaration, définition et appel :

float calcPi(void); /*declaration*/

2

float calcPi(void) /*definition*/

4 {

float r = 0;

6

for(int i = 0; i < 100 ; i = i + 1) /* calculons jusqu’au 100ieme terme*/

8 {

r = r + Puissance(-1.0,i) / (2* i + 1.0);

10 }

12 return 4.0 * r;

}

14

int main(void)

16 {

18 float valPi;

valPi = calcPi(); /*appel*/

20 }

Notons que lors de la définition et la déclaration, les paramètres sont remplacés par le motvoid, et que lors de l’appel les parenthèses sont vides.

Fonction sans sortie : C’est le cas notamment des fonctions qui ne produisent aucun calcul.Par exemple une fonction qui afficherait un nombre complexe :

1 void AffCplx(float Re, float Im)

{

21


3 printf(”%f␣+␣%f␣i”,Re,Im);}

2.3 Les Pointeurs

2.3.1 Notions élémentairesLes pointeurs sont un des outils les plus puissants du langage C, ce concept étant malheu-

reusement souvent difficile à assimiler.Le but premier d’un pointeur est de pouvoir naviguer dans la mémoire vive. Un pointeur a

la définition suivante :– un pointeur est une variable : Ceci signifie qu’on a le droit d’effectuer certaines opé-

rations sur les pointeurs, opérations que nous décrirons plus loin.– c’est une variable qui représente une adresse : Ceci signifie que sa valeur intrin-

sèque est une adresse.

Pour concrétiser cette notion, on peut faire une analogie entre un pointeur sur de la RAMet un curseur sur une bande magnétique (fig. 2.1).

F8 12 2E A0 01 BD 15 2A C2 31 2B 00 05 12 C9 F2 34 D6 62

0Adresses

Données

p

1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12

Figure 2.1 – Analogie Pointeurs/RAM et Curseur/Bandes Magnétiques

On supposera sur cet exemple que les valeurs sont exprimées en hexadécimal et que chaquecase fait 1 octet (ce qui explique que chacune soit représentée par 2 chiffres hexadécimaux).Ici, p est un pointeur dont la valeur est 9 puisque p est un curseur sur la case numéro 9, doncsur l’adresse 9. Les opérations possibles sur ce pointeur/curseur sont moins nombreuses quesur les variables dédiées au calcul. Il y en a 3 :

– L’affectation : On peut choisir la position du curseur sur la mémoire. Par exemple,pour être dans la situation de la figure 2.1, il suffit d’écrire en C : p = 9;

– L’incrémentation et la décrémentation : On peut déplacer le curseur à gauche ou àdroite. C’est précisément l’opération qui permet d’explorer la mémoire. En C, si on veutdéplacer par exemple le cuseur de deux cases à gauche, celà donne : p = p-2; ou encorep -= 2;

– Le déréférencement : C’est la seule opération qui est spécifique aux pointeurs. Elleconsiste à s’intéresser à la valeur située à l’adresse pointée par le pointeur. Sur notreexemple, le déréférencement de p vaut 0x31. En C, le déréférencement se note *. Ainsi,si on veut remplacer le 0x31 par 0x14, on écrirait le code suivant : (*p) = 0x14;

Notons que le * n’a ici pas du tout la valeur d’une multiplication. Il n’y a pas d’ambiguitécar la multiplication est un opérateur binaire (il demande une valeur à sa gauche et à sa droite)alors que le déréférencement est un opérateur unaire (il ne demande qu’une seule valeur à sadroite).

22

2.3 • Les Pointeurs

2.3.2 Typage des pointeursEn C, les pointeurs sont typés. Notons d’abord une chose : la taille d’un pointeur est tou-

jours la même, quel que soit son type. En effet, un pointeur étant une adresse, son codagedépend exclusivement de la taille du bus d’adresse. Par exemple, sur un ordinateur dotté d’unprocesseur 32bit, le codage d’un pointeur se fait sur 32bit, donc sur 4 octets. Sur une machine64bit, un pointeur fait 8 octets, etc ...

Dans ces conditions, à quoi sert le typage d’un pointeur ? Il est important de noterque :

Un pointeur n’est pas typé par rapport au codage des adresses mais parrapport à l’opération de déféférencement et uniquement par rapport àl’opération de déféférencement.

Ainsi, toujours sur l’exemple de la figure 2.1, si l’on considère que chaque case est un octet,dire que p est un pointeur de type char signifie que (*p) vaut 0x31. Si l’on dit maintenant quep est de type short, alors (*p) vaut la concatenation des contenus des deux cases aux adresses9 et A (puisque un short est sur 2 octets), soit le short formé du chiffre 0x31 en octet de poidsfort et 0x2B en octet de poids faible, donc la valeur (en hexadécimal) 0x312B soit 12587 endécimal. De même avec un long, 0x312B0005, soit 824901637 en décimal.

Notez aussi que le typage du pointeur sert aussi aux opérations d’incrémentation et dedécrémentation. Ainsi, si l’on déclare un pointeur de type short, alors l’opération p=p+1; dé-placera le pointeur de deux octets à droite (donc d’un seul short), le pointeur vaudra alors B à lafin de l’opération. De même, si le pointeur est de type long, ce décalage sera de 4. En résumé,le C vous permet de raisonner ”en cases” et non en octets, ce qui est le plus pratique au niveaudu code. Nous reverrons ceci en pratique.

2.3.3 Vie d’un pointeurComme toute variable en langage C, les pointeurs doivent être déclarés au début du corps

des fonctions. Leur déclaration est la suivante :type* nom;

C’est donc le * qui montre que l’on déclare une variable de type pointeur, il n’a alors pasdu tout le sens d’un déféférencement. Par exemple, si on veut déclarer un pointeur q ”detype short” (souvenez vous qu’un pointeur est typé par rapport au déféférencement et pas parrapport à son codage), on écrit simplement :

short* q;

Notez aussi que, comme pour toute variable en langage C, la valeur initiale d’un pointeur,après déclaration, est aléatoire. Ceci signifie qu’il pointe n’importe où en RAM, et même pro-bablement sur des données qui ne concernent pas votre application. Ainsi, écrire (*p) sansavoir d’abord affecté le pointeur à une zone qui vous appartient n’a tout bonnement pas desens et provoque :

– sur une machine dottée d’un système d’exploitation : usuellement votre application vaplanter avec une erreur système du type ”erreur de segmentation”,

– sur une machine sans système d’exploitation : usuellement une écriture ou une lecturedans une zone que vous ne maitrisez pas. C’est en fait le cas le plus ”pervers” car vouspouvez écrire quelque part dans le mapping (donc quelque part sur un port) ce qui peut

23


s’avérer dangereux, ou encore modifier le code même de votre application et la rendreinstable sans que vous puissiez comprendre pourquoi.

Ainsi, il ne faut surtout pas utiliser un pointeur qui n’a pas été préalablementcorrectement initialisé. La première opération à effectuer, dans la vie d’un pointeur, estdonc nécessairement l’affectation (ce qui est d’ailleurs vrai pour toute variable).

Par la suite, les opérations possibles ont déjà été décrites et correspondent à l’affectation,l’incrémentation, la décrémentation et le déréférencement.

2.3.4 Notation ”Tableau”Vous avez déjà utilisé en langage C des tableaux que vous avez déclaré et utilisé de la manière

suivante :int main(void)

2 {

long T[10];

4 unsigned long i;

6 for(i=0;i<10;i++)

{

8 T[i]=0; /*initialise a zero toutes les cases du tableau T.*/

}

10

}

En C, toute expression est typée. Sur cet exemple, on peut facilement dire que T[i] est unlong, c’est même le ieme long du tableau T. En revanche, quel est le type de T ? La réponse est :long*.

En effet, sans le dire explicitement avec la notation [], T est un pointeur, mais un pointeurqui pointe déjà sur une zone de mémoire de 10 long. Cette notation permet donc en un seulcoup d’avoir un pointeur déjà initialisé et prêt à travailler sur un tableau de 10 long. 1 Ainsi, onpeut tout à fait écrire la chose suivante :

1 int main(void)

{

3 long T[10];

long* p;

5 p=T; /*possible car p et T sont de meme type !*/

unsigned long i;

7

for(i=0;i<10;i++)

9 {

*p=0; /* initialise a zero toutes les cases du tableau T.*/

11 p=p+1; /* on fait avancer le pointeur d’une case a droite.*/

}

13

}

1. Notez que cette technique (dite ”allocation statique”) a au moins un défaut majeur : Il faut éviter d’allouerdes tableaux de grande taille par cette méthode, nous verrons pourquoi lorsque nous parlerons plus en détaild’allocation mémoire.

24

2.3 • Les Pointeurs

On peut aussi noter des équivalences entre les deux notations :

– *p=p[0];

– *(p+1)=p[1];

De même, pour accéder à la case numéro i du tableau T, on peut très bien écrire *(T+i).Ainsi, le programme initial peut tout aussi bien s’écrire :

int main(void)

2 {

long T[10];

4 unsigned long i;

6 for(i=0;i<10;i++)

{

8 *(T+i)=0; /* initialise a zero toutes les cases du tableau T.*/

}

10

}

La seule chose qui différencie p et T est que les opérations du type incrémentation et dé-crémentation ne sont autorisées que sur p et pas sur T, simplement parce que si l’on déplace Ton perd l’information sur le départ du tableau.

2.3.5 Opérateur Adresse

Lorsque l’on crée des variables en langage C, il est clair que chaque variable prend un certainespace en mémoire : si la variable est un short, la quantité utilisée est 2 octets, si la variable estun long, cette quantité vaut 4 octets. Cette mémoire réservée est donc située ”quelque part”en RAM et est donc située à une certaine adresse.

On peut demander au langage C de fournir l’adresse d’une telle variable, avec l’opérateurunaire ”&”. Imaginons que l’on écrive le programme suivant et que cela corresponde à l’implantationen mémoire (arbitraire) donnée sur la figure de droite 2 :

2. Notez que la représentation qui est donnée ici des chiffres est la représentation ”naturelle” et correspondnotamment à ce qui est fait en pratique sur les processeurs Motorola et IBM. Pour d’obscures raisons historiques,le codage sur les processeurs Intel est quelque peu différent (inversion des poids forts et poids faibles) et n’est pasreprésenté ici, cette ”originalité” existant en dépit du bon sens ...

25


1 long a;

short b;

3 char c,d;

5 a=0x2AEFF;

b=257;

7 c=’A’;

d=0xFF;

2FA F080

2FA F07F

2FA F07E

0

2FA F081

2FA F082

2FA F083

2FA F084

2FA F085

2FA F086

2FA F087

2FA F088

2FA F089

2FA F08A

2FA F08B

Fin de la RAM

a

b

cd

000014

02AEFF010141FFDE081F

A partir de cet exemple :– &a vaut donc 2FA F080,– &b vaut donc 2FA F084,– &c vaut donc 2FA F086,– &d vaut donc 2FA F087.

Il reste à noter que comme toute expression en C est typée, il faut pouvoir attribuer untype à une expression du genre &a. Pour savoir quel type attribuer à cette expression, il fautremarquer que l’opération & sur une variable est en quelque sorte l’opération réciproque del’opération * sur un pointeur. En effet :

– * permet en quelque sorte de ”passer” d’une adresse (un pointeur) à une valeur,– & permet de ”passer” d’une valeur à son adresse.Dans la mesure où &a est l’adresse d’un long, on peut considérer que c’est un pointeur sur

un long, son type sera donc long*. De même, le type de &d sera char*.

2.3.6 Conclusion intermédiaireLes notions rappelées ici sont absolument fondamentales pour la suite du cours : l’utilisation

des pointeurs, des opérations sur les pointeurs, et de l’opérateur adresse permettent un en-semble de ”tours de magie” qui sont à proprement parler l’objectif fondamental de la suite dece cours.

2.4 Préprocesseur et CompilationVous avez tous vus dans les programmes en langage C des instructions en tout début de

fichier du style :#include <stdio.h>

Dans l’exemple ci-dessus, la commande #include, vous le savez pour l’avoir déjà utilisé,sert entre autres à fournir au langage C la connaissance de fonctions d’affichage et de saisieque sont printf et scanf.

Il est important de noter que ces instructions ne sont pas du langage C à proprement parlermais ce que l’on appelle des ”commandes pré-processeur”. Les commandes pré-processeur onttoutes pour caractéristique, en terme de syntaxe, d’être précédées d’un #.

26

2.4 • Préprocesseur et Compilation

2.4.1 Schéma de CompilationDe plus, si l’on parle de ”commande pré-processeur”, c’est que ces commandes sont in-

voquées avant l’étape de compilation. Le schéma de compilation d’un programme en C estdonné sur la figure 2.2.

Edition des LiensVérification que toutesles fonctions appelées

sont définies

Fichier "Objet

Compilé"(xxx.O)

Fichier TexteContenant du

Codeen Langage C

(xxx.C)

Pré-CompilationInterprétation de

toutes les commandesen #

CompilationGénération de

Code Assembleur puis de Code Machine

à partirdu fichier pré-Compilé

ProgrammeExécutable

PROJET

Fichier "Objet

Compilé"(yyy.O)


Codeen Langage C

(yyy.C)






Fichier "Objet

Compilé"(zzz.O)


Codeen Langage C

(zzz.C)






Figure 2.2 – Compilation d ’un projet en Langage C

On voit clairement le cheminement : Le programme, qui n’est rien de plus qu’un ou plu-sieurs fichier(s) texte dont l’extension est ”.C”, passe d’abord à travers une première analyse descommandes préprocesseur (commandes en ’#’). Le programme résultant est à ce moment làpurement du langage C, qui lui peut être donné en entrée du compilateur C. Le résultat est unprogramme assembleur qui est, dans la plupart des cas, immédiatement transformé en codemachine. On obtient alors un fichier compilé ”.O” mais qui n’est pas encore un programmeexécutable, pour deux raisons :

– ce fichier contient le code compilé des fonctions, indépendament les unes des autres,sans qu’aucun lien n’existe entre les appels. Par exemple, si faites un appel à une ”f” dansun fichier C, rien ne garantit que cette fonction existe véritablement dans un des fichierscomposant le projet. Cette vérification sera faite ultérieurement.

27


– un programme exécutable n’est pas seulement du code compilé mais contient égalementune en-tête qui renseigne sur un ensemble de paramètres du programme. Par exemple,dans les programmes écrits pour les systèmes Microsoft, l’en-tête indique si le programmeva exploiter l’API Win32 ou si c’est un programme de type MS-DOS. C’est le genred’information qui permet à Windows XP d’interdire le lancement d’applications MS-DOS. Il se trouve que le ”.O” ne contient absolument pas ce genre d’information

La dernière étape est l’étape ”d’édition des liens”: c’est elle qui va vérifier si toutes les fonc-tions appelées existent bien et ajouter les informations additionnelles (en-tête notamment) quivont faire du programme un vrai fichier exécutable.

2.4.2 Commandes Pré-Processeur usuelles2.4.2.1 #include

Il est une commande que vous connaissez tous, c’est bien entendu #include. Celle-ci per-met d’accéder à des fonctionnalités du type printf et scanf. La syntaxe est la suivante :

#include <librairie.h>

pour une librairie intégrée au langage. Pour une librairie que vous amenez avec votre pro-gramme, la syntaxe est :

1 #include ”librairie.h”

2.4.2.2 #de ne

Nous introduisons ici une nouvelle commande pré-processeur : #define. Cette commandepermet d’effectuer des ”copier/coller” automatiques dans le code, en se basant sur la définitionde nouveaux symboles : c’est ce que l’on appelle des ”macro-commandes”. Voici la syntaxegénérale :

1 #define Symbole Valeur

Lors de son analyse, le pré-processeur va remplacer tous les symboles définis par leur valeur,un peu à la façon d’un copier/coller sur un texte. Ainsi :

1 #define A 50

#define B 12

3

int main(void)

5 {

int i;

7 i=A*B;

}

sera vu par le compilateur comme :

int main(void)

2 {

int i;

4 i=50*12;

}

28

2.4 • Préprocesseur et Compilation

Remarque importante : ici le symbole A n’est pas du tout une variable. Ainsi, si vous écrivez :1 #define A 50

3 int main(void)

{

5 A=2;

}

Ce programme génèrera une erreur de compilation, puisque le compilateur verra :int main(void)

2 {

50=2;

4 }

et que 50 n’est pas du tout une variable à laquelle on peut affecter la valeur 2 ...Autre Exemple :

#define TAILLE 50

2

int main(void)

4 {

long Tab[TAILLE];

6 unsigned long i;

8 for(i=0;i<TAILLE;i++)

{

10 Tab[i]=i*i; /*remplit Tab avec le carre de son indice.*/

}

12 }

Ce programme est avantageux sur le programme suivant :int main(void)

2 {

long Tab[50];

4 unsigned long i;

6 for(i=0;i<50;i++)

{

8 Tab[i]=i*i; /*remplit Tab avec le carre de son indice.*/

}

10 }

car si l’on souhaite changer la taille du tableau, on a une seule modification à faire au niveaudu #define au lieu de chercher tous les ”50” que l’on pourra trouver dans le code. Sur un pro-gramme long, on voit aisément l’avantage.

Attention également, #define permet de remplacer le symbole par des choses plus vastesque par des valeurs. Ainsi, on a tout à fait le droit d’écrire :#define DEBUT_PROGRAMME int main(void) {

2 #define FIN_PROGRAMME }

29


4 DEBUT_PROGRAMME

int i;

6 i=50;

FIN_PROGRAMME

sera vu par le compilateur comme :1 int main(void) {

int i;

3 i=50;

}

Il s’agit donc bel et bien d’un copier/coller ”brutal”.

2.5 Conclusion du ChapitreNous venons de voir deux outils importants du langage C : les pointeurs et le pré-processeur.

Dans la suite du cours, nous allons utiliser ces deux notions (les pointeurs plus particuliè-rement) pour se donner les moyens de réaliser des applications aussi performantes et bienconçues que le langage et notre inspiration le permettent.

30

Chapitre 3

Développement en Bas Niveau

Sommaire3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2 Affichage en Mode Texte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.2.1 Ecriture d’un texte en haut de l’écran . . . . . . . . . . . . . . . . . . . . 323.2.2 Ecriture d’un texte n’importe ou à l’écran . . . . . . . . . . . . . . . . . . 35

3.3 Utilisation de la RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.1 IntroductionLe développement en bas niveau nécessite l’utilisation la plus simple et la plus directe que

l’on puisse faire des pointeurs. Ces derniers vont en effet permettre l’accès aux différents portset interfaces de la machine considérée.

Comme nous l’avons déjà dit, pour ce type de développement, un ensemble de règles sontà respecter :

– La connaissance du Mapping de la machine est absolument indispensable, afin de connaitreles adresses correspondant à la RAM et aux diverses interfaces.

– La RAM est gérée à 100% par le programmeur lui-même, ce qui représente un avan-tage en terme de simplicité pour un petit programme mais peut rendre les choses trèsdélicates avec un programme plus important ou dans une application multitâches.

– Ce genre de développement ne peut avoir lieu que sur une machine sans sytème d’exploitationou dottée d’un système d’exploitation laxiste, sur lequel n’existe pas pas la notion de pro-tection mémoire.

– Les CPU utilisés ne disposent pas nécessairement de fonctions mathématiques câblées,ce qui peut représenter une difficulté en soi.

Cette partie du cours va se baser essentiellement sur quelques exemples utilisant le mappingd’un PC - donné sur la figure 1.2 du chapitre 1 - que l’on suppose fonctionner sous MS-DOS.

3.2 Af chage enMode TexteNous avons vu au chapitre 1 que la RAM video s’étendait de 0xA0000 jusqu’à 0xBFFFF in-

clus. Le PC dispose de plusieurs modes video, mais le mode par defaut est un mode qui a lescaractéristiques suivantes :

– C’est un mode texte : ceci signifie que les cases de cette RAM seront directement inter-prétées comme des caractères. Si c’était un mode graphique, chaque case représenterait

31

3 • Développement en Bas Niveau

un pixel dont on pourrait choisir la couleur.– L’adresse de départ du mode texte est l’adresse 0xB8000, c’est à dire quelque part dans la

RAM video totale disponible.– Chaque caractère est représenté par deux octets successifs, le premier contenant effec-

tivement le caractère à afficher, le second représentant un attribut de couleur et de style(gras, négatif, ...) que nous ne décrivons pas ici.

– on peut afficher, dans le mode de base, 25 lignes de texte, de 80 caractères chacune. Cecirevient à 80× 25 = 2000 caractères, ce qui représente, avec le codage sur 2 octets décritci-dessus, 4000 octets au total.

Tout ceci est résumé sur la figure 3.1.

80 caractères

RAM Video

Ecran

25 li

gn

es

8 bit 8 bit

Caractère Attributs

(0,0)

(0,0) (1,0) (2,0) (78,0) (79,0) (0,1) (1,1) (2,1) (78,1) (79,1) (0,2) (1,2)

(i,j)

(79,0)

(79,24)(0,24)

0xB 8000 0xB 80A0 0xB 8140Ligne 0 Ligne 1

Figure 3.1 – Structure de la RAM Video en mode Texte d ’un IBM-PC

3.2.1 Ecriture d’un texte en haut de l’écranNous avons vu que la RAM video démarrait en 0xB8000. De plus, elle est constituée de

blocs de 2× 8 octets.Ainsi, si l’on veut s’intéresser à cette RAM video, on va devoir utiliser un pointeur calé à

l’adresse 0xB8000 - puisque les pointeurs sont la seule possibilité que l’on a pour manipuler desadresses. Reste à faire le choix du type du pointeur, qui est, rappelons le, typé par rapport auxdonnées qu’il regarde et pas par rapport au codage de l’adresse.

Ici, nous avons deux choix :– Soit un codage en sequence de char : pour accéder au caractère numéro i, il faudra sauter2× i cases. Le pointeur sera alors de type char* (pointeur sur des char).

32

3.2 • Affichage en Mode Texte

– Soit un codage en sequence de short : ceci semble à priori plus approprié que char maispeut poser une difficulté pour séparer le caractère du style et de la couleur. Le pointeursera alors de type short* (pointeur sur des short).

Nous allons ici travailler avec les deux solutions.

3.2.1.1 Utilisation du type char

Pour cette solution, on aimerait instinctivement que le programme soit le suivant :

int main(void)

2 {

char* RamVideo;

4

RamVideo=0x0B8000;

6 }

Ce morceau de code est à priori correct mais est refusé à la compilation sur la ligne 5. Laraison est la suivante : Si l’on fait une analyse des types à gauche et à droite du signe ”égale”,RamVideo est de type char* et 0x0B8000 est une valeur immédiate sur plus de 16 bit, doncimplicitement codée sur un long. Or, en C, la conversion long vers char* n’est pas implicite.Le morceau de programme correct est donc :

int main(void)

2 {

char* RamVideo;

4

RamVideo=(char*)0x0B8000;

6 }

Nous avons ici invoqué l’opérateur de conversion (on dit ”de casting”) qui force la conver-sion du long vers un char*. Ainsi, à gauche et à droite de l’égalité, nous sommes en char*,ce qui convient au compilateur. Nous avons donc, à partir de maintenant, un pointeur appelé”RamVideo” qui pointe bien à la bonne adresse 1. Nous allons maintenant pouvoir travailler enaffichant un texte à l’écran en attaquant directement celle ci et sans invoquer printf.

Provoquons maintenant l’affichage de la séquence ”Salut” à l’écran. Le style correspondantau blanc en affichage normal est le style 0x07. En faisant tout ”à la main”, cela donne (en version”écriture pointeur” et en version ”écriture tableau”) :

1. Il faut quand même mentionner que les choses sont plus complexes en pratique sur les microprocesseursintel de la gamme 80x86 et Pentium sous MS-DOS, et ce, encore une fois, pour de très mauvaises raisons histo-riques. En effet, à cause des différents modèles de gestion de la RAM sur les processeurs intel, la majorité descompilateurs sous MS-DOS nécessitent plutot la syntaxe suivante si l’on travaille avec le système d’adressage debase :char far* RamVideo;

RamVideo=(char far*)0xB8000000;

Les 0 à la fin de l’adresse ne sont pas une erreur de frappe, mais l’explication de leur utilité sort complètementdu cadre de ce cours (se référer à des livres sur l’architecture des processeurs Intel et de l’IBM-PC sous MS-DOS).Encore une fois, il s’agit d’une absurdité historique liée à l’architecture Intel, ce genre de considération n’étanten pratique jamais à prendre en compte sur une autre plateforme, embarquée ou non.

33


int main(void)

2 {

char* RamVideo;

4


6 *(RamVideo)=’S’;

*(RamVideo+1)=0x07;

8 *(RamVideo+2)=’a’;

*(RamVideo+3)=0x07;

10 *(RamVideo+4)=’l’;

*(RamVideo+5)=0x07;

12 *(RamVideo+6)=’u’;

*(RamVideo+7)=0x07;

14 *(RamVideo+8)=’t’;

*(RamVideo+9)=0x07;

16 }

int main(void)

2 {

char* RamVideo;

4


6 RamVideo[0]=’S’;

RamVideo[1]=0x07;

8 RamVideo[2]=’a’;

RamVideo[3]=0x07;

10 RamVideo[4]=’l’;

RamVideo[5]=0x07;

12 RamVideo[6]=’u’;

RamVideo[7]=0x07;

14 RamVideo[8]=’t’;

RamVideo[9]=0x07;

16 }

On a bien rempli les octets pairs avec le texte et les octets impairs avec le style. On peuttout de même faire un peu mieux, surtout si le texte à afficher est un peu long :

int main(void)

2 {

char* RamVideo;

4 char Texte[]=”Bonjour␣a␣Tous␣!”;unsigned long i;

6


8

for(i=0;T[i]!=0;i++)

10 {

*(RamVideo+2*i)=*(Texte+i);

12 *(RamVideo+2*i+1)=0x07;

}

14

}

1 int main(void)

{

3 char* RamVideo;

char Texte[]=”Bonjour␣a␣Tous␣!”;5 unsigned long i;

7 RamVideo=(char*)0x0B8000;

9 for(i=0;T[i]!=0;i++)

{

11 RamVideo[2*i]=Texte[i];

RamVideo[2*i+1]=0x07;

13 }

15 }

Notez le critère d’arrêt de la boucle for qui correspond au fait que les chaines de caractèresen langage C se terminent systématiquement par un 0.

3.2.1.2 Utilisation du type short

L’intérêt du type short est que les données vont être naturellement calées par pas de 16bit. En revanche, ce qui va se compliquer, c’est l’accès à l’octet correspondant au caractèreséparément de celui correspondant au style.

L’idée générale est d’utiliser les opérations sur les bit du C. Rappelons que l’opération <<

correspond au décalage de bit à gauche, et que l’opérateur |correspond à l’opérateur ou logiquebit à bit. En combinant ces deux opérateurs, on peut arriver au programme suivant :

34

3.2 • Affichage en Mode Texte

1 int main(void)

{

3 short* RamVideo;


short valeur;

7

RamVideo=(short*)0x0B8000;

9

for(i=0;T[i]!=0;i++)

11 {valeur=*(Texte+i);

valeur=valeur<<8;

13 valeur=valeur|0x07

*(RamVideo+i)=valeur;

15 }

17 }

1 int main(void)

{

3 short* RamVideo;


short valeur;

7

RamVideo=(short*)0x0B8000;

9

for(i=0;T[i]!=0;i++)

11 {valeur=Texte[i];

valeur=valeur<<8;

13 valeur=valeur|0x07

RamVideo[i]=valeur;

15 }

17 }

3.2.2 Ecriture d’un texte n’importe ou à l’écranDans l’exemple précédent, nous avons écrit au début de la RAM video. Le début de la

RAM video correspond, comme celà est représenté sur la figure 3.1, au coin en haut à gauchede l’écran. Il serait plus sympathique de pouvoir écrire n’importe où. Pour réaliser celà, il fautbien comprendre le fonctionnement de la mémoire video. Avant même de commencer, onpeut constater qu’il y a une difficulté : la RAM est graduée selon un seul ”axe” (les adresses)alors qu’une image est nécessairement graduée selon deux axes x et y. Il faut donc trouver uneloi de conversion entre un espace à une dimension (la RAM) et un espace à deux dimensions(l’image). Dans cette partie, nous ne développerons que la version avec un pointeur sur des int.

D’abord, quelques remarques :– Si l’on souhaitait écrire sur la première ligne mais à 4 caractères du bord de l’écran, il

suffirait de commencer à l’adresse 0xB8000 décalée de 4 short.– Les lignes débutent toutes sur un multiple de 80 short (soit 80*2=0x50*0x2=0xA0 en oc-

tets) à partir de l’adresse 0xB8000. Ainsi, si l’on veut écrire un texte au début de la ligne 1(donc de la deuxième ligne), il suffit de commencer à écrire à partir de l’adressse 0xB80A0,comme indiqué sur la figure 3.1.

– Ainsi, pour écrire à partir du 3eme caractère de la deuxième ligne, il faut écrire à partirde l’adresse 0xB8000+A0+2*3=0xB80A6

Donc, pour se trouver sur la bonne ligne, il faut sauter autant de fois qu’il faut (y fois) 2 × 80octets soit 80 short, et ensuite il faut ajouter x short pour le décalage sur x. Ainsi, pour trouverle bon décalage en RAM video, exprimé en short, qui correspond à la position x, y à l’écran, ilsuffit d’écrire : k=y*80+x

Le programme devient :1 int main(void)

{

3 short* RamVideo;


35


short valeur;

7 short x,y,decalage;

9 RamVideo=(short*)0x0B8000;

x=7; y=11;

11 decalage=y*80+x;

13 for(i=0;T[i]!=0;i++)

{valeur=*(Texte+i);

15 valeur=valeur<<8;

valeur=valeur|0x07

17 *(RamVideo+decalage+i)=valeur;

}

19

}

Notez que si le texte est trop grand, étant donnée la structure d’une RAM video, la fin dutexte s’affichera naturellement au début de la ligne suivante.

3.3 Utilisation de la RAMJusqu’ici, nous avons utilisé ”un peu” de RAM à travers les quelques variables que nous

avons déclaré. Nous l’avons dit plus haut, utiliser l’allocation statique - c’est à dire des décla-rations du type char Tab[50]; - peut s’avérer dangereux pour de grands tableaux. Où se situele problème ? Le problème est que le Langage C utilise une petite zone de RAM qu’il réservepour stocker ses variables. Cette zone est appelée ”la pile” (stack en anglais). Comme cettezone est limitée et relativement réduite - on estime que les variables n’utilisent pas une grandequantité de mémoire, ce qui est raisonnable - réserver un tableau important est inadéquate :on risque un ”dépassement de pile” (Stack Overflow en anglais). Ainsi, pour les grands tableaux,il est largement préférable d’opter pour une autre solution.

Dans le cas d’un développement sans système d’exploitation, encore une fois, vous êtes”seul maître à bord”. Dans le cas de l’utilisation de la RAM, ceci signifie que vous décidez vous-même des emplacements où vous allez stocker des données, pour peu que ces emplacementscorrespondent au Mapping bien sûr. Notez que ceci n’est valable que pour le développe-ment sans système, et ne l’est pas sous MS-DOS par exemple, qui lui implémenteune gestion de la mémoire que vous êtes tenus d’utiliser. Ainsi, avec le Mapping d’unPC dotté de par exemple 640ko de RAM, et en absence de MS-DOS, on sait qu’il y a de laRAM de l’adresse 0x400 à l’adresse 0x99999. Si, pour votre application, vous avez besoin d’untableau de par exemple 50000 long, vous décidez simplement que ce tableau peut commencerau début de la RAM. Il faut tout de même prendre garde que la pile du Langage C n’y soitpas déjà, mais c’est un paramètre que vous pouvez fixer à la compilation. Vous obtenez donc lecode suivant pour remplir ce tableau par exemple d’une serie de 0 :#define TAILLE_TABLEAU 50000

2

int main(void)

4 {

long* TableauRAM;

6 unsigned long i;

36

3.3 • Utilisation de la RAM

TableauRAM=(long*)0x400;

8

for(i=0;i<TAILLE_TABLEAU;i++)

10 {TableauRAM[i]=0;

}

12 }

Si vous avez besoin de gérer un autre tableau, encore une fois, à vous de faire attention à ceque vous utilisez déjà ainsi que de la place prise par la pile.

37

38

Chapitre 4

Développement au niveau Système

Sommaire4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.2 Gestion Standard de la RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.2.1 La problématique et sa Solution Système . . . . . . . . . . . . . . . . . . 404.2.2 Application au Langage C . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2.3 Confrontation Allocation Statique/Allocation Dynamique . . . . . . . . 47

4.3 Gestion des Fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.3.1 Aspect Système . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.3.2 Accès aux fichiers en Langage C . . . . . . . . . . . . . . . . . . . . . . . . 494.3.3 Gestion du Curseur sur Fichiers . . . . . . . . . . . . . . . . . . . . . . . . 54

4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.1 IntroductionLes choses sont ici bien différentes. Contrairement à ce qui se passe en bas niveau, il

faut maintenant prendre en compte l’existance du système. Le système vous rendra de grandsservices, encore faut il que vous sachiez dialoguer avec lui. Notez aussi qu’il faut vraiments’imprégner de la philosophie d’utilisation du système et d’éviter de détourner les outils qu’iloffre (pour une autre utilisation que celle prévue) de façon à ce que l’application ait toutes leschances de continuer à fonctionner sur une autre version de ce même système.

A ce titre, il faut préciser que les systèmes d’exploitation n’offrent pas tous les mêmespossibilités. Si l’on compare par exemple MS-Dos et Windows XP, les systèmes sont très dif-férents en apparence (l’un est en mode texte, l’autre en mode graphique notamment), maisles différences à un niveau plus profond sont tout aussi importantes : MS-Dos ne gère pas laprotection mémoire, ce qui permet un accès direct aux périphériques comme nous l’avons vuprécédemment (cas de la RAM video, du Port Série, etc ...), alors que Windows XP bloque cetaccès et impose de passer par le système d’exploitation pour utiliser les périphériques.

Ils ont malgré tout un ensemble de choses en commun, dans la mesure ou chacun d’eux estun système d’exploitation :

– Ils permettent tous les deux une gestion de la mémoire vive (RAM) : si sur une machinesans OS on peut faire ce que l’on veut en terme d’utilisation de blocs de RAM, les chosessont très différentes en présence d’un système. En effet, le système recence pour vous lesblocs utilisés par l’ensemble des programmes en cours de fonctionnement, dans le butsimple de savoir quels blocs sont disponibles à chaque instant. La contrepartie est que

39

4 • Développement au niveau Système

vous devez passer par le système d’exploitation pour pouvoir utiliser un bloc de RAM. Ilest de toute façon presque impossible de gérer la RAM soi-même sur un système commeWindows XP à cause justement de la protection mémoire.

– Ils offrent également une gestion des fichiers. Exactement comme pour la RAM, le sys-tème s’occupe de gérer les blocs utilisés, l’espace libre, la hiérarchie des répertoires etdes fichiers, la correspondance entre le nom d’un fichier et les données qui lui sont as-sociées, etc ... On parle de ”Système de Fichiers”. Encore une fois, pour permettre unetelle gestion, il existe une contrepartie : Il faut impérativement passer par le systèmed’exploitation pour gérer les fichiers et surtout pas essayer de les gérer à la main. Unetelle chose est de toute façon quasi-impossible sur les OS modernes.

– Enfin, une gestion standardisée de certaines entrées/sorties élémentaires, telles que l’affichageà l’écran et la saisie au clavier.

Il reste à préciser que l’accès à la RAM, aux fichiers et aux entrées sorties ne se fait pas defaçon identique sous MS-Dos, Windows XP, ou avec les Unix et encore sous MacOs X. Pources trois entités, qui sont absolument fondamentales pour une application (toutes les applica-tions ont besoin de RAM par exemple ...), le Langage C propose tout un ensemble de fonctionsstandardisées et exactement identiques quel que soit le système d’exploitation. Ainsi, si l’ondéveloppe une application en langage C se limitant à faire des accès à la RAM, aux fichiers etaux entrèes/sorties en mode texte, on a la garantie que ce même programme pourra fonction-ner quel que soit le système et l’architecture matérielle, moyennant une recompilation tout demême. Ce sont précisément ces fonctions que nous allons utiliser dans tout ce chapitre.

4.2 Gestion Standard de la RAM

4.2.1 La problématique et sa Solution SystèmeLorsque vous développez un programme qui va fonctionner sur une machine dottée d’un

système, vous n’avez absolument pas la garantie qu’il va être chargé à chaque fois au mêmeemplacement en RAM : celà dépend des opérations qui ont déjà été effectuées par l’OS avantle lancement de votre application.

Prenons un exemple simple. Imaginons qu’au moment où vous lancez votre application,une autre application soit déjà lancée. La RAM est alors dans l’état suivant :

RAM

400

AutreProgramme

NotreProgramme Système

500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800

Figure 4.1 – Exemple d ’Etat de la RAM

Les zones grisées correspondent aux zones de RAM déjà réservées, les zones blanches sontles zones libres. Pendant le déroulement du programme, il est plus que probable que votreapplication ait besoin de RAM. Or, étant donné que vous ne maîtrisez pas du tout l’état dela RAM au moment où vous lancez l’application, vous ne pouvez pas décider que ce bloc seraà une adresse pré-définie : vous risquez d’empiéter sur une zone déjà utilisée par une autreapplication. Dans ces conditions, la seule alternative est de prendre en compte l’état de la

40

4.2 • Gestion Standard de la RAM

RAM. Et celà, le système le fait pour vous. Tout ce que vous avez à faire, c’est demander ausystème une certaine quantité de RAM, lui va essayer de trouver - si c’est possible bien sûr -un espace libre pour vous, et va vous dire à quelle adresse cet emplacement se situe. Ensuite,le système marque que ce bloc est pris par votre application de façon à ce qu’aucune autreapplication ne vienne empiéter dessus.

4.2.2 Application au Langage C

4.2.2.1 La fonctionMalloc

Pour réaliser tout celà, le Langage C met à disposition une fonction absolument fonda-mentale : malloc. Cette fonction est justement celle qui va demander au système de réserverla quantité de RAM dont vous avez besoin et qui va vous fournir l’adresse de départ du blocconsidéré. Elle appartient à la librairie stdlib. Voici le prototype de la fonction malloc :

void* malloc(unsigned long taille);

Comme attendu :– malloc prend en paramètre une valeur entière qui peut être importante (unsigned long).

Cette valeur est la quantité de RAM dont vous avez besoin et que vous souhaitez réserver.Attention, cette quantité est exprimée en octets. Ainsi, si vous avez besoin d’un tableaude 50 short, il faudra réserver 100 octets, donc demander un malloc(100);

– malloc renvoit bien une adresse sous forme d’un pointeur (*), mais un pointeur particu-lier : un pointeur void*.

Dans un premier temps, nous ne nous soucions pas du type void* de ce pointeur : cequi compte, c’est que malloc renvoit l’adresse de départ du bloc, sous forme de pointeur.Ainsi, on peut écrire intuitivement notre première allocation mémoire utilisant le systèmed’exploitation, ici sur un tableau de 50 short que nous remplissons ensuite de zeros :

1 #include <stdlib.h> /* inclusion de la librairie stdlib */

3 int main(void)

{

5 short* T;

unsigned long i;

7

T=malloc(100); /* demande 100 octets (donc 50 short)

9 au systeme d’exploitation */

for(i=0;i<50;i++)

11 {

T[i]=0;

13 }

15 }

Ce morceau de code, qui semble pourtant complètement logique, est refusé par la majoritédes compilateurs. L’erreur provient encore une fois d’un problème de type : nous demandonsau C d’affecter à un pointeur de type short* la valeur d’un pointeur de type void*, puisquemalloc renvoit un void*.

41


4.2.2.2 Pointeurs void*

Mais qu’est ce qu’un pointeur ”void*” ? Revenons d’abord à ce qu’est un pointeur de typeshort* par exemple. Un pointeur short* est un pointeur qui voit la mémoire comme une suc-cession de short. Ainsi, le déréférencement fournit des informations sur un short, et toutes lesopérations de déplacement du pointeur se font sur un nombre entier de short.

”void” signifie ”vide”. Ainsi, un pointeur de type ”void*” est un pointeur sans type associé.Ceci signifie notamment qu’il est impossible de déréférencer le pointeur, puisqu’on ne sait pasquelle est la taille d’une case, et qu’on ne peut pas non plus le déplacer en incrémentant oudécrémentant pour la même raison. Alors a quoi servent ces pointeurs ?

Le fait que malloc renvoit un pointeur de type void* signifie que lorsque vous faites l’allocationmémoire, la fonction malloc ne sait pas à priori sur quel type de données vous allez travailler.Tout ce que fait malloc, c’est vous fournir l’adresse de départ, et pour celà un pointeur de typevoid* est amplement suffisant. Ce sera donc à vous à convertir le pointeur avec le type qui cor-respond à ce que vous cherchez : il va falloir encore une fois invoquer les opérateurs de casting.Voici sur un exemple avec un tableau de 50 short une allocation mémoire typique écrite enLangage C :


3 int main(void)

{

5 short* T;

unsigned long i;

7

T=(short*) malloc(100); /* demande 100 octets (donc 50 short)

9 au systeme d’exploitation

+ conversion du pointeur void* renvoye par malloc

11 en pointeur short* */

for(i=0;i<50;i++)

13 {

T[i]=0;

15 }

17 }

Cette syntaxe, si elle vient d’être justifiée, est à connaître par coeur sans hésitation car elleest extrèmement usuelle. Notez également que cette technique d’utilisation de la mémoires’appelle allocation dynamique, par opposition aux tableaux déclarés avec la syntaxe [] quieux sont appellés tableaux statiques.

4.2.2.3 Opérateur sizeof()

Cet opérateur va nous permettre d’éviter d’avoir à calculer le nombre d’octets correspon-dant au nombre de cases dont nous avons besoin. En effet, si pour certains types (respecti-vement char, short et long) les tailles en octet n’amènent aucune ambiguité (respectivement1,2 et 4), pour d’autres types (notamment int et float), la taille en octet dépend de plusieursfacteurs 1 dont nous ne discuttons pas ici.

1. le type int fait 16 bit sur les machines à bus de données 16 bit et 32 sur les machines à bus 32 bit. Pire : surun Pentium sous MS-DOS, l’int fait 16 bit alors qu’il en fait 32 sous Windows NT/2000/XP ... De plus, la taille

42


L’utilité de cet opérateur est donc évidente, surtout si l’on souhaite pouvoir recompiler lesprogrammes et les voir fonctionner quelle que soit la plateforme et le système utilisés. sizeofest un opérateur qui renvoit sous forme d’entier la taille d’un type passé en paramètre expriméeen octets. Typiquement,sizeof(char) vaut 1,sizeof(short) vaut 2,sizeof(long) vaut 4. Voiciles valeurs que fournit cet opérateur sur quelques exemples sur deux processeurs différents :

CPU 16 bit CPU 32 bit CPU 64 bitsizeof(char) 1 1 1sizeof(short) 2 2 2sizeof(int) 2 4 4sizeof(long) 4 4 4sizeof(float) dépend du CPU dépend du CPU dépend du CPUsizeof(char*) 2 4 8sizeof(short*) 2 4 8sizeof(int*) 2 4 8sizeof(long*) 2 4 8sizeof(float*) 2 4 8

Vous constatez ici un résultat que l’on connait déjà mais qu’il est bon de confirmer : la tailled’un pointeur ne dépend pas du type des données sur lesquelles il pointe, puisque sa taille estcelle d’une adresse. Ici, avec le CPU 16 bit, le bus d’adresse fait 16 bit donc 2 octets, et avec leCPU 32 bit, le bus d’adresse fait 32 bit donc 4 octets.

Grâce à cet opérateur, on peut rendre plus générale l’écriture du malloc de façon à ne pasà se poser la question de la taille d’un type. Ainsi, voici, définitivement cette fois, la bonnesyntaxe pour l’appel de malloc (toujours sur l’exemple des 50 short) :


3 int main(void)

{

5 short* T;

unsigned long i;

7

T=(short*) malloc(50*sizeof(short)); /* demande 50*sizeof(short)

9 au systeme d’exploitation (soit 100 octets en tout)

+ conversion du pointeur void* renvoye par malloc

11 en pointeur short* */

for(i=0;i<50;i++)

13 {

T[i]=0;

15 }

17 }

du float change en fonction du type de processeur : dans la série motorola 680x0, le codage se fait sur 40 bit,alors que sur motorola PowerPC et Intel il se fait sur 32 bit. Il y a encore d’autres originalités qui ne sont pasdécrites ici, ce qu’il faut retenir c’est que le codage des entiers et flotants tend à changer en fonction de l’OS etdu microprocesseur.

43


Cette fois ci, la syntaxe est plus claire car on voit dans le code que l’on alloue vraiment 50short. Le travail fait par malloc est exactement le même, il s’agit ici d’améliorer la lisibilité duprogramme et de le rendre plus facilement transportable sur une autre machine.

Avec cette technique, il est possible d’allouer de très grands blocs (de la taille de la RAMtotale disponible si tout se passe bien ...) sans aucun risque de dépassement de pile, puisque lesblocs ne sont ici pas alloués sur la pile de l’application.

Ainsi, il est fortement déconseillé de créer des tableaux statiques dont la taille dépendraitd’un choix de l’utilisateur. En effet, si l’utilisateur choisit pendant l’exécution la taille du ta-bleau, ce tableau est potentiellement très grand et risque donc de dépasser de la pile. Notezégalement que dans de plus anciennes versions du C, ce type d’allocation ne permettait pasde créer des tableaux dont la taille est décidée pendant l’exécution et pas au moment de lacompilation, comme c’était le cas avec les tableaux statiques.

Le résultat est que le code suivant n’est pas conseillé en C :

A EVITER1 #include <stdlib.h>

3 int main(void)

{

5

7 unsigned long taille;

unsigned long i;

9 printf(”taille␣du␣tableau␣?”);scanf(”%ld”,&taille);

11

short T[taille]; //allocation statique

13 //d’un tableau dont la taille depend

//d’un choix de l’utilisateur

15 //DECONSEILLE

17 for(i=0;i<taille;i++)

{

19 T[i]=0;

}

21 }

Pour choisir la taille d’un tableau pendant l’exécution du programme, la bonne solution estl’allocation dynamique, comme le montre le programme suivant :

BONNE VERSION DU PROGRAMME1 #include <stdlib.h>

3 int main(void)

{

5 short* T;

unsigned long taille;

7 unsigned long i;

44


printf(”taille␣du␣tableau␣?”);9 scanf(”%ld”,&taille);

11 T=(short*)malloc(taille*sizeof(short));

//allocation dynamique : OK

13

for(i=0;i<taille;i++)

15 {

T[i]=0;

17 }

}

4.2.2.4 Echec d’Allocation

Il est possible que le bloc que vous demandez soit plus grand que la place disponible enRAM. Dans ce cas, malloc renvoit un pointeur dont la valeur est particulière : un pointeurNULL.

La valeur NULL est une adresse spécifique - définie dans stdlib.h - à laquelle aucun blocne peut être alloué. On peut donc choisir une place dans le Mapping qui est en dehors de laRAM, par exemple l’adresse zero (c’est usuel) puisqu’elle correspond, dans le cas des PC, à uneinterface, donc pas à un lieu disponible pour une allocation mémoire.

Ainsi, il est bon de vérifier après avoir invoqué malloc, si l’allocation a été correctementréalisée :

#include <stdlib.h>

2

int main(void)

4 {

short* T;


unsigned long i;


10

T=(short*)malloc(taille*sizeof(short));

12 if(T!=NULL) /* Si l’allocation s’est bien deroulee */

{

14 /*On peut travailler avec le bloc*/

}

16 else {

printf(”Impossible␣d’allouer␣la␣memoire!␣Fin␣du␣Programme.”);18 }

20 }

45


4.2.2.5 Libération de lamémoire

S’il est essentiel de pouvoir allouer des tableaux de mémoire, il est également important deles libérer lorsque votre application ne les utilise plus.

Prenons par exemple le cas d’un traitement de texte. Imaginons que vous ayez chargé deuxtextes différents. Lorsque vous fermez la fenêtre de l’un des textes, il est clair que celà signifieque vous ne travaillez plus, temporairement, sur le texte en question. Il est donc dommage, àpartir de ce moment, d’avoir un bloc de RAM réservé et persistant pour ce texte auquel vousn’accédez plus. C’est exactement à celà que sert la libération de la mémoire.

Pour cela, la bibliothèque stdlib fournit encore une fois une fonction :1 void free(void* ptr);

.Pour libérer un bloc de RAM, free a simplement besoin de l’adresse de départ du bloc,

c’est à dire celle qui était fournie par malloc. Ainsi, son utilisation pourrait être la suivante :1 #include <stdlib.h>

3 int main(void)

{

5 short* T;


7 unsigned long i;



if(T!=NULL)

13 {/*travail avec le bloc de memoire*/

15 free(T);

}

17 }

Notez que ca n’est pas le nom de la variable qui compte mais bel et bien la valeur de l’adresse.Ainsi, le code suivant ne libère pas correctement la mémoire, simplement parce que l’adressefournie à free n’est pas celle qui avait été donnée par malloc :

1 #include <stdlib.h>

3 int main(void)

{

5 short* T;


7 unsigned long i;



if(T!=NULL)

13 {

46



15 {

*T=0;

17 T=T+1;

}

19

free(T); /*ici, T n’est pas place

21 sur l’adresse de depart du bloc.*/

}

23 }

Ainsi, si l’on souhaite travailler en déplaçant le pointeur, il faut toujours garder la mémoirede l’adresse de départ. La bonne syntaxe pour ce genre de manipulation serait donc :


3 int main(void)

{

5 short* T;

short* p;


unsigned long i;


11

T=(short*)malloc(taille*sizeof(short));

13 if(T!=NULL)

{

15 p=T;


17 {

*p=0;

19 p=p+1;

}

21

free(T); /*ici, T est toujours place au bon endroit,

23 c’est p qui a bouge*/

}

25 }

4.2.3 Confrontation Allocation Statique/Allocation Dynamique

Nous résumons dans un tableau les caractéristiques des deux stratégies d’allocation de mé-moire, ici sur un tableau de 50 short :

47

4 • Développement au niveau SystèmeAllocation Statique Allocation Dynamique

Allocation short T[50];

short* T;

T=(short*)malloc(50* si-

zeof(short));

Libération

Automatique : la libération de lamémoire associée à un tableau sta-tique se fait lorsque le programmerencontre l’accolade } de ferme-ture de la fonction. Notez quetoutes les variables d’une fonctionsont libérées à ce moment là éga-lement.

free(T);

Notez que le fait de devoir libérer”à la main” la mémoire peut sem-bler contraignant mais s’avèrerafort utile plus tard. En effet, aulieu d’estimer que c’est contrai-gnant, on peut considérer aussique l’allocation mémoire ”survit” àla fermeture de la fonction.

Taille des Blocs Limitée à la taille de la pile - ne pasdépasser quelques ko en pratique,sinon risque de plantage du pro-gramme par dépassement de pile(message ”stack overflow”).

Si la RAM est correctement géréepar l’OS, peut aller jusqu’à la taillecomplète de la RAM libre.

Notez qu’en règle générale, si on hésite entre allocation statique et dynamique, on ne ferajamais une bêtise en optant pour l’allocation dynamique. L’allocation dynamique ajoute tout demême une contrainte dont il faut rester conscient : il ne faut pas oublier de libérer la mémoirequi a été allouée, alors qu’en allocation statique la libération est implicite.

Plus généralement, on optera pour une allocation statique lorsque la taille des donnéesallouées est constante (ne dépend pas des choix de l’utilisateur) et raisonnablement petite(typiquement quelques ko grand maximum).

4.3 Gestion des Fichiers

4.3.1 Aspect SystèmeLe but est ici de pouvoir créer un fichier, lire des informations dans un fichier existant,

écrire des modifications dans un fichier et compléter un fichier. L’accès aux fichiers se faittoujours selon un protocole bien précis qu’il faut impérativement respecter :

1. Ouverture du Fichier : Cette phase correspond à déclarer au système que l’on va tra-vailler avec un fichier bien précis. Lorsque l’on ouvre le fichier, on fournit au systèmele chemin + le nom, ainsi que le type d’opération que l’on compte faire avec ce fichier :lecture, écriture, lecture/écriture, création, etc ...

2. Travail sur le Fichier : Typiquement les accès en lecture/écriture pour récupérer ouimposer le contenu du fichier. C’est bien sûr la phase qui nous intéresse le plus, mais laphase d’ouverture est indispensable pour que tout fonctionne correctement.

3. Fermeture du Fichier : Cette phase est importante pour au moins une bonne raison :Elle permet de liberer le fichier. En effet, lorsque vous ouvrez un fichier en écriture parexemple, il est naturel que le système interdise à toute autre application un accès concur-rent en écriture. En revanche, lorsque vous ouvrez un fichier en lecture seule, le fichierest bien sûr disponible en lecture pour les autres applications. La phase de fermeture est

48

4.3 • Gestion des Fichiers

donc essentielle pour que votre application rende le fichier disponible aux autres appli-cations dès que votre travail est terminé.

Vous voyez donc que les phases d’ouverture et de fermeture sont fondamentales, car ellespermettent au système de gérer les accès concurrents aux fichiers par différentes applications.

4.3.2 Accès aux chiers en Langage C

Nous allons ici décrire chacune des étapes en Langage C. Il faut en premier lieu savoir queles fonctions d’accès aux fichiers sont contenues dans stdio.h. Ensuite, que les fonctions quivont nous intéresser dans un premier temps sont au nombre de 4 : fopen, fread, fwrite, etfclose.

4.3.2.1 fopen

C’est la fonction qui va permettre l’ouverture des fichiers. Voici le prototype de cette fonc-tion :

1 FILE* fopen(char* nomComplet,char* acces);

La fonction prend en paramètre deux chaines de caractères :– nomComplet est simplement une chaine de caractères qui contient le chemin d’accès au

fichier suivi du nom du fichier :• Sur un exemple sous Unix, si on a le fichier ”monFichier.txt” situé dans ”/home/

moi/”, cette chaine sera ”/home/moi/monFichier.txt”.• Sur un exemple sous Windows, si on a le fichier ”monFichier.txt” situé dans ”C :\

Documents and settings\Moi\”, cette chaine sera ”C :\\Documents and Settings\\Moi\\monFichier.txt”. Notez d’abord que les systèmes Unix utilisent le shash nor-mal pour séparer les éléments d’un chemin, alors que Windows utilise l’antislash 2. Pouraccéder aux antislashes, en C, il faut doubler le symbole ”\” : ceci est lié au fait que lescaractères spéciaux en C sont précédés d’un ”\”.L’exemple typique que vous utilisezsouvent est le retour à la ligne : ”\n”.Ainsi, pour accéder au caractère ”\”lui mêmesans que le caractère suivant ne soit pris comme une commande, le C prévoit que l’ondouble le symbole. Ainsi, le codage de ”\”en C est bel et bien ”\\”.

– acces est une chaine de caractères décrit de quelle manière vous allez accéder au fichierlors des opérations futures : lecture, écriture, lecture/écriture. Voici une description decette chaine :

2. Ce choix est vraissemblablement lié au fait que Microsoft n’a pas voulu être accusé de plagiat en utilisantle même symbole que les unixiens ...

49

4 • Développement au niveau SystèmeChaine Description”r” Ouverture du Fichier en Lecture Seule.”r+” Ouverture du Fichier en Lecture et Ecriture. Le fichier n’est pas créé

s’il n’existe pas.”w” Ouverture du Fichier en Ecriture. Efface le fichier existant s’il y en a un

et le remplace par un fichier vide. Le fichier est créé s’il n’existe pas.”w+” Ouverture du Fichier en Lecture/Ecriture. Efface le fichier existant s’il y

en a un et le remplace par un fichier vide. Le fichier est créé s’il n’existepas.

”a” Ouverture du Fichier en Ecriture. N’efface pas le fichier existant s’il yen a un. Le fichier est créé s’il n’existe pas.

”a+” Ouverture du Fichier en Lecture/Ecriture. N’efface pas le fichier exis-tant s’il y en a un. Le fichier est créé s’il n’existe pas.

Reste à s’intéresser à ce qui est renvoyé par la fonction. Si on fait une analyse rapide, fopenrenvoit un pointeur sur un type que nous n’avons encore jamais rencontré : le type FILE. Ce quiest important avec la gestion des fichiers, c’est que l’on se moque complètement du fait quefopen renvoit un pointeur FILE* : ici, on va pouvoir considérer que ce FILE* est simplementune valeur, et c’est bel et bien le cas puisque c’est un pointeur donc une adresse. C’est cettevaleur qui va identifier le fichier dans toute la suite des opérations. Ainsi, une fois le fichierouvert, c’est ce FILE* qui représente le fichier et plus son nom et son chemin. A noter aussique si l’on tente par exemple d’ouvrir en lecture seule un fichier qui n’existe pas, le pointeurFILE* renvoyé prend la valeur NULL encore une fois.

Sur un exemple :

1 #include <stdio.h>

3 int main(void)

{

5 FILE* f; /*declaration d’un identificateur

pour gerer un fichier*/

7

9 /*ouverture du fichier en lecture/ecriture

avec effacement s’il existe deja*/

11 f=fopen(”C:\\Documents␣and␣Settings\\Moi\\monTexte.txt”,”w+”);if(f!=NULL)

13 {

15 /* A partir d’ici, f vaut par exemple 0x12345678.

C’est cette valeur qui va representer

17 le fichier pour toutes les operations d’ecriture

et de lecture. Ainsi, il suffira de fournir f

19 aux fonctions dediees a la gestion des fichiers

pour qu’elles comprennent qu’il s’agit

21 du fichier C:\\Documents and Settings\\Moi\\monTexte.txt */

23 }

else

50


25 {printf(”impossible␣d’ouvrir␣le␣fichier”);}

27 }

A partir de la, les fonctions fread et fwrite permettent d’effectuer des échanges entre laRAM et le fichier dans les deux sens.

4.3.2.2 fread

La fonction fread va permettre de lire une certaine quantité de données d’un fichier et dela stocker dans un bloc de RAM dont vous fournissez l’adresse. Le prototype de la fonctionfread est le suivant :

1 long fread ( void* buffer, long tailleElement,

long nbElements,FILE* identificateurFichier);

Encore une fois, examinons les paramètres d’entrée :– identificateurFichier : c’est le paramètre le plus simple à comprendre, il s’agit simple-

ment du FILE* qui est fourni par fopen.– buffer : l’adresse d’une zone de RAM prète à recevoir les données lues. Sa taille doit être

au moins égale à la taille qui va être lue.– tailleElement et nbElements : le produit de ces deux valeurs est la taille des données

qui vont être lues en octets. Les concepteurs de la fonction ont choisi de séparer cettequantité en deux valeurs par rapport aux types. Par exemple, si on veut sauver le contenud’un tableau de 50 short, on mettra le paramètre tailleElement à 2 (ou mieux, à si-

zeof(short)) et le paramètre nbElements à 50. Ceci permet de raisonner en ”cases” aulieu de raisonner en octets.

Reste la valeur de retour : la valeur de retour est simplement le nombre d’éléments qui onteffectivement été lus. Ainsi, si vous avez fixé nbElements à 50 et que le fichier fait seulement40 short, fread renverra 40.

Sur un exemple (on suppose que le fichier f fait une taille de 100 octets) :

#include <stdio.h>


4 int main(void)

{

6 short* p;

FILE* f;

8 unsigned long i;


10

/*reserver de la memoire pour recevoir les donnees*/

12 p=(short*)malloc(50*sizeof(short));

14

/*ouverture du fichier en lecture seule*/

16 f=fopen(”C:\\Documents␣and␣Settings\\Moi\\monFichier.dat”,”r”);

18 /*si le fichier existe bien*/

51


if(f!=NULL)

20 {

/*lecture des valeurs dans le fichier*/

22 taille=fread(p,sizeof(short),50,f);

if(taille!=50)

24 {printf(”seulement␣%ld␣valeurs␣ont␣pu␣etre␣lues␣!\n”,taille);

26 }

28 printf(”Affichage␣des␣Valeurs␣:\n”);for(i=0;i<taille;i++)

30 {

printf(”%ld\n”,p[i]);

32 }

}

34 else

{

36 printf(”le␣fichier␣n’existe␣pas.␣Fin␣du␣Programme.\n”);}

38 free(p);

40 }

4.3.2.3 fwrite

La fonction fwrite fonctionne exactement de la même façon que la fonction fread, mis àpart le fait qu’elle le permet pas de lire mais d’écrire de données dans un fichier. Son prototypeest le suivant :

1 long fwrite ( void* buffer, long tailleElement,

long nbElements,FILE* identificateurFichier);

Les paramètres fournis à la fonction sont exactement les mêmes que ceux de fread, mis àpart le fait que le paramètre buffer ne sert pas à recevoir les informations mais contient lesdonnées à écrire dans le fichier. De plus, la valeur de sortie représente le nombre d’élémentsqui ont pu être inscrits, la valeur ne pouvant être différente de la valeur souhaitée que si l’onarrive en limite de taille du disque. Voici un exemple :

#include <stdio.h>


4 int main(void)

{

6 short* p;

FILE* f;

8 unsigned long i;


10

/*reserver de la memoire pour recevoir les donnees*/

52


12 p=(short*)malloc(50*sizeof(short));

14 /*on remplit le tableau avec des valeurs a stocker.

Ici les 50 premiers entiers pairs*/

16 for(i=0;i<50;i++)

{

18 p[i]=2*i;

}

20

22 /*ouverture du fichier en ecriture*/

/*cree le fichier s’il n’existe pas*/

24 f=fopen(”C:\\Documents␣and␣Settings\\Moi\\monFichier.dat”,”w”);

26 /*si le fichier a bien ete cree/vide*/

if(f!=NULL)

28 {

/*ecriture des valeurs dans le fichier*/

30 taille=fwrite(p,sizeof(short),50,f);

if(taille!=50)

32 {printf(”seulement␣%ld␣valeurs␣ont␣pu␣etre␣ecrites␣!\n”,taille);

34 }

}

36 else

{

38 printf(”le␣fichier␣n’a␣pas␣ete␣cree.␣Fin␣du␣Programme.\n”);}

40 free(p);

}

4.3.2.4 fclose

Reste maintenant à fermer le fichier. Notez que le fichier est automatiquement fermé parle système lorsque vous quittez votre application. Il est cependant très vivement conseilléd’invoquer vous-mêmes fclose, surtout si vous devez libérer l’accès au fichier pour un autreprogramme. La fonction fclose demande simplement l’identificateur du fichier pour le fermer.Son prototype est donc tout simple :

1 long fclose (FILE* identificateurFichier);

avec identificateurFichier le FILE* fourni par fopen. Voici sur un exemple :1 #include <stdio.h>

3 int main(void)

{

5 FILE* f;

7 f=fopen(”C:\\Documents␣and␣Settings\\Moi\\monFichier.dat”,”a+”);

53


9 if(f!=NULL)

{

11 /*travail sur le fichier avec fread et fwrite*/

13

15 /*fermeture du fichier*/

fclose(f);

17 }

}

4.3.3 Gestion du Curseur sur FichiersIl est clair que les fichiers peuvent être de taille bien plus importante que la RAM : prenez

par exemple une séquence video de 30 mn issue d’une caméra numérique, sa taille fait environ10 Go. Il est bien entendu impensable de charger le fichier en entier en RAM pour travaillerdessus puis de le resauvegarder. De plus, on ne travaille jamais sur la totalité de la séquencevideo : on peut très bien travailler par tronçons de quelques dizaines de Mo. Le langage Cpermet ainsi de ne charger et sauvegarder que des fragments du fichier de travail. Ceci sup-pose que nous disposons d’un curseur qui permet d’indiquer sur quelle zone du fichier noustravaillons. C’est justement de la gestion de ce curseur que nous allons parler, en introduisantdeux nouvelles fonctions (toujours incluses dans stdio.h) : fseek et ftell.

4.3.3.1 fseek

C’est la fonction qui permet de positionner le curseur à l’endroit que nous souhaitons. [Arédiger]

4.4 ConclusionNous avons vu dans ce chapitre comment utiliser le système d’exploitation en C pour utili-

ser correctement la RAM - via les pointeurs notamment - et accéder efficacement aux fichiers.Dans la suite de ce cours, nous allons largement utiliser la notion de pointeur pour mettre enplace certaines techniques de programmation avancée.

54

Chapitre 5

Utilisation Avancée des Pointeurs

Sommaire5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.2 Pointeur sur variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.3 Passage de Paramètres d’entrée/sortie à des fonctions . . . . . . . . . . . . . . . 57

5.3.1 Rappel : Passage de Paramètres à une Fonction . . . . . . . . . . . . . . 575.3.2 Rappel : Valeur Renvoyée par une Fonction . . . . . . . . . . . . . . . . . 595.3.3 Passage par Adresse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.4 Renvoi de Pointeur par une Fonction . . . . . . . . . . . . . . . . . . . . . . . . . 625.5 Tableaux de Pointeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655.6 Pointeurs de Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5.1 IntroductionC’est l’un des chapitres les plus difficiles cette année, mais il est essentiel d’en avoir une

bonne compréhension pour développer des applications efficaces. Nous allons ici utiliser lespointeurs ainsi que l’opérateur adresse pour se donner de nouveaux outils pour le développe-ment d’applications.

5.2 Pointeur sur variableNous l’avons vu, toute variable occupe nécessairement une certaine place en mémoire. Sur

un exemple :short a;

2

a=767; /*soit 0x02FF

4 en hexadecimal*/4FF AA00

4FF A9FF

4FF A9FE

0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

Fin de la RAM

a020014

FFAEFF01

55

5 • Utilisation Avancée des Pointeurs

L’état dans lequel se trouve la RAM et qui est illustré ici est totalement arbitraire. En effet,rien ne garantit que les variables seront situées aux adresses indiquées, puisque, nous l’avonsvu, les lieux où les blocs de RAM sont alloués dépendent de l’état de la RAM au moment dulancement de l’application. Ce schéma va simplement servir à appuyer quelques exemples dansla suite de ce cours.

Ainsi, sur cet exemple, on peut affirmer que la variable a se situe à l’adresse 0x4FFBA00.Ainsi, en C, on peut affirmer que &a vaut 0x4FFBA00. Rappelons ici que le type de &a, pour leC, est short*.

Complétons maintenant notre programme :short a;

2 short* p;

4 a=767;

p=&a;

Comme &a est de type short*, l’affectation p=&a est tout à fait correcte syntaxiquement. Onpeut même affirmer qu’à l’issue de cette expression, p vaut 0x4FFBA00, puisque c’est l’adressede a : on dit que p pointe sur a.

Une des particularités des pointeurs est l’opération de déréférencement. Ainsi, on peut sedemander quelle est la valeur de *p. Si on reprend l’exemple ci-dessus, un déréférencementqui ferait la taille d’un short à partir de l’adresse 0x4FFBA00 vaudrait 0x02FF, soit 767, c’est àdire la valeur qui a été affectée à la variable a. Ceci n’est absolument pas une coïncidence, c’estexactement l’effet recherché, c’est à dire accéder à la valeur de a via un pointeur.

On peut voir la chose sous un autre angle : Comme une variable occupe un certain espacede mémoire, on peut estimer que cet espace mémoire est un tableau de une case commençantà l’adresse de la dite variable. En d’autres termes, on peut dire qu’à l’adresse &a, soit 0x4FFBA00,commence un tableau de un short. Et tout ce que l’on a fait, c’est faire pointer p sur ce tableau.

Ainsi, incrémenter ou décrémenter p est dangereux car on ne maîtrise absolument pasl’espace mémoire autour de la variable. Par contre le déréférencement est tout à fait possible.

Prenons maintenant un autre exemple :1 int main(void)

{

3 short a;

short* p;

5

a=767;

7 p=&a;

printf(”a␣=␣%d␣(*p)␣=␣%d\n”,a,(*p));9 a=700;

printf(”a␣=␣%d␣(*p)␣=␣%d\n”,a,(*p));11 (*p)=600;

printf(”a␣=␣%d␣(*p)␣=␣%d\n”,a,(*p));13 }

Commentons ce qui est affiché par ce programme :– ligne 8 : Comme nous l’avons commenté plus haut, le programme affiche :

a = 767 (*p) = 767

En effet, la valeur de a est 767, et p pointe sur a, donc le déréférencement de p vaut lavaleur de a.

56

5.3 • Passage de Paramètres d’entrée/sortie à des fonctions

– ligne 10 : Ici, encore, les choses sont simples : nous modifions la valeur de a à la ligne 9.Le programme affiche donc :a = 700 (*p) = 700

En effet, p pointe toujours sur a et a a simplement changé de valeur.– ligne 12 : Un peu plus compliqué : à la ligne 11, nous changeons la valeur de ce qui est

pointé par p, c’est à dire la chose située à l’adresse 0x4FFBA00, donc la valeur de la variablea elle-même. Ainsi, le programme affiche :a = 600 (*p) = 600

Ainsi, si l’on fait pointer un pointeur sur une variable, les actions faites sur la variable serépercutent automatiquement sur la chose vue par le pointeur correspondant (puisqu’il s’agitde la même zone de RAM en réalité), et réciproquement.

5.3 PassagedeParamètresd’entrée/sortieàdesfonctions

5.3.1 Rappel : Passage de Paramètres à une FonctionA titre de rappel, il est essentiel de se souvenir que les paramètres d’une fonction sont

passés par recopie. Ceci est illustré par le petit programme suivant :


3 void f(short a, long b)

{

5 a=5;

b=3;

7 }

9 int main(void)

{

11 short i;

long j;

13

i=8;

15 j=7;

17 printf(”i=%d␣j=%ld”,i,j);f(i,j);

19

printf(”i=%d␣j=%ld”,i,j);21 }

Commentons les résultats affichés par ce programme :– ligne 17 : le programme affiche i=8 j=7 de façon évidente : c’est simplement la valeur à

laquelle ces deux variables ont été initialisées.– ligne 20 : le programme affiche toujours i=8 j=7, alors qu’on aurait peut-être pu s’attendre

à ce que le programme affiche i=5 j=3.Etant donnés les résultats, il est clair que l’appel à la fonction f n’a pas modifié les valeurs desvariables i et j de la fonction main. La raison a été donnée ci-dessus : les variables sont passées

57


aux fonctions par recopie. Alors que fait le langage C lorsque l’on fait appel à la fonction f ?Voici la description :

1. le C fait des copies de i et j en mémoire.

2. ces copies sont fournies à la fonction f et seront appelées a et b pendant toute l’exécutionde f. Ainsi, la fonction f ne voit pas directement les variables i et j mais des copies deces variables. Il est donc clair que toute modification effectuée sur a et b par la fonctionf ne va absolument pas affecter les valeurs de i et j.

3. lorsque l’on sort de la fonction f, c’est à dire lorsque l’on atteint son accolade fermante}, les copies sont effacées de la mémoire. Ainsi, juste après l’appel à la fonction, les mo-difications effectuées sur les copies sont oubliées.

Ceci est illustré plus en détail ci-dessous :

• Exécution du main avant l’appel à f :

1 int main(void)

{

3 short i;

long j;

5

i=8;

7 j=7;

Les deux variables i et j utilisent chacune un emplace-ment mémoire dont la taille dépend de leurs types res-pectifs.

8

74FF AA00

4FF A9FF

4FF A9FE0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

Fin de la RAM

i:main

j:main

000800

00000701

• Au moment de l’appel à la fonction f :

f(i,j);

Les deux variables i et j du main sont dupliquées en tantque a et b pour f.

8

74FF AA00

4FF A9FF

4FF A9FE0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

Fin de la RAM

i:main

j:main

a:f

b:f

000800

000007

8

74FF AA06

4FF AA07

4FF AA08

4FF AA09

4FF AA0A

000800

000007

Recop

ieReco

pie

58


• Pendant l’exécution de la fonction f :1 void f(short a, long b)

{

3 a=5;

b=3;

Les deux variables i et j du main ne sont pas visibles dela fonction f : la fonction ne peut modifier et consulterque a et b. Elle travaille donc sur les copies et pas sur lesvariables originales i et j. Ainsi, toute modification sur aet b n’affecte en rien i et j.

8

74FF AA00

4FF A9FF

4FF A9FE0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

Fin de la RAM

i:main

j:main

inac

cess

ible

s à

part

ir d

e f

a:f

b:f

000800

000007

5

34FF AA06

4FF AA07

4FF AA08

4FF AA09

4FF AA0A

000800

000007

• Après l’exécution de la fonction f :

}

Sur l’accolade fermante, les deux variables a et b de f sontlibérées de la mémoire : elles n’existent plus.

8

74FF AA00

4FF A9FF

4FF A9FE0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

Fin de la RAM

i:main

j:main

effa

cées

de

la p

ile

000800

000007

5

34FF AA06

4FF AA07

4FF AA08

4FF AA09

4FF AA0A

000800

000007

5.3.2 Rappel : Valeur Renvoyée par une FonctionSi l’on garde à l’esprit le fait que les paramètres sont passés par recopie, on voit qu’il est né-

cessaire d’avoir un mécanisme de renvoi de valeur de la fonction appelée vers la fonction appe-lant : il faut bien renvoyer un résultat à la fonction appelant. Ce mécanisme, vous le connaissez,se fait en utilisant le mot-clé return.

Il faut noter deux choses :– Ce mécanisme permet dde n’avoir qu’une et une seule valeur de sortie pour une fonction,

alors qu’on pourrait avoir besoin de plus de valeurs que celà.– De plus, ce mécanisme utilise également le principe de recopie. A ce stade du cours, ceci

n’est pas encore génant, mais peut amener une baisse significative des performances duprogramme dans certains cas. Nous aurons l’occasion d’en reparler plus loin.

Il existe une solution pour pallier à ces deux problèmes en une fois : le passage de para-mètres dit par adresse.

5.3.3 Passage par AdresseCe mécanisme est un tout petit peu délicat à mettre en oeuvre pour peu que l’on ait compris

le fonctionnement des pointeurs et celui du passage de paramètres par recopie. C’est lui quiva notamment solutionner le fait de pouvoir disposer de plusieurs variables de sortie.

59


Il s’appelle Passage par Adresse, par opposition au mécanisme classique de passage deparamètres, décrit plus haut, appelé Passage par Valeur.

Le principe est complètement basé sur l’utilisation de pointeurs sur variables décrit plushaut. L’idée est de fournir à la fonction un pointeur sur la (ou les) variable(s) que l’on souhaiteutiliser en entrée/sortie au lieu d’utiliser la variable simplement comme une entrée, commec’etait le cas avec le passage par valeur.

Reprenons l’exemple que nous avons vu lors des rappels sur le passage par valeur, et écrivonsle en passage par adresse de façon à ce que la variable a de la fonction f devienne une variabled’entrée/sortie cette fois ci. Le programme va subir plusieurs transformations :

• Il faut d’abord écrire que la variable i du main, qui correspond à la variable a de f, estpassée par adresse et pas par valeur. Pour cela, il faudra fournir &i au lieu de simplementi lors de l’appel à la fonction f. Ainsi, l’appel devient :

printf(”i=%d␣j=%ld”,i,j);18 f(&i,j);

20 printf(”i=%d␣j=%ld”,i,j);

• Dès que nous écrivons l’appel de cette façon, il faut voir que la déclaration de la fonctionf n’est plus correcte : en effet, f s’écrivait jusqu’ici :

2

void f(short a, long b)

4 {

Ce qui n’est plus correct dorénavant puisque nous fournissons maintenant &i au lieu dei, soit un short* au lieu d’un short. Il faut donc modifier le prototype de la fonction desorte que la syntaxe reste correcte :

2

void f(short* a, long b)

4 {

• Enfin, il reste à prendre en compte dans le code de la fonction f elle-même le fait quele paramètre a est un short*, ce qui revient, dans notre exemple, à remplacer toutes lesutilisations de la variable a simple par (*a) : les accès à la valeur se font maintenant,fatalement, par déréférencement. On a donc :

2


4 {

(*a)=5;

6 b=3;

}

Le programmme complet devient :

#include <stdio.h>

2


4 {

(*a)=5;

6 b=3;

60


}

8

int main(void)

10 {

short i;

12 long j;

14 i=8;

j=7;

16

printf(”i=%d␣j=%ld”,i,j);18 f(&i,j);

20 printf(”i=%d␣j=%ld”,i,j);}

Cette fois-ci, les résultats affichés sont :– ligne 17 : le programme affiche comme précédemment i=8 j=7 puisqu’il s’agit des va-

leurs auxquelles ces deux variables ont été initialisées.– ligne 20 : le programme affiche toujours i=5 j=7, puisque i a été passée par adresse et j

par valeur.

Reprenons maintenant la séquence d’appel pas à pas pour voir ce qui se passe en mémoire :

• Exécution du main avant l’appel à f :

1 int main(void)

{

3 short i;

long j;

5

i=8;

7 j=7;

Comme précédemment, les deux variables i et j utilisentchacune un emplacement mémoire dont la taille dépendde leurs types respectifs.

8

74FF AA00

4FF A9FF

4FF A9FE0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

Fin de la RAM

i:main

j:main

000800

00000701

• Au moment de l’appel à la fonction f :

61


f(&i,j);

Cette fois ci, c’est l’adresse de i qui est recopiée sur lapile (au lieu de sa valeur) en tant que a pour f : on peutdire que a pointe sur i. En revanche, pour j, c’est bien lavaleur qui est dupliquée en tant que b pour f.

8

74FF AA00

4FF A9FF

4FF A9FE0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

Fin de la RAM

i:main

j:main

a:f

b:f

000800

000007

adrde i

74FF AA06

4FF AA07

4FF AA08

4FF AA09

4FF AA0A

4FF AA0B

4FF AA0C

A9FF04

FE00000007

Recopie

Recop

ie

• Pendant l’exécution de la fonction f :1 void f(short* a, long b)

{

3 (*a)=5;

b=3;

En affectant une valeur au déréférencement du pointeura de la fonction f (ligne 5), on modifie directement i dumain puisque a pointe sur i. Ainsi, toute modification sur(*a) affecte directement i (puisque a pointe sur i), alorsque les modifications sur b n’affectent en rien j.

5

74FF AA00

4FF A9FF

4FF A9FE0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

Fin de la RAM

i:main

j:main

a:f

b:f

000500

000007

adrde i

74FF AA06

4FF AA07

4FF AA08

4FF AA09

4FF AA0A

4FF AA0B

4FF AA0C

A9FF04

FE00000007

Inaccessibledepuis f

ne change pas de valeur

Accessibledepuis f via a

• Après l’exécution de la fonction f :

}

Sur l’accolade fermante, les deux variables a et b de f sontlibérées de la mémoire : elles n’existent plus. En revanche,les modifications faites sur i via a vont subsister puisquela fermeture de f n’a aucune incidence sur les variablesdes autres fonctions, donc pas sur le main non plus.

5

74FF AA00

4FF A9FF

4FF A9FE0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

Fin de la RAM

i:main

j:main

a:f

b:f

000500

000007

adrde i

74FF AA06

4FF AA07

4FF AA08

4FF AA09

4FF AA0A

4FF AA0B

4FF AA0C

A9FF04

FE00000007

effa

cées

de

la p

ile

5.4 Renvoi de Pointeur par une FonctionIl s’agit ici d’examiner ce qui se passe lorsque la valeur renvoyée par une fonction est un

pointeur. Ceci peut s’avérer dangereux et même à proscrire dans certains cas bien précis. Pre-nons un exemple simple :

NE PAS FAIRE - RISQUES DE PLANTAGES

62

5.4 • Renvoi de Pointeur par une Fonction

short* f(void)

2 {

short i;

4 short* p;

6 i=3;

p=&i;

8

return p;

10 }

12 int main(void)

{

14 short* j;

short k;

16

j=f();

18

k=(*j);

20 }

La question qui est posée est la suivante : quelle est la valeur de k dans la fonction main ? Acette question, on aimerait répondre ”la valeur est 3 puisque j de main pointe sur i de f et quei de f vaut 3”. La vraie réponse est ... ”peut être 3, peut être n’importe quoi d’autre, peut êtremême que l’application va planter”. Pourtant en terme de syntaxe, de types, et de code, toutsemble correct. L’arnaque à laquelle nous sommes confrontés ici est liée à la création et à ladestruction des variables d’une fonction. Reprenons le cheminement de ce code, au momentoù l’on invoque la fonction f, exactement comme nous l’avons fait plus haut :

• Etat de la mémoire pendant l’appel à la fonction f :

short* f(void)

2 {

short i;

4 short* p;

6 i=3;

p=&i;

Les variables j et k du main ainsi que les variables i etp de f utilisent chacune un emplacement mémoire. Lesvaleurs des variables du main ont une valeur aléatoire carn’ont jamais été affectées.

3adrde i

4FF AA00

4FF A9FF

4FF A9FE0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

4FF AA06

4FF AA07

4FF AA08

4FF AA09

Fin de la RAM

j:main

k:main

p:f

i:f

??????

??????000304FFAA04

• Etat de la mémoire juste après la fin de la fonction f :

63


1

j=f();

On observe ici le mécanisme de retour : avant de détruireles deux cases mémoire, le Langage C fait une duplica-tion de la variable de retour vers la variable désirée dansle main.

adrde i3

adrde i

4FF AA00

4FF A9FF

4FF A9FE0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

4FF AA06

4FF AA07

4FF AA08

4FF AA09

Fin de la RAM

p:f

i:f

??

000304FFAA04

Recopie

??

0304FFAA

effacéesde la pile

j:main

k:main

Ainsi, (*j) n’a pas vraiment de sens puisque j pointe sur l’adresse du i de f qui vient d’êtrelibéré de la mémoire : la valeur de cette case mémoire n’est donc absolument plus fiable et onne peut plus faire confiance à son contenu. Rien ne dit en effet que cet emplacement n’a pasété déjà utilisé pour une autre utilisation.

Le problème est exactement le même avec un tableau statique :NE PAS FAIRE - RISQUES DE PLANTAGES

short* TableauVide(void)

2 {

short T[50];

4 short* p;

6 unsigned long z;

8 p=T;

10 for(z=0;z<50;z++)

{

12

T[i]=0;

14 }

16 return p;

}

18

int main(void)

20 {

short* j;

22 short k;

24 j=f();

26 k=j[5];

}

Comme dans la fonction TableauVide le tableau T est alloué en statique, exactement commen’importe quelle variable, il sera détruit dès la fin de l’exécution de la fonction. Il subit doncexactement le même traitement que les autres variables Ainsi, son contenu n’est plus viable et

64

5.5 • Tableaux de Pointeurs

tangible pour la fonction main, et renvoyer un pointeur dessus est à proscrire.Alors peut-on se permettre de renvoyer un pointeur ? La réponse est oui, à condition que la

chose pointée par le pointeur ait été allouée dynamiquement, c’est à dire par malloc, puisquece dernier ne peut être détruit qu’au moyen de la fonction free, que vous devez invoquer à lamain : vous maitrisez donc complètement la vie et la mort de ce tableau, ce qui n’est pas le casavec les tableaux et variables statiques. La règle à suivre est donc de ne JAMAIS renvoyer unpointeur sur une variable ou un tableau statique.

Pour en terminer avec cet aspect des choses, reprenons le programme ci-dessus dans uneversion qui fonctionne correctement

VERSION CORRECTE1 short* TableauVide(void)

{

3 short* p;

unsigned long z;

5

p=(short*) malloc(50*sizeof(long));

7

for(z=0;z<50;z++)

9 {

11 p[i]=0;

}

13

return p;

15 }

17 int main(void)

{

19 short* j;

short k;

21

j=f();

23

k=j[5];

25

free(p);

27 }

Ici, le malloc a été fait dans TableauVide et le free dans le main, pour que les opérationssur j dans le main puissent être réalisées.

5.5 Tableaux de PointeursLorsqu’un algorithme nécessite l’utilisation d’un nombre de variables pas connu à priori, il

est usuel de mettre ces variables sous forme d’un tableau. Par exemple, si l’on souhaite gérer lesnotes d’une classe d’étudiants, on ne sait pas à priori combien d’étudiants devront être géré :ce nombre change d’une année sur l’autre. Ainsi, on va mettre toutes les notes des étudiantsdans un tableau pour lever le problème. Celà donne typiquement :

65



3 int main(void)

{

5 unsigned long nbEtudiants,i;

float* Notes;

7 float Moyenne;

9 printf(”combien␣d’etudiants␣?”);scanf(”%ld”,&nbEtudiants);

11

Notes=(float*)malloc(nbEtudiants*sizeof(float));

13 if(Notes!=NULL)

{

15 /*Saisie des Notes*/

for(i=0;i<nbEtudiants;i++)

17 {

printf(”Note␣de␣l’Etudiant␣n.%ld”,i);19 scanf(”%f”,Notes+i);

}

21

/*Calcul de la Moyenne de la Classe*/

23 Moyenne=0;

for(i=0;i<nbEtudiants;i++)

25 {

Moyenne+=Notes[i];

27 }

Moyenne/=nbEtudiants;

29 printf(”La␣Moyenne␣de␣la␣Classe␣est␣:␣%f”,Moyenne);}

31 else

{

33 printf(”pas␣assez␣de␣RAM”);}

35

}

De la même façon, il est possible que l’on ait besoin d’un nombre arbitraire de pointeursdans une application. Le cas typique est le traitement d’images. Prenons le cas d’une image enniveaux de gris, 8 bit/pixel, soit 1 octet par pixel. Comme nous l’avons vu plus haut, la difficultéest le passage d’une RAM à 1 dimension à une image à deux dimensions. Le codage le plusfréquement utilisé est celui de la figure 5.1.

Comme nous l’avons déjà vu, pour trouver la case mémoire k du tableau contenant l’imageen RAM correspondant aux coordonnées (x, y) du pixel à traiter, il faut :

1. ”sauter” le bon nombre de cases pour arriver au début de la ligne contenant le pixel àtraiter. Si le pixel est situé sur la ligne y, il faut donc sauter y fois la largeur L de la ligne.Le nombre de cases à sauter est donc y × L.

2. ajouter le décalage sur x permettant d’arriver jusqu’à la case du pixel. Ce décalage vaut

66


L pixels

Tableau de codage de l'Image en RAM

Image Affichée

H li

gn

es(0,0)

(0,0) (1,0) (2,0) (L-2,0)(L-1,0) (0,1) (1,1) (2,1) (L-2,1)(L-1,1) (0,2) (1,2)

(x,y)

(L-1,0)

(L-1,H-1)(0,H-1)

0 L 2LLigne 0 Ligne 1

Figure 5.1 – Codage usuel d ’une image en mémoire vive.

bien entendu x.Ainsi, la formule permettant d’avoir le numéro k de la case du tableau en RAM à partir du

couple de coordonnées (x, y) est la suivante :

k = y × L+ x

C’est justement ici que se situe le problème : cette formule suppose que pour tout accès à unpixel de l’image, il faut faire une multiplication et une addition. Même si, pour les processeursmodernes, ces opérations peuvent sembler complètement banales et s’exécuter rapidement, onpréfère bien entendu faire l’économie de ce temps de calcul. Pour information, avec un écranusuel d’ordinateur, l’image affichée fait 1024 × 768, ce qui représente presque 800000 pixels.Un simple parcours d’une telle image représenterait donc 800000 multiplications et 800000additions, ce qui est pour le moins important. Ce temps de calcul est du temps perdu puisqu’ilne participe pas au traitement que l’on a à faire sur l’image : on va donc chercher à en fairel’économie.

L’idée qui va permettre de gagner ce temps de calcul est de dire que l’on peut au moinspré-calculer l’adresse de début de chaque ligne dans un tableau pour faire l’économie des mul-tiplications : il s’agit donc de stocker dans un tableau supplémentaire les adresses de chaquedébut de chaque ligne. Reprenons le cas d’une image 1024 × 768 en 8 bit/pixel. On peut déjàdire que le pointeur sur les données de l’image sera de type char* puisque chaque pixel estcodé sur un octet, donc sur un char. De plus, chaque adresse de début de ligne est égalementun char*. Il faut ajouter que nous avons 768 lignes, nous aurons donc besoin d’un tableau de768 pointeurs de type char*. Ce principe est représenté sur la figure 5.2.

Chaque ligne fait 1024 =0x400 octets. Supposons que les données de l’image soient sto-ckées à l’adresse 0xFFF0000, le tableau des adresses de début de ligne va donc correspondre auschéma de la figure 5.3.

67


L pixels

Tableau de codage de l'Image en RAM

Tab

lea

u d

es A

dre

sses

su

r le

s Li

gn

es

Image Affichée

H li

gn

es

(0,0)

(0,0) (1,0) (2,0) (1022,0)(1023,0) (0,1) (1,1) (2,1) (1022,1)(1023,1) (0,2) (1,2)

(x,y)

(1023,0)

(1023,767)(0,767)

0

0

1

2

766

767

L 2LLigne 0 Ligne 1

Figure 5.2 – Codage optimisé d ’une image en mémoire vive.

0xFFF0000 0xFFF0400 0xFFF0800 0xFFF0C00 0xFFF1000 0xFFF1400

Figure 5.3 – Contenu du Tableau des Adresses.

Au niveau du Langage C, le tableau des adresses va être représenté, comme tout tableau,par un pointeur. Ce pointeur va être un peu particulier. Prenons un exemple. Si l’on souhaiteavoir un tableau de char, le pointeur sur ce tableau sera de type char*. Par analogie, si l’onsouhaite avoir un tableau dont chaque case est un char*, le pointeur sur ce tableau sera detype char** : c’est un pointeur double.

Les étapes du programme vont donc être les suivantes :1. créer un tableau permettant de contenir la totalité des pixels de l’image, c’est à dire

contenant 1024× 768 char,2. créer et remplir un tableau permettant de contenir les pointeurs sur le début de chaque

ligne.Une fois que ces deux étapes sont remplies, on peut faire divers parcours sur l’image. Voici

un programme d’exemple, toujours sur une image de 1024× 768.int main(void)

2 {

unsigned long largeur=1024,hauteur=768,x,y;

4

68


6 char* data; /*pointeur sur les donnees de l’image*/

char** lignes; /*tableau des pointeurs sur les lignes de l’image*/

8 char* tmp;

10 /*reserve un tableau de largeur x hauteur char

pour les pixels de l’image*/

12 data=(char*)malloc(largeur*hauteur*sizeof(char));

14 /*reserve un tableau de hauteur pointeurs char*

pour le precalcul des lignes de l’image*/

16 lignes=(char**)malloc(hauteur*sizeof(char*));

18 /*si les deux allocations ont pu se faire*/

if(data!=NULL && lignes!=NULL)

20 {

/*remplir le tableau des adresses avec

22 les adresses des lignes*/

for(y=0;y<hauteur;y++)

24 {

lignes[y]=data+largeur*y;

26 }

28 /*remplir le tableau des pixels avec 3

degrades verticaux de 256 pixels de haut*/

30 for(y=0;y<hauteur;y++)

{

32 for(x=0;x<largeur;y++)

{

34 tmp=lignes[y];

/*tmp pointe sur la ligne y*/

36

tmp[x]=y;

38 /*tmp[x] correspond au x ieme

pixel de la ligne y*/

40 }

}

42 }

free(data);

44 free(lignes);

}

Comme attendu, le programme commence par faire les allocations mémoire nécessaires.Il calcule ensuite les adresses de toutes les lignes de l’image dans le tableau lignes. Enfin, ileffectue un traitement sur l’image, ici il la remplit avec 3 dégradés verticaux de 256 pixels dehaut, à l’aide de deux boucles imbriquées sur les lignes y et sur les colonnes x.

Notons aussi que l’on peut remplacer les lignes 33 à 38 : en effet l’étape du pointeur tmp n’estpas nécessaire. Ces lignes du programme peuvent en effet être remplacées par lignes[y][x]=y;.

69


En effet, lignes[y] pointe directement sur la ligne du pixel à traiter, et sur cette ligne, il fautaller à la case x.

On a donc bien fait un parcours de l’image sans jamais avoir à calculer de multiplication oud’addition : deux déréférencements suffisent à se positionner sur le bon pixel. Sur un traitementaussi simple, l’intérêt ne parrait pas si évident puisque le calcul du tableau des lignes demandelui aussi une multiplication et une addition. En revanche, si l’on fait un nombre d’accès impor-tant aux pixels de l’image, cette technique montre tout son intérêt.

5.6 Pointeurs de FonctionsTout comme les variables, les programmes utilisent une certaine place en RAM. Si les pro-

grammes utilisent une certaine place en RAM, c’est qu’ils ont une certaine adresse de départ,comme n’importe quel tableau. Mieux : toute fonction que l’on écrit a une adresse de départ.C’est justement de l’exploitation de cette adresse qu’il s’agit ici. Etant donné le lien étroit quiexiste en C entre adresses et pointeurs, il est légitime que le langage propose de définir despointeurs sur les fonctions.

Leur utilité est la suivante : prenons le cas d’un programme qui afficherait les n premièresvaleurs d’une fonction mathématique. Ecrivons un tel programme avec la fonction x2 :

1 #include <math.h>

#include <stdio.h>

3

void AfficheParabole(float xstart, float xstop, float deltax)

5 {

float x;

7 float y;

9 for(x=xstart;x<xstop;x+=deltax)

{

11 y=x*x;

printf(”x=%f␣y=%f”,x,y);13 }

15 }

17 int main(void)

{

19 AfficheParabole(0,1,0.1);

}

Si l’on voulait faire la même chose avec√x, il faudrait faire un copier/coller de la fonction

AfficheParabole, l’appeler AfficheRacine, et remplacer la ligne 11 par y=pow(x,0.5);. Or leCopier/Coller de code est quelque chose à absolument éviter. Imaginez en effet qu’il y aitun ”bug” dans la fonction AfficheParabole. S’il faut corriger le bug dans AfficheParabole, ilfaut également le corriger dans toutes les fonctions inspirées d’elle, ce qui est pour le moinspropice aux erreurs. Grâce aux pointeurs sur les fonctions, on va pouvoir écrire une fonctiond’affichage générique et fournir à cette fonction la fonction mathématique à afficher : on évitele copier/coller.

70

5.6 • Pointeurs de Fonctions

Commençons par écrire les fonctions Parabole et Racine et représentons le contexte quecelà suppose en RAM :

#include <math.h>


4 float Parabole (float x)

{

6 return x*x;

}

8

float Racine (float x)

10 {

return pow(x,0.5);

12 }

Le code Machine de chacune des deux fonctions occupechacune un espace de RAM. Chaque fonction a donc uneadresse de départ.

22A 12FE

22A 12FF

22A 1200

22A 1212

22A 1213

22A 12AA

22A 12AB

22A 12AC

22A 12B1

22A 12B2

0

Fin de la RAM

Co

de M

achin

ed

e "Parab

ole"

Co

de M

achin

ed

e "Racin

e"

C1AA

12

6C

85AE

Une fois que l’on a écrit ces fonctions, on peut définir un pointeur de fonction que l’on vafaire pointer sur l’une d’elles. Un pointeur de fonction va se définir de la façon suivante :

type_retour (*nom_variable)(type_param1,type_param2, ...);

Sur un exemple concret : écrivons un pointeur de fonction dont le nom serait p sur desfonction renvoyants un float et prenant un int puis un float en paramètre. Ceci donnerait :

1 float (*p)(int,float);

Attention : un tel pointeur ne pourra pointer que sur des fonctions dont le prototype cor-respond à :

1 float f(int i,float j);

Si nous reprenons l’exemple de l’afficheur de valeurs d’une fonction, le pointeur que l’on vadéclarer sera bien sûr de type :

1 float (*p)(float);

puisqu’il est destiné à pointer sur float Parabole(float x); ou sur float Racine(float

x);, ou sur toute fonction mathématique à une variable. Une fois le pointeur déclarer, il fautspécifier qu’on va le faire pointer sur telle ou telle fonction. Ceci se fait, sur notre exemple, dela façon suivante (ligne 20) :

1 #include <math.h>

#include <stdio.h>

3

float Parabole (float x)

5 {

return x*x;

7 }

9 float Racine (float x)

{

71


11 return pow(x,0.5);

}

13

int main(void)

15 {

float (*p)(float);

17

p=Parabole; /* fait pointer p sur la fonction Parabole*/

19

}

Il reste maintenant à appeler la fonction pointée par le pointeur p. La syntaxe est la sui-vante, en fournissant la valeur x = 5 (ligne 22) :

#include <math.h>


4 float Parabole (float x)

{

6 return x*x;

}

8

float Racine (float x)

10 {

return pow(x,0.5);

12 }

14 int main(void)

{

16 float y;

18 float (*p)(float);

20 p=Parabole; /* fait pointer p sur la fonction Parabole*/

22 y=(*p)(5);

}

Pour résoudre le problème que nous avons énoncé en début de chapitre (ne pas avoir àréécrire le code d’affichage), il faut fournir ce pointeur en paramètre d’entrée à une fonctiond’affichage pour qu’elle puisse l’utiliser. Nous obtenons ainsi le code suivant :

1 #include <math.h>

#include <stdio.h>

3

float Parabole (float x)

5 {

return x*x;

7 }

72

5.7 • Conclusion

9 float Racine (float x)

{

11 return pow(x,0.5);

}

13

15 void AfficheFonction(float xstart, float xstop,

float deltax,float (*Fonction)(float))

17 {

19 float x;

float y;

21

for(x=xstart;x<xstop;x+=deltax)

23 {

y=(*Fonction)(x); /*Appel a la fonction via le pointeur*/

25 printf(”x=%f␣y=%f”,x,y);}

27 }

29

int main(void)

31 {

AfficheFonction(0,1,0.1,Parabole);

33 AfficheFonction(0,5,0.1,Racine);

35

}

5.7 ConclusionNous avons vu ici l’ensemble des possibilités qu’offraient les pointeurs sur données et sur

fonctions. Nous allons maintenant introduire un nouveau concept : celui de structure de don-nées. Ce concept, associé à une utilisation bien maîtrisée des pointeurs, représentera l’outils leplus performant que puisse fournir le langage C en matière de développement de logiciels.

73

74

Chapitre 6

Structures de Données Simples

Sommaire6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756.2 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6.2.1 Utilité des Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756.2.2 Définition de Nouvelles Structures . . . . . . . . . . . . . . . . . . . . . . 776.2.3 Utilisation de Nouvelles Structures . . . . . . . . . . . . . . . . . . . . . . 78

6.3 Nouveaux Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 856.4 Les Unions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

6.1 IntroductionLe langage C peut être enrichi au niveau des fonctions : il vient avec un ensemble de fonc-

tions de base (printf, scanf, malloc, etc ...), et l’on peut en créer autant que l’on veut, selonles besoins. Nous allons voir ici comment enrichir le Langage C au niveau des types. En effet,si le langage C est fourni avec quelques types de base (char, short, float, long, int, ...), il offreégalement la possibilité de créer vos propres types de données, grâce au concept de structure.

6.2 Structures

6.2.1 Utilité des StructuresLes structures vont permettre de regrouper en tant qu’une seule variable l’ensemble des

caractéristiques d’un objet à décrire. Nous allons illustrer l’idée que l’on a besoin de regrouperdes variables sous un seul nom à travers quelques exemples.

6.2.1.1 Cas des Nombres Complexes

En Langage C, il n’existe pas de type ”nombre complexe”. Si nous avons des opérationsà faire sur des nombres complexes, il faut impérativement créer une variable pour la PartieRéelle, une pour la Partie Imaginaire, et tenir compte lorsque l’on tape les calculs des opéra-tions sur le nombre imaginaire (noté i en mathématiques, j en physique).

Prenons un exemple : on veut effectuer le calcul Z1 ×Z2. Avec ce que nous savons, la seulesolution est :

75

6 • Structures de Données Simples

int main(void)

2 {

float R1,I1,R2,I2,R3,I3; /*parties reelles et imaginaires des

4 2 nombres ainsi que du resultat*/

6 printf(”Partie␣Reelle␣du␣premier␣nombre␣?”);scanf(”%f”,&R1);

8 printf(”Partie␣Imaginaire␣du␣premier␣nombre␣?”);scanf(”%f”,&I1);

10 printf(”Partie␣Reelle␣du␣deuxieme␣nombre␣?”);scanf(”%f”,&R2);

12 printf(”Partie␣Imaginaire␣du␣deuxieme␣nombre␣?”);scanf(”%f”,&I2);

14

R3=R1*R2-I1*I2;

16 I3=R2*I1+R1*I2;

18 printf(”le␣Resultat␣vaut␣:␣%f+i%f”,R3,I3);

20 }

Le défaut de cette technique est que l’on ne voit pas que l’on manipule des nombres complexes.Il serait préférable d’avoir trois variables Z1, Z2 et Z3 comprenant chacune une partie réelle etune partie imaginaire : Si l’on avait cette possibilité, on pourrait lire au niveau du code que l’onmanipule des nombres complexes. Qui plus est, avec la technique que nous venons de mettre enplace, on peut très bien se tromper pendant la déclaration, c’est à dire ne pas forcément avoirune partie réelle associée à une partie imaginaire. Tout cela sans compter que si les noms devariables sont mal choisis, on peut avoir une ambiguité en terme de lecture de code sur quellevariable est une partie imaginaire et quelle variable est une partie réelle. Tous ces problèmesse résoudront naturellement avec l’utilisation des structures.

6.2.1.2 Cas des Dates

Un autre exemple est celui des dates : une date n’est pas un nombre mais une séquence de 3nombres, le jour, le mois et l’année. Ainsi, on aurait intérêt à regrouper dans une seule variableces trois informations au lieu de les avoir séparées, surtout si l’on a plusieurs dates à gérer.

6.2.1.3 Cas du Carnet d’Adresses

Un dernier exemple, mais il y en a une infinité, est celui du carnet d’adresses. Dans un car-net d’adresses, pour chaque personne, on a typiquement son nom, son prenom, son telephoneet par exemple sa date de naissance. En termes de types, le nom sera une chaîne de carac-tères, le prenom également, le téléphone est préférentiellement considéré comme une chaînede caractères car les caractéristiques changent d’un pays à l’autre, et la date de naissance estcomposée de 3 entiers, un pour le jour, un pour le mois, un pour l’année.

Si on doit gérer un grand nombre de contacts, il est fastidieux de créer sans se tromper desvariables correspondant à chaque nom, prénom, téléphone et date de naissance.

Ainsi, on voit que plus on étend le nombre de variables qui représentent un objet, plus lesrisques d’erreurs sont importants et plus les choses se complexifient.

76

6.2 • Structures

6.2.2 Dé nition de Nouvelles StructuresDans tous les cas de figures ci-dessus, l’idée qui est revenue a été de regrouper plusieurs

variables sous un seul nom. Ceci se fait en Langage C grâce au mot-clé :struct

Dans un premier temps, nous allons nous contenter de la syntaxe suivante :1 struct nom_de_la_structure

{

3 type1 var1_1, var1_2, ...,var1_n;

type2 var2_1, var2_2, ...,var2_n;

5 typem varm_1, varm_2, ...,varm_n;

};

Sur chacun des exemples décrits ci-dessus, ceci donne :• Pour les nombres complexes :

struct complexe

2 {

float Re,Im;

4 };

ou encore :struct complexe

2 {

float Re;

4 float Im;

};

Les deux syntaxes sont exactement équivalentes. En terme de jargon, chaque élémentcomposant la structure est appelé champ de la structure. Ainsi, Re et Im sont les champsde la structure complexe.

• Pour les dates :1 struct date

{

3 int Jour,Mois,Annee;

};

Ici, Jour, Mois et Annee sont les champs de la structure personnage.• Pour les fiches du Carnet d’Adresse :

struct personnage

2 {

char Nom[50]; /*le nom correspond a 50 char max*/

4 char Prenom[50]; /*le prenom correspond a 50 char max*/

char Tel[20]; /*le Telephone utilise 20 char max*/

6 int Jour,Mois,Annee; /* Date de Naissance*/

};

Ici, Nom, Prenom, Tel, Jour, Mois et Annee sont les champs de la structure date.Notez que les structures se déclarent TOUJOURS en dehors du corps d’une fonction.

77


6.2.3 Utilisation de Nouvelles StructuresTout ce que nous avons fait jusqu’ici, c’est décrire quelles informations feraient partie de la

structure, mais nous n’avons créé aucune variable basée sur cette description et encore moinsexploité cette variable. Cette étape de description s’appelle définition de la structure.

Il faut maintenant utiliser cette description en créant des variables basées sur la définitionde la structure. Une variable créée à partir d’une définition de structure est appelée instance.

Supposons que l’on ait défini la structure complexe et que l’on veuille exploiter cette des-cription. Pour créer une variable épousant le modèle complexe (une instance donc), il faut em-ployer encore une fois le mot-clé struct :

1 struct complexe Z1;

Sur un exemple un peu plus complet :1 struct complexe

{

3 float Re,Im;

5 };

7 int main(void)

{

9 struct complexe Z1;

}

On dit donc que Z1 est une instance de la structure complexe. Reste maintenant à utilisercette variable. Il faut bien entendu pouvoir accéder séparément chacun des champs de la struc-ture, c’est à dire ici à la partie Réelle, représentée par Re, et à la partie imaginaire, représentéepar Im. Ceci se fait avec l’opérateur ”.” :instance.champ

Completons notre exemple en mettant le complexe Z1 à la valeur 1 + 2i :1

struct complexe

3 {

float Re,Im;

5

};

7

int main(void)

9 {

struct complexe Z1;

11

Z1.Re=1;

13 Z1.Im=2;

}

6.2.3.1 Exemple complet : gestion des nombres complexes

Reprenons l’exemple des nombres complexes en utilisant les structures :

78

6.2 • Structures

struct complexe

2 {

float Re,Im;

4

};

6

int main(void)

8 {

struct complexe Z1,Z2,Z3;

10

12 printf(”Partie␣Reelle␣du␣premier␣nombre␣?”);scanf(”%f”,&Z1.Re);

14 printf(”Partie␣Imaginaire␣du␣premier␣nombre␣?”);scanf(”%f”,&Z1.Im);

16 printf(”Partie␣Reelle␣du␣deuxieme␣nombre␣?”);scanf(”%f”,&Z2.Re);

18 printf(”Partie␣Imaginaire␣du␣deuxieme␣nombre␣?”);scanf(”%f”,&Z2.Im);

20

Z3.Re=Z1.Re*Z2.Re-Z1.Im*Z2.Im;

22 Z3.Im=Z2.Re*Z1.Im+Z1.Re*Z2.Im;

24 printf(”le␣Resultat␣vaut␣:␣%f+i%f”,Z3.Re,Z3.Im);}

On voit ici, directement sur le code, que Z1, Z2 et Z3 sont des complexes, et que l’on va traiterles parties réelles et imaginaires des différents nombres : le code est plus clair et plus lisible,même si la syntaxe parrait un peu plus lourde. On peut même faire mieux, c’est à dire faire unefonction de saisie pour les complexes (on en a besoin deux fois ici), une fonction d’affichage etune fonction faisant le produit. Voici ce que çà donne :

struct complexe

2 {

float Re,Im;

4 };

6 /*fonction qui renvoie un complexe*/

struct complexe Saisie(void)

8 {struct complexe Z;

10 printf(”Partie␣Reelle␣?”);scanf(”%f”,&Z.Re);

12

printf(”Partie␣Imaginaire␣?”);14 scanf(”%f”,&Z.Im);

16 return Z;

}

18

79


20

22 /*fonction qui prend un complexe en parametre

et en affiche le contenu*/

24 void Affichage(struct complexe Z)

{

26 printf(”%f␣+␣i␣%f\n”,Z.re,Z.Im);}

28

30

/*fonction qui calcule le produit de deux complexes*/

32 struct complexe Produit(struct complexe G, struct complexe D)

{struct complexe Resultat;

34 Resultat.Re=G.Re*D.Re - G.Im*D.Im;

Resultat.Im=D.Re*G.Im + G.Re*D.Im;

36

return Resultat;

38 }

40

42 int main(void)

{

44 struct complexe Z1,Z2,Z3;

46 Z1=Saisie();

Z2=Saisie();

48 Z3=Produit(Z1,Z2);

50 printf(”le␣Resultat␣vaut␣:␣”);Affichage(Z3);

52 }

On voit que le code de la fonction main est très réduit et très lisible. C’est la version la pluslisible que l’on puisse faire de ce code. Examinons maintenant ce que ceci donne en mémoirevive. Lorsque l’on écrit struct complexe Z1;, le langage C réserve sur la pile un emplacementéquivalent à 2 float (un pour Re, un pour Im). Si l’on suppose qu’un float occupe 32 bit (4octets), la variable Z1 ressemblera à ce qui est montré sur la figure 6.1.

6.2.3.2 Exemple complet : gestion des dates

Pour la gestion des dates, l’opération la plus courante dont on puisse avoir besoin est lacomparaison de deux dates. Ecrivons un programme qui ferait ce travail :

struct date

2 {

int Jour, Mois, Annee;

80

6.2 • Structures

4FF AA00

4FF A9FF

4FF A9FE0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

Fin de la RAM

Z1.Re

Z1

Z1.Im4FF AA06

4FF AA07

4FF AA08

4FF AA09

4FF AA0A

Figure 6.1 – Représentation de la structure complexe en RAM.

4 };

6 struct date SaisieDate(void)

{

8 struct date D;

printf(”Jour␣?”);10 scanf(”%ld”,&D.Jour);

printf(”Mois␣?”);12 scanf(”%ld”,&D.Mois);

printf(”Annee␣?”);14 scanf(”%ld”,&D.Annee);

16 return D;

}

18

/* la technique de comparaison la plus simple

20 est de creer un nombre comprenant annee-mois-jour

sur le modele AAAAMMJJ (en decimal) pour chaque

22 date et de coparer les deux nombres*/

unsigned long DateVersNombre(date D)

24 {

unsigner long N;

26 N = D.Jour + 100*D. Mois + 10000*Annee;

return N;

28 }

30 int main(void)

{

32 struct date Date1, Date2;

unsigned long N1,N2;

34

Date1 = SaisieDate();

36 Date2 = SaisieDate();

81


38 N1 = DateVersNombre(Date1);

N2 = DateVersNombre(Date2);

40

if(N1>N2) {printf(”Date␣1␣posterieure␣a␣Date2”);}42 if(N1== N2) {printf(”Date␣1␣egale␣a␣Date2”);}

if(N1<N2) {printf(”Date␣1␣anterieure␣a␣Date2”);}44

}

Examinons maintenant ce que ceci donne en mémoire vive. Lorsque l’on écrit struct dateDate1;, le langage C réserve sur la pile un emplacement équivalent à 3 int (un pour Jour, unpour Mois et un pour Annee). Si l’on suppose qu’un int occupe 32 bit (4 octets), la variable Date1ressemblera à ce qui est montré sur la figure 6.2.

4FF AA00

4FF A9FF

4FF A9FE0

4FF AA01

4FF AA02

4FF AA03

4FF AA04

4FF AA05

Fin de la RAM

Date1.Jour

Date1

Date1.Mois

Date1.Annee

4FF AA06

4FF AA07

4FF AA08

4FF AA09

4FF AA0A

Figure 6.2 – Représentation de la structure date en RAM.

6.2.3.3 Exemple complet : gestion d’un Carnet d’Adresses

On va écrire ici un ensemble de fonctions :– Une fonction permettant de saisir un personnage

– Une fonction permettant d’afficher un personnage

– Une fonction main permettant d’ajouter un personnage et d’afficher l’ensemble des per-sonnage

L’originalité ici est que l’on va gérer un tableau de personnage au lieu de simplement gérerdes variables personnage. Pour l’allocation mémoire notamment, la technique est exactementla même que pour les types de base du Langage C mais en utilisat struct personnage commetype :


#include <stdlib.h>

3

struct personnage

5 {

char Nom[50]; /*le nom correspond a 50 char max*/

7 char Prenom[50]; /*le prenom correspond a 50 char max*/

char Tel[20]; /*le Telephone utilise 20 char max*/

82

6.2 • Structures

9 int Jour,Mois,Annee; /* Date de Naissance*/

};

11

personnage SaisiePerso(void)

13 {

struct personnage P;

15

printf(”Entrez␣le␣nom␣:”);17 scanf(”%s”,P.Nom);

printf(”Entrez␣le␣prenom␣:”);19 scanf(”%s”,P.Prenom);

printf(”Entrez␣le␣Telephone:”);21 scanf(”%s”,P.Tel);

printf(”Entrez␣le␣jour␣de␣naissance␣:”);23 scanf(”%d”,&P.Jour);

printf(”Entrez␣le␣mois␣de␣naissance␣:”);25 scanf(”%d”,&P.Mois);

printf(”Entrez␣l’annee␣de␣naissance␣:”);27 scanf(”%d”,&P.Annee);

29 return P;

}

31

void AffPerso(personnage P)

33 {

printf(”%s␣%s\nTel␣:␣%s\nNe␣le␣%d-%d-%d\n”,P.Nom,35 P.Prenom,P.Tel,P.Jour,P.Mois,P.Annee);

}

37

/*Gestion d’un Carnet d’Adresses en RAM*/

39 int main(void)

{

41 /*il faut un pointeur de type struct personnage pour gerer

un tableau pour le carnet*/

43 struct personnage* Carnet;

unsigned long nbFiches,i;

45

printf(”combien␣de␣fiches␣doit␣on␣gerer␣?”);47 scanf((”%ld”,&nbFiches);

49 Carnet=(struct personnage*)malloc(nbFiches*sizeof(struct personnage));

51 if(Carnet !=NULL)

{

53 printf(”Saisie␣des␣Fiches␣:\n”);for(i=0;i<nbFiches;i++)

55 {

Carnet[i]=SaisiePerso();

83


57 }

59 printf(”Affichage␣de␣toutes␣les␣Fiches␣du␣Carnet␣:\n”);for(i=0;i<nbFiches;i++)

61 {

AffPerso(Carnet[i]);

63 }

65 free(Carnet);

}

67 }

Examinons maintenant ce que ceci donne en mémoire vive. Lorsque l’on écrit struct per-

sonnage Perso;, le langage C réserve sur la pile un emplacement équivalent à 50 char pour leNom, 50 char pour le Prenom, 20 char pour le Tel, 3 int pour la Date. Si l’on suppose qu’un int

occupe 32 bit (4 octets), la variable Perso ressemblera à ce qui est montré sur la figure 6.3.

50 char50 char20 char1 int1 int

4FF A9FE0

4FF AA30

4FF AA62

Fin de la RAM

Perso.NomPerso.Prenom

Perso

Perso.TelPerso.JourPerso.MoisPerso.Année

4FF AA76

4FF AA7A

4FF AA7E

1 int4FF AA82

Figure 6.3 – Représentation de la structure personnage en RAM.

Interessons nous maintenant au tableau que nous avons créé : c’est un tableau de struct

personnage. C’est donc un tableau dans lequel chaque case est un struct personnage : chaquecase contient donc une instance de l’ensemble des 6 champs composant la structure, c’est àdire que chaque case est quelque chose de similaire à ce qui a été montré sur la figure 6.3. Ainsi,le tableau complet ressemble donc à ce qui est représenté sur la figure 6.4.

FF AA00 FF AA84 FF AB08 FF AB8C FF AC10 FF AC94

NOM : DupontPRENOM : MarcTel : 04 67 14 14 14Jour : 02Mois : 11Annee : 1980

NOM : DurandPRENOM : PaulTel : 04 67 14 14 15Jour : 11Mois : 02Annee : 1980

NOM : LopezPRENOM : JeanTel : 04 67 14 14 16Jour : 12Mois : 01Annee : 1982

Figure 6.4 – Représentation du tableau de struct personnage en RAM.

84

6.3 • Nouveaux Types

6.3 Nouveaux TypesJusqu’ici nous avons créé des structures. Les structures, même si elles ressemblent à de

nouveaux types, n’en sont pas pour le Langage C. La preuve est qu’il faut spécifier le mot cléstruct à chaque fois que l’on fait référence au nom de la structure.

On a en C la possibilité de définir de nouveaux types, en écrivant que l’on donne un nouveaunom à un type existant. Ceci se fait grâce au mot-clé typedef :

typedef ancien_type nouveau_type;

Sur un exemple simple :

1 typedef int entier;

Ces déclarations se font en dehors des fonctions. Voici sur un exemple :


#include <stdlib.h>

3

typedef int entier;

5

int main(void)

7 {

entier i; /*entier i est exactement equivalent a int i*/

9 int j; /*mais le symbole int existe toujours*/

entier* p;

11

p=(entier*) malloc(10*sizeof(entier));

13

i=5;

15 free(p);

}

A priori donner un nouveau nom à un type peu sembler assez peu intéressant. Ce genre demanipulation a deux buts :

– Si l’on écrit un programme qui manipule des valeurs dont le type n’est pas certain. Parexemple, si on veut manipuler du son et que l’on ne sait pas encore si l’on travaillera sur8 ou 16 bit, on peut écrire tout le programme en définissant :

typedef char typeAmplitude;

et en écrivant tout le programme sur le type typeAmplitude. Une fois la décision sur letype prise, il suffit de modificer le typedef pour que tout le programme soit adapté delui-même, à condition d’avoir rigoureusement toujours travaillé sur typeAmplitude.

– Le second but est le plus usuel : se débarasser, en terme de syntaxe, des struct que l’on estobligés d’écrire dès que l’on est confronté aux structures, et ainsi d’alléger grandementla syntaxe. Ainsi, on peut écrire :

1 struct cplx

{

3 float Re,Im;

};

5

85


typedef struct cplx complexe;

7

int main(void)

9 {

complexe Z1;

11

Z1.Re=1; Ze.Im=3;

13

}

et donc manipuler directement le nom ”complexe” au lieu de ”struct cplx” comme c’etaitle cas plus haut. On peut même écrire une version condensée, qui est en réalité la plususuelles (et la seule à retenir en réalité) :typedef struct

2 {

float Re,Im;

4 } complexe;

6 int main(void)

{

8 complexe Z1;

10 Z1.Re=1; Ze.Im=3;

12 }

Lorsque l’on écrit cette syntaxe, complexe est alors bien un nouveau type que l’on peutexploiter exactement comme n’importe quel autre type (int, short, long ...) avec enplus les caractéristiques d’une structure, permettant l’accès à des champs

6.4 Les UnionsLes unions ne sont pas un outil fondamental du Langage C et sont en pratique assez peu

utilisées. Néanmoins, dans certains cas, elles peuvent être une solution élégande à certainsproblèmes.

Les unions sont en quelque sorte l’inverse des structures. En effet, lorsque l’on donne laliste des champs qui composent une structure, ces champs sont placés les uns à la suite desautres : ils sont placés bout à bout et sont donc indépendants en mémoire. Une union, quand àelle, permet de voir une seule et même variable avec des types différents. Ainsi, si l’on modifieun des champs de l’union, cela à forcément un impact sur les autres champs. Les opérateurset la description des unions fonctionnent de facon exactement identique que les structures,mis à part le fait que nous manipulons des unions et non des structures. Prenons un exempleconcret :union decompose

2 {

long ValeurLong;

4 short ValeurShort;

char ValeurChar;

86

6.4 • Les Unions

6 };

8

int main(void)

10 {

union decompose i;

12

i.ValeurLong=0xFFAA7741;

14 printf(”%x”,i.ValeurShort);

/*affiche 0x7741, c’est à dire ”la moitie” du long*/

16

printf(”%c”,i.ValeurChar);

18 /*affiche ”A”, c’est à dire le ècaractre correspondant à la valeur 0x41*/

}

Ceci ne semble pas à priori très intéressant. Mais en combinant structures et unions, onpeut arriver à quelque chose de bien plus intéressant. Prenons pour exemple le code suivant :

1 typedef struct

{

3 short Low,High;

}shortDec;

5

typedef struct

7 {

char VeryLow,Low,High,VeryHigh;

9 }charDec;

11

union decompose

13 {

long ValLong;

15 shortDec ValShort;

charDec ValChar;

17 };

19 int main(void)

{

21 union decompose i;

i.ValLong=0x41424344;

23

printf(”%lx\n%x␣%x\n%c␣%c␣%c␣%c”,i.ValLong,i.ValShort.Low,i.ValShort.High,25 i.ValChar.VeryLow,i.ValChar.Low,

i.ValChar.High,i.ValChar.VeryHigh);

27

29 }

Ici, on superpose un long avec deux short et avec 4 char. On peut donc accéder séparémentaux octets et aux mots de poids fort et de faible composant le long. Le code affiche sur PC/Intel

87


ou AMD 1 :1 41424344

4344 4142

3 D C B A

1. Ce qui montre bien que le processeur intel/AMD inverse le poids faible et le poids fort ...

88

Chapitre 7

Structures de Données Avancées

Sommaire7.1 Listes Chaînées Simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

7.1.1 Limitation des Tableaux - Utilité des Listes Chaînées . . . . . . . . . . . 897.1.2 Fonctionnement des Listes Chaînées . . . . . . . . . . . . . . . . . . . . . 907.1.3 Les Listes Chaînées en Langage C . . . . . . . . . . . . . . . . . . . . . . 917.1.4 Problème du Premier Element . . . . . . . . . . . . . . . . . . . . . . . . 1017.1.5 Discussion : Tableaux ou Listes Chaînées . . . . . . . . . . . . . . . . . . 103

7.2 Listes Chaînées Doubles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1047.2.1 Limite des Listes Chaînées Simples . . . . . . . . . . . . . . . . . . . . . . 1047.2.2 Les Listes Doublement Chaînées en Langage C . . . . . . . . . . . . . . 104

Ce Chapitre va consister à utiliser ensemble les structures et les pointeurs : en combinantces deux outils importants du Langage C, on dispose de toute la souplesse nécessaire pour desdéveloppements de programmes évolués et performants.

L’idée générale est d’écrire des structures contenant un ou plusieurs pointeurs vers d’autresstructures. L’outil le plus simple qui exploite cette idée est la liste chaînée. Cet outil est extrè-mement utile et permet de lever certains problèmes que l’on peut rencontrer avec les tableaux.En revanche, contrairement aux tableaux, le Langage C n’a aucune connaissance au départ deslistes chaînées - exactement comme c’était le cas avec les nombres complexes par exemple - etil va falloir écrire les fonctions et les structures de données permettant d’y accéder.

7.1 Listes Chaînées Simples

7.1.1 Limitation des Tableaux - Utilité des Listes ChaînéesLes tableaux ont une limitation importante : ils ne permettent pas d’insérer une valeur

entre deux valeurs. Prenons le cas concret représenté sur la figure 7.1. Pour insérer la valeur62 entre le 15 et le 23, il faudrait que le tableau soit plus grand d’une case alors que celà n’apas été prévu et n’est en général pas possible. Il faudrait aussi déplacer toute la fin du tableaud’une case et enfin placer la nouvelle valeur au bon endroit. Ainsi, la seule solution qui marcheforcément et que nous ayons à portée de main est la suivante :

1. allouer avec malloc un tableau de n+1 cases. A ce stade, nous avons besoin de plus de 2fois la place mémoire utile pour le tableau, ce qui est pour le moins génant ...

2. recopier le début du tableau d’origine dans le nouveau tableau jusqu’à la valeur à insérer,

89

7 • Structures de Données Avancées

62

4AContenu 15 23 28

F00Adresse en RAM F01 F02 F03

Figure 7.1 – Essai d ’insertion dans un tableau

3. ecrire la valeur à insérer dans le nouveau tableau à la bonne position,4. recopier la fin du tableau d’origine après la valeur insérée,5. libérer la mémoire du tableau d’origine.Ceci représente un nombre d’opérations important (une recopie complète du tableau) ainsi

qu’un coût temporaire en mémoire qui peut rendre l’opération impossible pour un nombre decases important. Il va donc falloir trouver une alternative aux tableaux si le besoin d’insertions’avère fréquent dans l’application visée (et c’est d’ailleurs assez souvent le cas).

7.1.2 Fonctionnement des Listes ChaînéesL’idée de départ est de considérer que ce qui rend l’insertion impossible est le fait que les

cases d’un tableau soient successives les unes par rapport aux autres. On va donc maintenantestimer qu’elles sont complètement dissociées les unes des autres en RAM, comme celà estreprésenté sur la figure 7.2

?? 28 ?? ??

EFF

4A

EFE

??

EFD

??

EFC

15

EFB

??

EFA F01 F02 F03

??

F04

23

F05

??

F06

??

F07

??

F08

Figure 7.2 – Dissociation des cases du tableau.

Supposons maintenant que chaque case ”sache” (nous verrons comment y arriver) quelleest l’adresse de la case qui la suit. Supposons également que l’on sache que l’adresse de départest 0xEFE. On se retrouve alors avec le schéma de la figure 7.3

?? 28 ?? ??

EFF

4A

EFE

??

EFD

??

EFC

15

EFB

??

EFA F01 F02 F03

??

F04

23

F05

??

F06

??

F07

??

F08

Départ

Figure 7.3 – Dissociation des cases du tableau et connaissance de la case suivante.

Il est donc maintenant parfaitement clair qu’un tel système permet de décrire exactementla même information que celle contenue dans un tableau, en supposant que l’on soit capablede le mettre en place bien sûr. Vérifions maintenant que ce nouveau système permet bien

90

7.1 • Listes Chaînées Simples

?? 28 ?? ??

EFF

4A

EFE

??

EFD

??

EFC

15

EFB

??

EFA F01 F02 F03

??

F04

23

F05

??

F06

62

F07

??

F08

Départ

Nouvelle Valeur

Figure 7.4 – Allocation de la case à insérer.

d’insérer une valeur avec un coût réduit en mémoire et en temps. Pour celà, on commence parfaire une allocation mémoire pour la nouvelle case, comme le montre la figure 7.4.

A ce stade, la valeur n’est pas prise en compte dans la liste puisque aucune case ne ”sait”que 62 suit la valeur 15 dans ce système. Il faut donc modifier le parcours donné par les flèchespour prendre en compte la nouvelle valeur, c’est à dire indiquer à la case 15 qu’elle est suiviepar le 62, et que la case 62 est elle-même suivie par la valeur 23 (fig. 7.5)

?? 28 ?? ??

EFF

4A

EFE

??

EFD

??

EFC

15

EFB

??

EFA F01 F02 F03

??

F04

23

F05

??

F06

62

F07

??

F08

Départ

Figure 7.5 – Raccordement de la case à insérer.

Ainsi, tout ce qu’il a fallu faire ici, c’est allouer la nouvelle case mémoire et la raccorderau bon endroit dans la liste chaînée. Ceci représente un coût en mémoire minimum puisquela mémoire n’a augmenté que d’une case, et un coût en temps très réduit puisqu’il a suffi deraccorder les cases entre elles. C’est pour celà que l’on parle de ”liste chaînée” : chaque valeurest chaînée à la valeur suivante par un certain lien.

7.1.3 Les Listes Chaînées en Langage CVenons en maintenant à la pratique. On imagine assez bien d’après ce qui vient d’être vu

que l’on a besoin de représenter en langage C le système élémentaire de la figure 7.6.

valeursuivant

Figure 7.6 – Système élémentaire.

Il parrait clair qu’en créant autant d’instances de ce petit système élémentaire que l’onveut gérer de cases, on va pouvoir gérer des listes complètes contenant un nombre arbitrairede valeurs et permettant l’insertion. On appellera cet élément élémentaire ”un maillon” de lachaine. Ainsi, un maillon va être composé de deux choses :

– la valeur qui nous intéresse– l’adresse du prochain maillonL’outil le plus adéquate qu’offre le langage C pour associer deux quantités dans une seule

et même variable est bien sûr la structure : on va écrire une structure qui contient d’une part

91


la valeur et d’autre part l’adresse du prochain maillon. Il parrait donc naturel d’écrire le codesuivant comme brique de base de la liste chaînée (ici, on suppose que les valeurs sont des long) :

1 struct maillon

{

3 long valeur;

struct maillon* suivant;

5 };

Cette écriture peut donner l’impression que l’on définit la structure struct maillon àpartir d’elle même puisque l’on déclare un pointeur struct maillon* suivant; à l’intérieur.Il n’en n’est rien, et ce pour une raison simple : on n’a pas besoin de connaître la descriptioncomplète d’une structure pour créer un pointeur dessus, puisqu’un pointeur est de toute façonune adresse qui est elle même un simple chiffre. Ceci signifie que lors de la déclaration d’unpointeur, le type importe peu puisque tout ce que fait le Langage C est réserver une placemémoire typiquement de 4 octets (taille du bus d’adresses) sur un PC pour celui-ci. Il ne s’agitdonc absolument pas d’une définition par récurrence. Le Langage C est de toute façonincapable de créer une structure ou un type par récurrence.

7.1.3.1 Première Tentative

Tentons maintenant d’exploiter cette structure dans un exemple. Le but est ici de créerune liste composée des valeurs 8 puis 5 puis 12 (fig. 7.7).

1258

Figure 7.7 – Création d ’une Liste Chaînée : Première Tentative.

Exactement comme pour les tableaux, on a intérêt à créer les maillons par allocation dy-namique, puisque la taille d’une liste chainée peut être importante. Nous allons donc écrire unprogramme qui :

1. alloue la mémoire indépendament pour chacun des trois maillons,2. crée les liens entre les maillons.


3 struct maillon

{

5 long valeur;


7 };

9 int main(void)

{

11 struct maillon* e1;

struct maillon* e2;


92


15 /*memoire pour le premier element de la liste*/

e1=(struct maillon*)malloc(sizeof(struct maillon*));

17 /*memoire pour le second element de la liste*/


19 /*memoire pour le troisieme element de la liste*/


21

(*e1).valeur = 8;

23 (*e1).suivant=e2;

25 (*e2).valeur=5;

(*e2).suivant=e3;

27

(*e3).valeur=12;

29 (*e3).suivant=NULL;

31 }

Ce programme appelle un ensemble de remarques :– La fin de liste a été donnée par le pointeur NULL, défini dans stdlib.h. En effet, comme

on sait qu’aucun bloc ne peut être alloué à l’adresse NULL, il n’y a pas d’ambiguité endéterminant la fin de chaîne par un pointeur NULL.

– On a fait 3 fois la même chose : allocation mémoire, puis affectation de la valeur, puisaffectation du suivant. Il serait donc intéressant d’écrire une fonction qui rassemblel’ensemble de ces opérations,

– On a eu besoin d’autant de variables pointeur que de maillon, ce qui n’est pas très élégantpuisque l’on veut pouvoir créer un nombre de maillons arbitraire,

– On a encore les struct qu’il serait bon d’éliminer en écrivant un typedef.Avant de prendre en compte ces remarques, voyons ce qui se passe si on insère un 3 entre

le 5 et le 12 par exemple. Pour cela, ajoutons un morceau de code à l’exemple précédent :1 #include <stdlib.h>

3 struct maillon

{

5 long valeur;


7 };

9 int main(void)

{


struct maillon* e2;


struct maillon* e4;

15

/*memoire pour le premier element de la liste*/

17 e1=(struct maillon*)malloc(sizeof(struct maillon*));

93


/*memoire pour le second element de la liste*/


/*memoire pour le troisieme element de la liste*/


23 (*e1).valeur = 8;

(*e1).suivant=e2;

25

(*e2).valeur=5;


29 (*e3).valeur=12;

(*e3).suivant=NULL;

31

/*inserons ici le nouvel éélment*/

33 /*memoire pour le nouvel element*/


35

(*e4).valeur=3;

37 /*mise en place des liens adequates*/

(*e4).suivant=e2;


41 }

On va vouloir écrire ce code sous forme de fonction, puisque l’insertion et l’addition sontdes opérations usuelles sur les listes dont on va avoir besoin en permanence, il serait dommaged’avoir à les réécrire. On remarque, sur l’exemple ci-dessus, que la plupart du code correspon-dant à l’insertion est totalement identique, à une ligne près, au code qui permet d’ajouter unélément à la liste. Si l’on reste dans l’idée d’écrire ce code sous forme de fonctions, on va doncn’écrire que la fonction d’insertion : il suffira d’utiliser l’insertion en fin de liste pour provoquerl’ajout d’un élément à la liste. Ainsi, la gestion quasi totale des listes chainées repose sur d’unepart la description de la structure et d’autre part une écriture propre et rigoureuse de la fonc-tion d’insertion. On va donc chercher à écrire ces deux éléments essentiels aussi correctementque possible.

7.1.3.2 Le Typemaillon

Commençons par l’écriture de la structure maillon. Jusqu’ici, nous avons défini la structuremaillon. Nous avons vu plus haut dans ce cours que l’utilisation de types était préférable àl’écriture simple de structures, parce que cela permet notamment d’alléger l’écriture (on faitl’économie du mot clé struct dans beaucoup de situations). On aimerait pouvoir écrire lachose suivante, en se calquant sur ce qui a été dit sur les typedef :

1 typedef struct

{

3 long valeur;

maillon* suivant;

5

} maillon;

94


Ceci pourrait sembler correct et pourtant aucun compilateur C ne l’accepte : le Langage Crefuse de créer un pointeur de type maillon* alors que le type maillon n’est pas encore défini.Ca n’a pourtant à priori rien de génant, mais celà fait partie des (rares) limitations et lour-deurs du langage. Alors comment faire ? Repartons de ce que nous avions écrit initialement, etcomplétons :struct maillon

2 {

long valeur;

4 struct maillon* suivant;

6 };

8 typedef struct maillon element;

Ici, on crée le type element à partir de la structure maillon. Ici, le C est ”content”, il acceptede compiler. Il est toutefois génant d’avoir deux noms différents (maillon et element) pourdésigner au fond la même chose. Qu’à celà ne tienne, le C accepte qu’un type porte le mêmenom qu’une structure. On a donc le droit d’écrire :struct maillon

2 {

long valeur;


6 };

8 typedef struct maillon maillon;

Ici, on a créé le type maillon à partir de la structure maillon. Ainsi, lorsque l’on déclare unevariable, on peut indifférement écrire struct maillon ou maillon, le type ou la structure ayantbien sûr exactement la même structure. On peut donc faire l’économie du mot-clé struct àpartir de maintenant. On peut encore arranger un peu l’écriture en condensant les deux étapesen une seule :typedef struct maillon

2 {

long valeur;


6 } maillon;

Cette fois ci, c’est l’écriture la plus élégante que l’on puisse faire du type maillon en LangageC, et c’est celle que nous utiliserons dans toute la suite du cours. C’est grosso-modo ce que l’onpeut écrire de plus compliqué, dans le principe, comme type basé sur une structure en LangageC.

7.1.3.3 La fonction d’Insertion

Le rôle de la fonction d’insertion va être de pouvoir insérer un maillon entre deux maillonsexistant ou à la fin de la liste. Nous allons développer ici une fonction qui insère un élémentaprès un élément donné en paramètre à la fonction (Notez que l’insertion ”avant” serait bien

95


plus difficile car le pointeur embarqué dans le maillon est un pointeur sur l’élément suivant).Ainsi, cette fonction va prendre deux paramètres : la valeur à insérer et l’adresse du maillonaprès lequel il faut réaliser l’insertion. A ce stade, nous n’avons pas besoin de lui faire renvoyerquoi que ce soit. Son prototype sera donc :

maillon* insertion(long Valeur, maillon* courant);

Son rôle va être ”d’enrober” la valeur fournie dans un maillon et de positionner les liens.Pour celà, il faudra bien sûr allouer la mémoire nécessaire au nouveau maillon créé. Il fautensuite positionner les liens correctement, selon les 3 étapes suivantes :

• Etat initial de la liste :

12

3

5

courant (*courant).suivant

8

nouveau (*nouveau).suivant

(*courant).valeur

(*nouveau).valeur

On suppose que le pointeur fourni à la fonction d’insertion est un pointeur sur le maillon

contenant le 5. Initialement, le maillon contenant le 12 est donc accessible puisque c’est lesuivant du 5, et l’expression permettant d’y accéder est (*courant).suivant.

• Positionnement du suivant du nouvel élément

12

3

58

(*courant).suivant

(*nouveau).suivant

Si l’on écrivait directement que l’on positionne le suivant du 5 sur le 3, on aurait perdu le poin-teur sur le 12 puisqu’on accède au 12 via le 5. Ainsi, il est amplement préférable de commencerpar positionner le suivant du 3 sur le 12.

96


• Positionnement du suivant de l’élément courant

12

3

58

(*nouveau).suivant

(*courant).suivant

nouveau

Ici, il suffit de positionner le suivant de l’élément courant sur le nouvel élément pour qu’il soitpris dans la liste.

Voici donc le code de cette fonction :1 void insertion(long val, maillon* courant)

{

3 maillon* nouveau;

5 /*allocation émmoire*/

nouveau = (maillon*) malloc(sizeof(maillon));

7

/*affectation de la valeur*/

9 (*nouveau).valeur=val;

11 /*positionnement du suivant du nouvel éélment*/

(*nouveau).suivant = (*courant).suivant;

13

/*positionnement du suivant de lé’élment courant*/

15 (*courant).suivant = nouveau;

17 }

Utilisons maintenant cette fonction pour construire une liste :1 int main(void)

{

3 maillon premier;

premier.valeur=8;

5 premier.suivant=NULL;

7 insertion(5,&premier);

insertion(12,&premier);

9 }

Ce programme a plusieurs défauts :– nous insérons toujours après le premier élément. Il est difficile d’insérer en fin de liste,

puisque nous ne connaissons pas à chaque étape l’adresse du dernier élément puisqu’il

97


vient d’être créé par malloc dans la fonction insertion. Ainsi, dans l’exemple ci-dessus,les éléments sont dans l’ordre 8 - 12 - 5, alors que les valeurs ont été placées dansl’ordre 8 - 5 - 12.

– Si le malloc a échoué, la fonction qui appelle ne sait pas que le maillon n’a pas pu êtrecréé,

– il faut traiter le premier élément séparément des autres, ce qui est loin d’être optimal.Nous reparlerons de ce problème plus loin dans ce cours.

Pour pallier aux deux premiers problèmes simultanément, il suffit de faire renvoyer à la fonc-tion d’insertion l’adresse renvoyée par malloc : De cette façon, nous avons toujours l’adressedu dernier maillon créé et nous pouvons toujours insérer en fin de chaîne. De plus, nous avonségalement l’information sur le pointeur NULL lors d’un échec d’allocation. Voici le programmecomplet avec la version définitive de la fonction d’insertion :

1 typedef struct maillon

{

3 long valeur;


5

}maillon;

7

void insertion(long val, maillon* courant)

9 {

maillon* nouveau;

11

/*allocation émmoire*/

13 nouveau = (maillon*) malloc(sizeof(maillon));

15 if(nouveau!=NULL)

{

17

/*affectation de la valeur*/


21 /*positionnement du suivant du nouvel éélment*/

(*nouveau).suivant = (*courant).suivant;

23

/*positionnement du suivant de lé’élment courant*/

25 (*courant).suivant = nouveau;

27 }

29 return nouveau;

}

31

int main(void)

33 {

maillon premier;

35 maillon* dernier;

98


premier.valeur=5;

37 premier.suivant=NULL;

39 dernier=&premier;

41 dernier=insertion(5,dernier);

dernier=insertion(12,dernier);

43

}

Le dernier problème rencontré (problème du premier élément) sera traité plus loin dans cecours.

7.1.3.4 Parcours de la Liste Chaînée

Pour parcourir la liste chaînée, on ne peut bien sûr plus utiliser l’opérateur [] comme c’étaitle cas avec mes tableaux. Il va falloir utiliser un pointeur que l’on va faire pointer successive-ment sur les différents maillons de la chaîne. Ecrivons pour celà un petit exemple (la définitiondu type maillon et de la fonction d’insertion sont supposés déjà écrits plus haut dans le code) :

32 int main(void)

{

34 maillon premier;

maillon* dernier;

36 maillon* courant;

long numero;

38 long encore=1;

40 printf(”entrez␣la␣valeur␣du␣premier␣numero␣:”);scanf(”%ld”,&premier.valeur);

42 dernier=&premier;

44 /*écration de la liste îéchane*/

printf(”entrez␣maintenant␣les␣autres␣numeros.”);46 printf(”La␣saisie␣s’èarrtera␣quand␣vous␣entrerez␣”);

printf(”un␣nombre␣strictement␣éngatif\n\n”);48 while(encore==1)

{

50 printf(”valeur␣?”);scanf(”%ld”,&numero);

52 if(numero>=0)

{

54 dernier=insertion(numero,dernier);

}

56 else

{

58 encore=0;

}

60 }

99


62 /*parcours de la liste îéchane*/

printf(”vous␣avez␣entre␣les␣nombres␣suivants␣:”>);64 /*pointer le premier element de la liste*/

courant=&premier;

66 /*tant que la liste n’est pas terminee*/

while(courant!=NULL)

68 {

/*afficher la valeur du maillon époint*/

70 printf(”%ld␣␣”,(*courant).valeur);/*pointer le prochain maillon de la liste

72 pour recommencer*/

courant=(*courant).suivant;

74 }

76 }

7.1.3.5 La fonction de Suppression

Maintenant que nous savons créer et utiliser une liste chaînée, il serait intéressant de pou-voir supprimer un élément ou même de pouvoir libérer la totalité de la RAM que la liste occupe.Pour celà, il suffit de savoir supprimer un maillon de la liste : si on sait supprimer un maillon,on sait supprimer l’ensemble de la liste.

Pour supprimer un maillon, il faut non seulement libérer la mémoire qu’il occupe grâce àla fonction free, mais aussi rétablir les liens pour que la liste garde sa continuité. Pour que toutcelà soit possible, il faut fournir à la fonction le maillon précédant le maillon à effacer, puisqu’onn’a pas la possibilité de trouver le maillon qui précède un maillon passé en paramètre. Ceci sevoit très bien sur un schéma représentant la liste avant suppression d’un élément :

125


8

(*courant).valeur

(*(*courant).suivant).suivant

L’élément ne sera supprimé de la liste que si le maillon 8 a son champ suivant qui pointesur le 12. Ensuite, il faudra libérer la mémoire du maillon contenant le 5, comme le montre leschéma ci-dessous :

125

(*courant).suivant

8

Le code correspondant à ce principe est donné ci-dessous, sous forme d’une fonction :

void suppression(maillon* courant)

2 {

maillon* a_supprimer;

4 /*on garde le pointeur sur le maillon à supprimer

100


car sans cela son adresse sera impossible à retrouver

6 une fois qu’il sera sorti de la liste*/

a_supprimer=(*courant).suivant;

8

/*fait sortir le maillon de la liste*/

10 (*courant).suivant=(*a_supprimer).suivant;

12 /*libere la memoire du maillon*/

free(a_supprimer);

14 }

7.1.4 Problème du Premier ElementNous l’avons vu plus haut, la gestion du premier élément telle que nous l’avons fait jusqu’ici,

même si elle est simple, est loin d’être optimale. En effet, nous avons eu à gérer le premier élé-ment ”à la main” tant au niveau de l’allocation mémoire (nous avons créé une variable pourle premier élément) qu’au niveau de la gestion de sa valeur puisque nous avons dû faire cetteaffectation sans passer par la fonction d’insertion. Ceci peut sembler peu de choses, mais sinous étions dans le cas où les informations transportées par la liste sont plus complexes qu’unsimple long, ceci peut rendre la chose bien plus ennuyeuse. Qui plus est, et c’est le plus impor-tant, il est impossible d’insérer un maillon avant le premier puisqu’on ne peut insérer qu’aprèsun maillon.

Alors quelle est ”la bonne” solution ? La bonne solution passe par l’emploi d’un ”élémentzero” : nous allons débuter la liste par un maillon dont le champ valeur n’est jamais utilisé.Cet élément va être situé avant le premier élément, et seul son champ suivant sera utile. Unereprésentation de la liste utilisant un élément zero est donnée ci-dessous.

125

maillonzero

8?

premiermaillon

Cette façon de procéder a de nombreux intérêts :– La gestion du premier élément se fait exactement à l’identique des autres éléments, y

compris pour la gestion de son contenu.– On peut insérer un élément avant le premier élément puisqu’il suffit d’insérer après

l’élément zero.– On a un codage possible de la liste vide (liste ne contenant aucun élément), ce qui n’était

pas possible aupar-avant puisque le premier élément existait d’office.Voici le code source qui met en place cette nouvelle façon de gérer le début de la liste :

typedef struct maillon

2 {

long valeur;


}maillon;

6

101


8 maillon* insertion(long val, maillon* courant)

{

10 maillon* nouveau;

12 nouveau = (maillon*) malloc(sizeof(maillon));

if(nouveau!=NULL)

14 {

(*nouveau).valeur=val;

16 (*nouveau).suivant = (*courant).suivant;

(*courant).suivant = nouveau;

18 }

return nouveau;

20 }

22 void suppression(maillon* courant)

{

24 maillon* a_supprimer;

a_supprimer=(*courant).suivant;

26 (*courant).suivant=(*a_supprimer).suivant;

free(a_supprimer);

28 }

30 int main(void)

{

32 /*creation de l’element zero*/

maillon zero;

34 maillon*p;

long val,encore;

36

/*creons la liste vide*/

38 zero.suivant=NULL;

40 encore=1;

p=&zero;

42 while(encore==1)

{

44 printf(”quelle␣est␣la␣valeur␣à␣ajouter␣à␣la␣liste␣?”);scanf(”%ld”,&val);

46 if(val>=0)

{

48 p=insertion(val,p);

}

50 }

52 /*affichons la liste complete*/

p=zero.suivant;

54 while(p!=NULL)

{

102


56 printf(”%ld␣␣”,(*p).valeur);p=(*p).suivant;

58 }

60 /*édtruisons la liste complete pour élibrer la émmoire*/

p=&zero;

62 while(p!=NULL)

{

64 suppression(p);

printf(”%ld␣␣”,(*p).valeur);66 }

68 }

Notez que ni la structure, ni la fonction d’insertion, ni la fonction de suppression n’ontété modifiées par rapport à ce qui a été fait précédement. Tout ce qui a changé, c’est la ges-tion du début de la liste. Cette technique est définitivement la bonne façon de gérer les listessimplement chaînées.

7.1.5 Discussion : Tableaux ou Listes Chaînées

Malgré tous les avantages qu’elle procure, la liste chaînée n’a pas que des avantages parrapport aux tableaux. En effet, pour chaque valeur transportée par la liste, nous avons en plusun pointeur. Ainsi, dans l’exemple que nous avons pris, chaque long coûte en réalité :

sizeof(maillon) = sizeof(long)+sizeof(maillon*)

... c’est à dire sur un PC standard deux fois la taille d’un long. Le coût en mémoire d’uneliste chaînée est donc relativement important, surtout si la donnée transportée est de tailleplus petite voire égale à celle d’un pointeur.

De plus, l’accès aléatoire aux cases est impossible : dans un tableau, on peut très bien ac-céder à la case n°10 puis à la case n°15 et revenir à la case n°8 sans problème. En revanche, avecune liste simplement chainée, l’accès aux maillons précédents est impossible, et l’accès à lacase n°15 par exemple à partir de la case n°10 nécessite de passer par les cases n°11, 12, 13 et 14alors que çà n’est pas le case avec un tableau. En revanche, si l’on a besoin d’ajouter ou d’insérerdes éléments dans une liste sans connaître le nombre d’éléments à l’avance, le choix de la listechaînée est incontestable.

Il faut donc faire attention au choix que l’on fait dans le codage des données pour uneapplication. Il est même possible de développer des structures hybrides liste chainée/tableau,comme c’est par exemple le cas dans de nombreux logiciels de traitement de textes. Imaginezun texte d’une 50aine de pages, et que vous tapiez du texte sur la page 2. Si l’on avait opté pourune structure tableau, à chaque caractère tapé il faudrait refaire une allocation mémoire de latotalité des 50 pages de texte comme nous l’avons décrit plus haut. Si l’on choisit un codage enliste chaînée, le coût en RAM est trop important puisque pour un caractère, c’est à dire 1 char,on a un pointeur à stocker, ce qui représente 5 fois la taille nécessaire pour représenter le texte ! !Ainsi, on choisit de faire une liste chaînée dans laquelle chaque maillon est un paragraphe dutexte : si l’on fait une modification au début du texte, la seule allocation mémoire que l’on a àrefaire correspond à celle du paragraphe en cours et pas à tout le texte.

103


7.2 Listes Chaînées Doubles

7.2.1 Limite des Listes Chaînées Simples

Nous avons vu ci-dessus que le choix d’utiliser la liste chaînée présentait au moins le défautde ne pas pouvoir revenir en arrière. Le seul défaut important que nous pouvons compenserest justement ce défaut la. L’idée est simple : ajouter à la structure un pointeur sur le maillonprécédent. La liste peut alors être représentée par :

125

maillonzero

8?

premiermaillon

La seule difficulté supplémentaire est donc la gestion de ce nouveau pointeur dans l’opérationd’insertion et de suppression. Nous présentons ici la ”bonne” version de la liste doublementchaînée, c’est à dire celle qui utilise l’élément zero, même si ceci n’est pas plus obligatoire ici(même si c’est fortement recommandé) qu’avec la liste simplement chaînée.

7.2.2 Les Listes Doublement Chaînées en Langage C

Commençons par écrire la nouvelle structure :

typedef struct maillon

2 {

long val;


struct maillon* precedent;

6 }maillon;

Encore une fois, la fonction d’insertion est la plus importante à écrire pour la gestion deslistes chaînées. Avant insertion, la situation est la suivante :

12

3

5


8

nouveau (*nouveau).suivant(*nouveau).precedent

104

7.2 • Listes Chaînées Doubles

Lors de l’insertion du 3 entre le 5 et le 12, voici les liens qui devront être mis en place :

12

3

58

courant prochain

nouveau

Le code correspondant est donné ici :typedef struct maillon

2 {

long val;


struct maillon* precedent;

6 }maillon;


{

10 maillon* nouveau;

maillon* prochain;

12

nouveau=(maillon*) malloc(sizeof(maillon));

14 if(nouveau!=NULL)

{


18 /*pour se simplifier l’ecriture, on se donne

un pointeur sur le suivant du courant*/

20 prochain=(*courant).suivant;

22 /*traitons les liens du nouvel éélment*/

(*nouveau).precedent=courant;

24 (*nouveau).suivant=prochain;

26 /*lien du maillon courant a mettre a jour*/

(*courant).suivant=nouveau;

28

/*lien du maillon prochain a mettre a jour*/

30 (*prochain).precedent=nouveau;

}

32

return nouveau;

105


34 }

Ensuite, les choses sont pratiquement identiques a ce qui a été traité précédemment. Voicile code complet :


{

3 maillon* nouveau;

maillon* prochain;

5

nouveau=(maillon*) malloc(sizeof(maillon));

7 if(nouveau!=NULL)

{


11 /*pour se simplifier l’ecriture, on se donne

un pointeur sur le suivant du courant*/

13 prochain=(*courant).suivant;

15 /*traitons les liens du nouvel éélment*/

(*nouveau).precedent=courant;

17 (*nouveau).suivant=prochain;

19 /*lien du maillon courant a mettre a jour*/

(*courant).suivant=nouveau;

21

/*lien du maillon prochain a mettre a jour*/

23 (*prochain).precedent=nouveau;

}

25

return nouveau;

27 }

29 int main(void)

{

31 maillon zero;

maillon*p;

33 unsigned long val,encore;

35 zero.suivant=NULL;

zero.precedent=NULL;

37

39 encore=1;

p=&zero;

41 while(encore==1)

{

43 printf(”quelle␣est␣la␣valeur␣à␣ajouter␣à␣la␣liste␣?”);scanf(”%ld”,&val);

106

7.2 • Listes Chaînées Doubles

45 if(val>=0)

{

47 p=insertion(val,p);

}

49 }

51 /*affichons la liste complete*/

p=zero.suivant;

53 while(p!=NULL)

{

55 printf(”%ld␣␣”,(*p).valeur);p=(*p).suivant;

57 }

59 }

107

108

Conclusion

Maintenant vous avez tous les outils pour programmer correctement. En effet, tous leslogiciels et toutes les bibliothèques utilisent en permanence les 3 outils que nous avons expé-rimenté :

– les fonctions,– les structures,– les pointeurs

En mélangeant ces trois concepts avec rigueur, vous pouvez aborder tous les domaines de laprogrammation en langage C ou dans d’autres langages, notamment en utilisant des biblio-thèques : communication réseau, interfaces graphiques, traitement d’images, traitement duson, ... Le développement en C concerne 95% de la programmation sur microcontrôleur au-jourd’hui (l’assembleur devenant de plus en plus marginal, même si la connaissance de l’assem-bleur peut s’avérer être un outil très précieux) et encore une bonne part de la programmationsur ordinateur.

Pour aller plus loin et devenir ”développeur de logiciels” notamment sur ordinateur, il vousreste à apprendre les concepts ”objet”, notamment à travers des langages les plus diffusés dontla syntaxe s’inspire fortement du C, comme par exemple en C++(Linux-Windows-Mac), Java(Linux-Windows-Mac), Objective C (sur mac) ou C# (sous windows), et le fonctionnement de”Frameworks” (bibliothèques d’objets) tels que ”Qt” (Linux-Mac-Windows), ”dotNet” (Win-dows) ou ”Cocoa/Aqua” (Mac) .

109