Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Faculté des Sciences et T echniques de Tanger Maroc Module : Algorithmes & Stru

Faculté des Sciences et T echniques de Tanger Maroc Module : Algorithmes & Structures de Données en Langage C MIPC II-4 Réalisé par : Professeur Chakkor Saad 2010-2011 1 saadchakkor@gmail.com 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 Algorithmique & Programmation : Langage C 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 Algorithmique & Programmation : Langage C 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. Algorithmique & Programmation : Langage C 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’un tableau 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’une matrice de n colonnes et m lignes. Exercice 5: Ecrire un programme permettant de calculer le déterminant d’une matrice (2X2) 11 Algorithmique & Programmation : Langage C 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 Algorithmique & Programmation : Langage C 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 Algorithmique & Programmation : Langage C 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épasse pas 80 caractères. * char *mot ; il faudra réserver dynamiquement la mémoire : on abordera plus loin ce sujet. Algorithmique & Programmation : Langage C 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) ; } } Algorithmique & Programmation : Langage C Strcmp cette fonction compare lexicographiquement deux chaînes de caractè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") ; Algorithmique & Programmation : Langage C 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); strcat mot3 = strcat(mot1, mot2); mot3 est la concaténation de mot1 et mot2. Algorithmique & Programmation : Langage C 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. Algorithmique & Programmation : Langage C 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 Algorithmique & Programmation : Langage C 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 Algorithmique & Programmation : Langage C Remarques: On peut avoir des fonctions sans arguments, comme on peut avoir une 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 plus tard comment modifier les arguments d'une fonction. 21 Algorithmique & Programmation : Langage C 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 parfaits inférieurs à un chiffre donné. Exercice 5 : Ecrire une fonction permettant de calculer pour une valeur X son image par un polynôme P(X) de degré N. 22 Algorithmique & Programmation : Langage C 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 Algorithmique & Programmation : Langage C Exercice 1 : uploads/Ingenierie_Lourd/ cours-structures-de-donnees.pdf