typedef float type_val;
typedef struct scomp {type_val val; struct scomp *suiv;} type_comp;
typedef type_comp *adr_comp;
Nous representerons les composantes des listes (de type
type_comp) ainsi :
Supposons disposer de la liste ci-dessous en memoire (nous verrons plus loin comment la creer en memoire). La variable prem, de type adr_comp (donc pointeur sur une composante) contient l'adresse de la premiere composante. Le champ suiv de la derniere composante contient la valeur NULL, donc ne pointe sur rien.
Pour simplifier les algorithmes, on peut mettre d'office une composante particuliere en debut et fin de liste (appelee sentinelle). Ceci evite de devoir traiter de maniere particuliere le premier et dernier element de la liste, puisque chaque composante utile possede toujours un precedent et un suivant. Cette methode prend un peu plus de memoire (negligeable en % pour de longues listes) et evite des tests systematiques dans le boucles, alors qu'ils ne servent que pour les extremites (d'ou gain de temps appreciable, toujours en cas de longues listes). Une autre methode pour reperer le dernier element est de le faire pointer sur lui-meme. Nous utiliserons dans la suite des listes sans sentinelle, le dernier element pointant sur NULL.
L'appel de : affiche_lst(prem) affichera a l'ecran 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 premiere composante. On affiche la valeur
pointee par l puis on fait pointer l sur son suivant. On
repete le processus jusqu'en fin de liste (lorsque l'on pointe
sur NULL). La variable l doit etre locale (donc passee par valeur)
pour ne pas modifier le contenu de prem, et donc perdre l'adresse du
debut de la liste, ce qui empecherait tout acces
ulterieur a la liste.Comme pour les chaines de caracteres, plutot que de gerer un variable entiere indiquant toujours la longueur actuelle de la liste, c'est la specificite du dernier element (ici, le champ suiv contient NULL) qui permet de preciser que l'on est en fin de liste. Pour connaitre 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'etre reellement dynamiques,
c'est a dire que l'on peut a loisir les rallonger ou les
raccourcir, avec pour seule limite la memoire disponible (ou la taille
du super-tableau). Par exemple pour inserer une nouvelle composante en
debut 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 inserant la valeur 5 a notre exemple
precedent, on obtient la liste :
La variable prem a du etre passee par adresse, pour que l'on recupere bien l'adresse de la nouvelle premiere composante (appel : insert_premier(&prem,5)). En fait le schema ci-dessus n'est qu'une representation abstraite de la liste (chaque composante pointe sur la suivante), alors que les composantes sont physiquement placees differemment en memoire. Dans le meilleur des cas, la nouvelle composante creee a ete placee juste derriere celles deja existantes (premier emplacement libre). Un schema plus proche de la realite serait donc :
Ces deux schemas sont equivalents (les liens partent des memes cases, et pointent sur les memes cases), seule la disposition des cases differe. En fait ceci nous montre bien que la disposition reelle en memoire ne nous interesse pas (jamais la valeur effective de l'adresse contenue dans un pointeur ne nous interessera). Dans nos schemas, nous choisirons donc une disposition des composantes correspondant plus au probleme traite qu'a la disposition reelle en memoire (par exemple dans le schema suivant, on utilise une representation bidimensionnelle, alors que la memoire n'est qu'unidimensionnelle).
Le second avantage des listes est que l'insertion
d'une composante au milieu d'une liste ne necessite que la modification
des liens avec l'element precedent et le suivant,
le temps necessaire sera donc independant 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_apres(X,15)
donnera le resultat suivant :
void insert_apres(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
premiere position (qui n'a pas de precedent dans notre cas
puisque sans sentinelle), il faut traiter specifiquement le premier de
la liste (voir plus haut). L'insertion necessite la connaissance de
l'adresse du precedent et du suivant. Les composantes ne
comportant que des liens vers l'element suivant, il faut
necessairement donner a la fonction insert_apres l'adresse
du precedent, alors que d'habitude on prefere
donner l'element devant lequel on veut faire l'insertion
(tableaux par exemple). Ceci nous montre le principal probleme des
listes : l'acces est sequentiel.
On devra, pour chercher la composante precedente, parcourir toute
la liste depuis son debut (on donne l'adresse du debut de la
liste et de l'element dont on cherche le precedent):adr_comp rech_prec(adr_comp prem, adr_comp suiv)
/* rend l'adresse, NULL si non trouve */
{
while(prem->suiv!=suiv && prem!=NULL)
prem=prem->suiv;
return(prem);
}
Une autre solution, si l'on a frequemment besoin de parcourir
la liste vers l'avant et vers l'arriere, est de stocker dans chaque
composante l'adresse du suivant et celle du precedent. Ceci
necessite plus de place en memoire et ralentit un peu les
manipulations de base (il y a plus de liens a mettre a jour).
Mais meme dans ce cas, l'acces reste sequentiel. Ceci
empeche d'utiliser un certain nombre d'algorithmes utilisant
l'acces direct (la dichotomie par exemple). Pour trouver l'adresse du
Nieme element d'une liste il faudra utiliser (on suppose
numeroter 0 le premier) :adr_comp rech_ind(adr_comp l, int i)
/* rend l'adresse du (i+1)ieme, NULL si liste trop courte */
{
int j;
for(j=0;j<i && l!=NULL;j++) l=l->suiv;
return(l);
}
La recherche d'un element, meme si la liste est
triee, se fera donc toujours sequentiellement :adr_comp rech_val(adr_comp l, type_val v)
/* rend l'adresse, NULL si non trouve */
{
while(l!=NULL && l->val!=v) l=l->suiv;
return(l);
}
Pour creer une liste, la solution la plus simple consiste
a boucler sur un appel de la fonction insert_premier, mais les
elements seront stockes dans l'ordre inverse de leur
introduction (le dernier saisi sera place en premier). Pour une
creation de liste dans l'ordre, on fera :adr_comp saisie_lst(void)
{
adr_comp prem=NULL,prec,actu; /* premier, precedent, actuel*/
type_val v;
int err;
do
{
printf("entrez votre prochaine valeur, un caractere 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 cree la liste en memoire, effectue la saisie et
retourne l'adresse du debut de la liste.Il nous reste a traiter les suppressions dans une liste. Il faut ici encore preciser l'element precedent celui a supprimer, et traiter de maniere particuliere le debut de la liste :
void suppr_suivant(adr_comp prec)
{
adr_comp a_virer;
if(prec==NULL || prec->suiv==NULL)
{puts("rien a 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 a supprimer");return;}
a_virer=*prem;
*prem=(*prem)->suiv;
free(a_virer);
}
La suppression
complete d'une liste permet de recuperer la place en
memoire. Cette operation n'est pas necessaire en fin de
programme, le fait de quitter un programme remet la memoire dans son
etat initial et libere donc automatiquement toutes les
memoires allouees dynamiquement : {
adr_comp deuxieme;
while(prem!=NULL)
{
deuxieme=prem->suiv;
free(prem);
prem=deuxieme;
}
}
Il n'etait a priori pas obligatoire d'utiliser la
variable deuxieme car la liberation par free
n'efface pas les memoires, le suivant est donc encore disponible
apres free et avant tout nouveau malloc. Neanmoins cette
ecriture est plus sure, ne gerant pas la memoire nous
meme (sauf si methode du super-tableau), en particulier en cas de
multitāche, d'interruption materielle...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-etre plus le meme 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 eviter d'utiliser les
variables actu et suiv. Le temps d'acces aux variables
aurait ete un peu plus long mais on supprimait deux des trois
affectations situees en fin de boucle.
void tri_insertion_lst(adr_comp *prem)
{
/*position testee, precedent,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 effectues plus haut */
pt->suiv=dpp->suiv;
dpp->suiv=pt;
}
}
}
Ici egalement, on aurait pu tenter d'eviter
l'utilisation des deux variables prec et pt puisque pt est le suivant de prec,
mais les echanges auraient alors necessite une variable
tampon. Cette version du tri est stable
(le nouveau est insere derriere les valeurs
egales), mais ceci ralentit un peu la recherche de la position
definitive d'une valeur en cas de nombreuses valeurs egales (si
la stabilite n'est pas necessaire, il suffit d'arreter la
recherche au premier element superieur ou egal).
Dans tous les cas, on fera au maximum N echanges (aucun en bonne
position), en moyenne N/2 pour les fichiers melanges. Dans la cas
d'un fichier melange, le nombre de boucles internes est de
N(N-1)/2 en moyenne. Dans le cas d'un fichier presque trie, dans le cas
de quelques elements (en nombre P) pas du tout a leur
place, ce tri est tres efficace : P echanges, (P+2)*N/2 boucles
internes, donc on devient lineaire en N. Par contre dans le cas de
nombreux elements pas tout a fait a leur place
(a la distance D), il l'est moins que le tri bulle, la recherche de la
position exacte se faisant a partir du debut de la liste (proche
de N2 : (N-D)(N-1) boucles internes). Dans ce cas, si l'on peut
egalement disposer d'un chainage arriere, on fera la
recherche a partir de la position actuelle, ce qui rendra le tri
tres efficace egalement dans ce cas : D(N-1) boucles internes
donc lineaire en N. Sinon, on peut memoriser la position du
Dieme precedent, le comparer a la valeur a
inserer et donc dans la majorite des cas (si D bien choisi)
rechercher derriere lui, dans les quelques cas ou il faut
l'inserer devant lui, on effectue une recherche depuis le debut.
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 precedent)*/
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;
/* echange (si beaucoup d'elements
deja en place, rajouter un test pour ne pas echanger
inutilement) */
i=pdpp->suiv;
pdpp->suiv=i->suiv;
i->suiv=pdpd->suiv;
pdpd->suiv=i;
}
*prem=faux_debut.suiv; /* retourner le bon premier */
}
pdpd represente le Precedent De la Place
Definitive (boucle principale : de place definitive valant *prem
jusqu'a fin de la liste), pdpp represente le
Precedent Du Plus Petit (de la suite de la liste, pas encore
traitee). On a dans cette implantation evite les variables
pour la place definitive et le plus petit, ceux-ci etant les
suivants des variables precisees ci-dessus. Ceci nuit a la
clarte mais ameliore l'efficacite. On pouvait
ameliorer la clarte (definir les "variables" pd et pp)
sans nuire a l'efficacite (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 portee de ces substitutions a cette fonction, il suffit de declarer juste derriere la fin de la fonction :
#undef pd #undef ppDe plus, afin d'eviter de tester partout le cas particulier du premier de la liste, on a choisi d'ajouter un element en debut de liste (faux_debut), pointant sur le premier de la liste. Dans ce cas, tous les elements y compris le premier ont un precedent. Le gain est donc appreciable (en temps car moins de tests et en taille du code source), pour un cout limite a une variable locale supplementaire.
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 moities.... donc N*P, P etant la profondeur de recursivite, qui est de log(N)). Par contre les echanges sont plus nombreux que les autres tris (en moyenne une boucle interne sur deux pour un fichier melange). Pour transposer l'implantation detaillee pour les tableaux, il faut disposer d'une liste a chainage avant et arriere, mais il est facile de n'utiliser que le chainage avant : l'algorithme devient donc :