[PDF] Algorithmique & programmation en langage C - vol.1 - Archive

View - Download Algorithmique & programmation en langage C - vol.1 - Archive

Previous PDF

Next PDF

>G A/, +2H@yRRdeRRN ?iiTb,ff?HXb+B2M+2f+2H@yRRdeRRNpk am#KBii2/ QM R 62# kyRN

Bb KmHiB@/Bb+BTHBM`v QT2M ++2bb

`+?Bp2 7Q` i?2 /2TQbBi M/ /Bbb2KBMiBQM Q7 b+B@

2MiB}+ `2b2`+? /Q+mK2Mib- r?2i?2` i?2v `2 Tm#@

HBb?2/ Q` MQiX h?2 /Q+mK2Mib Kv +QK2 7`QK

i2+?BM; M/ `2b2`+? BMbiBimiBQMb BM 6`M+2 Q` #`Q/- Q` 7`QK Tm#HB+ Q` T`Bpi2 `2b2`+? +2Mi2`bX /2biBMû2 m /ûT¬i 2i ¨ H /BzmbBQM /2 /Q+mK2Mib b+B2MiB}[m2b /2 MBp2m `2+?2`+?2- Tm#HBûb Qm MQM-

Tm#HB+b Qm T`BpûbX

.Bbi`B#mi2/ mM/2` *`2iBp2 *QKKQMbii`B#miBQM @ LQM*QKK2`+BH @ a?`2HBF2% 9Xy

