Cours Structures de Donnees

Faculté des Sciences et Techniques de Tanger Maroc

Module : Algorithmes & Structures

de Données en Langage C

MIPC II-4 Réalisé par : Professeur Chakkor Saad

2010-2011

1

[email protected]

Programme

�Tableaux et chaînes de caractères

�Les fonctions et Récursivité

�Directives au pré processeur

� Méthodes de tri et de recherche

Pointeurs et Fichiers

2

�Pointeurs et Fichiers

� Type composé et structures

�Listes chaînées

�Arbres

�Tables de hachage

�Graphes

Evaluation� Remarque !! :

� la présence et la réalisation des Exos de TD & de TP & mini-projet seront pris en considération dans la note finale de module.

� CC1� CC1� CC2

� Examen de TP

3

Les tableaux

� Un tableau représente selon ses dimensions, un vecteur ou une matrice d'éléments d'un même type.

4

� Un tableau est un ensemble fini d'éléments de même type, stockés en mémoire à des adresses contiguës.

Les tableaux

� Déclaration de tableaux en C :

<TypeSimple> <NomTableau>[<Dimension>];

5

<TypeSimple> <NomTableau>[<Dimension>];

Les noms des tableaux sont des identificateurs

Algorithmique & Programmation : Langage C

Les tableaux à une dimension

Déclaration: type nom[dim]; Exemples: int compteur[10];float nombre[20];

Utilisation:

Les tableaux

6

Un élément du tableau est repéré par son indice. En langage C les tableaux commencent à l'indice 0. L'indice maximum est donc dim-1.

Appel: nom[indice]

Exemples: compteur[2] = 5;nombre[i] = 6.789;printf("%d",compteur[i]);scanf("%f",&nombre[i]);

6


Les tableaux

Les tableaux à plusieurs dimensions:

Tableaux à deux dimensions:

Déclaration: type nom[dim1][dim2];

Exemples : int compteur[4][5];

float nombre[2][10];

Utilisation:

7

Utilisation:

Un élément du tableau est repéré par ses indices. En langage C les tableaux

commencent aux indices 0. Les indices maximum sont donc dim1-1, dim2-1.

Appel: nom[indice1][indice2]

Exemples: compteur[2][4] = 5;

nombre[i][j] = 6.789;

printf("%d",compteur[i][j]);

scanf("%f",&nombre[i][j]);

7


Initialisation des tableaux

On peut initialiser les tableaux au moment de leur déclaration:

Exemples:

int liste[10] = {1,2,4,8,16,32,64,128,256,528};

Les tableaux

8

int liste[10] = {1,2,4,8,16,32,64,128,256,528};

float nombre[4] = {2.67,5.98,-8,0.09};

int x[2][3] = {{1,5,7},{8,4,3}}; /* 2 lignes et 3 colonnes *

8

Les tableaux

� Si la dimension n'est pas indiquée explicitement lors de l'initialisation, alors le compilateur réserve automatiquement le nombre d'octets nécessaires.

� Exemples :

9

� Exemples :

� int A[] = {10, 20, 30, 40, 50};

� ==> réservation de 5*sizeof(int) octets (dans notre cas: 10 octets)

� float B[] = {-1.05, 3.33, 0.87, -12.3};

� ==> réservation de 4*sizeof(float) octets (dans notre cas: 16 octets)

Les tableaux

• Affichage et affectation :

Ecrire un programme qui permet de saisir N valeurs entières

10

dans un tableau puis de les afficher horizontalement.

Calculer et afficher la somme des éléments de ce tableau.


Les tableaux : Exercices

Exercice 1:Ecrire un programme qui permet de chercher le maximum et l’indice de néléments d’un tableau.

Exercice 2 :Ecrire un programme qui permet de calculer la somme de n éléments d’untableau

11

tableau

Exercice 3:Ecrire un programme qui permet de compter le nombre d’occurance d’unélément dans un tableau de n éléments.

Exercice 4:Ecrire un programme permettant de saisir et d’afficher les éléments d’unematrice de n colonnes et m lignes.

Exercice 5:Ecrire un programme permettant de calculer le déterminant d’une matrice (2X2)

11


Exercice 6:

� Ecrire un programme qui permet d’insérer une valeur entrée au clavier dans un tableau d’entiers.

Exercice 7:

� Rechercher dans un tableau d'entiers une valeur VAL entrée au clavier. Afficher la position de VAL si elle se trouve dans le tableau, sinon afficher un message correspondant. La valeur POS qui est utilisée pour mémoriser la position de la valeur dans le tableau, aura la valeur -1 aussi longtemps que VAL n'a pas été trouvée.

12


Exercice 8 :

� Ecrire un programme qui permet de supprimer une valeur d’un tableau d’entiers en indiquant sa position dans ce tableau.ce tableau.

Exercice 9 :

� Ecrire un programme qui permet de modifier une valeur d’un tableau d’entiers en indiquant sa position dans ce tableau.

13


Les chaînes de caractères

� Les chaînes de caractères sont des tableaux de caractères

dont le dernier élément est \0.

� On peut les déclarer comme :

14

On peut les déclarer comme :

* char mot[80] ;

il faudra dans ce cas s'assurer que la longueur du mot ne dépassepas 80 caractères.

* char *mot ;

il faudra réserver dynamiquement la mémoire : on abordera plusloin ce sujet.


Les chaînes de caractères : exemple

# include <stdio.h>

# define MAXCHAINE 80

main()

/* copie une chaîne de caractères lue sur l'entrée standard dans une autre chaîne */

{ char mot1[MAXCHAINE], mot2[MAXCHAINE] ;

int i ;

printf("entrez une chaîne de caractères : mot1 =?\n") ;

15

printf("entrez une chaîne de caractères : mot1 =?\n") ;

scanf("%80s",mot1) ;

i = 0 ;

while ((mot1[i] != '\0') && (i < MAXCHAINE))

{ mot2[i] = mot1[i] ;

i++ ; }

if (i >= MAXCHAINE) printf("mot trop long\n") ;

else { mot2[++i] = '\0' ;

printf(" mot2 = %s\n",mot2) ; } }


