Algo 3 - Cours 1 · – Lecture/écriture au format texte – Lecture/écriture au format binaire....

Preview:

Citation preview

1/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Informatique 3

Licence SI 2ème annéebenoit.crespin@unilim.fr

2/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Et d'abord ça veut dire quoi "Informatique" ?

• Informatique : mot créé en 1962 à partir de "information" et "automatique"

• Dans le sens moderne, « ensemble des sciences et techniques en rapport avec le traitement de l'information »

• On différencie parfois l'informatique fondamentale (computer science) du « génie logiciel » ou « génie informatique » (computer engineering)

3/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Deux semestres résumés en 3h...• Introduction• Boucles, fonctions, récursivité

– Méthodes itératives (boucles)– Fonctions– Méthodes récursives

• Structures, vecteurs, listes– Structures– Vecteurs– Listes chaînées

• Stockage sur disque– Principe général– Opérations courantes– Lecture/écriture au format texte– Lecture/écriture au format binaire

4/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Algorithme

• Algorithme : méthode de résolution d'un problème programmable sur un ordinateur (vient de Al-Khuwarizmi, également « inventeur » de l'algèbre au 9ème siècle)

• Différents types de méthodes : itératives (boucles) ou récursives

• Utilisation de structures de données (vecteurs, listes)• Pour résoudre un problème complexe, décomposition en

sous-problèmes et donc en sous-programmes

5/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Exemple : rendre une fraction irréductible

• Exemple : comment réduire la fraction 178468 / 267702 à... 2/3 ?

• Méthode datant de l'antiquité grecque (Euclide) : trouver le Plus Grand Commun Diviseur (PGCD) des deux nombres, puis les diviser par ce PGCD

• … Nouvelle question : comment trouver « facilement » le PGCD de deux nombres u et v ?

6/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Exemple : trouver le PGCD de deux nombres u et v

• On s'aperçoit que si u ≥ v, alors le PGCD de deux nombres positifs u et v = PGCD(u − v, v)

• Si v > u alors il faut échanger u et v• Si u ≤ 0, alors PGCD(u, v) = v• Par exemple :

– PGCD(10, 4) = PGCD(6, 4)– PGCD(6, 4) = PGCD(2, 4)– PGCD(2, 4) =[échange] PGCD(4, 2) = PGCD(2, 2)– PGCD(2, 2) = PGCD(0, 2)– PGCD(0, 2) = 2

7/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Exemple : trouver le PGCD de deux nombres u et v

• Algorithme :while (u > 0){if (u <= v){

w = u ;u = v ;v = w ;

}u = u − v ;}

Echange de deux valeurs

8/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Programme final en C/C++: reducFraction.cpp

#include <iostream>using namespace std;int main(){

int numerateur, denominateur;int u, v, w;cin >> numerateur >> denominateur;u = numerateur;v = denominateur;while (u > 0) {

Variables

Saisie au clavier

Lignes à toujours mettre au début du programme

9/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Programme final : reducFraction.cpp

if (u < v) {w = u;u = v;v = w;}u = u - v;

}

numerateur = numerateur / v;denominateur = denominateur / v;cout << "Fraction réduite: " << numerateur

<< " / " << denominateur << endl;}

Affichage

10/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

11/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Programme final en ooBasic

Sub MainDim maFeuille As ObjectDim numerateur As Long, denominateur As LongDim u As Long, v As Long, w As LongmaFeuille = ThisComponent.Sheets.getByName("Feuille1")' Cellule B3numerateur = maFeuille.getCellByPosition(1,2).getValue' Cellule B4denominateur = maFeuille.getCellByPosition(1,3).getValue u = numerateurv = denominateur

Le type Integer ne permet pas demanipuler de grands nombres...

12/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Programme final en ooBasic

While u > 0 If u < v Then w = u u = v v = w End If u = u - vWendnumerateur = numerateur / vdenominateur = denominateur / vprint "Fraction réduite: " + numerateur + " / " + denominateurEnd Sub

13/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Programmer avec des fonctions...

• A partir du problème principal, identifier des sous-problèmes

• Pour chaque sous-problème, écrire la solution sous forme de procédure ou de fonction

• On pourra faire appel à ces sous-programmes depuis le programme principal

• On pourra aussi réutiliser une procédure ou une fonction plus tard si le même sous-problème se pose... sans avoir à réécrire le code.

