[PDF] [PDF] Initiation - à lalgorithmique et à la programmation - Numilog

View - Download [PDF] Initiation - à lalgorithmique et à la programmation - Numilog

Previous PDF

Next PDF

Initiation

àl"algorithmique

et à laprogrammation en

CRetrouver ce titre sur Numilog.com

Retrouver ce titre sur Numilog.com

Rmy Malgouyres

Rita Zrour

Fabien Feschet

Cours avec 129 exercices corrigés

Initiation

àlalgorithmique

et à laprogrammation en C 3 e

ditionRetrouver ce titre sur Numilog.com

Illustration de couverture : © alwyncooper - istock.com

©Dunod, 2008, 2011, 2014

5 rue Laromiguière, 75005 Paris

www.dunod.com ISBN 978-2-10-071001-0Retrouver ce titre sur Numilog.com

TABLE DES MATIèRES

Avant-proposXIII

PARTIE1

BASES DU LANGAGEC

Chapitre 1. QuÔest-ce quÔun ordinateur? 3

1.1 Exemples d"applications de l"informatique

3

1.2 Codage des données3

1.3 Fonctionnement d"un ordinateur4

1.3.1 Système d"exploitation4

1.3.2 Processeur4

1.3.3 Mémoire centrale5

1.3.4 Périphériques5

Chapitre 2. Premiers programmes 7

2.1 Qu"est-ce qu"un programme?

7

2.2 Afficher un mot8

2.3 Lire un nombre8

2.4 Effectuer un calcul et mémoriser le résultat9

Exercices10

Corrigés11

Chapitre 3. Types de donnes 15

3.1 Variables et opérations

15

3.2 Type entierint15

3.3 Les types réelsfloatetdouble16

3.4 Le typechar17

3.5 Les typesunsigned17

3.6 Affectations et conversions17

3.7 Les constantes et le #define18

3.8 Définir ses propres types19

Exercices20

Corrigés21

Chapitre 4. Entres-sorties :stdio.h23

4.1 Qu"est-ce qu"une bibliothèque d"entrées-sorties?

23

4.2 L"affichagededonnéessousformedetexte23

4.2.1 Afficher des caractères23

4.2.2 Afficher d"autres données24

4.3 Lecture au clavier25

©Dunod. Toute reproduction non autorisée est un délit.

VRetrouver ce titre sur Numilog.com

Initiation ‡ lÔalgorithmique et ‡ la programmation enC

Exercices

27

Corrigés28

Chapitre 5. Excution conditionnelle 29

5.1 Qu"est-ce l"exécution conditionnelle?

29

5.2 Conditionsi-alors29

5.3 Conditionsi-alors-sinon30

5.4 Notions de calcul booléen31

5.4.1 Expressions de base31

5.4.2 Opérations booléennes32

5.5 Leswitch34

Exercices35

Corrigés36

Chapitre 6. Structuration dÔun programmeC41

6.1 Qu"est-ce qu"un sous-programme?

41

6.2 Exemple de fonctionC41

6.3 Exemple de structuration d"un programme42

6.4 Forme générale d"une fonctionC44

6.4.1 Prototype44

6.4.2 Déclaration et définition45

6.4.3 Variables locales45

6.5 Passage de paramètres par valeur45

Exercices46

Corrigés48

Chapitre 7. Structures 51

7.1 Déclaration d"une structure

51

7.2 Utilisation d"une structure51

Exercices54

Corrigés55

Chapitre 8. Itration 59

8.1 Bouclewhile

59

8.2 Bouclefor60

Exercices62

Corrigés63

PARTIE2

STRUCTURES SÉQUENTIELLES

Chapitre 9. Tableaux 71

9.1 Déclaration d"un tableau

71

9.2 Accès aux éléments72

9.3 Nombre d"éléments fixé72

VIRetrouver ce titre sur Numilog.com

Table des matiŽres

9.4 Nombre d"éléments variable borné

73

9.5 Initialisation lors de la déclaration75

Exercices76

Corrigés77

Chapitre 10. Fichiers texte 81

10.1 Qu"est-ce qu"un fichier texte?

81

10.2 Ouverture et fermeture d"un fichier texte81

10.3 Lire et écrire des données formatées83

10.3.1 Lire des données formatées83

10.3.2 Écrire des données formatées86

Exercices87

Corrigés88