� Strcmp

cette fonction compare lexicographiquement deux chaînes decaractères.

Exemple:

Manipulation des chaînes

16

Exemple:

char *mot1, *mot2 ;

...

if (strcmp(mot1, mot2) < 0) then printf("mot1 < mot2") ;

else if (strcmp(mot1, mot2) > 0) then printf("mot1> mot2") ;

else printf("mot1 = mot2") ;


� strcpy

strcpy(mot1,mot2);

copie la chaîne mot2 dans mot1.

� strlen

Manipulation des chaînes

17

� strlen

int longueur_mot ;

longueur_mot = strlen(mot);

� strcatmot3 = strcat(mot1, mot2);

mot3 est la concaténation de mot1 et mot2.


Manipulation des chaînes : Exercices

Exercice 1 :Ecrire un programme qui lit une ligne de texte (ne dépassant pas 200 caractères) la

mémorise dans une variable chaîne et affiche ensuite:

a) la longueur L de la chaîne.

b) le nombre de 'e' contenus dans le texte.

c) toute la phrase à rebours, sans changer le contenu de la variable TXT

Exercice 2 :Ecrire un programme qui lit un texte TXT (de moins de 200 caractères) et qui enlève

18

Ecrire un programme qui lit un texte TXT (de moins de 200 caractères) et qui enlève

toutes les apparitions du caractère ‘a' en tassant les éléments restants. Les

modifications se feront dans la même variable TXT.

Exercice 3 :Ecrire un programme qui lit deux chaînes de caractères CH1 et CH2, les compare

lexico graphiquement et affiche le résultat:

Exercice 4 :Ecrire un programme qui lit deux chaînes de caractères CH1 et CH2 et qui copie la

première moitié de CH1 et la première moitié de CH2 dans une troisième chaîne

CH3. Afficher le résultat.


Déclaration :

type_de_la_fonction nom_de_fonction(type arg1, type arg2, ...)

{

déclarations

Les fonctions

19

déclarations

instructions

return(valeur_de_la_fonction) ;

}

19


Exemple :

Les fonctions

int max(int x, y )

/* calcule le maximum de deux entiers */

