typedef float type_val; typedef struct scomp {type_val val; struct scomp *suiv;} type_comp; typedef type_comp *adr_comp;Nous représenterons les composantes des listes (de type type_comp) ainsi :
Supposons disposer de la liste ci-dessous en mémoire (nous verrons plus loin comment la créer en mémoire). La variable prem, de type adr_comp (donc pointeur sur une composante) contient l'adresse de la première composante. Le champ suiv de la dernière composante contient la valeur NULL, donc ne pointe sur rien.
Pour simplifier les algorithmes, on peut mettre d'office une composante particulière en début et fin de liste (appelée sentinelle). Ceci évite de devoir traiter de manière particulière le premier et dernier élément de la liste, puisque chaque composante utile possède toujours un précédent et un suivant. Cette méthode prend un peu plus de mémoire (négligeable en % pour de longues listes) et évite des tests systématiques dans le boucles, alors qu'ils ne servent que pour les extrémités (d'où gain de temps appréciable, toujours en cas de longues listes). Une autre méthode pour repérer le dernier élément est de le faire pointer sur lui-même. Nous utiliserons dans la suite des listes sans sentinelle, le dernier élément pointant sur NULL.
L'appel de : affiche_lst(prem) affichera à l'écran le contenu de la liste :
void affiche_lst(adr_comp l) { while(l!=NULL) { printf("%6.1f ",l->val); l=l->suiv; } printf("\n"); }l pointe sur la première composante. On affiche la valeur pointée par l puis on fait pointer l sur son suivant. On répète le processus jusqu'en fin de liste (lorsque l'on pointe sur NULL). La variable l doit être locale (donc passée par valeur) pour ne pas modifier le contenu de prem, et donc perdre l'adresse du début de la liste, ce qui empêcherait tout accès ultérieur à la liste.
Comme pour les chaînes de caractères, plutôt que de gérer un variable entière indiquant toujours la longueur actuelle de la liste, c'est la spécificité du dernier élément (ici, le champ suiv contient NULL) qui permet de préciser que l'on est en fin de liste. Pour connaître la longueur d'une liste, on utilisera :
int longueur_lst(adr_comp l) { int n=0; while(l!=NULL) { l=l->suiv; n++; } return(n); }Les listes ont l'avantage d'être réellement dynamiques, c'est à dire que l'on peut à loisir les rallonger ou les raccourcir, avec pour seule limite la mémoire disponible (ou la taille du super-tableau). Par exemple pour insérer une nouvelle composante en début de liste, on utilisera :
void insert_premier(adr_comp *prem,type_val val) { adr_comp nouv; nouv=(adr_comp)malloc(sizeof(type_comp)); nouv->val=val; nouv->suiv=*prem; *prem=nouv; }En insérant la valeur 5 à notre exemple précédent, on obtient la liste :
La variable prem a dû être passée par adresse, pour que l'on récupère bien l'adresse de la nouvelle première composante (appel : insert_premier(&prem,5)). En fait le schéma ci-dessus n'est qu'une représentation abstraite de la liste (chaque composante pointe sur la suivante), alors que les composantes sont physiquement placées différemment en mémoire. Dans le meilleur des cas, la nouvelle composante créée a été placée juste derrière celles déjà existantes (premier emplacement libre). Un schéma plus proche de la réalité serait donc :
Ces deux schémas sont équivalents (les liens partent des mêmes cases, et pointent sur les mêmes cases), seule la disposition des cases diffère. En fait ceci nous montre bien que la disposition réelle en mémoire ne nous intéresse pas (jamais la valeur effective de l'adresse contenue dans un pointeur ne nous intéressera). Dans nos schémas, nous choisirons donc une disposition des composantes correspondant plus au problème traité qu'à la disposition réelle en mémoire (par exemple dans le schéma suivant, on utilise une représentation bidimensionnelle, alors que la mémoire n'est qu'unidimensionnelle).
Le second avantage des listes est que l'insertion
d'une composante au milieu d'une liste ne nécessite que la modification
des liens avec l'élément précédent et le suivant,
le temps nécessaire sera donc indépendant de la longueur de la
liste. Supposons disposer d'une variable X de type adr_comp, pointant
sur la composante de valeur 10. L'appel de insert_après(X,15)
donnera le résultat suivant :
void insert_après(adr_comp prec,type_val val) { adr_comp nouv; nouv=(adr_comp)malloc(sizeof(type_comp)); nouv->val=val; nouv->suiv=prec->suiv; prec->suiv=nouv; }Cette fonction permet l'insertion en tout endroit de la liste, sauf en première position (qui n'a pas de précédent dans notre cas puisque sans sentinelle), il faut traiter spécifiquement le premier de la liste (voir plus haut). L'insertion nécessite la connaissance de l'adresse du précédent et du suivant. Les composantes ne comportant que des liens vers l'élément suivant, il faut nécessairement donner à la fonction insert_après l'adresse du précédent, alors que d'habitude on préfère donner l'élément devant lequel on veut faire l'insertion (tableaux par exemple). Ceci nous montre le principal problème des listes : l'accès est séquentiel. On devra, pour chercher la composante précédente, parcourir toute la liste depuis son début (on donne l'adresse du début de la liste et de l'élément dont on cherche le précédent):
adr_comp rech_prec(adr_comp prem, adr_comp suiv) /* rend l'adresse, NULL si non trouvé */ { while(prem->suiv!=suiv && prem!=NULL) prem=prem->suiv; return(prem); }Une autre solution, si l'on a fréquemment besoin de parcourir la liste vers l'avant et vers l'arrière, est de stocker dans chaque composante l'adresse du suivant et celle du précédent. Ceci nécessite plus de place en mémoire et ralentit un peu les manipulations de base (il y a plus de liens à mettre à jour). Mais même dans ce cas, l'accès reste séquentiel. Ceci empêche d'utiliser un certain nombre d'algorithmes utilisant l'accès direct (la dichotomie par exemple). Pour trouver l'adresse du Nième élément d'une liste il faudra utiliser (on suppose numéroter 0 le premier) :
adr_comp rech_ind(adr_comp l, int i) /* rend l'adresse du (i+1)ième, NULL si liste trop courte */ { int j; for(j=0;j<i && l!=NULL;j++) l=l->suiv; return(l); }La recherche d'un élément, même si la liste est triée, se fera donc toujours séquentiellement :
adr_comp rech_val(adr_comp l, type_val v) /* rend l'adresse, NULL si non trouvé */ { while(l!=NULL && l->val!=v) l=l->suiv; return(l); }Pour créer une liste, la solution la plus simple consiste à boucler sur un appel de la fonction insert_premier, mais les éléments seront stockés dans l'ordre inverse de leur introduction (le dernier saisi sera placé en premier). Pour une création de liste dans l'ordre, on fera :
adr_comp saisie_lst(void) { adr_comp prem=NULL,prec,actu; /* premier, précédent, actuel*/ type_val v; int err; do { printf("entrez votre prochaine valeur, un caractère pour finir :"); err=scanf("%f",&v); if(err<=0)break; /*scanf rend le nombre de variables lues sans erreur*/ actu=(adr_comp)malloc(sizeof(type_comp)); actu->val=v; if(prem==NULL)prem=actu; else prec->suiv=actu; prec=actu; } while(1); actu->suiv=NULL; return(prem); }Cette fonction crée la liste en mémoire, effectue la saisie et retourne l'adresse du début de la liste.
Il nous reste à traiter les suppressions dans une liste. Il faut ici encore préciser l'élément précédent celui à supprimer, et traiter de manière particulière le début de la liste :
void suppr_suivant(adr_comp prec) { adr_comp a_virer; if(prec==NULL || prec->suiv==NULL) {puts("rien à supprimer");return;} a_virer=prec->suiv; prec->suiv=a_virer->suiv; free(a_virer); } void suppr_premier(adr_comp *prem) { adr_comp a_virer; if(*prem==NULL) {puts("rien à supprimer");return;} a_virer=*prem; *prem=(*prem)->suiv; free(a_virer); }La suppression complète d'une liste permet de récupérer la place en mémoire. Cette opération n'est pas nécessaire en fin de programme, le fait de quitter un programme remet la mémoire dans son état initial et libère donc automatiquement toutes les mémoires allouées dynamiquement :
{ adr_comp deuxieme; while(prem!=NULL) { deuxieme=prem->suiv; free(prem); prem=deuxieme; } }Il n'était à priori pas obligatoire d'utiliser la variable deuxième car la libération par free n'efface pas les mémoires, le suivant est donc encore disponible après free et avant tout nouveau malloc. Néanmoins cette écriture est plus sure, ne gérant pas la mémoire nous même (sauf si méthode du super-tableau), en particulier en cas de multitâche, d'interruption matérielle...
On trouvera un exemple utilisant ces fonctions dans test_lst.c (disquette d'accompagnement)
void tri_bulle_lst(adr_comp *prem) /* le premier ne sera peut-être plus le même donc passage par adresse */ { int ok; adr_comp prec,actu,suiv; do { ok=1; /* vrai */ prec=NULL; actu=*prem; suiv=actu->suiv; while(suiv!=NULL) { if(actu->val > suiv->val) { ok=0; if(prec!=NULL) prec->suiv=suiv; else *prem=suiv; actu->suiv=suiv->suiv; suiv->suiv=actu; } prec=actu; actu=suiv; suiv=actu->suiv; } } while(!ok); }En utilisant prec->suiv et prec->suiv->suiv, on pouvait éviter d'utiliser les variables actu et suiv. Le temps d'accès aux variables aurait été un peu plus long mais on supprimait deux des trois affectations situées en fin de boucle.
void tri_insertion_lst(adr_comp *prem) { /*position testée, précédent,dernier plus petit*/ adr_comp pt,prec,dpp; for(prec=*prem,pt=(*prem)->suiv;pt!=NULL;prec=pt,pt=pt->suiv) if(prec->val>pt->val) /*inutile de chercher si en bonne position */ { prec->suiv=pt->suiv; if((*prem)->val > pt->val) /*cas particulier du premier*/ { pt->suiv=*prem; *prem=pt; } else { dpp=*prem; while(dpp->suiv->val <= pt->val)dpp=dpp->suiv; /* on est sur d'en trouver un, vu les tests effectués plus haut */ pt->suiv=dpp->suiv; dpp->suiv=pt; } } }Ici également, on aurait pu tenter d'éviter l'utilisation des deux variables prec et pt puisque pt est le suivant de prec, mais les échanges auraient alors nécessité une variable tampon. Cette version du tri est stable (le nouveau est inséré derrière les valeurs égales), mais ceci ralentit un peu la recherche de la position définitive d'une valeur en cas de nombreuses valeurs égales (si la stabilité n'est pas nécessaire, il suffit d'arrêter la recherche au premier élément supérieur ou égal). Dans tous les cas, on fera au maximum N échanges (aucun en bonne position), en moyenne N/2 pour les fichiers mélangés. Dans la cas d'un fichier mélangé, le nombre de boucles internes est de N(N-1)/2 en moyenne. Dans le cas d'un fichier presque trié, dans le cas de quelques éléments (en nombre P) pas du tout à leur place, ce tri est très efficace : P échanges, (P+2)*N/2 boucles internes, donc on devient linéaire en N. Par contre dans le cas de nombreux éléments pas tout à fait à leur place (à la distance D), il l'est moins que le tri bulle, la recherche de la position exacte se faisant à partir du début de la liste (proche de N2 : (N-D)(N-1) boucles internes). Dans ce cas, si l'on peut également disposer d'un chaînage arrière, on fera la recherche à partir de la position actuelle, ce qui rendra le tri très efficace également dans ce cas : D(N-1) boucles internes donc linéaire en N. Sinon, on peut mémoriser la position du Dième précédent, le comparer à la valeur à insérer et donc dans la majorité des cas (si D bien choisi) rechercher derrière lui, dans les quelques cas où il faut l'insérer devant lui, on effectue une recherche depuis le début.
void tri_selection_lst(adr_comp *prem) { type_comp faux_debut; adr_comp pdpd,pdpp,i; faux_debut.suiv=*prem; for(pdpd=&faux_debut;pdpd->suiv!=NULL;pdpd=pdpd->suiv) { /*recherche du plus petit (du moins son précédent)*/ pdpp=pdpd; /*le plus petit est pour l'instant l'actuel, on va tester les suivants*/ for(i=pdpd->suiv;i->suiv!=NULL;i=i->suiv) if(i->suiv->val < pdpp->suiv->val)pdpp=i; /* échange (si beaucoup d'éléments déjà en place, rajouter un test pour ne pas échanger inutilement) */ i=pdpp->suiv; pdpp->suiv=i->suiv; i->suiv=pdpd->suiv; pdpd->suiv=i; } *prem=faux_debut.suiv; /* retourner le bon premier */ }pdpd représente le Précédent De la Place Définitive (boucle principale : de place définitive valant *prem jusqu'à fin de la liste), pdpp représente le Précédent Du Plus Petit (de la suite de la liste, pas encore traitée). On a dans cette implantation évité les variables pour la place définitive et le plus petit, ceux-ci étant les suivants des variables précisées ci-dessus. Ceci nuit à la clarté mais améliore l'efficacité. On pouvait améliorer la clarté (définir les "variables" pd et pp) sans nuire à l'efficacité (ne pas devoir les remplacer par leur suivant en fin de boucle) par des #define :
#define pd pdpd->suiv #define pp pdpp->suivPour limiter la portée de ces substitutions à cette fonction, il suffit de déclarer juste derrière la fin de la fonction :
#undef pd #undef ppDe plus, afin d'éviter de tester partout le cas particulier du premier de la liste, on a choisi d'ajouter un élément en début de liste (faux_début), pointant sur le premier de la liste. Dans ce cas, tous les éléments y compris le premier ont un précédent. Le gain est donc appréciable (en temps car moins de tests et en taille du code source), pour un coût limité à une variable locale supplémentaire.
Pour le tri rapide, le nombre de boucles internes est de l'ordre de Nlog(N) (N sur toute la liste, puis deux fois N/2 sur les deux moitiés.... donc N*P, P étant la profondeur de récursivité, qui est de log(N)). Par contre les échanges sont plus nombreux que les autres tris (en moyenne une boucle interne sur deux pour un fichier mélangé). Pour transposer l'implantation détaillée pour les tableaux, il faut disposer d'une liste à chaînage avant et arrière, mais il est facile de n'utiliser que le chaînage avant : l'algorithme devient donc :