14/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

• On a besoin d'une fonction qui cherche Sarah Connor

• Programme principal :– Tant que Sarah Connor

non trouvée, chercher Sarah Connor

– Tuer Sarah Connor

Exemple : Terminator

15/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

• On a besoin d'une fonction qui dessine un trait entre deux points

• Programme principal :– Pour chaque sommet du polygone,

dessiner un trait entre ce sommet et le suivant

– Si le sommet est le dernier, dessiner un trait entre ce sommet et le premier

Exemple : dessiner un polygone

16/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Programme : pgcdFonction.cpp

int pgcd(int u, int v) {int w;while (u > 0) {

if (u < v) {w = u;u = v;v = w;}

u = u - v;}

return v;}

17/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Programme : pgcdFonction.h

#ifndef PGCDFONCTION#define PGCDFONCTION

int pgcd(int u, int v);

#endif

Le fichier .h ne fait que répertorier les fonctions écrites

A toujours écrire au débutd'un fichier .h

18/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Programme : reducFraction.cpp#include <iostream>

using namespace std;

#include "pgcdFonction.h"

int main() {

int numerateur, denominateur, p;

cout << "Numérateur? "; cin >> numerateur;

cout << "Dénominateur ? "; cin >> denominateur;

p = pgcd(numerateur, denominateur);

numerateur = numerateur / p;

denominateur = denominateur / p;

cout << "Fraction réduite: " << numerateur << "/" << denominateur << endl;

}

19/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Compilation et Exécution

benoit@HP:Info3/Cours/ReducFraction$ g++ reducFraction.cpp pgcdFonction.cpp

benoit@HP:Info3/Cours/ReducFraction$ ./a.out

Numérateur? 345

Dénominateur ? 18

Fraction réduite: 115/6

20/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Programme ooBasicFunction pgcd(u As Long, v As Long) As Long Dim nu As Long, nv As Long, w As Long nu = u nv = v While nu > 0 If nu < nv Then w = nu nu = nv nv = w End If nu = nu - nv Wend pgcd = nvEnd Function

Attention, ne jamais modifier lesparamètres d'une fonction Basic !

Il vaut mieux les copier dansdes variables temporaires

Équivalent à retourne (nv)

21/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Programme ooBasicSub Main

Dim maFeuille As Object

Dim numerateur As Long, denominateur As Long, p As Long

maFeuille = ThisComponent.Sheets.getByName("Feuille1")

numerateur = maFeuille.getCellByPosition(1,2).getValue

denominateur = maFeuille.getCellByPosition(1,3).getValue

p = pgcd(numerateur, denominateur)

print "PGCD: "+p

numerateur = numerateur / p

denominateur = denominateur / p

print "Fraction réduite: " + numerateur + " / " + denominateur

End Sub

22/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Programmer de manière récursive...

• On parle de programme ou de fonction récursive si la fonction s'appelle elle-même

• Généralement, une fonction récursive fait appel à elle-même pour résoudre une sous-partie du problème, puis utilise le résultat obtenu pour résoudre le problème global

• Nécessite une formulation récursive du problème (par exemple une relation de récurrence)

23/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

• Exemple : pour dessiner un arbre, on va utiliser la fonction qui dessine un trait pour définir la fonction dessineArbre (angle A, taille T):

– Si T > 0 Alors :• Dessiner trait d'angle A et de taille T• dessineArbre (A – 45°, T-1)• dessineArbre (A + 45°, T-1)

– Sinon on arrête

• La condition Si... est nécessaire pour que le programme s'arrête un jour !

• Pour dessiner l'arbre : dessineArbre (90°, 10)

Programmer de manière récursive...

24/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Calculer le PGCD de manière récursive

int pgcd(int u, int v) { int w;

if (u <= 0) return v ;if (u < v) { w = u; u = v; v = w;}return pgcd(u-v, v);

}

…......... Le programme principal n'est pas modifié !

Condition d'arrêt

25/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Liste des appels récursifs

fonction pgcd(E u, v: Entiers): Entier

Variables:w: Entier

DébutSi (u <= 0) alors retourne(v)Si (u < v) alors {

w ← uu ← vv ← w

}retourne pgcd(u - v, v)

Fin

