Licence 2 Informatique
Partiel du 7 novembre 2014
Éléments de correction
Structure de Données et Algorithmes
Partiel du 7 novembre 2014, de 9h à 12h.
L’examen est noté sur 20 points, le barème est donné à titre indicatif.
Les documents sont autorisés.
1
Tri avec deux piles (4 points)
Dans cet exercice, nous implémentons deux piles d’entiers dans un seul tableau tab de taille fixe n.
Chacune des deux piles peut contenir au plus n entiers, sans qu’à aucun moment le nombre d’entiers
contenus dans les deux piles ne soit supérieur à n. Nous utilisons cette structure en suite pour trier
une suite d’entiers. La structure utilisée est la suivante :
1
2
3
4
typedef struct deux_piles_tab {
int * tab ;
int n ;
} Deux_piles ;
5
6
Deux_piles * p ; /* variable globale partag é e par les fonctions */
Corrigé
Il faut constater qu’on doit faire partir chaque pile d’un bout du tableau pour ne pas décider
à l’avance un partitionnement du tableau en deux. La même idée a été évoquée en cours pour
implémenter une file avec un tableau circulaire.
Q1.1 Implémenter les fonctions estVide, empiler, sommet, depiler, qui prendront un premier argument (0 ou 1) désignant la pile à utiliser. Les fonctions partagerons la variable p, il n’est donc
pas nécessaire de la passer en paramètre.
1
Corrigé
Il faut stocker l’indice du sommet de chaque pile (ou bien sa hauteur/taille). Pour cela on peut
modifier la structure proposée, en créer une nouvelle ou utiliser des variable globales, etc.
1
2
3
4
5
6
typedef struct deux_piles_tab {
int * tab ;
int n ;
/* taille du tableau */
int top1 ; /* sommet de la premi è re pile , initialis é à 0 */
int top2 ; /* sommet de la deuxi è me pile , initialis é à n -1 */
} Deux_piles ;
7
8
Deux_piles * p ; /* variable globale partag é e par les fonctions */
9
10
11
12
13
14
15
int estVide ( int pile ) {
if ( pile == 0)
return p - > top1 == 0;
else
return p - > top2 == n - 1;
}
16
17
18
19
20
21
22
23
24
25
26
27
void empiler ( int pile , int e ) {
if ( top1 == top2 + 1)
printf ( " piles pleines \ n " );
else if ( pile == 0) {
p - > tab [ top1 ] = e ;
p - > top1 ++;
} else {
p - > tab [ top2 ] = e ;
p - > top2 - -;
}
}
28
29
30
31
32
33
34
35
36
int sommet ( int pile ) {
if ( estVide ( pile ))
printf ( " pile vide \ n " );
else if ( pile == 0)
return p - > tab [p - > top1 - 1];
else
return p - > tab [p - > top2 + 1];
}
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int depiler ( int pile ) {
int som ;
if ( estVide ( pile ))
printf ( " pile vide \ n " );
else if ( pile == 0) {
som = p - > tab [p - > top1 - 1];
p - > top1 - -;
} else {
som = p - > tab [p - > top2 + 1];
p - > top2 ++;
}
return som ;
}
Q1.2 Avec n = 4, et en supposant que les deux piles sont initialement vides, écrivez le contenu du
2
tableau tab après exécution de la suite d’instructions suivante :
1
2
empiler (0 ,1); empiler (0 ,2); empiler (1 ,5); empiler (0 ,3);
depiler (0); depiler (0); empiler (1 ,4); empiler (0 ,1);
Corrigé
empiler(0,1)
empiler(0,2)
empiler(1,5)
empiler(0,3)
depiler(0)
depiler(0)
empiler(1,4)
empiler(0,1)
1
1
1
1
1
1
1
1
2
2
2
2
1
3
4
4
5
5
5
5
5
5
Q1.3 En utilisant les fonctions de la question Q1.1, écrivez une fonction qui utilise la structure précédente de deux piles pour trier une suite d’entiers dans l’ordre croissant. Nous supposons que la
suite d’entiers est déjà contenue dans la pile 0. A la fin de l’exécution, la suite triée est contenue
dans la pile 1.
Corrigé
L’algorithme suivant est inspiré de l’algorithme de tri par insertion :
1
2
3
4
5
6
7
8
void tri () {
while (! estVide (0) ) {
int e = depiler (0);
while ( ! estVide (1) && e < sommet (1) )
empiler (0 , depiler (1));
empiler (1 , e );
}
}
Q1.4 Donnez la complexité asymptotique de votre fonction de tri en nombre d’opérations nécessaires
sur les piles.
Corrigé
La complexité de l’algorithme O(n2 ) dans le pire cas et en moyenne, et linéaire O(n) dans le meilleur
cas (pour plus de détails http://fr.wikipedia.org/wiki/Tri_par_insertion).
2
Skip-listes (8 points)
Une skip-liste (inventée en 1990 par W. Pugh) est une structure de données probabiliste, basée sur
des couches superposées de listes chaînées, dont les éléments sont triés dans un ordre croissants.
La Figure 1 montre l’idée sous-jacente à la skip-liste. Observons sur la Figure 1a une liste chaînée
standard, dont les éléments sont triés. Rechercher un élément nécessite de traverser les n éléments de
la liste. Si maintenant un sommet sur deux contient un pointeur vers son deuxième successeur (Figure
1b), alors une recherche ne nécessite plus que de traverser au plus n/2 + 1 éléments. En poursuivant
le raisonnement, un sommet sur 4 peut avoir un pointeur sur son quatrième successeur et la recherche
ne nécessite plus que de traverser n/4 + 2 sommets (Figure 1c). Si chaque sommet d’indice 2i a un
pointeur vers le sommet 2i plus loin, alors la recherche ne nécessite plus la visite que de log2 n sommets
(Figure 1d).
3
Figure 1 – Principe de la skip-liste.
C’est efficace pour la recherche, mais catastrophique pour l’insertion ou la suppression. En effet, un
élément ajouté décale les indices de tous les suivants, et il faudrait recalculer de nombreux pointeurs.
L’idée majeur de la skip liste, est de ne pas spécifier où sont les sommets qui ont beaucoup de pointeurs,
mais de seulement préciser une proportion de sommets qui ont beaucoup de pointeurs.
Ainsi, environ un sommet sur deux auront deux pointeurs, un sommet sur quatre auront trois
pointeurs, un sommet sur huit auront quatre pointeurs, etc (Figure 1e). De plus, un sommet a trois
pointeurs ne pointera pas sur son quatrième successeur, mais sur le prochain sommet qui a (au moins)
trois pointeurs. Le nombre de pointeurs d’un sommet (on parle de niveau) sera tiré aléatoirement selon
une loi qui respecte la proportion indiquée.
On se propose dans la suite de créer une structure de données en C pour les skip-listes, ainsi que
quelques algorithmes.
Q2.1 On suppose que tout sommet a au moins un pointeur, un sur deux a au moins deux pointeurs, un
sur quatre a au moins trois pointeurs, etc. Combien y aura-t-il de pointeurs en tout au maximum ?
(On suppose que le nombre d’éléments n de la liste est une puissance de 2.)
Corrigé
On a d’abord n pointeurs (niveau 1), puis n/2 pointeurs (niveau 2), puis n/4 . . . soit en tout n(1 +
1/2 + 1/4 + 1/8 + . . .) <= 2n
Q2.2 Il s’agit d’abord de modéliser chaque élément dans la skip-liste. Un élément est créé avec un niveau
donné (nombre de pointeurs) et une valeur donnée. Écrire la structure C correspondante (appelée
Element) ainsi que la fonction en créant une (n’oubliez pas d’initialiser à null les pointeurs) :
1
2
/* retourne un é l é ment allou é dynamiquement . */
Element * creerElement ( int valeur , int niveau );
4
Corrigé
1
2
3
4
5
typedef struct SElement {
int val ;
int niv ;
struct SELement ** ptr ;
} Element ;
6
7
8
9
10
11
12
13
14
Element * CreerElement ( int valeur , int niveau ) {
Element * e = ( Element *) malloc ( sizeof ( Element ) );
e - > val = valeur ;
e - > niv = niveau ;
e - > ptr = ( Element **) malloc ( sizeof ( Element *) * niveau );
for ( int i = 0; i < niveau ; i ++ ) e - > ptr [ i ] = null ;
return e ;
}
Q2.3 Écrivez la fonction qui retourne le suivant de degré i donné d’un élément, ou null s’il n’existe
pas. Écrivez de plus la fonction qui modifie le suivant de degré i d’un élément. (NB : i commence
à 0.)
1
2
Element * suivant ( Element * e , int i );
void modifierSuivant ( Element * e , int i , Element * nouv_succ );
Corrigé
1
2
3
4
Element * suivant ( Element * e , int i ) {
if ( i >= e - > niv ) return null ;
return e - > ptr [ i ];
}
5
6
7
8
9
void modifieSuivant ( Element * e , int i , Element * nouv_succ ) {
if ( i < e - > niv )
e - > ptr [ i ] = nouv_succ ;
}
Q2.4 Écrivez maintenant la structure C SkipListe qui contient un élément initial (non valide, cf Figure)
ainsi que le niveau maximal donné. Donnez aussi la fonction qui alloue dynamiquement une
SkipListe initialisée à la liste vide.
1
SkipListe * creerSkipListe ( int niveau_max );
On note que niveau_max doit valoir à peu près log2 n, où n sera le nombre d’éléments maximal de
la liste.
5
Corrigé
1
2
3
typedef struct {
Element * start ;
} SkipListe ;
4
5
6
7
8
9
SkipListe * CreeSkipListe ( int niveau_max ) {
SkipListe * sl = ( SkipListe *) malloc ( sizeof ( SkipListe ) );
/* l ’ element fictif contiendra le niveau max . */
sl - > start = CreerElement ( 0 , niveau_max );
}
Q2.5 En supposant que la skip-liste contient un nombre arbitraire d’éléments, écrire la fonction de
recherche d’un élément dans la skip-liste :
1
2
/* Retourne un pointeur vers l ’é l é ment si trouv é ou null sinon . */
Element * chercher ( SkipListe * sl , int valeur );
Corrigé
1
2
3
4
5
6
7
8
9
10
11
Element * chercher ( SkipListe * sl , int valeur ) {
Element * cur = sl - > start ;
for ( int i = sl - > start - > niv - 1; i >= 0; i - - )
while ( ( suivant ( cur , i ) != null )
&& ( suivant ( cur , i ) - > val < valeur ) )
cur = suivant ( cur , i );
cur = Suivant ( cur , 0 );
if ( ( cur != 0 ) && ( cur - > val == valeur ) )
return cur ;
return null ;
}
Q2.6 On se propose maintenant de réaliser l’insertion d’un nouvel élément dans une skip liste. Il y
a donc une phase de recherche, puis un tirage aléatoire du niveau du nouvel élément et enfin
une phase de modification de certains pointeurs (Figure 2). On vous donne (vous n’avez pas à
implémenter) une fonction qui vous retourne aléatoirement un nouveau niveau pour un élément
d’une skip-liste, en respectant les probabilités spécifiées.
1
int niveauAleat ( SkipListe * sl );
Écrivez maintenant la fonction d’insertion dans une skip-liste :
1
void inserer ( SkipListe * sl , int valeur );
On note qu’il faut maintenir (dans un tableau par exemple) les derniers pointeurs successeurs de
chaque niveau, afin de mettre facilement à jour les pointeurs du nouvel élément.
6
Figure 2 – Principe de l’insertion dans skip-liste.
Corrigé
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void inserer ( SkipListe * sl , int valeur ) {
Element * cur = sl - > start ;
Element ** mem = ( Element **) malloc ( sizeof ( Element *) * cur - > niv );
for ( int i = sl - > start - > niv - 1; i >= 0; i - - ) {
while ( ( suivant ( cur , i ) != null )
&& ( suivant ( cur , i ) - > val < valeur ) )
cur = suivant ( cur , i );
mem [ i ] = cur ;
}
cur = suivant ( cur , 0 );
if ( ( cur != 0 ) && ( cur - > val == valeur ) )
return ; /* l ’ element existe d é j à . */
Element * e = CreerElement ( valeur , NiveauAleat ( sl ) );
for ( int i = e - > niv - 1; i >= 0; i - - ) {
modifieSuivant ( e , i , suivant ( mem [ i ] , e ) );
modifieSuivant ( mem [ i ] , i , e );
}
}
Q2.7 Dans les deux questions précédentes, pourquoi la recherche comme l’insertion sont-elles plus
efficaces que dans une simple liste triée ? Donnez une indication informelle de la complexité
moyenne de ces deux opérations.
Corrigé
Les pointeurs de niveau important permettent de faire des grands pas dans la liste, au contraire d’une
liste chaînée où l’on ne peut avancer que de un par un. La complexité sera environ logarithmique en
moyenne dans les deux cas (l’insertion ne coûte pas plus cher car elle est de complexité niveau_max,
donc égale à log2 n).
3
PileMin (4 points)
Le but de cet exercice est de concevoir une structure de données appelée PileMin qui implémente le
type abstrait Pile et permet d’obtenir son élément minimum efficacement.
Nous supposons que l’on dispose d’un type Pile, ainsi que les opérations suivante :
7
1
2
3
4
void empiler ( Pile * p , int valeur );
int depiler ( Pile * p ); /* retourne l ’é l é ment au sommet et le supprime */
int sommet ( Pile * p ); /* retourne l ’é l é ment au sommet sans le supprimer */
int estVide ( Pile * p );
Q3.1 Complétez la structure de données PileMin pour implémenter une pile d’entiers qui permet d’effectuer les opérations empiler, depiler, estVide, minimum en temps O(1).
1
2
3
4
typedef struct pile_min_st {
Pile * elems ;
... /* à compl é ter */
} PileMin ;
Corrigé
L’idée est d’utiliser une pile auxiliaire pour stocker les valeurs minimums. Les opérations empiler
et depiler seront implémenter de façon à garantir que le sommet de la pile auxiliaire correspond
toujours à la valeur minimum de la pile elems.
1
2
3
4
typedef struct pile_min_st {
Pile * elems ;
Pile * min ;
} PileMin ;
Q3.2 Écrivez les opérations empilerMin, depilerMin, minimum et vérifier que leur complexité en
temps de calcul est de O(1) :
1
2
3
void empilerMin ( PileMin p , int valeur );
int depilerMin ( PileMin p );
int minimum ( PileMin p ); /* retourne la valeur minimale */
Corrigé
1
2
3
4
5
6
7
8
9
10
11
void empilerMin ( PileMin p , int valeur ) {
if ( estVide ( p . elems ) ) {
empiler ( p . elems , valeur );
empiler ( p . min , valeur );
} else {
if ( valeur < sommet ( p . min ) )
empiler ( p . min , valeur );
else
empiler ( p . min , valeur );
}
}
12
13
14
15
16
int depilerMin ( PileMin p ) {
depiler ( p . min );
return depiler ( p . elems );
}
17
18
19
20
int minimum ( PileMin p ) {
return sommet ( p . min );
}
8
4
Listes doublement triées (4 points)
Dans une liste multi-chaînée, chaque nœud contient plusieurs liens vers d’autres nœuds de la liste
(la liste doublement chaînée vue en cours en est un cas particulier).
Dans cet exercice, nous considérons la structure suivante d’une liste doublement chaînée :
1
2
3
4
5
6
typedef struct st_maillon {
char nom [100];
unsigned int age ;
st_maillon * suivant_nom ;
st_maillon * suivant_age ;
} Maillon ;
7
8
9
10
11
typedef struct st_liste {
Maillon * par_nom ;
Maillon * par_age
} ListeTriee ;
Cette structure peut être utilisé pour organiser les informations (nom, age) d’une collection de
personnes dans l’ordre croissant, selon deux critères simultanément : le nom et l’age. En partant de
par_nom et en suivant les pointeurs suivant_nom, nous parcourons la liste dans l’ordre alphabétique des
noms ; ainsi en partant de par_age et en suivant les pointeurs suivant_age, nous parcourons la liste dans
l’ordre croissant des ages.
Q4.1 Dessinez la liste triée (par nom et par age) correspondante aux personnes suivantes [(“Anne”, 29),
(“Cyrille”, 41), (“Guillaume”, 39)].
Corrigé
Anne
29
Cyrille
41
Guillaume
39
Q4.2 Écrivez la fonction d’insertion des information d’une nouvelle personne dans une liste triée. La
liste reste triée par nom et par age après l’insertion.
1
void inserer ( ListeTriee * l , char * nom , unsigned int age );
Quelle est la complexité asymptotique de cette fonction en nombre de comparaison en fonction
de la longueur de la liste n ?
9
Corrigé
1
2
3
4
5
6
7
8
/* on suppose que l est non null */
void inserer ( ListeTriee * l , char * nom , unsigned int age ) {
/* cr é er un maillon pour le nouvel é l é ment */
Maillon * nouv = ( Maillon *) malloc ( sizeof ( Maillon ) );
strcpy ( nouv - > nom , nom );
nouv - > age = age ;
nouv - > suivant_nom = NULL ;
nouv - > suivant_age = NULL ;
9
/* ins é rer au bon endroit selon l ’ ordre alphab é tique des nom */
Maillon * prev = NULL , cour = l - > par_nom ;
while ( cour != NULL && strcmp ( cour - > nom , nouv - > nom ) > 0) {
prev = cour ;
cour = cour - > suivant_nom ;
}
if ( prev == NULL )
l - > par_nom = nouv ;
else
prev - > suivant_nom = nouv ;
nouv - > suivant_nom = cour ;
10
11
12
13
14
15
16
17
18
19
20
21
/* ajuster les pointeurs d ’ age */
Maillon * prev = NULL ;
Maillon * cour = l - > par_age ;
while ( cour != NULL && cour - > age < nouv - > age ) {
prev = cour ;
cour = cour - > suivant_age ;
}
if ( prev == NULL )
l - > par_age = nouv ;
else
prev - > suivant_age = nouv ;
nouv - > suivant_age = cour ;
22
23
24
25
26
27
28
29
30
31
32
33
34
}
— Complexité en temps : O(n)
Q4.3 Écrivez une fonction qui prend une liste multi-chaînée et renvoie une copie de cette liste :
1
2
/* retourne un pointeur vers la t ê te de la nouvelle liste */
ListeTriee * dupliquerListe ( ListeTriee l );
Cette fonction dois avoir une complexité en temps linéaire O(n) ou n est la longueur de la liste.
Vous disposez de la fonction Maillon* copierMaillon( Maillon* p ); qui copie le maillon p et renvoie
un pointeur vers la copie (vous n’avez pas à l’implémenter).
10
Corrigé
1
2
3
4
5
6
7
8
9
10
/* on suppose que l est non null */
ListeTriee * dupliquerListe ( ListeTriee l ) {
/* é tape 1: dupliquer chaque noeud de l et ins é rer le nouveau noeud
apr è s le noeud originale dans la liste l */
Maillon * cour = l - > par_nom ;
while ( cour != NULL ) {
Maillon * copie = copierMaillon ( cour );
copie - > suivant_nom = cour - > suivant_nom ;
cour - > suivant_nom = copie ;
}
11
/* é tape 2: ajuster les pointeurs d ’ age */
Maillon * cour = l - > par_nom ;
while ( cour != NULL ) {
cour - > suivant_nom - > suivant_age = cour - > suivant_age - > suivant_nom ;
cour - > suivant_nom - > suivant_nom ;
}
12
13
14
15
16
17
18
/* é tape 3: s é parer la liste copi é e de la liste originale */
ListeTriee * dup_liste = ( ListeTriee *) malloc ( sizeof ( ListeTriee ) );
dup_liste - > par_nom = NULL ;
dup_liste - > par_age = NULL ;
if (l - > par_nom == NULL )
return dup_liste ;
else {
dup_liste - > par_nom = l - > par_nom - > suivant_nom ;
sup_liste - > par_age = l - > par_age - > suivant_nom ;
}
Maillon * orig = l - > par_nom ;
Maillon * copie = NULL ;
while ( orig != NULL ) {
copie = orig - > suivant_nom ;
orig - > suivant_nom = copie - > suivant_nom ;
if ( copie - > suivant_nom != NULL )
copie - > suivant_nom = copie - > suivant_nom - > suivant_nom ;
orig = orig - > suivant_nom ;
}
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
return dup_liste ;
39
40
}
— Complexité en temps : O(n)
— Espace auxiliaire utilisée : O(1)
Fin du sujet. Bonne Chance !
11
© Copyright 2024 ExpyDoc
