3) Fichiers
Exercice 1 : Ecrire un algorithme qui délivre le nombre d’éléments d’un fichier.
Exercice 2 : Ecrire une fonction qui délivre la somme des éléments de rang pair d’un fichier de nombres entiers
(x2 + x4 +…).
Exercice 3 : Ecrire une fonction qui délivre la valeur du dernier élément du fichier.
Exercice 4 : Ecrire une fonction qui délivre la somme du premier élément et du dernier élément du fichier (par
convention, si le fichier ne contient qu’un seul élément x1, le résultat sera égal à 2x1).
Exercice 5 : Ecrire une fonction qui calcule le nombre d’occurrences d’une valeur « val » dans un fichier.
Exercice 6 : Ecrire une fonction qui calcule le rang de la dernière occurrence de la valeur « val » dans un fichier.
Exercice 7 : Ecrire une fonction qui vérifie qu’un fichier possède au moins n éléments.
Exercice 8 : Ecrire une fonction qui délivre le rang de la première occurrence de la valeur « val » (cette fonction
délivre zéro si la valeur « val » est absente du fichier).
Exercice 9 : Ecrire une fonction qui vérifie que le fichier f est trié dans l’ordre croissant sans répétition.
Exercice 10 : Ecrire une fonction qui délivre le nombre d’occurrences de la valeur « val » dans un fichier trié.
Exercice 11 : Ecrire une fonction qui délivre le rang de la dernière occurrence de la valeur « val » dans un fichier trié.
Exercice 12 : Ecrire une fonction d’insertion de la valeur « valinsert » après chaque occurrence de la valeur « val ».
Exercice 13 : Ecrire une fonction de suppression dans un fichier de tous les éléments ayant un rang compris entre i et j (j i).
4) Structures linéaires chaînées.
Exercice 14 : Ecrire un programme en C qui crée la chose :
P
1 2
Afficher 1, puis 2, puis de nouveau 1.
Exercice 15 : Que fait la fonction suivante ?
vide ecritliste(pointeur liste)
{ if(liste != NULL)
{ printf("%d ", liste->info);
ecritliste(liste->suivant);
printf("%d ", liste->info);
}
}
Exercice 16 : Que fait la fonction suivante ?
vide ecritliste(pointeur liste)
{ if(liste != NULL)
{ ecritliste(liste->suivant);
printf("%d ", liste->info);
ecritliste(liste->suivant);
}
}
Dans les deux exercices, liste contien les valeurs <a, b, c>.
Exercice 17 : soit la déclaration : entier n, x ;
Calculer xn x0 = 1 ;
xn = x * xn-1 ;
En écrivant la fonction récursive appelée puissance.
Exercice 18 : x0 =1
n
x x2n = (xn)2
x2n+1 = x * x2n
En écrivant la fonction récursive appelée puissance.
1
Exercice 19 : Ecrire la fonction récursive espacer dont l’en-tête est :
vide espacer(entier n)
//spécification(n0)(écrit n en séparant les chiffres par un espace)
Exemple : espacer(123) donne 1 2 3.
Exercice 20 : booléen pluslongue (pointeur l1, pointeur l2)
//spécification()(pluslongue = l1 a un nombre d’éléments au nombre d’éléments de l2)
Exercice 21 : booléen memeliste (pointeur l1, pointeur l2)
//spécification()(l1 et l2 ont les mêmes éléments dans le même ordre)
Exercice 22 : booléen appartient (entier n, pointeur l)
//spécification()(appartient = x est une information d’une cellule de l)
Exercice 23 : Ecrire la fonction point sous forme itérative. Elle délivre l’adresse de la cellule contenant la valeur
val.
Exercice 24 : Ecrire une fonction, sous forme itérative et récursive, qui vérifie qu’une liste est triée.
Exercice 25 : Ecrire sous forme itérative, un algorithme de recherche de la première occurrence d’une valeur
dans une liste triée.
Exercice 26 : On considère qu’une liste chaînée est la représentation d’une chaîne de caractères. L’information
contenue dans une cellule est donc réduite à un seul caractère.
On désire écrire des fonctions permettant de comparer deux chaînes de caractères. Pour toutes les fonctions, on
donnera un schéma itératif et un schéma récursif.
Ecrire les fonctions d’en-tête qui suit :
- booléen egal (pointeur liste1, pointeur liste2)
// spécification ()(egal = (liste1+ = liste2+))
Cette fonction délivre la valeur vrai si les deux chaînes sont égales, faux dans le cas contraire.
- booléen super (pointeur liste1, pointeur liste2)
// spécification ()(egal = (liste1+ > liste2+))
Cette fonction délivre la valeur vrai si la chaîne contenue dans liste1 est plus grande, par ordre alphabétique, par
rapport à celle contenue dans liste2, faux dans le cas contraire.
Exercice 27 : écrire, sous forme itérative et récursive, les algorithmes suivants :
- insertion d’un élément avant la première occurrence d’une valeur.
- insertion d’un élément avant toutes les occurrences d’une valeur.
- suppression de toutes les occurrences d’une valeur.
- suppression de la première occurrence d’une valeur dans une liste triée.
-
5. Les structures linéaires particulières.
Exercice 28 : écrire sous forme post-fixée l’expression : ((((A+B)+D)>H)(E<F)).
Exercice 29 : donner la trace de l’algorithme evalpost pour l’expression post-fixée obtenue à l’exercice 30 et
l’environnement : A=4, B=5, D=1, E=3, H=2, F=0.
Exercice 30 : donner l’algorithme evalpref d’évaluation d’une expression préfixée supposée syntaxiquement correcte.
Exercice 31 : écrire sous forme préfixée l’expression : ((((A+B)+D)>H)(E<F)).
Exercice 32 : faire la trace de l’algorithme evalpref (exercice 28)
Exercice 33 : donner l’algorithme de transformation d’une expression complètement parenthésée en écriture préfixée.
Exercice 34 : Donner un algorithme de passage d’une écriture infixée à une écriture préfixée.
Exercice 35 : Dans une liste chaînée bidirectionnelle :
- écrire une un algorithme de suppression de la kième élément,
- écrire un algorithme de suppression de toutes les occurrences de la valeur « val ».