Chapitre 11. Adresses, pointeurs et passage par adresse 93

11.1 Mémoire centrale et adresses

93

11.2 Variables de type pointeur93

11.3 Cas d"un pointeur sur structure95

11.4 Passage de paramètre par valeur95

11.5 Passage de paramètre par adresse96

Exercices98

Corrigés99

Chapitre 12. Allocation dynamique 103

12.1 Gestion de la mémoire centrale

103

12.2 Allocation avecmalloc103

12.3 Allocation aveccalloc105

Exercices107

Corrigés109

Chapitre 13. Cha"nes de caractŽres 115

13.1 Qu"est-ce qu"une chaîne de caractères?

115

13.2 Opérations prédéfinies sur les chaînes116

13.2.1 Fonctions de116

13.2.2 La bibliothèque119

Exercices122

Corrigés123

Chapitre 14. Fichiers binaires 129

14.1 Différence entre fichiers texte et binaire

129

14.2 Ouverture et fermeture d"un fichier binaire129

14.3 Lecture dans un fichier binaire130

14.4 Écriture dans un fichier binaire132

14.5 Se positionner dans un fichier binaire133

Exercices135

Corrigés136

©Dunod. Toute reproduction non autorisée est un délit.

VIIRetrouver ce titre sur Numilog.com

Initiation ‡ lÔalgorithmique et ‡ la programmation enC

Chapitre 15. Tableaux ‡ double entre 145

15.1 Tableaux de dimension 2

145

15.2 Allocation dynamique et libération d"un tableau de dimension 2146

Exercices148

Corrigés150

PARTIE3

ALGORITHMES

Chapitre 16. Langage algorithmique et complexit 161

16.1 Pourquoi un autre langage?

161

16.2 Types161

16.3 Entrées-sorties161

16.3.1 Clavier et écran161

16.3.2 Fichiers texte162

16.4 Syntaxe162

16.5 Fonctions et procédures163

16.5.1 Fonctions163

16.5.2 Procédures164

16.6 Enregistrements165

16.7 Pointeurs, adresses et allocation165

16.8 Notion de complexité d"un algorithme166

16.8.1 Définition intuitive de la complexité166

16.8.2 Notion de grandO166

Exercices168

Corrigés171

Chapitre 17. Algorithmes de tri quadratiques 175

17.1 Qu"est-ce qu"un tri?

175

17.2 Tri par sélection175

17.2.1 Principe du tri par sélection175

17.2.2 Algorithme de tri par sélection176

17.2.3 Estimation du nombre d"opérations176

17.3 Tri par insertion177

17.3.1 Principe du tri par insertion177

17.3.2 Algorithme de tri par insertion178

17.3.3 Estimation du nombre d"opérations178

17.4 Tri par bulles179

17.4.1 Principe du tri par bulles179

17.4.2 Algorithme du tri par bulles179

17.4.3 Estimation du nombre d"opérations180

VIIIRetrouver ce titre sur Numilog.com

Table des matiŽres

Chapitre 18. Le tri rapide (quicksort) 181

18.1 Partitionnement

181

18.2 L"algorithme de tri rapide182

18.3 Comparaison de temps de calcul183

Exercices184

Corrigés184

PARTIE4

STRUCTURES DE DONNÉES

QuÔest-ce que les structures de donnes? 189

Chapitre 19. Listes cha"nes 191

19.1 Qu"est-ce qu"une liste chaînée?

191

19.2 Déclarer une liste chaînée191

19.3 Insertion en tête de liste193

19.4 Construction d"une liste chaînée193

19.5 Parcours de liste194

19.6 Insertion en queue de liste196

19.7 Libération de mémoire197

Exercices199

Corrigés202

Chapitre 20. Piles 221

20.1 Qu"est-ce qu"une pile?

221

20.2 Implémentation sous forme de tableau222

20.2.1 Types222

20.2.2 Créer une pile vide222

20.2.3 Pile vide, pile pleine222

20.2.4 Accéder au sommet de la pile223

20.2.5 Ajouter un élément au sommet223

20.2.6 Supprimer un élément223

20.2.7 Vider et détruire224

20.3 Implémentation sous forme de liste chaînée224

20.3.1 Types224

20.3.2 Créer une pile vide225

20.3.3 Pile vide, pile pleine225

20.3.4 Accéder au sommet de la pile225