Calcul de pgcd(10, 4) => retourne pgcd(6, 4)Calcul de pgcd(6, 4) => retourne pgcd(2, 4)Calcul de pgcd(2, 4) => retourne pgcd(2, 2)Calcul de pgcd(2, 2) => retourne pgcd(0, 2)Calcul de pgcd(0, 2) => retourne 2Donc pgcd(2, 2) retourne 2Donc pgcd(2, 4) retourne 2Donc pgcd(6, 4) retourne 2Donc pgcd(10, 4) retourne 2

On peut faire la liste des appels récursifs en faisant une simulationd'exécution du programme

26/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Quizz #1 (somme des n premiers entiers): combien de lignes

comportent une erreur ?1. #include <iostream>

2. using namespace std

3. int somme(int n) {

4.  int somme = n;

5.  for (int i = 1; i < n; i­­)

6.   somme = somme + i

7.  return i;

8. }

9.  int main() {

10.  int n;

11.  cout >> "Entrez n: ";

12.  cin << n;

13.  cout >> Somme = >> somme(n) >> endl;

14. }

15. }

27/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Renvoie un entieraléatoire entre 0 et 9

Quizz #2: le programme suivant est...

#include <stdlib.h>#include <iostream>using namespace std;

int main() {int valeur1, valeur2;int reponse;srand(time(NULL));valeur1 = rand()%10;valeur2 = rand()%10;cout<<"Quel est le résultat de "<<valeur1<<

" fois "<<valeur2<<" ?"<<endl;cin>>reponse;while (reponse != (valeur1*valeur2)) {

cout<<"Non ! Quel est le résultat de "<<valeur1<<" fois "<<valeur2<<" ?"<<endl;

cin>>reponse;}cout<<"Bravo !"<<endl;}

A) Un jeu de rapiditéB) Un jeu de calcul mental à

deux joueursC) Un jeu de calcul mental à

un joueur assez facileD) Un jeu de calcul mental à

un joueur assez difficile

28/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Deux semestres résumés en 3h...• Introduction• Boucles, fonctions, récursivité

– Méthodes itératives (boucles)– Fonctions– Méthodes récursives

• Structures, vecteurs, listes– Structures– Vecteurs– Listes chaînées

• Stockage sur disque– Principe général– Opérations courantes– Lecture/écriture au format texte– Lecture/écriture au format binaire

29/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Variables de type Structure

• Une structure permet d'organiser et de manipuler un ensemble de valeurs qui peuvent être de types différents

• Par exemple, on peut considérer qu'un(e) étudiant(e) est une entité constituée de :– un nom– une date de naissance– un numéro INE– un booléen indiquant s'il ou elle est boursier(e)– ...

30/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Exemple : structure fraction

• Définition de la structure• Définition des fonctions associées :

– Saisir une fraction au clavier– Afficher une fraction– Diviser une fraction– ...

31/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

struct fraction {int numerateur, denominateur;

};fraction saisirFraction() {

fraction nb;cin>>nb.numerateur>>nb.denominateur;

return nb;}void diviserFraction(fraction &nb, int v) {

nb.numerateur = nb.numerateur / v;nb.denominateur = nb.denominateur / v;

}

Programme : reducFractionStructure.cpp

!

32/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

void afficherFraction (fraction nb) {cout<<nb.numerateur<<" / "<< nb.denominateur<<endl;

}

int main() {fraction f;int p;f = saisirFraction();p = pgcd(f.numerateur, f.denominateur);diviserFraction(f, p);cout<<"Resultat: ";afficherFraction(f);

}

Programme : reducFractionStructure.cpp

33/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Variables de type Vecteur (ou Tableau)

• Un vecteur permet d'organiser et de manipuler un ensemble fini de valeurs toutes du même type

• Un vecteur est représenté par une suite de n cases numérotées de 0 à n − 1

• Exemples :– Les notes d'un groupe de 10 étudiants à un partiel– Les valeurs mesurées toutes les heures par un capteur

sur une période de 24 heures– Suite de 5 fractions qu'on peut réduire avec le

programme précédent– ...

34/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Exemple : le crible d'Eratosthène (3ème siècle av. JC)

• On cherche à savoir quels sont les nombres premiers entre 2 et 99

• On crée un tableau de booléens de taille 100• On suppose d'abord que tous ces nombres sont premiers :