{

20

{

int m ;

if (x > y) then m=x ;

else m=y ;

return (m) ;

}

20


Remarques:

� On peut avoir des fonctions sans arguments, comme on peut avoirune fonction qui ne retourne rien; à ce moment , on écrit :

void nom_fct (void) ou bien void nom_fct ()

Les fonctions

21

void nom_fct (void) ou bien void nom_fct ()

� Le type d'une fonction est implicitement entier.

� Le passage des arguments se fait toujours par valeur : on verra plustard comment modifier les arguments d'une fonction.

21


Exercice 1:

Ecrire une fonction qui permet de calculer le carré d’un entier.

Exercice 2 :

Ecrire une fonction qui permet de calculer la moyenne d’un tableau.

Exercice 3 :

Ecrire une fonction qui permet de calculer la factorielle d’un entier N!,une autre fonction pour calculer XN une troisième pour calculer XN!

Les fonctions : Exercices

22

une autre fonction pour calculer XN une troisième pour calculer XN!

Exercice 4 :

Ecrire une fonction permettant de vérifier qu’un nombre est parfait.

Ecrire une fonction permettant d’afficher la liste des nombres parfaitsinférieurs à un chiffre donné.

Exercice 5 :

Ecrire une fonction permettant de calculer pour une valeur X son imagepar un polynôme P(X) de degré N.

22


� La récursivité est une méthode de description d’algorithmes qui permet à une fonction de s’appeler elle-même !

� Forme générale :

� If(condition) return valeur

� Else fonction récursive

Récursivité

� Else fonction récursive

� Exemple : calcul de la factorielle :� Long fact (int N){

� If(N==0) return 1;

� Else

� Return fact(N-1)*N;

� }

23


� Exercice 1 :

� Ecrire une fonction récursive qui calcule le produit de deux valeurs entières A et B ?

� Exercice 2 :

� Ecrire une fonction récursive qui calcule le PGCD de

Récursivité

� Ecrire une fonction récursive qui calcule le PGCD de deux entiers A et B ?

� Exercice 3 :

� Ecrire une fonction récursive permettant d’afficher des entiers < N saisi au clavier selon l’ordre :

� Croissant ? Décroissant ?

24


� Exercice 4 :

� Ecrire une fonction récursive qui convertit un nombre donné en base 10 vers une base B 2<=B<=9 ?

Récursivité

donné en base 10 vers une base B 2<=B<=9 ?

� Ecrire une fonction récursive qui réalise l’opération inverse ?

25


Les directives au préprocesseur

� Le préprocesseur est la première étape de la compilation en C. Plusexactement le préprocesseur s’exécute avant le compilateur.

� Le préprocesseur s’occupe seulement d’effectuer des remplacements� Le préprocesseur s’occupe seulement d’effectuer des remplacementsde valeurs ou des inclusions de fichier.

� Le préprocesseur permet également de créer des constantes. Il n’esten aucun cas capable de détecter les erreurs qu’elle soit logiques ousyntaxiques.

2626



� les directives d’inclusionl’inclusion peut se faire de deux façons différentes :

#include <nom_de_fichier>#include "nom_de_fichier "

Exemple:

27

� Les directives de définition de variableson définit une variable avec le préprocesseur de la façon suivante :

#define NOM valeur de remplacement.

Ainsi pour l’exemple précédent on a :#define PI 3.14159265358979

Exemple:

#include <stdio.h>#include <math.h>

27



� Exemple:

#include <stdio.h>

#define FONCTION_PRINCIPALE void main ()

#define BEGIN {

#define END }

28

#define END }

#define DEBUT_AFFICHAGE printf(

#define FIN_AFFICHAGE );

FONCTION_PRINCIPALE

BEGIN

DEBUT_AFFICHAGE "define c'est bien !!! " FIN_AFFICHAGE

END

28


Les tableaux : algorithmes de Tri

Le tri est le classement dans ordre croissant ou décroissant deséléments d’un tableau.

Plusieurs méthodes de tri :

� Tri par sélection

29

� Tri par sélection

� Tri par insertion

� Tri par bulle

� Tri rapide

� Tri par fusion


� Tri par sélection :

� Problème : Classer les éléments d'un tableau A par ordre décroissant.

� Principe :

� Parcourir le tableau de gauche à droite à l'aide de l'indice I. Pour chaque élément A[I] du tableau, déterminer la position PMAX du (premier) maximum à droite de A[I] et échanger A[I] et A[PMAX].


maximum à droite de A[I] et échanger A[I] et A[PMAX].

30


Algorithme de Tri par sélection :

� tab_entiers[MAX]

� PROCEDURE selection (tab_entiers t)

� POUR CHAQUE i entier dans [0 ; MAX - 1 [

� min ⇐ i min ⇐ i

� POUR CHAQUE j entier dans [ i+1 ; MAX [

� SI t[j] < t[min] ALORS

� min ⇐ j

� SI min ≠ i ALORS

� t[i] ⇐ t[min]

31


� Exercice 1 :

� Ecrire un programme permettant de réaliser le tri par sélection des éléments d’un tableau d’entiers selon l’ordre décroissant ?


l’ordre décroissant ?

32



� Tri par propagation ou par bulle (bubble sort) :

� Problème : Classer les éléments d'un tableau A par ordre croissant.

� Principe :� Principe :

� On parcourt la liste, et on compare les couples d'éléments successifs. Lorsque deux éléments successifs ne sont pas dans l'ordre croissant, ils sont échangés. Après chaque parcours complet de la liste, l'algorithme recommence l'opération. Lorsque aucun échange n'a lieu pendant un parcours, cela signifie que la liste est triée : l'algorithme peut s'arrêter. (comme une bulle qui remonte à la surface d'un liquide).

33


�Tri par propagation ou par bulle (bubble sort) :

34


� Prenons la liste de chiffres suivante "5 1 4 2 8" et trions-la de manière croissante en utilisant l'algorithme de tri à bulles.

� Première étape:( 5 1 4 2 8 ) ( 1 5 4 2 8 ) Ici, l'algorithme compare les deux premiers éléments (5 et 1) et les intervertit.

� ( 1 5 4 2 8 ) ( 1 4 5 2 8 )

�Tri par propagation ou par bulle (bubble sort) :

� ( 1 5 4 2 8 ) ( 1 4 5 2 8 )( 1 4 5 2 8 ) ( 1 4 2 5 8 )( 1 4 2 5 8 ) ( 1 4 2 5 8 )

� Deuxième étape:( 1 4 2 5 8 ) ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) ( 1 2 4 5 8 )( 1 2 4 5 8 ) ( 1 2 4 5 8 )( 1 2 4 5 8 ) ( 1 2 4 5 8 )

Troisième étape:( 1 2 4 5 8 ) ( 1 2 4 5 8 )( 1 2 4 5 8 ) ( 1 2 4 5 8 )( 1 2 4 5 8 ) ( 1 2 4 5 8 )( 1 2 4 5 8 ) ( 1 2 4 5 8 )

35


� Exercice 2 :

� Ecrire un programme permettant de réaliser le tri par bulle des éléments d’un tableau d’entiers selon l’ordre croissant ?


croissant ?

36


� Tri par insertion :


� Principe :


� on suppose les i-1 premiers éléments triés. On prend le i ème élément, et on essaie de le mettre à sa place dans les éléments déjà triés. Et on continue jusqu'à i=N.

� Pour classer le i ème élément du tableau A, on regarde successivement en marche arrière à partir du i-1ème . On décale les éléments visités vers la droite pour pouvoir mettre A[i] à sa juste place.

� Décaler les éléments du tableau pour insérer l'élément considéré à sa place dans la partie déjà triée.

37


� Algorithme de Tri par Insertion :� DEBUT Const N=/*Valeur positive*/

� Var Tab: tableau(1..N) entier

� Aux,i,k : entier

� Pour i<---2 à N faire

� Aux <---Tab[i]


� k <--- i

� Tantque(k>1 et Tab[k-1]>Aux) faire

� Tab[k] <---Tab[k-1]

� k <--- k-1

� FinTantque

� Tab[k] <---Aux

� FinPour

� FIN

38



�Tri par insertion :

�Exercice 4 :

� Ecrire un programme

39

� Ecrire un programme permettant de réaliser le tri par insertion des éléments d’un tableau d’entiers selon l’ordre croissant ?


� Tri par fusion :


� Principe :


1) On découpe en deux parties à peu près égales les données à trier

2) On trie les données de chaque partie

3) On fusionne les deux parties

40


� Tri par fusion :

� Fusionner [1;2;5] et [3;4] : On sait que le premier élément de la liste fusionnée sera le premier élément d'une des deux listes d'entrée (soit 1, soit 3), propriété non remarquable sur des listes non triées.

� On compare donc 1 et 3 → 1 est plus petit.� [2;5] - [3;4] → [1]

On compare 2 et 3 → 2 est plus petit.


� On compare 2 et 3 → 2 est plus petit.� [5] - [3;4] → [1;2]� On compare 5 et 3 → 3 est plus petit.� [5] - [4] → [1;2;3]� On compare 5 et 4 → 4 est plus petit.� [5] → [1;2;3;4]� [1;2;3;4;5]

41


Tri par fusion :

42


� Exercice 3 :

� On dispose de deux tableaux A et B (de dimensions respectives N et M), triés par ordre croissant. Fusionner les éléments de A et B de façon à obtenir un seul tableau trié selon l’ordre croissant ?


trié selon l’ordre croissant ?

