Introduction au langage C

Maperal

Description

Introduction au langage C, Notions de compilation, Variables, types, constantes, Tableaux, opérateurs, Entrées sorties de base, Structures de contrôle, Algorithmes de recherche, Algorithmes de Tri –Insertion-Fusion,...

Informations

• Publié par: Force_IT
• Nombre de lectures: 37
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

            

PLAN DU COURS

Introduction au langage C Notions de compilation Variables, types,constantes, Tableaux, opérateurs Entrées sorties de base Structures de contrôle Algorithmes de recherche Algorithmes de Tri –Insertion-Fusion Les pointeurs Procédures et fonctions les types composés Allocation dynamique Listes Chaînées

MAP - UNS

ALGORITHME DE RECHERCHE

Objectif : Rechercher une information dans un tableau Méthode :séquentielle SoitTun tableau deNéléments etvall’élément cherché parcours du tableau à partir du premier élément (T[0]) Arrêt quand élément trouvé ou si fin de tableau (T[n-1])

Complexité : linéaire de l’ordre de n. Pire cas : parcourt de tout le tableau

MAP - UNS

101

102

12/03/2013

1

RECHERCHE SÉQUENTIELLE

Algorithmerecherche_sequentielle {Recherche le premier indice où se trouve la valeurvalparmi lesNdonnées du tableautab; affiche l’indicesi la valeur est trouvée. } variables:T[0, N1], valentier n, val, indice :entier Début indice ←0 tant que ( val <> T[indice] && indice < N-1) faire indice←indice + 1 ftq 7 115 82 sivalT[indice] =alors afficher( " l'élément se trouve en : » indice); sinon afficher( « Elément non présent " ); fsi Fin

MAP - UNS

ALGORITHME DE RECHERCHE

103

Objectif : Rechercher une information dans untableau trié Méthode :dichotomique ou« diviser pour régner » SoitTun tableau deNéléments etvall’élément cherché T est trié Sinon effectuer unprétraitement de tri. Comparervalavec l’élément u milieu du tableauT. Si c’est le même => trouvé sinon on recommence sur la première moitié ou la seconde selon que val est < àvalmidou val >valmid Arrêt quand élément trouvé ou si fin de tableau (T[indice-1])

Complexité : T(n) nombre d’opérations sur un tableau de taille n T(n) satisfait l’équation de récurrence T(n) = T(n/2)+1

MAP - UNS

104

12/03/2013

2

RECHERCHE DICHOTOMIQUE

Algorithmerecherche_dichotomique {Recherche le premier indice où se trouve la valeurvalen utilisantla stratégie diviser pour régner} variables T[0, N-1] , valentier lnf, Sup, N, Mi :entier Début Saisir(val) Inf ←0 Sup ←N-1 Mi ←(Inf + Sup)/2 tant que( val <> T[Mi] && Inf <= Sup)faire sival < T[Mi]alors Sup = Mid - 1 sinon Inf = Mid + 1 fsi Mi ←(Inf + Sup)/2 ftq siT[Mi] =valalors afficher( " l'élément se trouve en : » Mi); sinon afficher( « Elément non présent " ); fsi Fin MAP - UNS

            

PLAN DU COURS

Introduction au langage C Notions de compilation Variables, types,constantes, Tableaux, opérateurs Entrées sorties de base Structures de contrôle Algorithmes de recherche Algorithmes de Tri –Insertion-Fusion Les pointeurs Procédures et fonctions les types composés Allocation dynamique Listes Chaînées

MAP - UNS

105

106

12/03/2013

3

ALGORITHMES DE TRI

Objectif : Etant donné une suite deNnombres de la ranger par ordre croissant (ou décroissant) Différents algorithmes Tri par sélection Tri se fait enespace constant (2 boucles for imbriquées )Peu économe en temps Boucle interne fait N-1 opérations Boucle externe fait N-1 à itération 1, N-2 (itération 2) … 2 Com plexité2*(N-1)+(N-2) +(N-3) …+ 1 = (N+1)*N+N! ≈ N Tri à bulles Peu économe en temps(2 boucles for imbriquées ) 2 Complexité ≈ N Tri rapide Econome en temps Complexité ≈ N*Log(N) Algorithme récursif

MAP - UNS

ALGORITHME DE TRI

107

Objectif : Etant donné une suite deNnombres de la ranger par ordre croissant (ou décroissant) Méthode :Tri par sélection SoitTun tableau deNéléments er Rechercher le plus petit élément parmi lesNet on l’échange à la finavec le1

7 8 9 2 0 Puis recherche du plus petit parmi lesN-1éléments restant et échange avec le èm e 2 0 8 9 2 7

ièm e … parmiN-k+1élémen angeavec leK 0 2 9 8 7 0 2 7 8 9

MAP - UNS

108

12/03/2013

4

TRI PAR SELECTION

