Formation algorithmes et programmation, tutoriel & guide de travaux pratiques en pdf.

Programmes en C

/* Tri par selection, page 20 */ #include <stdio.h> /* contient la signature de printf */ #include <stdlib.h> /* contient la signature de rand */ #include <time.h> /* contient la signature de clock */
#define N 10
int a[N]; /* Le tableau a trier */
void Initialisation() /* On tire au sort des nombres */ { /* entre 0 et 127, en initialisant */ int i, s; /* le tirage au sort sur l’heure */
s = (unsigned int) clock(); srand(s); for (i = 0; i < N; ++i) a[i] = rand() % 128;
}
void Impression() { int i; for (i = 0; i < N; ++i) printf (« %3d « , a[i]); printf (« \n »); }
void TriSelection() { int i, j, min, t;
for (i = 0; i < N – 1; ++i) { min = i; for (j = i+1; j < N; ++j) if (a[j] < a[min]) min = j;
t = a[min]; a[min] = a[i]; a[i] = t;
}
}
int main() { Initialisation(); /* On lit le tableau */ TriSelection(); /* On trie */ Impression(); /* On imprime le resultat */ return 0; }
void TriBulle() /* Tri bulle, voir page 22 */ { int i, j, t;
for (i = N-1; i >= 0; –i) for (j = 1; j <= i; ++j) if (a[j-1] > a[j]) { t = a[j-1]; a[j-1] = a[j]; a[j] = t; }
}
void TriInsertion() /* Tri par insertion, voir page 24 */ { int i, j, v;
for (i = 1; i < N; ++i) { v = a[i]; j = i; while (j > 0 && a[j-1] > v) { a[j] = a[j-1]; –j; } a[j] = v; }
}
void TriShell() /* Tri Shell, voir page 27 */ { int i, h;
h = 1; do h = 3*h + 1; while ( h <= N ); do { h = h / 3; for (i = h; i < N; ++i) if (a[i] < a[i-h]) { int v = a[i], j = i; do { 1.3. PROGRAMMES EN C 39 a[j] = a[j-h]; j = j – h; } while (j >= h && a[j-h] > v); a[j] = v;
} } while ( h > 1);
}
int Recherche (char x[]) /* Recherche 1, voir page 28 */ { int i; for (i = 0; i < N; ++i) if (strcmp(x, nom[i]) == 0) return tel[i]; return -1; }
int Recherche (char x[]) /* Recherche 2, voir page 28 */ { int i = 0; while (i < N && strcmp(x, nom[i]) != 0) ++i; if (i < N) return tel[i]; else return -1; }
int Recherche (char x[]) /* Recherche 3, voir page 28 */ { int i = 0; nom[N] = x; tel[N] = -1; while (strcmp (x, nom[i]) != 0) ++i; return tel[i]; }
#include #include #define N 6 /* Recherche Lineaire, voir page 29 */ char *nom[N+1]; int tel[N+1]; char x[100];
void Initialisation() { nom[0] = « paul »; tel[0] = 2811; nom[1] = « roger »; tel[1] = 4501;
40 CHAPITRE 1. TABLEAUX
nom[2] = « laure »; tel[2] = 2701; nom[3] = « anne »; tel[3] = 2702; nom[4] = « pierre »; tel[4] = 2805; nom[5] = « yves »; tel[5] = 2806;
}
int Recherche (char x[]) { int i = 0;
nom[N] = x; tel[N] = -1; while (strcmp (x, nom[i]) != 0) ++i; return tel[i];
}
int main() { Initialisation(); for (;;) { scanf(« %s », x); printf(« %d\n », Recherche(x)); } return 0; }
void Initialisation() /* Recherche dichotomique, voir page 30 */ { nom[0] = « anne »; tel[0] = 2702; nom[1] = « laure »; tel[1] = 2701; nom[2] = « paul »; tel[2] = 2811; nom[3] = « pierre »; tel[3] = 2805; nom[4] = « roger »; tel[4] = 4501; nom[5] = « yves »; tel[5] = 2806; }
int RechercheDichotomique (char x[]) { int i, g, d;
g = 0; d = N-1; do { i = (g + d) / 2; if (strcmp (x, nom[i]) == 0) return tel[i]; if (strcmp(x, nom[i]) < 0) d = i – 1; else g = i + 1; } while (g <= d); return -1;
}