� Exercice 4 :

� Ecrire un programme permettant de réaliser le tri par fusion d’un tableau d’entiers selon l’ordre croissant ?

43


� Tri rapide :


� Principe :On place un élément d'un tableau à trier (pivot) à sa place définitive en permutant tous les éléments de telle sorte que tous ceux qui


définitive en permutant tous les éléments de telle sorte que tous ceux qui lui sont inférieurs soient à sa gauche et que tous ceux qui lui sont supérieurs soient à sa droite. Cette opération s'appelle le partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l'opération de partitionnement. Ce processus est répété récursivement,

jusqu'à ce que l'ensemble des éléments soit trié.

44


� Tri rapide :

45


� Algorithme de Tri rapide :

� Tri_rapide(a, gauche, droite)

� tant que droite-gauche+1 > 1

� sélectionner une valeur de pivot a[pivotIndex]

� pivotNewIndex := partition(a, gauche, droit, pivotIndex)

� si pivotNewIndex-1 - gauche < droit - (pivotNewIndex+1) � si pivotNewIndex-1 - gauche < droit - (pivotNewIndex+1) tri_rapide(a, gauche, pivotNewIndex-1)

� gauche := pivotNewIndex+1

� sinon tri_rapide(a, pivotNewIndex+1, droit)

� droit := pivotNewIndex-1

� fin_si

� fin_tant_que

46


� Exercice 5 :

� Ecrire un programme permettant de réaliser le tri rapide d’un tableau d’entiers selon l’ordre croissant ?


47


� Recherche séquentielle :� Principe :

Lire le tableau du début vers la fin. Si le tableau n'est pas trié, arriver en fin du tableau signifie que l'élément n'existe pas, dans un tableau trié le premier élément trouvé supérieur à l'élément recherché permet d'arrêter

Les tableaux : algorithmes de Recherches

premier élément trouvé supérieur à l'élément recherché permet d'arrêter la recherche, de plus cette position correspond à celle où il faudrait insérer

l'élément cherché pour garder un tableau trié.

48


int Rech_Sequentielle(type_tus tab, int N, composante val)

/*rend -1 si val non trouvée, première occurrence trouvée sinon */

