Cours algorithmique et structures de données

Formation algorithmique et structures de données, tutoriel & guide de travaux pratiques en pdf.

Tableaux multidimensionnels

Les tableaux statiques à 2 dimensions
Ils sont utilisés pour représenter des matrices, ou toutes autres formes de données rectangulaires (images, feuilles de calcul de tableur, modèles numériques de terrain, etc…). C’est aussi de cette façon que sont organisées certains résultats d’interrogation de bases de données : un tableau d’enregistrements, chaque enregistrement étant un tableau de champs, même si ici les champs n’ont pas tous le même type (texte, valeur etc.).
Matrices
Prenons l’exemple des matrices. En mathématique, on désigne chaque élément d’une matrice par aij où i est le numéro de ligne et j celui de colonne. En programmation, il en va de même : si m est une matrice de taille M lignes et N colonnes, on la déclare à l’aide d’un tableau par : float m[M][N]; Comme pour les tableaux mono-dimensionnels, la numérotation commence à 0 pour les lignes et pour les colonnes, donc l’élément aij est obtenu par m[i-1][j-1], ou réciproquement, l’élément m[i][j] d’un tableau est celui situé à la (i+1)ème ligne et (j+1)ème colonne. Pour illustrer nos propos, nous prenons le cas des matrices carrées 3×3, pour lesquels nous définissons un nouveau type, le type Matrice3x3. typedef float Matrice3x3[3][3];
Matrice3x3 m1,m2; Matrice3x3 identite= { {1.0, 0.0, 0.0}, {0.0, 1.0, 0.0}, {0.0, 0.0, 1.0}}; En mémoire, tous les éléments d’un tableau à 2 dimensions sont contigus : d’abord ceux de la première ligne, puis ceux de la deuxième etc. Les tableaux 2D sont donc des tableaux de tableaux. L’adresse de l’élément m[i][j] est celle du premier + (i*Nombre de colonnes) + j. Donc on peut très facilement programmer des matrices avec des tableaux à une dimension. Matrice3x3 m; float t[3*3]; t[i*3+j]=m[i][j]; Tout d’abord, voyons une fonction permettant de fixer les valeurs de chaque élément d’une matrice. Pour accéder à tous les éléments, on imbrique deux boucles : pour toutes les lignes faire pour tous les éléments sur chaque colonne de la ligne courante faire traitement de l’élément (ligne courante, colonne courante) finpour finpour Dans les exemples suivants, on utilise l’indice i pour désigner les lignes, et j pour les colonnes. void initMatrice(Matrice3x3 m) { int i,j;
for(i=0;i<3;i++) for(j=0;j<3;j++) { printf(« entrez l’élément m[%d][%d] : « ,i,j); scanf(« %d », &m[i][j]); } } De la même manière, la fonction qui affiche à l’écran une matrice 3×3 est : void afficheMatrice(Matrice3x3 m) { int i,j;
for(i=0;i<3;i++) { for(j=0;j<3;j++)
printf(« %6.2f « ,m[i][j]); printf(« \n »); } } La matrice identité est celle dont les éléments de la diagonale (même numéro de ligne et de colonne) valent 1, alors que tous les autres valent 0. void initIdentite(Matrice3x3 m) { int i,j;
for(i=0;i<3;i++) for(j=0;j<3;j++) m[i][j]=(float)(i==j); } La recopie d’une matrice dans une autre est quasiment identique à la recopie d’un tableau dans un autre. On peut la pratiquer élément par élément, ligne par ligne ou d’un seul coup. void copieMatrice(Matrice3x3 m, Matrice3x3 m2) { int i,j;
for(i=0;i<3;i++) for(j=0;j<3;j++) m2[i][j]=m[i][j]; }
void copieMatrice(Matrice3x3 m, Matrice3x3 m2) { int i;
for(i=0;i<3;i++) recopieTableauFloat(m[i], 3, m2[i], 3); // ou memcpy(m2[i], m[i], 3*sizeof(float)); }
void copieMatrice(Matrice3x3 m, Matrice3x3 m2) { memcpy(m2, m, sizeof(Matrice3x3)); } La somme de 2 matrices A et B est une matrice C où chaque élément cij est la somme des éléments correspondants aij et bij void sommeMatrices(Matrice3x3 A, Matrice3x3 B, Matrice3x3 C) { int i,j;
for(i=0;i<3;i++) for(j=0;j<3;j++) C[i][j]=A[i][j]+B[i][j]; } La transposée At d’une matrice A est obtenue en inversant simplement numéros de ligne et numéros de colonne. Dites ce qui peut poser problème dans la première version, et comparez avec la deuxième. void transposeMatrice(Matrice3x3 A, Matrice3x3 At) { int i,j; for(i=0;i<3;i++) for(j=0;j<3;j++) At[i][j]=A[j][i]; }
void transposeMatrice(Matrice3x3 A, Matrice3x3 At) { int i,j; for(i=0;i<3;i++)
Algorithmique et Structures de Données Page 11 Pierre Tellier
for(j=0;j<3;j++) At[i][j]=A[i][j]; for(i=0;i<3;i++) for(j=0;j<i;j++) permuterEntiers(&At[i][j], &At[j][i]); }
La matrice C résultant du produit de 2 matrices A et B (le nombre de colonnes de A doit être égal au nombre de lignes de B, on le note n) est obtenu par la formule : ∑ = = n k kjikij bac 0 . Notez que l’on passe par une matrice intermédiaire sinon la fonction rend des résultats erronés lorsqu’on l’utilise avec accumulation : produitMatrices(A, B, A) ou produitMatrices(A, B, B) . void produitMatrices(Matrice3x3 A, Matrice3x3 B, Matrice3x3 C) { Matrice3x3 Ctmp; int i,j,k;
for(i=0;i<3;i++) for(j=0;j<3;j++) { Ctmp[i][j]=0.0; for (k=0;k<3;k++) Ctmp[i][j] += A[i][k]*B[k][j]; } copieMatrice(Ctmp,C); } Enfin un exemple d’utilisation de ces fonctions sur les matrices : main() { Matrice3x3 A,B,C;
initMatrice(A); initMatrice(B); produitMatrice(A,B,C); afficheMatrice(C); } Et encore quelques fonctions utiles, comme l’application d’une matrice à une vecteur : /* Application d’une matrice à un vecteur */ void appliqueMatrices(Matrice3x3 m, vecteur v1, vecteur v2) { int i,k; vecteur v2t;
for(i=0;i<3;i++) { v2t[i]=0.0; for (k=0;k<3;k++) v2t[i] += m1[i][k]*v1[k]; } recopieTableauFloat(v2t, 3, v2, 3); } ou l’inversion d’une matrice 3×3 avec calcul du déterminant : /* Inversion de matrice 3×3. Résultat : succès ou échec */ int inverseMatrice(Matrice3x3 m, Matrice3x3 m2) { float determinant, unSurDeterminant; float cf[3][3]; int i, j, res=0; determinant = m[0][0]*(m[1][1]*m[2][2] – m[1][2]*m[2][1]) – m[0][1]*(m[1][0]*m[2][2] – m[1][2]*m[2][0]) +
Algorithmique et Structures de Données Page 12 Pierre Tellier
m[0][2]*(m[1][0]*m[2][1] – m[1][1]*m[2][0]); if (determinant != 0.0) { res = 1; unSurDeterminant = 1.0 / determinant; cf[0][0] = m[1][1]*m[2][2] – m[1][2]*m[2][1]; cf[0][1] = -(m[1][0]*m[2][2] – m[1][2]*m[2][0]); cf[0][2] = m[1][0]*m[2][1] – m[1][1]*m[2][0];
cf[1][0] = -(m[0][1]*m[2][2] – m[0][2]*m[2][1]); cf[1][1] = m[0][0]*m[2][2] – m[0][2]*m[2][0]; cf[1][2] = -(m[0][0]*m[2][1] – m[0][1]*m[2][0]); cf[2][0] = m[0][1]*m[1][2] – m[0][2]*m[1][1]; cf[2][1] = -(m[0][0]*m[1][2] – m[0][2]*m[1][0]); cf[2][2] = m[0][0]*m[1][1] – m[0][1]*m[1][0]; for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) m2[i][j] = unSurDeterminant*cf[j][i]; } return res; }