toutes les cases du tableau sont initialisées à vrai• Pour chaque nombre, on détermine ses multiples : les cases

correspondantes passent à faux• A la fin, seules les cases correspondant à un nombre

premier ont la valeur vrai !

35/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

#include <iostream>using namespace std;void initialisation (bool p[]) { int i;

for (i = 2; i <= 99; i++) p[i] = true;

}void modificationMultiples (int nb, bool p[]) { int i = 2; while (nb*i < 100) {

p[nb*i] = false; i++;}

}

Programme : cribleEratosthene.cpp

36/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

int main()

{

bool premiers[100];

int i;

initialisation (premiers);

for (i = 2; i <= 99; i++) {

modificationMultiples (i, premiers);

}

for (i = 2; i <= 99; i++) {

if (premiers[i] == true)

cout << i << " est premier" << endl;

}

}

Programme : cribleEratosthene.cpp

Attention, il n'y aaucun lien entrecette variable i et

celles utiliséesdans nosfonctions

37/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Quizz #3 : quelle est la seule réponse vraie ?

A) Dans un vecteur les éléments peuvent être de types différents

B) Dans une structure les éléments sont obligatoirement tous du même type

C) On ne peut pas créer une structure contenant un vecteur

D) On peut créer un vecteur contenant des structures

38/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Quizz #4 : quel est le contenu du tableau « liste » après exécution ?

...

int liste[6] = {1, 1, 1, 2, 2, 2};

int i, j;

i = 0;

while (i < 6) {

 if ((i%2) == 0) {

  j = liste[i];

  liste[i+1] = j+1;

 }

 i++;

}

...

A) {1, 1, 1, 2, 2, 2}B) {1, 2, 3, 1, 2, 3}C) {1, 2, 1, 2, 2, 3}D) {1, 2, 1, 2, 3, 2}

39/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Listes

• Une liste permet d'organiser et de manipuler un ensemble non-défini de valeurs toutes du même type

• Une liste est une structure dynamique : sa taille peut augmenter ou diminuer pendant l'exécution du programme.

• Elle permet également d'insérer ou de supprimer simplement des éléments

• Les valeurs sont rangées dans des cellules, qui comportent aussi un lien vers la cellule suivante dans la liste (chaînage)

• Si une cellule a un lien NUL, elle est la dernière cellule• Le début de la liste est identifié par un pointeur, appelé en

général L ; si L = NUL, alors la liste est vide

40/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Définition d'une cellule

structure elem_liste {données : Entierlien : pointeur sur elem_liste

}

L3 5 Nul

Données Lien Données Lien

41/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Affichage d'une liste : listeAffichage

• Principe : parcourir la liste en suivant le chaînage

procédure affichage(E L: pointeur)DébutTant que (L != NUL) Faire { Afficher(L → données) L ← (L → lien)}

Fin

42/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Affichage d'une liste : simulation d'exécution

L3 12

Données Lien Données Lien

5 Nul

Données Lien

• Au départ L pointe la première cellule

Afficher(L → données)

43/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Affichage d'une liste : simulation d'exécution

L

3 12

Données Lien Données Lien

5 Nul

Données Lien

• L ← (L → lien)

• Afficher(L → données)

44/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Affichage d'une liste : simulation d'exécution

L

3 12

Données Lien Données Lien

5 Nul

Données Lien

• Afficher(L → données)

• L ← (L → lien)

• Tant que (L != NUL)…=> condition d’arrêt

45/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Création d'une liste

• Principe (ajout en tête):1. créer une nouvelle cellule2. chaîner cette nouvelle cellule avec la tête

de liste3. la nouvelle cellule devient la tête de liste4. on repart à l'étape 1

46/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Création d'une liste : listeCreationfonction création (): pointeurVariables:

L,p: pointeur; c: caractèreDébut

L ← NULFaire { p ← allouer elem_liste Afficher("Entrez une valeur") Saisir(p → donnees) (p → lien) ← L L ← p Afficher("Encore ? (O/N)") Saisir(c)} Tant que (c = 'O')

retourne(L)Fin

47/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Création d'une liste : simulation d'exécution

LNul

DébutL ← NULFaire

48/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Création d'une liste : simulation d'exécution

LDonnées Lien