{ int i;

Recherche séquentielle :

{ int i;

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

{

if(tab[i]==val)

return(i);

}

return(-1); }

49


� Recherche dichotomique :

Dans le cas d'un tableau trié, en cherchant à limiter l'espace de recherche. On compare la valeur cherchée à l'élément central du tableau, si ce n'est pas la bonne, un test permet de trouver dans quelle moitié du tableau on trouvera la valeur. On


dans quelle moitié du tableau on trouvera la valeur. On continue récursivement jusqu'à un sous-tableau de taille 1.

50


� Algorithme dichotomie :� //déclarations début, fin, val, mil : Entier t : Tableau [0..100] d'entier

� trouvé : Booléen

� //initialisation début <- 0 fin <- 100 trouvé <- faux

� //Question Répéter Afficher "Valeur recherchée ? (entre 0 et 100)

� Saisir val Jusqu'à début<=val et val<=fin

� //Boucle de recherche


� //Boucle de recherche

� Répéter mil <- début + ((fin-début) / 2)

� Si t[mil] = val alors trouvé <- vrai Sinon

� Si val > t[mil] Alors début <- mil + 1

� Si t[début] = val Alors mil <- début trouvé <-Vrai

� FinSi Sinon fin <- mil – 1

� Si t[fin] = val Alors mil <- fin trouvé <- vrai FinSi FinSi FinSi

� Jusqu’à trouvé ou ( début >= fin )

51


Recherche dichotomique :

� Rech_dichotomie(int tab[], int N, composante val)

� { int g,m,d; /* gauche, milieu, droite */

� g=0;d=N;

� while (g<=d)

� { m=(g+d)/2; /* division entière */

� if(val<tab[m])� if(val<tab[m])

� d=m-1;

� else

� if(val>tab[m])

� g=m+1;

� else return(m) }

� return(-1);}

52


� Définition :

� Un pointeur est une variable spéciale qui contient l’adresse d’une autre variable.

� Une variable de type pointeur se déclare à l'aide de l'objet pointé précédé du symbole * (opérateur d'indirection).

Les pointeurs

d'indirection).

� Exemples :

� Int *p ; p est un pointeur pointant sur un objet de type int

� Char *c ; c est un pointeur pointant sur un objet de type char

53


� il s'agit d'une technique de programmation très puissante, permettant de définir des structures dynamiques, c'est-à-dire qui évoluent au cours du temps (par opposition aux tableaux par exemple qui sont des structures de données statiques, dont la taille est figée à la définition).

� un pointeur est une variable qui permet de stocker une

Les pointeurs

� un pointeur est une variable qui permet de stocker une adresse, il est donc nécessaire de comprendre qu'est ce qu’une adresse.

54


Intérêt des pointeurs

� Les pointeurs ont un grand nombre d'intérêts :

� manipuler des données pouvant être importantes (au lieu de passer à une fonction un élément très grand (en taille) : fournir un pointeur vers cet élément...)

� Les tableaux ne permettent de stocker qu'un nombre fixé d'éléments de même type. En stockant des pointeurs dans les cases d'éléments de même type. En stockant des pointeurs dans les cases d'un tableau, il sera possible de stocker des éléments de taille diverse, rajouter des éléments au tableau en cours d'utilisation (notion de tableau dynamique qui est très étroitement liée à celle de pointeur)

� créer des structures chaînées, c'est-à-dire comportant des maillons

55


� Soit la variable :

� Int a=7 ;

� a est représentée par :

� L’adresse de l’espace mémoire qui lui est réservée.

� Le contenu de cet espace mémoire.

� Int *pt ;

Les pointeurs

� Int *pt ;

� Pt=&a si Pt contient l’adresse d’une variable a on dit que ptpointe sur a.

&a 7

&pt Pt

56


� Les opérateurs de base :

� & : opérateur qui renvoie l’adresse de l’objet désigné.

� * : opérateur qui renvoie le contenu de la variable pointée.

� Exemples :

� Int X=4,Y ;

Int *p,*q ;

Les pointeurs

� Int *p,*q ;

� P=&X ; /* p contient l’adresse de X*/

� Printf(‘%d’,*P) : affiche le contenu de la variable pointée par P

� Y=*P-1 ; /* y vaut 3 */

� *P+=1 ; /* incrémente X de 1*/

� (*P)++ ; /* incrémente de 1 la variable pointée par P , X vaut 6*/

� N.B : les parenthèses sont importantes. Car *P++ incrémente le pointeur P(l’adresse )et non pas la valeur de X(contenu).

57


� Pointeurs et tableaux :

� Les pointeurs ont une forte relation avec les tableaux, ils facilitent beaucoup plus leur manipulation.

� Exemple :

Int * tab ;

Les pointeurs

� Int * tab ;

� Tab=(int *)malloc(sizeof(int) *10) ;

� Réserve un espace mémoire pour dix entiers.

� Il faut impérativement utiliser une fonction pour allouer dynamiquement un espace Comme la fonction malloc de la bibliothèque <malloc.h>.

58


� Les écritures suivantes sont équivalentes :

� *tab �� tab[0] ;

� Tab �� &tab[0] ;

� *(tab+i) �� tab[i] ;

Les pointeurs

� *(tab+i) �� tab[i] ;

� (tab+i) �� &tab[i] ;

59


� Pointeurs et chaînes de caractères :

� Une chaîne de caractère est un tableau de caractères : la manipulation des chaînes de caractères est identique à celle d’un tableau.

Les pointeurs

� Déclaration :

Char *ch ;

Ch=(char *)malloc(sizeof(char)*20) ;

60


� Passage des arguments d’une fonction :

� Deux types de passage des arguments, passage par valeur et passage par adresse.

� Passage par valeur :

� Les paramètres sont passés par copie de valeur et ne seront pas modifiés en dehors de la fonction.

� Exemple :

� #include <stdio.h>

Les pointeurs


� Void echanger(int x,int y)

� {int z ; z=x ; x=y ;y=z ;

� Printf(‘x= %d y=%d ‘,x,y) ;

� }

� main()

� {

� int x=5,y=7 ; Exécution :

� Echanger(x,y) ; X=7 y=5

� Printf(‘x= %d y=%d ‘,x,y) ; X=5 y=7

� }

61


� Passage par adresse :

� Pour échanger les paramètres x et y de la fonction, il faut le passage par adresse. Les pointeurs offrent la possibilité de modifier les contenus des variables de la fonction principale (fonction main()).

Les pointeurs

fonction principale (fonction main()).

62


� Exemple :


� Void echanger(int *x,int *y)

� {int z ; z=*x ; *x=*y ;*y=z ;

� Printf(‘x= %d y=%d ‘,*x,*y) ;

� }

Les pointeurs

� }

� Void main()

� {

� int *x=5,*y=7 ; Exécution :

� Echanger(&x,&y) ; X=7 y=5

� Printf(‘x= %d y=%d ‘,*x,*y) ; X=7 y=5

� }

63


� Allocation dynamique de la mémoire :

� Lorsque l’on déclare une variable de type char, int, ...l’espace mémoire est réservé automatiquement.

� Pour les pointeurs l’espace mémoire n’est pas réservé.

� On utilise donc des fonctions permettant d’allouer l’espace mémoire à un pointeur.

Les pointeurs

On utilise donc des fonctions permettant d’allouer l’espace mémoire à un pointeur.

� Exemple :

� � fonction malloc de la bibliothèque <malloc.h>

� Char *c ;

� C=(char *)malloc(sizeof(char)*10)

64


� � Fonction calloc() ;

� char *s ;

� s = (char *) calloc(256, sizeof(char)); réserve 256 octets initialisés à '\0'

� Pour libérer l’espace mémoire réservé à une variable on

Les pointeurs

� Pour libérer l’espace mémoire réservé à une variable on utilisera la fonction free() ; dont l’argument est un pointeur.

� Free(s) ;

� Free(c ) ;

65


� La fonction realloc() modifie la taille du bloc mémoire.

� realloc () : permet d’augmenter ou de diminuer la taille du tableau sans écraser sans contenu.

� Exemple :

� #include<stdio.h>

Les pointeurs

� #include<stdio.h>

� #include<stdlib.h>

� Int main()

� {int *tab, N ;

� Printf(‘donner la dimension ‘) ;scanf ’%d’,&N) ;

� Tab=(int *)malloc(sizeof(int)*N) ;

66


� For(int i=0 ;i<N ;i++)

� {

� Printf(‘donnez tab[%d] ‘,i) ;scanf(‘%d’,(tab+i)) ;

� }

� Printf(‘ ajout de 2 éléments dans le tableau ‘) ;

� Tab=(int *)realloc(tab,(N+2)*sizeof(int)) ;

Les pointeurs

� Tab=(int *)realloc(tab,(N+2)*sizeof(int)) ;

� Printf(‘donnez tab[%d] ‘,N) ;scanf(‘%d’,(tab+N)) ;

� Printf(‘donnez tab[%d] ‘,N+1) ;scanf(‘%d’,(tab+N+1)) ;

� For(int i=0 ;i<N+2 ;i++)

� Printf(‘d% ‘,*(tab+i)) ) ;

� Free(tab) ;/* libère l’espace réservé */

� }

67


� Exercice 1:

� 1) Ecrire une fonction qui calcule la somme des éléments d’un tableau.

� 2) Ecrire une fonction qui détermine le minimum d’un tableau.

� 3) Ecrire un programme qui fait appel à ces deux fonctions.

Exercice 2 :

Les pointeurs

� Exercice 2 :� Soit p un pointeur qui pointe sur un tableau A :

� Int A[]={12,23,27,42,67,70, 73,76,89,90}

