LES MATRICES CREUSES

Les matrices creuses sont des matrices ayant beaucoup d'éléments nuls. Pour chaque élément non nul a[i,j] on crée un enregistrement de cinq champs contenant la valeur, les indices i,j et deux pointeurs vers l'élément non nul suivant de sa colonne et de sa ligne respectivement. On utilise de plus un tableau ligne et un tableau colonne de pointeurs tête de liste pour les lignes et les colonnes respectivement. Par exemple la matrice :

• Ecrire la déclaration des types des éléments d'une matrice représentée ainsi.
• Ecrire le programme transformant un tableau a[i,j] de taille m x n donné pour le mettre sous la forme indiquée. Attention : la complexité devra être en O(mn).
• Ecrire un programme qui recopie une matrice creuse en temps linéaire par rapport au nombre de ses éléments non nuls, en supposant que ce nombre est au moins de l'ordre de n ou m (recopier signifie créer une nouvelle représentation de la même matrice).
• Ecrire une procédure d'addition pour les matrices creuses. On fera attention à la complexité. Quelle est-elle ?

N'oubliez pas de :