Après le précédent chapitre sur la gestion de tables, nous
allons voir quelques routines pour gérer des listes chainées. Une liste chainée
contient un certain nombre de nœuds contenant une ou plusieurs valeurs et un
pointeur qui donne l’adresse du nœud suivant. Le pointeur du dernier nœud est à
zéro. L’adresse de début de la chaine pointe sur une structure identique à un
nœud. Si ce premier pointeur est nul, c’est que la chaine est vide.
Dans le programme, routListCH1.s, nous commençons par
décrire la structure de chaque nœud. Pour faire simple, nous décrivons qu’une
valeur et un pointeur next.
Nous déclarons deux têtes de liste par :
qDebutListe1:
.skip llist_fin
qDebutListe2:
.skip llist_fin
puis dans le programme principal, nous testons les
différentes routines.
L’initialisation d’une liste consiste à mettre les valeurs
et le pointeur à zéro. Cette routine n’est pas utilisée ici car les têtes sont
décrites dans la bss section et donc initialisées à zéro par le système.
Ensuite nous trouvons une routine de création d’un nœud, qui
se contente d’allouer la place de la taille d’un nœud données par la structure
et de stocker la valeur passée en paramètre et d’initialiser le pointeur vers
le nœud suivant. La routine retourne l’adresse du nœud crée, adresse qui va
nous servir dans la routine suivante d’insertion du nœud dans la chaine.
On passe à cette routine l’adresse du nœud à insérer et
l’adresse du nœud après lequel il faut insérer ce nœud. Si c’est le premier nœud, on passe l’adresse de l’entête de liste. L insertion est très simple
puisqu’il s’agit de mettre d’adresse du nœud dans le pointeur next du nœud précédent et de mettre l’adresse du nœud suivant dans le pointeur du nœud
inséré !!!
Ensuite nous trouvons la routine d’affichage de toutes les
valeurs de la liste. Nous passons à la routine l’adresse de l’entête de liste.
Si le pointeur next est à zéro, nous affichons le message liste vide sinon nous
passons au premier nœud pour afficher sa valeur et nous chargeons le nouveau
pointeur. Nous bouclons sur ces instructions jusqu’à trouver un pointeur à
zéro.
La recherche d’une valeur dans la liste consiste simplement
à balayer la liste jusqu’à trouver la valeur correspondante. Mais si la valeur
n’est pas trouvée, toute la liste est balayée ce qui peut être couteux en temps d’exécution : c’est le principal défaut des listes chainées par rapport
aux tables.
Il est possible d’améliorer la recherche en triant la liste
puis en arrêtant la recherche quans la clé recherchée est inférieure à une
valeur de la liste.
La routine de tri est un peu particulière car elle détruit
la liste initiale pour reconstruire une nouvelle liste avec une entête
différente. Il faut donc après cette routine, utiliser l’adresse retournée dans
le registre x0 pour toute action sur cette liste triée.
Nous trouvons ensuite une routine d’insertion dans une liste
triée qui insère un nœud à la bonne place, une routine de copie de liste et une
routine de suppression d’un nœud en fonction de sa valeur.
Nous verrons dans les chapitres suivants, une utilisation de
ces routines.
Il existe aussi des listes doublement chainées qui permettent
le balayage dans les 2 sens à l’aide d’un pointeur supplémentaire.
Le programme DblListCH.s
donne quelques routines de base en modifiant les structures de
définition de la liste et des nœuds.
Nous créons une structure de liste qui contient 2
pointeurs, un qui pointe sur le premier nœud de la liste (ou est nul si la
liste est vide) et l’autre qui pointe sur le dernier nœud de la liste (ou qui
est nul si la liste est vide).
Et nous ajoutons à la structure du nœud un pointeur prev qui
pointera sur le nœud précédent (ou qui est nul s’il s’agit du premier nœud).
Ensuite nous trouvons 3 routines : une qui insère un nœud
au début de liste, une qui insère en fin de liste et la dernière qui insère une
valeur après une autre. Ces 3 routines nécessitent la manipulation des pointeurs pour
assurer un bon fonctionnement de la liste.
Puis nous avons une routine de recherche de valeur dans la
liste et 2 routines d’affichage de la liste complète ,une dans un sens et l’autre
dans l’autre sens.
Comme exercice, je vous laisse le soin d’écrire la
suppression d’un nœud et l’insertion avant une certaine valeur.
Aucun commentaire:
Enregistrer un commentaire