� Int *p ;

� Int p=A ;

� Quelles valeurs fournissent ces expressions :

� *p+2 ; *(p+2) ;*(p+(*p-9)) ;*(p+*(p+8)-A[7]) ;

68


� Exercice 3 :

� Ecrire un programme qui compte le nombre de lettres majuscules dans une chaîne de caractères entrée par l’utilisateur, en utilisant le formalisme pointeur ?

� Exercice 4 :

Les pointeurs

� Ecrire un programme qui convertie une chaîne de caractères majuscule en minuscule en utilisant les pointeurs ?

� Exercice 5 :

� Ecrire un programme qui lit une phrase puis détermine le nombre de caractères et le nombre d’espaces existants dans cette phrase saisie ?

69


� Exercice 6 :

� Ecrire un programme permettant de saisir les notes de N etudiants d’une classe connus par leur CNE puis de calculer la moyenne de cette classe et de classer ces étudiants par ordre de mérite ?

� Indication : utiliser une structure étudiant, formalise pointeur !

Les pointeurs

� Indication : utiliser une structure étudiant, formalise pointeur !

� Exercice 7 :

� Ecrire un programme qui teste si une chaîne de caractères entrée par l’utilisateur est palindrome (une chaîne de caractère est dite palindrome si elle se lit de droite comme de gauche), Exemple : NON, RESSASSER, AZIZA…

70

Les fichiers

• Un fichier (file) est un ensemble structuré de

données stocké en général sur un support

externe (disque dur, disque optique, ...).

71

externe (disque dur, disque optique, ...).

• Un fichier structuré contient une suite

d'enregistrements homogènes, qui regroupent

le plus souvent plusieurs composantes.

Les fichiers

� Opérations possibles avec les fichiers:

Créer - Ouvrir - Fermer - Lire - Ecrire - Détruire -Renommer.

� La plupart des fonctions permettant la manipulation des fichiers sont rangées dans la bibliothèque <STDIO.H>, fichiers sont rangées dans la bibliothèque <STDIO.H>, certaines dans <IO.H>.

� Déclaration:

FILE *fichier;

/* majuscules obligatoires pour FILE */

� La déclaration des fichiers doit figurer AVANT la déclaration des autres variables.

72

Les fichiers

� Ouverture:

� FILE *fopen(char *nom, char *mode);

� FILE *fopen(filename, mode)

� /* déclaration dans stdio.h */� /* déclaration dans stdio.h */

� char filename[], mode[];

� On passe donc 2 chaînes de caractères

� nom: celui figurant sur le disque, exemple: « C :\test.dat »

73

Les fichiers

� fopen a pour argument deux chaînes de caractères, le nom du fichier et le mode d'ouverture.

� donne comme résultat un pointeur NULL si l'ouverture a échoué

� sinon le pointeur renvoyé est utilisé dans les écritures, les lectures et les déplacements ultérieurs.lectures et les déplacements ultérieurs.

74

Les fichiers

� Mode (pour les fichiers TEXTES) :

� « r » : lecture seule