Algorithmetri_selection { Ranger par ordre croissant (ou décroissant) une suite deNnombres rangés dans un tableauT . } variablestab :tableau[0, N1] deentier N, i, j, indiceMin, ValMin:entier Début pouri = 0àN-2faire 9 2 07 8 indiceMin ←i i= ValMin ← T[i] pourj = i +1àN-1faire 9 2 0 siT[j] < ValMinalors indiceMin ← j=2 j=3 j=4 ValMin ← T[j] fsi in=0 ValMin=7 fpour in=3 ValMin=2 T[indiceMin] ← T[i]{ Echange des deux vale IndiceMin=4 ValMin=0 T[i] ← ValMin T[0]=0 fpour T[4]=7 MAP - UNS109 Fin

ALGORITHME DE TRI

Objectif : faire remonter les plus grandes valeurs en haut de tableau Méthode :Tri à bulle SoitTun tableau deNéléments er èmeer ème Comparer ntavec 2. Si 1>2 ,échanger les deux éléments 5 1 4 2 8 ème èmeer ème élément avec 3Comparer 2>3 ,. Si 2échanger les deux éléments

1 5 4 2 8 ième ièmeième ième, avec N-1… comparer N-2.échanger les deux éléments.Si N-2> N-1

1 4 2 5 8 partir du début tant que vous avez opéré au moins à un échangeRecommencer à

MAP - UNS

110

12/03/2013

5

TRI À BULLE

Algorithmetri_à_bulle faire remonter les plus grandes valeurs en haut d’un tableauTdeNéléments { .} variablestab :tableau[0, N1] deentier N, i, j, temp :entier nouvel_echange :booleen Début répéter nouvel_echange ←faux pouri = 0àN-1faire siT[ i ] > T[i+1]alors temp ←T[ i +1] T[i+1 ] ← T[ i ] T[ i ] ← temp nouvel_echange ←vrai fsi fpour tant quenouvel_echange ==vrai MAP - UNS111 Fin

ALGORITHME D’INSERTION POSITION P

Objectif : Ajouter un élément dans un tableau trié ou pas. Insertion n’est possible que si il reste de la place dans le tableau. L’Insertion est un décalage à droite des éléments du tableau Méthode :InsertionSoitTun tableau de taille deNéléments, On insère un élémentVà un positionp Variable k positionnée en fin de tableau 5 1 4 2 8 p Copie de T[k] dans T[k+1]tant que k>=P 5 1 4 2 88 p k 5 1 4 2 28 k 5 1 4 4 28 Qdk=pranger la valeurven T[k] IncrémenterN p k 5 1 v 4 28 MAP - UNS112

12/03/2013

6

INSERTION À UNE POSITION P

AlgorithmeINSERTION_POSITION_P {Insérer une valeurvà une positionpdans un tableauTdeNéléments et de tailleS} Constantes S= 20 variablesT :tableau[0, S1] deentier N, p , v, :entier Début { Code d’initialisation des N éléments du tableau } Afficher(« entrez val à insérer et position p} Saisir(p);Saisir(v); siN < Salors pourk= N-1àppas-1faire T[k+1] ← T[k] fpour T[p] ← v N ← N+1 sinon Afficher («Insertion impossible ») fsi MAP - UNS113 Fin

ALGORITHME D’INSERTION DANS TABLEAU TRIÉ Objectif: Ajouter un élément dans un tableau trié ou pas. Insertion n’est possible que si il reste de la place dans le tableau. L’Insertion est un décalage à droite des éléments du tableau Méthode :InsertionSoitTun tableau de taille deNéléments triés , On insère un élémentV Variable k positionnée en fin de tableau 1 2 4 5 8 Copie de T[k] dans T[k+1] tant que k>=0 && V>T[k] 1 2 4 5 88 k 1 2 4 5 58 k QdT[k]<vranger la valeurven T[k+1] 1 2 4 4 58 IncrémenterN k 1 2 v 4 58 k MAP - UNS114

12/03/2013

7

INSERTION DANS UN TABLEAU TRIÉ

AlgorithmeINSERTION_V_dans_TableauTrié {Insérer une valeurvà une positionpdans un tableauTdeNéléments et de tailleSrangé par ordre croissant} Constantes S= 20 variablesT :tableau[0, S1] deentier N, p , v, :entier Début { Code d’initialisation des N éléments du tableau } Afficher(« entrez val à insérer}Saisir(v); siN < Salors tant quek>= 0 &&T[k] > valfaire T[k+1] ← T[k] k ← k -1 fpour T[k+1] ← v N ← N+1 sinon Afficher («Insertion impossible ») fsi MAP - UNS115 Fin

ALGORITHME DE SUPPRESSION POSITION P

Objectif : Supprimer un élément dans un tableau trié ou pas. La suppression est un décalage à gauche des éléments du tableau Méthode :SuppressionSoitTun tableau de taille deNéléments, On supprime un élémentVà un positionp Variablekpositionnée àp+1 5 1 4 2 8 k Copie de T[k] dans T[k-1]tant que k<N 5 1 2 2 8 p 5 1 2 8 8 p k

DécrémenterN

MAP - UNS

12/03/2013

8

SUPPRESSION À UNE POSITION P

AlgorithmeSUPPRESSION_POSITION_P {Supprimer l’élément à une positionpdans un tableauTdeNéléments et de tailleS} Constantes S= 20 variablesT :tableau[0, S1] deentier N, p , v, :entier Début { Code d’initialisation des N éléments du tableau } Afficher(« entrez position p de l’élément à supprimer ») Saisir(p); pourk= p+1àN – 1faire T[k-1] ← T[k] fpour N ← N-1 Fin

MAP - UNS

SUPPRESSION D’UNE VALEUR V

AlgorithmeSUPPRESSION_VALEUR_V {Supprimer une valeurvdans un tableauTdeNéléments et de tailleS} variablesT :tableau[0, S1] deentier N, p=0 , v, k :entier Début { Code d’initialisation des N éléments du tableau } Afficher(« entrez la valeurà supprimer ») Saisir(v); tant que&& p < N-1T[p] <> valfaire p ← p +1 ftq siT[p] == valalors pourk= p+1àN -1faire T[k-1] ← T[k] fpour N ← N-1 sinon Afficher(« valeur non trouvée ») fsi MAP - UNS Fin

117

118

12/03/2013

9