AMi2`MiBQMH GB+2Mb2

H;Q`Bi?KB[m2 T`Q;`KKiBQM 2M HM;;2 * @ pQHXR

hQ +Bi2 i?Bb p2`bBQM, .KB2M "2`i?2i- oBM+2Mi G#imiX H;Q`Bi?KB[m2 T`Q;`KKiBQM 2M HM;;2 * @ pQHXR, amTTQ`ib /2 +Qm`b oQHmK2 R Sû`BQ/2 kyy8@kyR9X GB+2M+2X H;Q`Bi?KB[m2 2i S`Q;`KKiBQM- AbiM#mH- hm`[mB2X kyR9- TTXkjkX +2H@yRRdeRRNpk

Université Galatasaray

Algorithmique &

programmation en langage C

Damien Berthet & Vincent Labatut

Notes de cours

Supports de cours Volume 1

Période 2005-2014

Damien Berthet & Vincent Labatut 2005-2014

Ce document est sous licence Creative Commons Attribution - - Partage

dans les Mêmes Conditions 4.0 International. Pour accéder à une copie de cette licence, merci de vous

rendre à l'adresse suivante : http://creativecommons.org/licenses/by-nc-sa/4.0/Galatasaray Üniversitesi

Mühendislik ve Teknoloji Fakültesi

version 0.9Turquie 1/0/201 Supports de cours vol.1 Période 2005-2014 3/232

SOMMAIRE ................................................................................................................................................ 3

CONVENTIONS ........................................................................................................................................... 8

1 INTRODUCTION .................................................................................................................................. 9

1.1 DÉFINITIONS ........................................................................................................................................ 9

1.2 PRÉSENTATION DU LANGAGE C ............................................................................................................. 14

2 TYPES DE DONNÉES .......................................................................................................................... 23

2.1 REPRÉSENTATION DE L'INFORMATION ..................................................................................................... 23

2.2 NOMBRES ENTIERS ............................................................................................................................. 25

2.3 NOMBRES RÉELS ................................................................................................................................ 31

2.4 CARACTÈRES ...................................................................................................................................... 37

2.5 IMAGES ............................................................................................................................................ 39

3 VARIABLES ET CONSTANTES LITTÉRALES........................................................................................... 44

3.1 CONSTANTES LITTÉRALES...................................................................................................................... 44

3.2 VARIABLES ........................................................................................................................................ 46

4 EXPRESSIONS ET OPÉRATEURS ......................................................................................................... 51

4.1 EXPRESSIONS ..................................................................................................................................... 51

4.2 OPÉRATEURS ..................................................................................................................................... 52

4.3 CONVERSIONS ................................................................................................................................... 56

5 CONDITIONS ET BOUCLES ................................................................................................................. 59

5.1 INSTRUCTIONS DE TEST ........................................................................................................................ 59

5.2 INSTRUCTIONS DE RÉPÉTITION ............................................................................................................... 64

5.3 ANALYSE D'UN PROGRAMME ................................................................................................................ 68

6 TABLEAUX ........................................................................................................................................ 74

6.1 DÉFINITION ....................................................................................................................................... 74

6.2 MÉMOIRE ......................................................................................................................................... 75

6.3 MANIPULATION ................................................................................................................................. 76

6.4 CHAÎNES DE CARACTÈRES ..................................................................................................................... 77

6.5 TABLEAUX MULTIDIMENSIONNELS .......................................................................................................... 79

6.6 EXERCICES ......................................................................................................................................... 80

7 FONCTIONS....................................................................................................................................... 82

7.1 PRÉSENTATION .................................................................................................................................. 82

7.2 PASSAGE DES PARAMÈTRES .................................................................................................................. 87

7.3 TABLEAUX ......................................................................................................................................... 91

7.4 EXERCICES ......................................................................................................................................... 93

8 TYPES PERSONNALISÉS ..................................................................................................................... 95

8.1 GÉNÉRALITÉS ..................................................................................................................................... 95

8.2 STRUCTURES ..................................................................................................................................... 96

8.3 UNIONS .......................................................................................................................................... 101

8.4 ÉNUMÉRATIONS ............................................................................................................................... 102

8.5 NOMMAGE DE TYPES ........................................................................................................................ 104

9 CLASSES DE MÉMORISATION .......................................................................................................... 106

9.1 PERSISTANCE D'UNE VARIABLE ............................................................................................................ 106

9.2 DÉCLARATIONS LOCALES .................................................................................................................... 106

9.3 DÉCLARATIONS GLOBALES .................................................................................................................. 109

9.4 FONCTIONS ..................................................................................................................................... 109

10 POINTEURS

10.1 PRÉSENTATION

10.2 ARITH

10.3 POINTEURS ET TABLEAUX

11 ALLOCATION DYNAMIQUE

11.1 PRÉSENTATION

11.2 ALLOCATION SIMPLE

11.3 AUTRES FONCTIONS

11.4 EXERCICES

12 FICHIERS

12.1 STRUCTURE FILE

12.2 OUV/FERMETURE

12.3 LECTURE/ÉCRITURE NON-FORMATÉES EN MODE CA

12.4 LECTURE/ÉCRITURE NON-FORMATÉES EN MODE CH

12.5 LECTURE/ÉCRITURE FORMATÉES

12.6 LECTURE/ÉCRITURE PAR BLOC

12.7 EXERCICES

13 FONCTIO

13.1 PRÉSENTATION

13.2 TYPES DE RÉCURSIVITÉ

13.3 ARBRE DES APPELS

13.4 STRUCTURE D'UNE FONCTION RÉCURSI

13.5 COMPARAISON ITÉRATIF/RÉCURSIF

13.6 EXERCICES

14 LISTES CHAÎNÉES

14.1 PRÉ

14.2 LISTES SIMPLEMENT CHA

14.3 LISTES DOUBLEMENT CHA

15 PILES DE DONNÉES

15.1 PRÉ

15.2 TYPE ABSTRAIT

15.3 IMPLÉMENTATION PAR TA

15.4 IMPLÉMENTATION PAR LI

16 FILES DE DONNÉES

16.1 PRÉSENTATION

16.2 TYPE ABSTRAIT

16.3 IMPLÉMENTATION SIMPLE

16.4 IMPLÉMENTATION CIRCUL

16.5 IMPLÉMENTATION PAR LI

17 COMPLEXITÉ ALGORITHM

17.1 INTRODUCTION À LA COM

17.2 CALCUL DE COMPLEXITÉ

17.3 ALGORITHMES RÉCURSIFS

18 ALGORITHMES DE TRI

18.1 PRÉSENTATION

18.2 TRI À BULLES

18.3 TRI PAR SÉLECTION

18.4 TRI PAR INSERTION

Supports de cours vol.1 Période 2005-2014 5/232 18.5 TRI FUSION...................................................................................................................................... 208

18.4 TRI RAPIDE ...................................................................................................................................... 212

19

ARBRES ........................................................................................................................................... 215

19.1 DÉFINITIONS .................................................................................................................................... 215

19.2 ARBRES BINAIRES ............................................................................................................................. 218

19.3 ARBRES BINAIRES DE RECHERCHE ......................................................................................................... 223

Supports de cours vol.1 Période 2005-2014 6/232 Ce document constitue le support de cours écrit pour différents enseignements

2) et de leurs corrigés (volume 3).