� « w » : écriture seule (destruction de l'ancienne version si elle existe)

� « w+ » : lecture/écriture (destruction ancienne version si elle existe)

� « r+ » : lecture/écriture d'un fichier existant (mise à jour), pas de création d'une nouvelle version.

� « a+ » : lecture/écriture d'un fichier existant (mise à jour), pas de création d'une nouvelle version, le pointeur est positionné à la fin du fichier.

75

Les fichiers

� Mode (pour les fichiers BINAIRES) :

� On ajoute b devant les modes qu’on a vu :

� « rb » « wb » …

� Exemple : FILE *fichier ;

� fichier = fopen(« C:\test.dat», « rb ») ;

76

Les fichiers

� #include <stdio.h> /* Inclusion de la biblio standard */

� int main()

� { /* Déclaration d'un fichier */

� FILE* fichier;

� /* Ouverture du fichier test en lecture */

� fichier = fopen("/home/users/manouvrier/test","r"); � fichier = fopen("/home/users/manouvrier/test","r");

� /* Test de l'ouverture pour vérifier les éventuels problèmes */

� if (fichier== NULL) /* Il y a eu un problème */

� { /* Affichage d'un message d'erreur */

� printf("Erreur ouverture fichier ");

� } /* Si l'ouverture a pu se faire */

� else ... }

77

Les fichiers

� Fermeture:

Int fclose(FILE *fichier);

Retourne 0 si la fermeture s’est bien passée, EOF en cas d’erreur.

Il faut toujours fermer un fichier à la fin d'une session. mode Il faut toujours fermer un fichier à la fin d'une session. mode (pour les fichiers TEXTE) :

Exemple : FILE *fichier ;

fichier = fopen(« C:\test.dat », « rb ») ;

/* Ici instructions de traitement */

fclose(fichier) ;

78

Les fichiers

� Destruction:

int remove(char *nom);

Retourne 0 si la fermeture s’est bien passée.

Exemple : remove(« C:\test.dat ») ;

� Renommer:

int rename(char *oldname, char *newname);

Retourne 0 si la fermeture s’est bien passée.

79

Les fichiers

� Positionnement du pointeur au début du fichier :

void rewind(FILE *fichier);

int feof(FILE *id) dit si on est en fin de fichier ou non (0).

� Récupération de la position du curseur dans le fichier :

int ftell (FILE * fichier) ;

Exemple :#include <stdio.h>

FILE* fichier;

int pos;

pos=ftell(fichier);

80

Les fichiers

� Ecriture dans le fichier texte:

int putc(char c, FILE *fichier);

Ecrit la valeur de c à la position courante du pointeur , le pointeur avance d'une case mémoire.pointeur avance d'une case mémoire.

Retourne EOF qui marque la fin de fichier, en cas d’erreur.

Exemple : putc(‘A’, fichier) ;

81

Les fichiers

� int putw(int n, FILE *fichier);

le pointeur avance du nombre de cases correspondant à la taille d'un entier (4 cases).

Retourne n si l’écriture s’est bien passée.

� int fputs(char *chaîne, FILE *fichier);

le pointeur avance de la longueur de la chaine ('\0' n'est pas rangé dans le fichier). signifie "met une chaîne dans un fichier"

Retourne EOF en cas d’erreur.

Exemple : fputs(« BONJOUR ! », fichier) ;

82

Les fichiers� fputc : ce qui signifie "met un caractère dans un fichier". Comme son nom l'indique, cette fonction écrit un octet dans un fichier.

Exemple :char erreur;erreur = fputc('x', Pointeur_sur_fichier); putc� putc

putc(caractère, pointeur_sur_fichier)écrit le caractère dans un fichier à la position pointeur_sur_fichier (et renvoie le caractère).

83

Les fichiers

� Ecriture dans le fichier binaire:

� int fwrite(void *p,int taille_bloc,int nb_bloc,FILE *fichier);

p écrit à partir de la position courante du pointeur fichier nb_bloc X taille_bloc octets lus à partir de l'adresse p.

Retourne le nombre de blocs écrits.

Exemple :

taille_bloc=4 (taille d'un entier en C), nb_bloc=3, écriture de 3 octets.

int tab[10] ;

fwrite(tab,4,3,fichier) ;

84

Les fichiers

� fwrite : écrit dans un fichier des objets d'un type quelconque. Il faut préciser la taille d'un objet (par exemple avec sizeof(objet)), le nombre d'objets à écrire et le pointeur du fichier destination.

� la fonction renvoie le nombre d'éléments effectivement écrits.écrits.

85

Les fichiers

� int fprintf(FILE *fichier, char *format, liste d'expressions);

réservée plutôt aux fichiers ASCII.

Retourne EOF en cas d’erreur.

Exemples: fprintf(fichier,"%s","il fait beau");

fprintf(fichier,%d,n);

fprintf(fichier,"%s%d","il fait beau",n);

86

Les fichiers

� getc

getc(pointeur_sur_fichier)

renvoie le caractère lu dans un fichier à l'endroit pointé par le pointeur_sur_fichier et incrémente ce pointeur, ou renvoie EOF si on est à la fin du fichier.

87

Les fichiersExemple : copier un fichier dans un autre

void main(int argc, char *argv[] )/* copier le fichier en premier argument dans le fichier en 2ème argument */{FILE *fopen(), *pf1, *pf2 ;int c ;if (argc <= 2)if (argc <= 2)printf(" deux arguments SVP...") ;

else{ pf1 = fopen(argv[1] , "r") ; /* uverture du premier fichier en lecture */pf2 = fopen(argv[2] , "w") ; /* ouverture du deuxième fichier en écriture */while ( (c = getc(pf1)) != EOF ) putc(c, pf2) ;fclose(pf1) ;fclose(pf2) ;}

}

88

Les fichiers

� Lecture dans un fichier :

fscanf : lecture analogue à scanf.

Syntaxe :

Nb_lu = fscanf(Pointeur_sur_fichier, format, liste de pointeurs);

Nb_lu est le nombre d'arguments lus et acceptés. Nb_lu est le nombre d'arguments lus et acceptés.

Exemple :

Nb_lu = fscanf(Pointeur_sur_fichier, "%s", Chaîne);

89

Les fichiers

� Dans un fichier texte

� fgetc : ce qui signifie "prend un caractère dans un fichier".

Exemple :

int caractere;int caractere;

caractere = fgetc(Pointeur_sur_fichier);

90

Les fichiers� fgets : ce qui signifie "prend une chaîne dans un fichier".

Lit un certain nombre de caractères dans un fichier et les met dans une chaîne en ajoutant le caractère nul à la fin.

Exemple :

� fgets(Chaine, 10, Pointeur_sur_fichier);

� Lit 10 caractères dans le fichier et les écrits dans Chaine. Un dernier � Lit 10 caractères dans le fichier et les écrits dans Chaine. Un dernier caractère nul est ajouté.

� Si une fin de ligne (EOL) est rencontrée avant le dixième caractère lu, seuls les caractères avant la fin de ligne seront lus et ils seront suivis dans la chaîne par EOL et NULL

91

Les fichiers

Dans un fichier binaire

� Syntaxe :

� Nb_lu = fread(pointeur_sur_tableau, taille_element, nb_elements, fichier);

� Nb_lu est égal à nb_elements si l'écriture s'est passée � Nb_lu est égal à nb_elements si l'écriture s'est passée correctement.

92

Les fichiers

� Exemple:

#include <stdio.h>

FILE *Pointeur_sur_fichier;

fopen("C:\FSTT\essai.dat", "wb");fopen("C:\FSTT\essai.dat", "wb");

int tableau[5];

nb = fread(tableau, sizeof(int), 3, Pointeur_sur_fichier);

Lit des nombres entiers et les range dans les trois premières cellules du tableau ; nb a pour valeur le nombre d'éléments écrits, 3 si tout s'est bien passé.

93

Les fichiers

� Exercice 1:

� Ecrire un programme qui permet de créer un fichier d’étudiants.

� Exercice 2 :

� Ecrire une procédure qui permet de modifier les � Ecrire une procédure qui permet de modifier les informations d’un étudiant.

94


Les types composéstypedef int entier ; /* on définit un nouveau type "entier" synonyme de "int" */

typedef int vecteur[3]; /* on définit un nouveau type "vecteur" synonyme */

/* de "tableau de 3 entiers" */

Exemple :

#include <stdio.h>

typedef int entier;

typedef float point[2];

95

typedef float point[2];

void main()

{

entier n = 6;

point xy;

xy[0] = 8.6;

xy[1] = -9.45;

etc ...

}

95


Les structures

Une structure est un ensemble de données de même type ou de typesdifférents

Déclaration: 2 manières :

Struct nom_structure Typedef struct

96

Struct nom_structure Typedef struct

{ {

Type var1 Type var1;

Type var2 Type var2;

: :

}; } Nouveau_nom;

N.B: une structure peut contenir une autre structure.


Les structures

Exemple :

struct point

{

int x;

Typedef struct

{

int x;

Typedef struct{

char nom[10];

97

int x;

int y;

int z;

};

int x;

int y;

int z;

} point;

char nom[10];char prenom[10];int age;float note;

}fiche;


Utilisation:

On déclare des variables par exemple: fiche f1,f2;

puis, par exemple:

strcpy(f1.nom,"DUPONT");

Les structures

98

strcpy(f1.nom,"DUPONT");

strcpy(f1.prenom,"JEAN");

f1.age = 20;

f1.note = 11.5;

L'affectation globale est possible avec les structures: on peut écrire: f2 = f1;


Les structures et les tableaux

Une structure peut contenir des tableau.

Un tableau peut contenir des structures.

Exemples :

typedef struct /* On définit un type struct */

99

typedef struct /* On définit un type struct */{char nom[10];char prenom[10];int age;float note;}fiche;


Les structures et les tableaux

Exemples :

�

� fiche f[10]; /* on déclare un tableau de 10 fiches */

� Utilisation:� Utilisation:

�

� strcpy(f[i].nom,"DUPONT")

� strcpy(f[i].prenom,"JEAN");

� f[i].age = 20;

� f[i].note = 11.5;

�

100


Les structures : Exercices

Exercice 1 :

Créer une structure point {int num; float x; float y;}Saisir des points, les ranger dans un tableau puis les afficher.

101

Calculer la distance entre 2 points saisis ?

Utiliser deux fonctions : l’une pour la lecture des données et l’autrepour l’affichage.


Exercice 2 :

� Ecrire un programme qui permet de définir une structure de données regroupant toutes les informations (Nom, Prenom, CIN, CC1(40%), CC2(60%), Moy, Resultat) pour N étudiants.

Les structures : Exercices

� Ajouter une fonction qui permet de trouver l’étudiant qui a la 1ère note et celui qui a la dernière note.

� La variable Resultat est de type Char qui prend les valeurs :

� V si Moy >= 10 Validé

� R si 8 <= Moy < 10 Rattrapage

� N si Moy < 8 Non validé

102


Les structures : exercices

Sujet de Travaux Pratiques N°1 :

On se propose de réaliser « un répertoire d’adresses » :

un répertoire est un ensemble d’information dont chaque

élément possède les informations suivantes :

103

élément possède les informations suivantes :

Contact : Nom*, Prénom*, Lien de parenté, adresse,

Tél.dom, Tél.entreprise, GSM*, email*

Adresse : NuméroRue, Nom Rue, Code Postal, Ville, Pays.

Le lien de parenté est un indice de la liste suivante :

0 : Mère 3 : Frère 6 : Ami 1 : Père 4 : cousin 7 : Relation personnelle 2 : Sœur 5 : Parent 8 : Relation professionnelle


Les informations indiquées par * sont obligatoires

1) Fonctions à programmer :

2) Ajouter un contact

3) Afficher la liste des contacts


3) Afficher la liste des contacts