20.3.5 Ajouter un élément au sommet225

20.3.6 Supprimer un élément226

20.3.7 Vider et détruire226

20.4 Comparaison entre tableaux et listes chaînées227

Exercices227

Corrigés228

©Dunod. Toute reproduction non autorisée est un délit.

IXRetrouver ce titre sur Numilog.com

Initiation ‡ lÔalgorithmique et ‡ la programmation enC

Chapitre 21. Files 235

21.1 Qu"est-ce qu"une file?

235

21.2 Gestion naïve par tableaux236

21.3 Gestion circulaire par tableaux238

21.3.1 Enfiler et défiler238

21.3.2 Autres primitives238

21.4 Gestion par listes chaînées240

21.4.1 Structures de données240

21.4.2 Primitives241

Exercices243

Corrigés243

Chapitre 22. Rcursivit 247

22.1 Qu"est-ce que la récursivité?

247

22.2 Comment programmer une fonction récursive?247

22.2.1 Résolution récursive d"un problème247

22.2.2 Structure d"une fonction récursive248

22.3 Pile d"appels248

Exercices249

Corrigés251

Chapitre 23. Arbres binaires 257

23.1 Qu"est-ce qu"un arbre binaire?

257

23.2 Parcours d"arbres binaires258

23.2.1 Parcours préfixé258

23.2.2 Parcours postfixé260

23.2.3 Parcours infixé260

23.3 Libération de mémoire261

Exercices262

Corrigés264

Chapitre 24. Graphes 277

24.1 Définition mathématique d"un graphe

277

24.2 Chemins dans un graphe277

24.3 Représentation par matrices d"adjacence278

Exercices279

Corrigés280

Chapitre 25. Parcours de graphes 285

25.1 Parcours en profondeur récursif

285

25.2 Parcours en largeur286

Exercices287

Corrigés289

XRetrouver ce titre sur Numilog.com

Table des matiŽres

Chapitre 26. Listes dÔadjacence 293

26.1 Représentation par listes d"adjacence

293

Exercices295

Corrigés296

Annexes

Annexe A. Notions sur la compilation 305

A.1 Qu"est-ce qu"un compilateurCANSI?

305

A.2 Compiler son premier programme305

A.2.1 Créer un répertoire306

A.2.2 Lancer un éditeur de texte306

A.2.3 Compileretexécuterleprogramme306

Annexe B. Programmation multiÝchiers 307

B.1 Mettre du code dans plusieurs fichiers

307

B.2 Compiler un projet multifichiers308

B.2.1 Sansmakefile308

B.2.2 Avecmakefile309

Annexe C. Complments sur le langageC311

C.1 Énumérations

311

C.2 Unions312

C.3 Variables globales313

C.4Do...while314

C.5i++et++i314

C.6 Le générateur aléatoire : fonctionrand315

C.7breaketcontinue316

C.8 Macros317

C.9atoi,sprinfetsscanf318

C.10 Arguments d"un programme319

C.11fgetcetfputc320

C.11.1 Lire caractère par caractère320

C.11.2 Écrire caractère par caractère321

C.12 Arithmétique de pointeurs322

Exercices323

Corrigés324

Bibliographie329

Index331

©Dunod. Toute reproduction non autorisée est un délit.

XIRetrouver ce titre sur Numilog.com

Retrouver ce titre sur Numilog.com

AVANT-PROPOS

)C &BA A & 3, Cet ouvrage est destiné aux étudiants de première année des filières informatique (L1, DUT, certaines licences professionnelles), et à tous ceux qui veulent acquérir des bases solides en programmation, sans connaissances préalables, avec la volonté d"approfondir. Il inclut la programmation en langageC(syntaxe, exécution condi- tionnelle, boucles itératives, tableaux, fichiers, allocation dynamique de mémoire, récursivité...), les algorithmes et la complexité (langage algorithmique, complexité

d"algorithmes, tris...), ainsi que les structures de données (listes chaînées, piles, files,

arbres, graphes et parcours de graphes). L"un des objectifs fixés lors de la rédaction de ce livre était de produire un ouvrage digeste. Le texte ne vise pas l"exhaustivité sur le langageC.

ÊLÔ'TUDIANT