1 (Simple DirectMedia Layer

ue. Les outils utilisés en TP (GCC23

notions abordées le sont parfois de façon simplifiée et/ou incomplète. s de 2 heures réparties

de la façon suivante : Séance Sujet abordé Sections traitées

01 Introduction 1

02 Types simples 2

03 Variables, expressions et opérateurs 3-4

04 Structures de contrôle 5

05 Tableaux 6

06 Définition de fonctions 7-7.2.1

07 Passage de paramètres 7.2.2-7.4

08 Structures et unions 8-8.3

09 Types personnalisés & classes de mémorisation 8.4-9

10 Pointeurs 10

11 Allocation dynamique de mémoire 11

12 Fichiers 12

13 Fonctions récursives 13

14 Listes simplement chaînées 14-14.2

15 Listes doublement chaînées 14.3-14.3.5

16 Piles de données 15

17 Files de données 16

18 Introduction à la complexité 17-17.1

19 Complexité d'algorithmes itératifs 17.2

20 Complexité d'algorithmes récursifs 17.3

21 Tris quadratiques 18-18.4

22 Tris log-linéaires 18.5-18.4

23 Arbres binaires 19-19.2

24 Arbres binaires de recherche 19.3

sabsent du cours magistral, et était plutôt traité lors du tout premier TP. 1https://www.libsdl.org/ 2 3

Les principales références bibliographiques utilisées pour préparer ce cours sont les

, Thomas Cormen, Charles Leiserson & Ronald Méthodologie de la programmation en C, Achille Braquelaire, Dunod, 4ème

Langage, Gerhard Willms, MicroApplication, 1996.

Ce document utilise différentes conventions, dont certaines sont aussi appliquées dans les fonctions, variables, constantes, etc.) sont indiqués en utilisant la polCourier.

Courier

Entrez une valeur

Lorsque du code source est cit

int ma_function(int x)

Concept

1 1.1 1.1.1

Le mot algorithme ème

Al Khuwarizm4rythme, ce qui explique

y

Algorithme

ithme Algorithmiqueensemble des méthodes permettant de définir des (dans le cadre informatique) son implém 1.1.2

Un informel, ou incomplètement

informatique) ou autres. Par opposition, une démonstration mathématique ou un formels5 comp 6 Les étapes sont représentées par des liens

Les étapes de test

Les étapes de début fin

Les étapes de traitement

Les appels à des fonctions sous) sont

4 algèbre.

5 6 entrée/sortie complexes tout en gardant un diagramme lisible. pa exemple -

Version organi

Version pseudo

debut tant fin 1.1.3 Dans notre cas, le problème à résoudre est souvent compliqué d. Cette méthode récursivement

élémentaires,

Début

Fin

Afficher "début du traitement"

Afficher "fin du traitement"

compteur <= 0

Si compteur<4

Traitement X

Incrémenter compteur

faux vrai e

Énoncé du p

o o La table traçante possède un compteur. o Elle est capabl

ƒ lever/baisser

avec la feuille de papier posée sur la table de dessin, ou au contraire

ƒ centrer

ƒ haut/bas/gauche/droite ͳ

ƒ initialiser/incrementer

o Le problème est de dessiner une croix centrée sur la feuille, et dont chaque R début 10 fin o Algorithme de niveau ૛ debut fin o Algorithme de nivea૜

ƒ On décompose aller au centre sans tracer

debut fin ƒ On décompose tracer la branche du haut debut tant que ƒ On recommence avec les autres actions du niveau -, et en remplaçant 1.1.4

On peut considérer un programme comme la

de programmation, i.e. un langage formel compréhensible par un ordinateur. On dit alors que implémentation

Programme : n ordinateur.

Instruction

s programmesource exécutable. Le premier cont code sourcebinaire, aussi appelé machine objet.

Code source :

Code binaire

Remarque programme

compilation. Ce traitement est réalisé par un programme spécial appelé le compilateur.

Compilationaction d

utiliser pour exécuter le programme. implémente sont deux choses bien

La personne qui écrit le programme

Le langage de programmation employé

utilisés etc. ici au cas du langage C, décrit dans la figure ci programme en plusieurs fichiers séparés

La première précompiler

#. Ces version complétée deuxième compilation . assembleur. Ce langage est qualifié de bas troisième assemblage, et consiste à transformer chaque .o. quatrième édition des liens. Elle consiste à rassembler

Remarque abus de langage, on appelle compilation

étape).

1.1.5 en fonction du moment où elles sont détectées

Erreur de compilation

ut autre étape du processus. avertissement main() fonct1() fichiers source précompilation fonct2() fonct3() fonct4() fichiers complétés main() fonct1() fonct2() fonct3() fonct4() ADD

JUMP X

ADD X,Y

ADD Y,Z

LABEL UN

JUMP DE

compilation fichiers assembleur

01101010

01010100

01010101

01110111

01111011

01111011

11010100

11001100

10101001

assemblage fichiers objet

10010101

00010101

00010101

00101010

10010101

01010101

01000111

édition des liens

fichier exécutable 7 votre programme.

échoué. Ces erreurs

compilateur compilateur utilisé pour être capable de les int corriger la toute première causer les erreurs ultér attendu lors de son exécution. fatales non. programme se termine intempestivement. Par contre, localiser la partie du code source non

Remarque entifier les

1.2 superficielle, afin de pouvoir progresser dans le cours. La plupart de ces notions seront ensuite 1.2.1

Le langage C est

Unix8

7 Integra