DébutL ← NULFaire {

p ← allouer elem_liste

pNul

49/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Création d'une liste : simulation d'exécution

LDonnées Lien

DébutL ← NULFaire {

p ← allouer elem_listeSaisir(p → donnees)

p 5Nul

50/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Création d'une liste : simulation d'exécution

LDonnées Lien

Nul

DébutL ← NULFaire {

p ← allouer elem_listeSaisir(p → donnees) (p → lien) ← L

p 5Nul

51/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Création d'une liste : simulation d'exécution

LDonnées Lien

Nul

DébutL ← NULFaire {

p ← allouer elem_listeSaisir(p → donnees) (p → lien) ← LL ← p

p

5

52/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Création d'une liste : simulation d'exécution

LDonnées Lien

Nul

DébutL ← NULFaire {

p ← allouer elem_listeSaisir(p → donnees) (p → lien) ← LL ← p

5

Données Lien

p

53/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Création d'une liste : simulation d'exécution

LDonnées Lien

Nul

DébutL ← NULFaire {

p ← allouer elem_listeSaisir(p → donnees) (p → lien) ← LL ← p

5

Données Lien

p12

54/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Création d'une liste : simulation d'exécution

L3 12

Données Lien Données Lien

5 Nul

Données Lien

55/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Suppression dans une liste

• Suppression de toutes les cellules ayant la valeur val. Deux cas possibles :– Si la cellule est en tête de liste, alors la tête de liste se

déplace sur la cellule suivante– Sinon, on modifie le chaînage de la cellule précédente – Les cellules ne sont pas réellement supprimées, elles

sont simplement sorties de la liste

56/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Suppression dans une liste : listeSuppression

procédure suppression (E/S L: pointeur, E val:Entier)

Variables:premier: booléenp, prec: pointeur

Débutpremier ← vraip ← Ltant que (p != NUL) faire {

si (p → données = val) alors {// Suppression du 1er élémentsi (premier) alors

L ← L → lien

// Suppression ailleurs

57/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

sinon prec → lien ← p → lien} // finsi (p → données = val) sinon premier ← fauxprec ← pp ← p → lien} //fin tant que (p != NUL)

Fin

Suppression dans une liste : listeSuppression

58/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Suppression dans une liste : simulation d'exécution

premier ← vraip ← L tant que (p != NUL) faire {

si (p → données = val) … sinon

L3 12

Données Lien Données Lien

5 Nul

Données Lien

premier

p

val = 12

59/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Suppression dans une liste : simulation d'exécution

sinon premier ← fauxprec ← pp ← p → lien

//fin tant que (p != NUL)

L3 12

Données Lien Données Lien

5 Nul

Données Lien

premier

p

val = 12

prec

60/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Suppression dans une liste : simulation d'exécution

si (p → données = val) alors {si (premier) alors L ← L → lien sinon prec → lien ← p → lien} // finsi (p → données = val)

L3 12

Données Lien Données Lien

5 Nul

Données Lien

premier

p

val = 12

prec

61/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Suppression dans une liste : simulation d'exécution

si (p → données = val) alors {si (premier) alors L ← L → lien sinon prec → lien ← p → lien} // finsi (p → données = val)

L3 12

Données Lien Données Lien

5 Nul

Données Lien

premier

p

val = 12

prec

62/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Suppression dans une liste : simulation d'exécution

tant que (p != NUL) faire {…}fin

L3 12

Données Lien Données Lien

5 Nul

Données Lien

premier

p

val = 12

prec

63/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Suppression dans une liste : simulation d'exécution

premier ← vraip ← L tant que (p != NUL) faire {

si (p → données = val)

L3 12

Données Lien Données Lien

5 Nul

Données Lien

premier

p

val = 3

64/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Suppression dans une liste : simulation d'exécution

premier ← vraip ← L tant que (p != NUL) faire {

si (p → données = val)

L3 12

Données Lien Données Lien

5 Nul

Données Lien

premier

p

val = 3

65/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Suppression dans une liste : simulation d'exécution

si (premier) alorsL ← L → lien

L3 12

Données Lien Données Lien

5 Nul

Données Lien

premier

p

val = 3

66/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

• Pour plus d'infos sur les listes chaînées :– Reprendre le cours d'Info II

– Faire des simulations d'exécution

67/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Programme : liste.cpp#include <iostream>using namespace std;

struct elem_liste {int donnees;elem_liste *lien;

};

typedef elem_liste * pointeur;

void affichage (pointeur L) {while (L != NULL) {

cout<<L → donnees<<endl;L = L → lien;

}}

68/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

pointeur creation() {pointeur L, p;char c;L = NULL;do {

p = new elem_liste;cout<<"Entrez une valeur: ";cin>>p → donnees;p → lien = L;L = p;cout<<"Encore ? (O/N): ";cin>>c;

} while (c == 'O');return L;

}

Programme : liste.cpp

69/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

pointeur creation() {pointeur L, p;char c;L = NULL;do {

p = new elem_liste; cout<<"Entrez une

valeur: ";cin>>p → donnees;p → lien = L;L = p;cout<<"Encore ?

(O/N): ";cin>>c;

} while (c == 'O');return L;

}

Programme : liste.cpp

Source d’ennui si le système n’a plus assez de mémoire, i.e.

retourne null

Si p=null : Segmentation Fault !Il faudrait toujours tester lavaleur d'un pointeur avant des'en servir...

70/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

pointeur creation() {pointeur L, p;char c;L = NULL;do {

p = new elem_liste;if (p!=null) {

cout<<"Entrez une valeur: ";cin>>p → donnees;p → lien = L;L = p;cout<<"Encore ? (O/N): ";cin>>c; }

else c = ‘n’;} while (c == 'O');return L;

}

Programme : liste.cpp

71/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

void suppression (pointeur &L, int val) {bool premier; pointeur p, prec;premier = true;p = L;while (p != NULL) {

if (p → donnees == val) {if (premier)

L = L → lien;else

prec → lien = p → lien;}

else premier = false;prec = p;p = p → lien;}

}

Programme : liste.cpp

72/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

int main() {

pointeur L;

L = creation();

suppression(L, 10);

affichage(L);

}

Programme : liste.cpp

73/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Deux semestres résumés en 3h...• Introduction• Boucles, fonctions, récursivité

– Méthodes itératives (boucles)– Fonctions– Méthodes récursives

• Structures, vecteurs, listes– Structures– Vecteurs– Listes chaînées

• Stockage sur disque– Principe général– Opérations courantes– Lecture/écriture au format texte– Lecture/écriture au format binaire

74/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Fichiers

• Un fichier est une entité dans laquelle on peut lire ou écrire des données. Une fois écrites, les données sont conservées sur le support (disque dur, clef USB, ...)

• Lire des données depuis un fichier équivaut un peu à saisir des données au clavier : le fichier remplace le clavier

• Ecrire des données dans un fichier équivaut un peu à afficher des données à l'écran : le fichier remplace l'écran

• Seule différence : on peut éventuellement se déplacer à l'intérieur du fichier

• Avant toute opération, le fichier doit être chargé en mémoire : on parle d'ouverture ou de chargement

75/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Exemple de fichier

• Fichier contenant des relevés météo stockés sous la forme suivante : VILLE HEURE1 TEMPERATURE1 HEURE2 TEMPERATURE2

• Exemple :Reykjavik 4 -15.4 16 3.4Limoges 6 -1.5 18 12.5GothamCity 5 18.5 20 30.2

76/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Ouverture d'un fichier

• Si le fichier n'existe pas encore, il faut le créer (dire où il sera sauvegardé)

• Sinon, il faut le désigner (dire où il est placé)• Une fois créé ou désigné, il faut spécifier le mode

d'ouverture :– mode lecture : permettra seulement de lire des données

dans le fichier– mode écriture : permettra seulement d'écrire des

données dans le fichier– mode lecture/écriture : permettra les deux.

77/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

La tête de lecture/écriture

Là.

78/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

La tête de lecture/écriture

• Lorsqu'on ouvre un fichier, la tête de lecture/écriture est positionnée au début du fichier

• Lorsqu'on lit ou écrit un élément dans le fichier, cette opération s'effectue à la position courante de la tête

• Après l'opération, la tête se déplace derrière l'élément qui vient d'être lu ou écrit

• La fonction Fin (fichier) renvoie vrai si la tête a atteint la fin du fichier (inutile d'essayer de lire des données dans ce cas)

• Il est impossible de supprimer ou d'insérer de nouvelles données dans un fichier ; par contre on peut écraser des données (écrire "par-dessus" des données existantes)

79/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Format texte

• Des données stockées au format texte sont "lisibles par un humain"

• ... et donc lisibles par un éditeur de texte, par exemple gedit ou wordpad

• Dans la pratique (en langage C), lecture avec fscanf et écriture avec fprintf

• Il faudrait toujours vérifier que la fonction fscanf renvoie une valeur > 0 avant d'exploiter les données…!

80/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Charger un fichier texte (dont on connaît la structure...)

#include <stdio.h>

#include <stdlib.h>

#include <iostream>

using namespace std;

int main() {

 FILE *f;

 f = fopen("relevesMeteo.txt", "r");

 if (f == NULL) {

  printf ("Opération impossible");

  exit (0);

 } 

 while (1) {

  char nom[100];

  int h1, h2; float r1, r2;

  fscanf(f, "%s", nom);

  if (feof(f)) break;

  fscanf(f, "%d", &h1);

  fscanf(f, "%f", &r1);

  

  fscanf(f, "%d", &h2);

  fscanf(f, "%f", &r2);

  cout<<nom<<": ("<<h1<<", "<<r1<<")     ("<<h2<<", "<<r2<<")"<<endl;

 }

 fclose(f);

}

Choix d'un fichierdans le dossier courant

Indique qu'il n'y a plus rien à lire dans le fichier

81/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Les formateurs

• La syntaxe des formateurs est la suivante :

• %[attributs][largeur][.précision][taille] type

• Un formateur commence donc toujours par le caractère %. Pour afficher ce caractère sans faire un formateur, il faut le dédoubler (%%)

Type de donnée à afficher Caractère de formatage

Entier décimal signé d

Entier décimal non signé u ou i

Entier octal non signé o

Entier hexadécimal non signé

x (avec les caractères 'a' à 'f') ou X (avec les caractères 'A' à 'F')

Flottant de type double f, e, g, E ou G

Caractère isolé c

Chaîne de caractères s

Pointeur p

82/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Ouverture en lecture, écriture, ...pointeur creation (char nom_fichier[]) {

FILE *f; pointeur L, p;f = fopen(nom_fichier, "r");

• le premier paramètre est évidemment le nom du fichier, le 2ème ("r") représente de mode d'ouverture de ce fichier. Voici les paramètres possibles

– r ouverture en lecture seulement – w ouverture en écriture seulement (la fonction crée le fichier s'il n'existe

pas) – a ouverture en écriture seulement avec ajout du contenu à la fin du fichier

(la fonction crée le fichier s'il n'existe pas) – r+ ouverture en lecture et écriture – w+ ouverture en lecture et écriture (la fonction crée le fichier s'il n'existe

pas) – a+ ouverture en lecture et écriture avec ajout du contenu à la fin du fichier

(la fonction crée le fichier s'il n'existe pas)

83/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Créer un fichier texte#include <stdio.h>

#include <stdlib.h>

#include <iostream>

using namespace std;

int main() {

 FILE *f;

 int n, i;

 f = fopen("notesEtudiants.txt", "w");

 if (f == NULL) {

  printf ("Opération impossible");

  exit (0);

 } 

 cout<<"Nombre d'étudiants ? ";

 cin>>n;

 for (i = 0; i < n; i++) {

  char nom[100];

  float note;

  cout<<"Nom ? ";

  cin>>nom;

  cout<<"Note ? ";

  cin>>note;

  fprintf(f, "%s ", nom);

  fprintf(f, "%f\n", note);

 }

 fclose(f);

}

!

A vous d'ajouterles espaces et les retours à la ligne

84/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Quizz #5 : laquelle de ces propositions est fausse ?

A) Un fichier texte peut contenir des données de n'importe quel type (caractères, nombres, etc)

B) Un fichier texte ne peut contenir une image ou une vidéo

C) Un fichier texte peut être facilement compressé

D) Un fichier texte peut contenir un nombre quelconque de caractères

85/85Benoit.Crespin@unilim.fr - https://community-sciences.unilim.fr/course/view.php?id=1873

Format binaire

• Les données seront stockées sous forme binaire, donc illisibles avec un éditeur de texte

• Une conversion automatique se fait lors des opérations de lecture/écriture

• En langage C, on utilise les fonctions fread et fwrite

• Ici encore, il faut vérifier que fread renvoie une valeur > 0

Recommended