Ce livre permet d"aborder la programmation en langageCsans connaissance préa- lable de l"informatique. Il est conçu pour pouvoir être utilisé comme un outil d"ap- prentissage en autodidacte. L"étudiant peut utiliser ce livre, et notamment les exer- cices corrigés, en complément de l"enseignement qu"il reçoit par ailleurs. Il peut aussi apprendre seul, en abordant les chapitres dans l"ordre, encontrôlant ses connais- sances avec les exercices corrigés et avec les travaux pratiques sur machine. Le texte présente de manière concise les bases qui sont nécessaires aux exercices. Les exercices de chaque chapitre sont progressifs et doivent de préférence être traités dans l"ordre. Une indication de la difficulté des exercices est donnée par des étoiles lors de l"énoncé. Les pièges et les erreurs les plus courants sont mis en évidence clairement dans le texte par des panneaux spéciauxAttention!

Complments

Des compléments sont donnés au fil du texte; ils apportent un éclairage sur cer- taines notions difficiles et peuvent être abordés lors d"une seconde lecture ou lors de la phase d"exercices. ©Dunod. Toute reproduction non autorisée est un délit.

XIIIRetrouver ce titre sur Numilog.com

Initiation ‡ lÔalgorithmique et ‡ la programmation enC Des annexes expliquent comment compiler un programmeCsur son ordinateur personnel avec le compilateur gratuitgcc. Des sujets supplémentaires de travaux pra- tiques sur machine pour chaque chapitre sont disponibles sur le site web de l"auteur

Rémy Malgouyreshttp://www.malgouyres.org/.

ÊLÔENSEIGNANT

Le langageC, dont découlent de très nombreux autres langages actuels, reste la réfé- rence pour la programmation bas niveau. En particulier, ce langage est très présent en programmation système et réseaux. L"apprentissage de l"algorithmique enCpermet notamment de percevoir la gestion mémoire à partir d"une gestion manuelle, qui ap- porte une meilleure compréhension des constructeurs et destructeurs duC++ou des subtilités dugarbage collectorenJava... L"apprentissage des structures de données enCpermet de comprendre en détail la nature des objets manipulés à travers les li- brairiesJavaou laSTLduC++. L"abord de la programmation par leCest le moyen le plus efficace de former des informaticiens complets, ayant au final une maîtrise parfaite du bas niveau comme du haut niveau et une compréhension profonde des concepts. L"enseignant pourra s"appuyer sur la structure de l"ouvrage, qui permet de dé- rouler le contenu sans référence à ce qui suit. L"exposé, mais surtout les exercices contiennent de très nombreux exemples qui peuvent être réutilisés. L"ouvrage est conçu pour un apprentissage autonome. Les exercices de chaque chapitre sont pro- gressifs. En complément des exercices propres à chaque enseignant, les exercices du livre peuvent être donnés à faire aux étudiants qui peuvent consulter la solutiona posteriori.

XIVRetrouver ce titre sur Numilog.com

Partie 1

Bases du langageCRetrouver ce titre sur Numilog.com

Retrouver ce titre sur Numilog.com

QUÔEST-CE

QU

ÔUN ORDINATEUR?