pour écrire le code source. Pour nos TP, nous utiliserons 8 Portabilitéun langage de programmation est dit portable machines et de systèmes différents, sans avoir besoin d. stabilisée en 1978 et est appelée Kernighan & Ritchie

C K&R;

ANSI9C89

C ANSI

ISO10 répandue. Nous indiq bas niveau 11 que C++, Java, C#, JavaScript ou PHP. Un gra

Remarque

informatique 1.2.2 chaque instruction se termine par un point;). Pour améliorer la lisibilité du code bloc. exemple instruction 1;

Il est aussi possible de définir un bloc

récursivement. On peut alors parler de sous. exemple 9 10 11 instruction 1; de le désigner fonction. Outre son nom, une

Fonction

identificateur. À noter que cette notion 1.2.5 effectué par la fonction est appelé corps de la fonction, alors que son identificateur et ses en.

Corps de fonction

En type de retour void) si la fonction ne renvoie rien, ou bien une valeur entière, une valeur réelle, ou typ paramètres variables ( )) et séparées par des virgules. Pour pas limité, il peut même ne pas y avoir de param exemple ma_fonction, dont le type de retour est type_r p1 p3 type_p1 type_p3. Les couleurs sont type_ 1.2.3 séquence de fonction principale, dont le nom est main. En règle générale, un programme ne peut pas contenir plusieurs main int Le type de retour (int) et les deux paramètres (int argc char** argv) seront programme minimal suivant, que vous pouvez copier int main(int argc Notez que ce programme ne fait absolument rien du to exemple f1, f2, f3 fonction principale t_a f1(t_b p1, t_c p2) 1.2.4 Comme dans la plupart des langages de programmation, il est possible de définir des commentaires

Commentaire

un être humain, et ils sont par conséquent complètement ignorés par le compilateur. Les IDE

/* */, et peut occuper plusieurs lignes. On peut exemple

Commentaire de plusieurs lignes

Commentaire de

programme, car cela améliore Lisib indiquer à quel exercice correspond quelle parti

12indentation

Indentation

Toute accolade fermante } {

Toute instruction doit être alignée

exemple instruction 1;{ instruction 4;

Une bonne méthode générale de pr

1) diviser satisfaisant. On recopie cet algorithme sous forme de commentaires dans le code source, qui ne On 1.2.5 foncti I unique, d qui constituent le programme On utilisera seulement des lettres (minuscules et majuscules), des chiffres et le _ 12

Remarque

var V

Les noms des var1)

Les CST)

On utilise le caractère ex_de_var)

sens qui lit le programme quelle est la signification de la variable ou fon mots protégés mots réservésmots Mot exemples for, if, else, return 1.2.6 En dehors des fonctions mentionnées, il est possible de pl directives de pré. Être précédée du caractère dièse (i.e. #).

Ne pas ;).

#i #d ces programmes doivent prendre la forme xxxxx.h la section Une forme locale, dans laquelle le nom du fichier est entouré de guillemets " #include "xxxxx.h" Une forme système, dans laquelle le nom du fichier est entouré des signes #include Consta lettres minuscules. La définition se fait en utilisant la syntaxe suivante #define Où XXXXX eur est la valeur associée. Par exemple, pour définir une

C ͷ, on écrira

#define C 5 Cette directive fonctionne de la façon suivante

XXXXX valeur. Il est

XXXXX mentionner que le programme utilise la bibliothèque stdio.h CSTE

ͻͻ. Alors on écrira (en gras)

#include 1.2.7 Comme expliqué précédemment, le langage C permet de décomposer un programme en main. Celui on nous main.c. Outre la fonction main, il peut contenir des fonctions secondaires.quotesdbs_dbs22.pdfusesText_28

[PDF] FICHE n°6 : PROGRAMMER DES BOUCLES - Maths-et-tiques

[PDF] fiche maternelle algorithme imprimer- pdf documents

[PDF] Fiche enseignant ALGORITHMES NIVEAU : GRANDE SECTION

[PDF] Algorithme et numération - Académie de Nancy-Metz

[PDF] L 'atelier des petites chenilles en PS Etape 1 - académie de Caen

[PDF] reproduire une suite algorithmique - Accueil DSDEN 22

[PDF] Rappels : Tableaux et Matrices

[PDF] N°96 - spécial mouvement intra 2016pub - Snes

[PDF] Algorithmique et programmation : les bases (Algo) Corrigé

[PDF] TP7 : le théor`eme du point fixe en action sous MATLAB

[PDF] Séance de travaux pratiques n° 1

[PDF] simulations, algorithmes en probabilités et statistique(s) au - Apmep

[PDF] Loi de Bernoulli et loi binomiale, cours, première S - MathsFG - Free

[PDF] Probabilités, simulation et algorithmique (pour TI)

[PDF] Algorithmes et programmation en Pascal TD corrigés - Limuniv-mrsfr