Matrices dynamiques

Après ces exemples sur les matrices de taille 3×3, nous montrons comment manipuler des informations bidimensionnelles de taille quelconque.

Tableaux mono-dimensionnels

La manière la plus pratique de représenter notre tableau à 2 dimensions de tailles inconnues à l’avance est incontestablement l’utilisation d’un tableau alloué dynamiquement. Le principal inconvénient est que l’accès à l’élément sur la i-ème ligne et la j-ème colonne d’une matrice M de L lignes de chacune C colonnes devient un peu moins intuitif : M[i*C+j] au lieu de M[i][j] pour un véritable tableau bidimensionnel. Il devient bien sûr nécessaire de préciser, en paramètres des fonctions de manipulation de tels tableaux, leurs dimensions. Par exemple voici la fonction qui calcule (si possible) le produit de 2 matrices réécrite selon ces conventions. Chaque matrice est un pointeur sur des nombres réels, complétée par son nombre de lignes nl et nombre de colonnes nc. On suppose la matrice résultat est préalablement allouée, c’est pourquoi on fournit aussi sa taille physique totale en paramètre. Cette version n’est pas optimale, puisqu’on pourrait faire un calcul incrémental des indices, qui éviterait toutes ces multiplications à chaque itération. Toutefois, pour rester à peu près lisible, nous ne présentons pas de version plus optimisée, ce qui est d’ailleurs inutile car aujourd’hui les compilateurs sont capables de pratiquer eux-mêmes ces améliorations. /* calcul du produit m3 = m1 * m2, *nl3, *nc3 : taille de la matrice produit */ int produitMatrices(float *m1, int nl1, int nc1, float *m2, int nl2, int nc2, float *m3, int taille, int *nl3, int *nc3) { float *m3t=NULL; int res=0,i,j,k; if ((nc1 == nl2) && (nl1*nc2 <= taille)) { res=1; *nl3=nl1; *nc3=nc2; CALLOC(m3t, float, nl1*nc2); for(i=0;i<nl1;i++) for(j=0;j<nc2;j++) { m3t[i*n1+j]=0.0; for (k=0;k<nc1;k++) m3t[i*nc2+j] += m1[i*nc1+k]*m2[k*nc2+j]; } memcpy((void *)m3, (void *)m3t, nl1*nc2*sizeof(float)); FREE(m3t); } return res; }

