Salut,
je suis en train de réviser pour les rattrapages de septembre à la fac ou je suis.
Je mets les questions que j'ai du mal à faire
L'enoncé sera laissé en noir,les questions seront mises en bleu
Merci a tous ceux qui m'aideront
Problème
Dans le problème nous manipulons des tas.Un tas est un conteneur de données,qu'on peut représenter comme un arbre dont la racine contient à chaque instant le plus petit élément du conteneur (on note que cela suppose qu'il existe une relation d'ordre sue les éléments).Ainsi ,l'opération retrouver le plus petit élément se réalise toujours en temps constant .Nous allons nous servir des tas pour réaliser des tris sur des donnéés.
Pour ne pas implémenter les tas ,on récupère ( sur le Web,par exemple), un module C permettant de les manipuler.Ce module est composé d'un fichier heap.c contenant les définitions de fonctions de manipulation d'un tas,et d'un fichier heap.h dont le contenu est:
#ifndef _HEAP_H
#define _HEAP_H
typedef struct _heap {
/*On se moque du contenu de la structure*/
} Heap;
/*Toutes ces fonctions retournent 0 ssi pas d'erreur,
un code d'erreur sinon*/
/*Création d'un tas .Le paramètre cmp permet de préciser
la relation d'ordre sur ces éléments. Cplx : 0(1)*/
extern int newHeap(Heap **h, int (*cmp)(void *,void *));
/*Ajouter l'élément désigné par newElt au tas désigné par h.
Fait une copie à usage interne de l'élément.
Cplx : 0(log(nb d'éléments du tas)+taille élément)*/
extern int addToHeap(Heap *h, void *newElt);
/*Retirer le plus petit élément du tas ,le recopier dans la zone
désignée par res ,qu'on suppose suffisament grande.
Cplx: 0(log(nb d'éléments du tas)+taille élément)*/
extern int removeSmallestFromHeap(Heap *h, void *res);
/*Libérer les ressources occupées par le tas. au retour de la fonction,
*h vaut NULL.Cplx: 0(nb d'éléments du tas)*/
extern int freeHeap(Heap **h);
/*Ici ,le fichier contient d'autres déclarations de fonctions,
qui ne nous intérressent pas
*/
...
#endif
Nous nous intedisons de mofifier ces fichiers: nous ne pouvons pas les utiliser.
Dans les fonctions de comparaisons qu'on vous demande d'écrire dans le problème ,
les conventions pour la valeur sont les memes que pour strcmp.
Exercice 1
Ecrire une fonction réalisant la comparaison de deux chaines de caractères suivant l'ordre lexicographique.Votre fonction devra avoir la signature suivante:
int cmpLexico(const char *s1, const char * s2);
Code :
- int cmpLexico(const char *s, const char *t){
- int i=0, j=0;
- if(s[i]=='\0' && t[j]=='\0')
- while(s[i]!='\0' && t[j]!='\0'){
- if(s[i] == t[i]){
- i++;
- j++;
- }
- if(s[i] < t[j]) return -1;
- if (s[i] > t[j]) return 1;
- }
- return 0;
- }
|
Meme chose,mais pour l'ordre lexicographique inverse (cette fois-ci le nom de la fonction sera cmpInvLexico)
Code :
- int cmpInvLexico(const char *s1,const char *s2){
- int res = strcmp(s1,s2);
- return (-res);
- }
|
Exercice 2
L'ordre militaire sur les mots est donné par le nombre des lettres des mots: moins un mot a de lettres ,plus il est petit pour l'ordre militaire.
Ecrivez une fonction réalisant la comparaison de deux chaines de caractères suivant l'ordre militaire.Votre fonction devra avoir la signature suivante:
int cmpMilitaire(const char *s1, const char * s2);
Code :
- int cmpMilitaire(const char *s1, const char *s2){
- size_t l1,l2;
- l1 = strlen(s1);
- l2 = strlen(s2);
- if(l1 < l2) return 1;
- if(l1 > l2) return -1;
- else return (cmpLexico(s1,s2));
- }
|
Meme chose,mais pour l'ordre militaire inverse (cette fois-ci le nom de la fonction sera cmpInvMilitaire)
Code :
- int cmpInvMilitaire(const char *s1, const char *s2){
- return (-cmpMilitaire(s1,s2));
- }
|
Exercice 3
On définit maintenant une relation d'ordre sur les chaines de caractères de la façon suivante. Soit u un mot. A partir de u, on calcule u' en ramenant les voyelles au début du mot ,sans en changer l'ordre. Par exemple,si u = xbygeak,alors u' = yeaxbgk. Soient deux mots u1 et u2 . On dit que u1 est plus petit que u2 si et seulement si u1' est plus petit,pour l'odre lexicographique que u2'. Par exemple u1 = xbegyak est plus petit que u2 = xbygeak, car u1' = eyaxbgk est plus petit,pour l'ordre lexicographique , que u2' = yeaxbgk. Nous appellerons cette relation d'ordre voyelles-consonnes.
Ecrire une fonction réalisant la comparaison de deux chaines de caractères suivant la relation voyelles-consonnes.Attention :au sortir de la fonction ,les chaines de caractères doivent etre telles qu' elles étaient au départ de la fonction.
Code :
- char *range(const char *s){
- char * tmp;
- int i, j=0, k=j;
- for(i=0; i<strlen(s1); i++){
- if(s[i]=='a' || s[i]=='e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u' || s[i] == 'y')
- tmp[j] = s[i];
- while(k != i){
- tmp[k+1] = s[k];
- k++;
- }
- }
- return tmp;
- }
- int cmpVoyellesConsonnes(const char *s1, const char *s2){
- return strcmp(range(s1),range(s2));
- }
|
Exercice 4
Soit un flot texte, ouvert en lecture , dont nous supposerons qu'il ne contient que des lignes composées de consonnes et de voyelles (pas de chiffres,espacements,ponctuations,etc..).Ecrire une fonction
int triFlots(FILE *flotLecture, FILE *flotEcriture,
int (*cmp)(const char *s1, const char *s2))
prenant un tel flot en paramètre ,avec un autre flot texte ,ouvert en écriture ,et qui met dans le second toutes les lignes du premier, triées par l'ordre donné par la fonction désignée par cmp.Vous n'avez pas le droit de faire le tri directement : vous devez utiliser un tas ,dans lequel vous mettrez les lignes du flot en lecture,puis vous en retirerez les éléments un par un pour pour les mettre dans le flot en écriture.La fonction retourne 0 si tout se passe bien ,un code d'erreur sinon. N'oubliez pas de libérer toutes les ressources intermédiaires quand vous n'en avez plus besoin.
Exercice 5
Ecrire un programme dans lequel vous utilisez triFlots pour trier l'entrée standart par l'ordre voyelles-consonnes, en mettant le résultat sur la sortie standart.
Exercice 6
On va maitenant trier un tableau de chaines de caractères .
Ecrire une fonction
int triTab(char **tab, int (*cmp)(const char *s1, const char *s2))
ou tab désigne le premier élément d'une suite de chaines de caratères qu'il fau trier ,la suite se terminant par NULL ,et cmp permet de spécifier la relation d'ordre à utiliser pour le tri.Au sortir de la fonction , la suite désignée par tab sera triée par l'ordre spécifié. Encore, une fois ,vous n'avez pas le droit de réaliser le tri à proprement parler vous-meme,vous devez passer par un tas. La fonction retourne 0 si tout se passe bien un code d'erreur sinon. N'oubliez pas de libérer toutes les ressources intemédiaires quand vous n'en avez plus besoin.
Exercice 7
Ecrire un programme prenant en premier paramètre
-a: ordre lexicographique
-b: ordre lexicographique inverse
-c: ordre militaire
-d: ordre militaire inverse
-e: ordre voyelles consonnes
puis des mots quelconques, et affichant sur sa sortie standart ces mots triés par l'ordre spécifié. Par exemple
% tri -c sdf rgtrt sddd d g reffr y
d
g
y
sdf
sddd
rgtrt
reffr
Vous devez utiliser ce que vous avez déjà écrit dans les exercices précédents
Message édité par Profil supprimé le 13-08-2005 à 12:55:59
![[:mlc]](https://forum-images.hardware.fr/images/perso/mlc.gif "[:mlc]")