[Langage C] algo & structure de donnée : Ensembles

[Soulfly_tribe90]

J'ai un ptit exo de SDA que j'ai envie de me faire tranquillement donc je vous expose les deux premiers points :

1. Spécification des ensembles

Ecrire un module de spéc ENSEMBLE pour la sorte Ens des ensembles de caractères pris uniquement dans l'alphabet des 26 lettres majuscules romaines de 'A' à 'Z', avec les constructeurs de base : 

- v : ensemble vide;
- i : tel que i(e,x) est l'insertion dans l'ensemble e de la lettre désignée par x;

Donnez l'expression de construction avec v et i de l'ensemble e1 contenant exactement les lettres 'B', 'C', 'G'.

Dans ENSEMBLE, définir par rapport à v et i les fonctions : 

- estv, telle que estv(e) retourne vrai si et seulement l'ensemble e est vide;
- app, telle que app(e,z) est vrai si et seulement si la lettre z est dans l'ensemble e;
- card, telle que card(e) est le cardinal de l'ensemble e;
- d, telle que d(e,z) efface la lettre z de l'ensemble e;

Spécifier également la fonction rang fournissant le rang d'une lettre dans l'alphabet, et la fonction lettre faisant l'inverse.

On écrira soigneusement les préconditions nécessaires, en utilisant la comparaison <= entre les caractères supposée connue, et des constantes notées entre deux '.

2. Implantation des ensembles

On représente en mémoire tout ensemble e comme un entier naturel écrit en binaire b26...b2,b1, ou bk est le chiffre binaire 1 si la lettre rang k est dans e, et 0 sinon. Le chiffre b1 est le bit de poids faible et b26 celui de poids fort.
Ecrire la représentation binaire de l'ensemble e1 pris en exemple dans 1., et sa valeur en décimal.

Déclarer en C le type des ensembles pour cette représentation. Programmer en C très simplement les fonctions rang et lettre, en se rappelant que, en C, tout caractère est assimilé à son codage en entier.

Programmer en C toutes les opérations de la question 1., en passant pour i, app, card et d par des fonctions auxiliaires appelées i1, app1, card1 et d1, où l'argument caractère est remplacé par son rang. Ces dernières fonctions sont à programmer récursivement, en même temps sur l'ensemble et sur le rang. On pourra à cet effet utiliser des quotients et restes de divisions entières par 2.

Le point numéro 2 me pose quelques problèmes...

En fait j'ai fait une fonction qui me permet de modifier n'importe quels bits de mon entier :

void bit_set(int *ens, int pos, int etat) {
unsigned int masque;
int i;

masque = 0x2000000;

for(i=0;i<(pos%26);i++)
	masque = masque >> 1;

if(etat)
	ens[pos/26] = ens[pos/26] | masque;
else
	ens[pos/26] = ens[pos/26] & (~masque);

	return;
}

Explication des paramètre : ens c'est l'ensemble qui est un entier, pos c'est la position ou l'on veut modifier le bit de ens et etat c'est la valeur du bit (0 ou 1)

Alors je voulais savoir si vous avez une meilleur solution et qu'est ce que vous pensez de l'exercice et vos idées à la rigueur

Merki d'avance

[tom103]

Salut,

Juste pour vérifier que j'ai bien compris... par exemple, si l'ensemble comprend juste la lettre 'A', la représentation binaire correspondante sera :

00000000000000000000000001

Si on ajoute 'X', par exemple, on aura :

00100000000000000000000001

C'est bien ça ?

Sinon, si ens est un pointeur vers un entier, et non un tableau d'entier, l'expression ens[pos/26] n'a aucun sens...

Moi je ferais comme ça :

void bit_set(int *ens, int pos, int etat) {
unsigned int masque;
int i;

masque = 1 << (pos%26);

if(etat)
	*ens = *ens | masque;
else
	*ens = *ens & (~masque);

	return;
}

Un peu plus simple...

[Soulfly_tribe90]

Ouai tu as bien compris le truc

Je te remercie pour ta contribution et je vais regarder ca un peu plus tard, je suis passé sur un autre truc => je regarderais ca demain

[Soulfly_tribe90]

Je viens de réagir sur le fait qu'il faut que je programme ce truc par récursivité donc pour la fonction i par exemple qui insert dans l'ensemble e une lettre, il faut passer par une fonction i1 intermédiaire...

je vois pas trop comment faire : d'après ce que je comprend j'appelle la fonction i qui va appeller dans un premier temps la fonction rang pour obtenir le rang de la lettre et après on appelle la fonction i1 qui va modifier le bit de rang k (rang de la lettre) de façon récursive... je vois pas comment faire cela exactement.

Quelqu'un a une idée judicieuse a me proposer ?