Tableaux de tableaux

Cette approche est un peu plus lourde que l’approche précédente, néanmoins elle présente 2 avantages : on conserve la notation intuitive d’accès aux données en laissant le soin au compilateur de calculer lui-même l’adresse de chaque élément. Du fait que chaque ligne est représentée par un tableau dynamique, cette méthode est bien adaptée aux cas où les lignes n’ont pas la même longueur. Cela est assez rare, mais se produit par exemple pour les tables à 2 entrées qui sont symétriques, comme un tableau de distance entre villes, pour lequel on n’a pas besoin d’un rectangle puisqu’un triangle suffit. Nous reprenons l’exemple précédent qui consiste à réaliser le produit de 2 matrices. Les matrices seront représentées à l’aide d’un tableau dynamique de tableaux dynamiques. En langage C, cela s’exprime par un double pointeur ou pointeur de pointeur : typedef float **Matrice; Notre fonction de multiplication de matrice est intéressante, car elle procède à l’allocation d’une matrice temporaire. Dans cette version, nous avons supposé que la matrice m3 est déjà correctement allouée en dehors de la fonction, et avec les bonnes dimensions. int produitMatrices(Matrice m1, int nl1, int nc1, Matrice m2, int nl2, int nc2, Matrice m3) { Matrice m3t=NULL; int res=0,i,j,k;
if (nc1 == nl2) { res=1; CALLOC(*m3t, float *, nl1); /* allocation du tableau de lignes */ for(i=0;i<nl1;i++) { CALLOC(m3t[i], float, nc2); /* allocation des lignes */ for(j=0;j<nc2;j++) { m3t[i][j]=0.0; for (k=0;k<nc1;k++) m3t[i][j] += m1[i][k]*m2[k][j]; } } for(i=0;i<nl1;i++) { memcpy((void *)m3[i], (void *)m3t[i], nl1*nc2*sizeof(float)); FREE(m3t[i]); } FREE(m3t); }
return res; }