Exercices de C pour révision

[Compte_supprime_69952]

Salut,

je suis en train de réviser pour les rattrapages de septembre à la fac ou je suis.

Je mets les quetions que j'ai du mal à résoudre

L'enoncé sera laissé en noir et 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);

int cmpLexico(cont char *s1, const char *s2){
return(strcmp(s1,s2));
}

Meme chose,mais pour l'ordre lexicographique inverse (cette fois-ci le nom de la fonction sera cmpInvLexico)

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);

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)

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.

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

[Chimayscripteur]

Pour un peu tous tes posts, je crois que ce tuto serait pas mal:

Tuto Listes Chaînees

[Compte_supprime_69952]

Pour un peu tous tes posts, je crois que ce tuto serait pas mal:

Tuto Listes Chaînees

Merci pour le tuto.

Je voudrais savoir si tu sais comment faire pour manipuler 2 fichiers en lecture et en écriture pour écrire un programme qui lit un fichier, tri le fichier et met le résultat dans un fichier ouvert en écriture ce programme doit utiliser un tas comme décrit dans le problème (cf début du post)

merci de me répondre

[Chimayscripteur]

Tout d'abord, tu ne peux ouvrir un fichier qu'en lecture OU en écriture, pas les 2 en même temps (pitit rappel ).

Pour ton problème, tu ouvres le premier fichier en flux de lecture, tu le trie (en utilisant des variables temporaires) et tu enregistres ton résultat dans un autre flux de fichier mais cette fois ouvert en écriture.

Si tu veux plus de détails, tu peux faire des recherches sur les forums dédiés à la programmation et au développement!

[therabbit]

je peux pas t'aider dans ton domaine mais je voulais t'exprimer toute ma solidarité, étant un grand habitué de cet ignoble procédé qu'est le septembrage.