Structures de données et de fichiers
|
Enoncé 11 : Listes linéaires chaînées Corrigé 11
Exercice 1 : Matrices creuses
Une matrice est dite creuse lorsque le nombre d'éléments nuls y figurant est très supérieur à celui des éléments non nuls. On peut représenter une matrice creuse en ne tenant compte que des éléments non nuls. Chaque ligne de la matrice est une liste linéaire chaînée ordonnée (selon le rang de la colonne) des éléments non nuls. Une table de N éléments ( N étant le nombre de lignes de la matrice) donne les adresses de tête de chacune des listes. Un élément de la liste contient l'indice de la colonne et la valeur de l'élément.
- Décrire la structure de données.
- Remplir une telle structure à partir d'une matrice A(M, N) donnée.
- Réaliser la somme de 2 matrices ainsi représentées.
Sachant qu'un élément de la matrice occupe 4 octets, qu'un pointeur occupe 2 octets et qu'un indice occupe 2 octets,
- quel est le gain d'espace quand le nombre de zéros est de � % ?
- quelle valeur minimale attribuée à � pour que l'on puisse opter pour une telle représentation?
Exercice 2 : Représentation d'un nombre binaire en une liste linéaire chaînée.
On convient de représenter un nombre binaire b1b2..bn, o� chaque bi est un 0 ou un 1, par une liste linéaire chaînée o� chaque élément contient un bi.
Considérons la procédure récursive suivante :
L est une liste linéaire chaînée représentant un nombre binaire,
R est une variable globale initialisée à 1,
A MOD B désigne le reste de la division de A par B.
PROCEDURE P(L)
VAR L : POINTEUR
X : ENTIER
SI L # NIL :
P( Suivant(L))
X := Valeur(L) + R
Aff_val(L, X MOD 2)
SI X=2 : R := 1 SINON R := 0 FSI
FSI
FIN
Donner les différentes valeurs de L et X, dans l'ordre, après l'appel récursif pour la liste suivante représentant le nombre 1011 :
Que fait cette procédure ?
Ecrire un algorithme qui utilise cette procédure pour incrémenter un nombre binaire ainsi représenté.
