Ex 1.1 : A faire...
Vide(Creer(E))= Vrai
Vide(Ajouter(E,X))= Faux
Ajouter(E,X)= ajoute un element en queue de E
Supprimer(Ajouter(E,X),Y)= Y apprtient a E, X n'apprtient plus a E.
taille de E inchangé
Cardinal(Creer(E))= 0
Cardinal(Ajouter(E,X),Y)= Cardinal(E) + 1
Cardinal(Supprimer(E,X))= Cardinal(E) - 1 (E∫0)
Pred(Succ(E))= E (Si E n'est pas le dernier de l'ensemble)
Succ(Pred(E))= E (Si E n'est pas le premier de l'ensemble)
Ex 1.2 :
typedef int Element; /* Je met int de maniere arbitraire, on peut aussi
mettre float, ou autre chose... */
typedef struct Cellule {
Element valeur;
struct Cellule * suivant;
struct Cellule * precedent;
} Cellule;
typedef struct Cellule * Ensemble;
Ex 1.3 :
Avantages: mémoire illimité, pas besoin de connaitre
la taille de l'ensemble (a l'inverse d'un tableau) on peut donc ajoute
autant d'elements que l'on veut !
Inconvenients: impossible d'acceder directement a une valeur donne,
on est oblige de parcourir la liste chainee pour cela (perte de temps)
Ex 1.4 :
X n'appartient pas a E.
Ex 1.5 :
/* pour APPARTIENT, il faut preciser que l'Ensmble E n'est pas
classe dans un ordre croissant ou decroissant */
/* BOOL : Booleen */
BOOL Appartient(E:Ensemble,X:Element) { /* ITERATIF */
while(E!=NULL) {
if (E->valeur==X)
return(VRAI);
E=E->suivant;
}
return(FAUX);
}
BOOL Appartient(E:Ensemble,X:Element) { /* RECURSIF */
if (E==NULL)
return(FAUX);
if (E->valeur==X)
return(VRAI);
return(Appartient(E->suivant,X));
}
Nat Cardinal(E:Ensemble) { /* ITERATIF */
Nat compt=0;
while(E!=NULL) {
compt++;
E=E->suivant;
}
return(compt);
}
Nat Cardinal(E:Ensemble) { /* RECURSIF */
if (E==NULL)
return(0);
else
return(Appartient(E->suivant)+1);
}
Ex 1.6 :
/* E est trie dans l'ordre croissant */
BOOL Appartient(E:Ensemble,X:Element) { /* RECURSIF */
if (E==NULL)
return(FAUX);
if (E->valeur>X)
return(FAUX);
if (E->valeur==X)
return(VRAI);
return(Appartient(E->suivant,X));
}
©2002
All Rights Reserved to Didier STRAUS www.Software-DS.com
Ex 1.7 :
Ensemble Min(E:Ensemble) { /* ITERATIF, on suppose E non vide
*/
Ensemble M;
M=E->valeur;
E=E->suivant;
while(E!=NULL) {
if ((E->valeur)<(M->valeur))
M=E;
E=E->suivant;
}
return(M);
}
Ex 1.8 :
Ensemble Min(E1,E2:Ensemble) { /* ITERATIF, on suppose E non
vide */
if (E1==NULL)
return(E2);
if ((E1->valeur) < (E2->valeur))
return(Min(E1->suivant,E1));
/* else */
return(Min(E1->suivant,E2));
}
Ex 1.9 :
Ajouter(E1,E2:Ensemble){
while(E1->suivant!=NULL){
E1=E1->suivant;
}
E1->suivant=Min(E2); /* Min de 1.7 */
E1->suivant->suivant=NULL;
}
©2002
All Rights Reserved to Didier STRAUS www.Software-DS.com
Ex 1.10 :
Effacer(E:Ensemble){
Ensemble P;
P=Min(E);
P->precedent->suivant=P->suivant;
P->suivant->precedent=P->precedent;
free(P);
}
Ex 1.11 :
Tri_Selection(E:Ensemble){
Ensemble E2;
Creer(E2);
while(Cardinal(E)!=0){
Ajouter(E2,E);
Effacer(E);
}
E=E2;
}
©2002
All Rights Reserved to Didier STRAUS www.Software-DS.com
Ex 1.12 :
Oui, le tri rapide consiste a diviser un tableau en 2 sous tableau
et a trier
les 2 sous tableau par rapport a un pivot.
Ex 1.13 :
Union:
Si E1 est vide, on recopie E2 dans E
Si E2 est vide, on recopie E1 dans E
Si E1 et E2 non vide:
E1 et E2 sont trie tous les 2, donc on va recopier la valeur de E1 dans
E
s'il n'y a pas de valeurs plus petite que E1 dans E2 (si c'est le cas,
on
recopira ces valeurs dans E puis on copira la valeur de E1 dans E)
Les valeurs recopier seront supprimer
Algo iteratif:
tant que !vide(E1) et !vide(E2) faire
si vide(E1) alors
si !Appartient(E,Val(E2)) alors ajouter(E,val(E2));
supprimer(E2);
sinon si vide(E2) alors
si !Appartient(E,Val(E1)) alors ajouter(E,val(E1));
supprimer(E1);
sinon si Val(E1)<Val(E2) alors
si !Appartient(E,Val(E1)) alors ajouter(E,val(E1));
supprimer(E1);
sinon
si !Appartient(E,Val(E2)) alors ajouter(E,val(E2));
supprimer(E2);
fin tant que
Ex 1.14 :
Inter:
Si E1 est vide, E=NULL , on a fini
Si E2 est vide, E=NULL , on a fini
Si E1 et E2 non vide:
on prend la valeur de tete de E1, on rechercher si elle existe dans
E2, si c'est le cas on
la memorise dans E2 et on la supprime de E1.
(Pour une meilleur optimisation, on n'utilise pas la fonction Appartient
!)
Algo iteratif:
si vide(E1) ou vide(E2) alors
E=NULL
sinon
tant que !vide(E1)
si (Val(E1)==Val(E2) alors
ajouter(E,Val(E1));
supprimer(E1);
supprimer(E2);
sinon si (Val(E1)<Val(E2) alors
supprimer(E1);
sinon
supprimer(E2);
fin tant que
Ex 1.15 :
typedef int Element; /* Je met int de maniere arbitraire, on
peut aussi mettre float, ou autre chose... */
typedef struct Cellule {
Element valeur;
int nb; /* nombre de fois */
struct Cellule * suivant;
struct Cellule * precedent;
} Cellule;
typedef struct Cellule * Multi_Ensemble;
Ex 1.16 :
int c;
Element E
Liste K,M
K=L
tant que K->suivant∫NULL faire
E=K->Valeur;
c=0;
M=L
tant que M->suivant∫NULL faire
si M->valeur==E alors
c=c+1;
fin tant que
ajouter(MU,E,c);
fin tant que
Cette correction est ma correction, elle ne vous permet pas d'avoir
un 20/20 mais une bonne note.
©2002 All Rights Reserved to Didier
STRAUS www.Software-DS.com
|