'(' %. *.. & BA * AB )C Voici quelques exemples d"utilisation des ordinateurs : •BureautiqueL"ordinateur emmagasine des données saisies par une secrétaire par exemple (textes, chiffres, fichiers clients, etc.) ou des données issues d"archives, et les met en forme pour permettre une compréhension synthétique, un affichage ou une communication de ces données. •Jeux vidéoL"ordinateur combine des données entrées par le concepteur du jeu (données sur l"univers) avec les événements créés par l"utilisateur du jeu (clics de souris, etc.) pour générer des images, du son, etc.

•Prévision météorologiqueÀ partir de la donnée des relevés de toutes les stations

météo d"une zone géographique, l"ordinateur calcule une situation future et génère des cartes de températures et de pressions atmosphériques. •Applications multimédia sur InternetL"ordinateurtéléchargedes données sto- ckées sur unserveurdistant et affiche ces données sur l"ordinateur de l"utilisateur. Éventuellement, des actions de l"utilisateur peuvent influer sur les données affi- chées (on parle alors d"applications interactives). Dans tous ces exemples, l"ordinateurtraite des données, et produit un résultat, soit communiqué à l"utilisateur (son, images, texte), soit affiché sur un écran, ou stocké sur un disque, ou un autre support.

1.2 CODAGE DES DONN'ES

Les données informatiques sont toujours, en fin de compte,codées en binaire, c"est- à-dire qu"elles sont représentées par des suites de 0 et de 1. En effet, les données binaires sont plus faciles à mémoriser sur des supports physiques (bandes magné- tiques, disques, etc.). Par exemple, si l"on veut stocker un nombre entier sur le disque dur d"un ordina- teur, on code généralement ce nombre en base 2 au lieu de le coder en base 10 comme nous y sommes naturellement habitués. ©Dunod. Toute reproduction non autorisée est un délit.

3Retrouver ce titre sur Numilog.com

Chapitre 1

QuÔest-ce quÔun ordinateur?

Ainsi le nombre 12 (en base 10) sera codé en base 2 par la suite binaire 00001100, ce qui signifie que :

12=0+0+0+0+8+4+0+0

=0×2 7 +0×2 6 +0×2 5 +0×2 4 +1×2 3 +1×2 2 +0×2 1 +0×2 0 Une donnée égale soit à 0 soit à 1 s"appelle unbit. Une séquence de 8 bits consé- cutifs s"appelle unoctet(en anglaisbyte). On mesure la quantité de mémoire stockée dans les ordinateurs en :

•Octets : 1 octet=8 bits;

•Kilo-octets (en abrégéKoou en anglaisKb):unKovaut 1024 octets. •Méga-octets (en abrégéMoouMb):unMovaut 1 048 576 octets •Giga-octets (en abrégéGoouGb):unGovaut 1 073 741 824 octets L"apparition des nombres 1024, 1 048 576 et 1 073 741 824 peut paraître surpre- nante, mais ce sont des puissances de 2. On retient en général qu"unKofait environ mille octets, unMoenviron un million, et unGoenviron un milliard.

1.3 FONCTIONNEMENT DÔUN ORDINATEUR

'((' 9 5$ Un programme informatique doit recevoir des données pour les traiter et produire d"autres données. Pourqueleprogramme puisse fonctionner, ilfaut dumatériel (com- posants électroniques), et il faut une couche logicielle intermédiaire avec le matériel, appeléesystème d"exploitation. Le système assure la communication entre le pro- gramme informatique et le matériel, et permet au programme d"agir sur le matériel.

1.3.2 Processeur

Le processeur effectue des opérations (par exemple des opérations arithmétiques comme des additions ou des multiplications). Ces opérations sontcâbléesdans le processeur, c"est-à-dire qu"elles sont effectuées par des circuits électroniques pour être efficaces. Avec le temps, de plus en plus d"opérations complexes sont câblées au niveau du processeur, ce qui augmente l"efficacité. La vitesse d"un processeur, c"est- à-dire en gros le nombre d"opérations par seconde, appeléevitesse d"horloge, est mesurée en hertz (Hz), kilohertz (1kHz=1000Hz) , megahertz (1MHz=10 6 Hz,et gigahertz (1GHz=10 9 Hz). Sur les architectures récentes, la puce contient plusieurs cores, chaque core étant l"équivalent d"un processeur etlescores communiquant entre eux très rapidement par desbusde données. Pour la personne qui programme enC, la configuration et la structure de la puce esttransparente, c"est-à-dire que l"on n"a pas à s"en préoccuper (sauf pour l"optimisation en programmation très avancée).

4Retrouver ce titre sur Numilog.com

1.3. Fonctionnement dÔun ordinateur

Au cours du déroulement du programme, celui-ci utilise des données, soit les don- nées fournies en entrée, soit des données intermédiaires que le programme utilise pour fonctionner. Ces données sont stockées dans desvariables. Physiquement, lesquotesdbs_dbs22.pdfusesText_28

[PDF] poème contre la guerre

[PDF] comment faire un quadrillage sur scratch

[PDF] acrogym a 2

[PDF] poeme poilus 14-18

[PDF] poeme maladie cancer

[PDF] poeme pour combattre le cancer

[PDF] poeme triste maladie

[PDF] poeme maladie courage

[PDF] poeme maladie coeur

[PDF] texte sur la maladie

[PDF] pendant une maladie hugo

[PDF] dictionnaire grec biblique pdf

[PDF] poème 20ème siècle amour

[PDF] alimentation cm2 exercices

[PDF] hermaion initiation au grec ancien pdf