4) Consulter un contact

5) Modifier un contact

6) Supprimer un contact

7) Recherche par Nom

8) Recherche multicritère : Nom, Prénom, Ville,

9) Amélioration : l’ajout doit vérifier si le contact existe déjà.

104


Sujet de Travaux Pratiques N°2 : Gestion d’un compte bancaire

� Chaque client est identifié par : nom, prénom, numéro du compte (type long), solde(type double) ;

� Définir la structure compte.

� Implémenter les fonctions suivantes :

� Une fonction char menu () ; qui affiche les choix suivants :

� Printf(‘’_______Ajouter un compte ______ A\n) ;


� Printf(‘’_______Ajouter un compte ______ A\n) ;

� Printf(‘’_______Supprimer un compte ______S\n) ;

� Printf(‘’_______Opérations sur un compte ______ O\n) ;

� Printf(‘’ * Affichage A\n) ;

� Printf(‘’ * virement V\n) ;

� Printf(‘’ * Retrait R\n) ;

� Printf(‘’_______lister les débiteurs ______D\n’’) ;

� Printf(‘’_______Lister les comptes ______L\n’’) ;

� Printf(‘’_______Quitter ______Q\n’’) ;

� Printf(‘’Entrer votre choix : ’’) ;

105


� Ajouter :

� Une fonction char sous_menu() qui retourne le choix de l’utilisateur et qui affiche :

� Printf(‘’ ** Affichage ** A\n’’) ;

� Printf(‘’ ** virement** V\n’’) ;


Printf(‘’ ** virement** V\n’’) ;

� Printf(‘’ ** Retrait** R\n’’) ;

� Printf(‘’ *pour quitter taper** Q\n’’) ;

� Printf(‘’Entrer votre choix : ’’) ;

� Une fonction void saisir () qui permet de saisir toutes les infos d’un client.

� Une fonction void Afficher(compte T_compte [], Long num_compte ) ;

� Une fonction void Ajouter (compte T_compte [], compte C) ;

106


� Une fonction int position(long num) ; si le compte est trouvé la fonction retourne la position du compte dans le tableau, sinon elle retourne -1 ;

� Une fonction void operation (compte T_compte[]) ; qui fait appel aux fonctions (verser(),ajouter() et afficher suivant le choix, c’est dans cette fonction qu’on fait appel au sous_menu() ;).


cette fonction qu’on fait appel au sous_menu() ;).

� Une fonction void verser (long num_compte, double solde) ;

� Une fonction void retirer (long num_compte, double solde) ;

� Une fonction : void lister_debiteurs(compte T_compte[]) ;pour lister les débiteurs(on fait appel à la fonction afficher() pour les afficher.)

� Une fonction : void lister_comptes(compte T_compte[]) ;pour lister tous les comptes.

107

Documents

Cours Structures de Donnees