Scribd
Importer
67 vues26 pages

Implémentation des Listes en C

Le document décrit différents types de données abstraits comme les listes, piles, files et arbres. Il présente leur implémentation à base de tableaux ou de listes chaînées et définit formellement les opérations sur les listes.

Transféré par

souad mhiri
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
67 vues26 pages

Implémentation des Listes en C

Le document décrit différents types de données abstraits comme les listes, piles, files et arbres. Il présente leur implémentation à base de tableaux ou de listes chaînées et définit formellement les opérations sur les listes.

Transféré par

souad mhiri
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Types de données abstraits

Les types qui vont être étudiés

•les listes

•les piles

•les files

•les arbres
Implémentation

• A base de tableaux

• A base de listes chaînées


Les listes
•Une liste est une suite ordonnée d'éléments d'un type
donné ;

•une liste peut contenir zéro, un ou plusieurs éléments.

•Exemples :

(3 , 7, 2, 8, 10, 4) est une liste d'entiers ;

(lundi, mardi, mercredi, jeudi, vendredi, samedi,


dimanche) est la liste des jours de la semaine
• La longueur d'une liste est son nombre d'éléments

longueur((3 , 7, 2, 8, 10, 4) )=6


• Une liste vide est une liste de longueur nulle

Longueur(())=0
• La tête de la liste est son premier élément

tête((3 , 7, 2, 8, 10, 4) )= 3
• La définition de la queue d'une liste n'est
est pas universelle ; certains la définissent
comme étant le dernier élément de la liste
et d'autres comme la liste obtenue en
enlevant la tête.
On adopte la seconde :
queue((3 , 7, 2, 8, 10, 4) )= (7, 2, 8,10,4)
Implémentation

– A base de tableaux

– A base de listes chaînées


Implémentation des listes à
base listes chaînées
Listes linéaires :
struct nœud{ int x;
struct nœud *suivant;
}
typedef struct nœud Nœud;
typedef Nœud *liste;
liste tete;
tete= (Nœud *) malloc (sizeof (Nœud));
free(p);
Axiomatisation
Les listes sont des sortes dotées de
fonctions de création et d’axiômes
définissant certaines opérations de base.
– Créateurs : nil et adjq sont les 2 créateurs de
listes.
nil correspond à la création d’une liste vide
adjq à l’adjonction en queue d’un élément
- nil : liste
- adjq : element x liste  liste
Ajouter un élément en tête de liste :
adjt : element X liste  liste
adjt(e, nil)= adjq(e, nil)
adjt(e1, adjq(e2,l)) = adjq (e2,adjt(e1,l))

Effacer le premier élément :


suppt : liste  liste
suppt(nil)= ┴
suppt (adjq(e,nil))=nil
suppt (adjq(e,l))=adjq(e, suppt(l))
Concaténation :
conc : liste X liste liste
conc (l, nil)=l
conc (l1,adjq(e,l2))=adjq(e,conc(l1,l2))

Appartient :
appartient : element X listeboolean
appartient (e, nil)= false
appartient (e1, adjq(e2,l))= ou (e1=e2, appartient(e1,l))
liste creer ()
/* créer une liste vide */
{
return (NULL);
}
liste adjq(int el, liste ancienne)
/* ajoute en queue l’élément el à la liste ancienne */
{liste y, courant; /*création de l’élément à rajouter*/
y= (Nœud *) malloc (sizeof (Noeud));
yx= el; ysuivant= NULL;
if (!ancienne) /*ajout à une liste vide */
ancienne=y;
else { courant= ancienne;
while (courantsuivant)
courant=courantsuivant;
courantsuivant=y;
}
return ancienne;
}
liste adjt(int el, liste ancienne)
{ liste ll;
ll= (Nœud *) malloc (sizeof (Noeud));
llx=el; llsuivant=ancienne;
return (ancienne=ll);
}
liste supprimer_premier (liste tete)
{ liste p;
if (tete != NULL)
{ p=tete; tete= tete suivant;
free(p); }
return (tete);
}
Effacer le dernier élément (axiomatisation en exercice)
liste debut (liste tete)
{ liste p,q;
if (tete==NULL) {}
else if (tetesuivant ==NULL)
{p=tete; tete=tetesuivant; free(p);}
else {p=tete;
while (psuivantsuivant !=NULL)
p=psuivant;
q=psuivant; psuivant=NULL; free(q);
}
return(tete);
}
liste conc( liste tete1, liste tete2)
{ liste courant;
if (courant=tete1) /*retourne 0 si tete1 n’existe
pas*/
{ while (courantsuivant)
courant=courantsuivant;
courantsuivant=tete2;
}
else tete1=tete2;
return tete1;
}
int appartient (int el, liste tete)
{ liste courant;
int trouve=0;
if (tete)
{courant=tete;
while (courant && !trouve)
{ if (courantx == el)
trouve=1;
courant=courant suivant;
}
}
return trouve;
}
longueur : Liste  nat
longueur(nil)=0
longueur(adjq(e,l))=1+longueur(l)
Longueur version itérative :
int longueur (liste tete)
{ liste courant;
int i=0;
if (tete==NULL)
else { courant=tete;
while (courant)
{i++; courant=courantsuivant;}
}
return i;
}
Version récursive avec perte :

int longueur (liste tete)


{
if (tete==NULL)
return 0;
else return (1+ longueur (debut(tete)));
}
Le problème c’est qu’on perd la liste.
Version récursive sans perte :

int longueur (liste tete)


{
if (tete==NULL)
return 0;
else return (1+ longueur (tete→ suivant));
}
Variantes sur les listes
• Listes doublement chainées

• Listes circulaires simplement chainées

• Listes circulaires doublement chainées


Listes doublement chainées
struct nœud_double
{ int x;
struct nœud_double *precedent;
struct nœud_double *suivant;
}
typedef struct nœud_double Nœud_double;
typedef Nœud_double *liste_double;
liste_double tete;
En exercice
• Donner les fonctions C relatives aux
opérations de bases sur les listes
doublement chainées (creer, adjq,
adjt, suppq, suppt, conc, appartient)
• Donner les fonctions C relatives aux
opérations de base sur listes
circulaires simples
• Donner les fonctions C relatives aux
opérations de base sur listes
circulaires doubles

Vous aimerez peut-être aussi