BIENVENUE SUR VOTRE BLOG D'EXERCICES DE L'UNIVERSITE VIRTUELLE
NB: Pour voir la suite téléchargez la fiche complète en cliquant  ici

On considérera dans les exercices, sauf cas contraire une liste chaînée de ce type :
Type Liste =  ^Cellule
Type Cellule = Structure
  Info : chaîne de caractères
  Suivant : Liste
  Fin structure










EXOS 1 Fonction de comptage dans une liste chaînée
Ecrire une fonction qui renvoie le nombre d’éléments d’une liste chaînée. 

EXOS 2 Fonction de comptage d’occurrences dans une liste chaînée
Ecrire une fonction qui renvoie le nombre d’éléments d’une liste chaînée ayant une valeur donnée (champ Info). 

EXOS 3 -Fonction de vérification d’une liste chaînée triée
Ecrire une fonction qui vérifie si une liste chaînée est triée par valeurs croissantes du champ Info.

EXOS 4-Procédure d’insertion en tête de liste chaînée
Ecrire une procédure qui insère un nouvel élément en tête d’une liste chaînée. 

EXOS 5-Procédure d’insertion en queue de liste chaînée
Ecrire une procédure qui insère un nouvel élément en queue d’une liste chaînée. 

EXOS 6 - Procédure d’insertion à une position donnée 
Ecrire une procédure qui insère un nouvel élément de sorte qu'il se trouve à une position donnée dans la liste. La position est un entier et correspond au numéro du futur élément dans la liste. Le premier élément porte le numéro 1. 

EXOS 7 - Procédure de suppression d’un élément d’une liste chaînée à une position donnée
Ecrire une procédure qui supprime un élément d’une liste chaînée à une position donnée. 


EXOS 8 -Fonction de calcul de moyenne des étudiants
Le département dans lequel vous êtes inscrit souhaite gérer les notes de ses étudiants. Les étudiants ont pour identifiant leur numéro d’étudiant. Ils ont un nom et un prénom. Ces informations sont stockées dans une liste chaînée dont chaque élément comporte aussi un champ moy pour la moyenne de l'étudiant et un champ eval qui est un pointeur sur sa liste de notes. La liste de notes de chaque étudiant est aussi une liste chaînée dont la tête est le champ eval de la cellule de l'étudiant.

On dispose des déclarations suivantes :

Types :
 Ch10   = Chaine de 10 caractères
 Ch30   = Chaine de 30 caractères
 Ent    = entier
 Nb    = réel
 Pe    = ^Etudiant
 Pn    = ^Note

 Etudiant = Structure   no    : Ch10   nom    : Ch30   prenom   : Ch30   moy    : Nb   eval    : Pn   suivant  : Pe        fin Structure

 Note   = Structure   note    : Nb   coeff   : Ent   suivant  : Pn        fin Structure

Faire un schéma de cette structure et vérifier à la page suivante où elle est représentée.

On suppose que tous les champs de la liste des étudiants sont remplis sauf le champ moy. On suppose que toutes les notes des étudiants et tous les coefficients sont remplis

Écrire une procédure moyennesEtudiants qui parcourt la liste des étudiants, et qui calcule et met à jour le champ moy de chaque étudiant à l'aide de la liste des notes sur laquelle pointe le champ eval. La procédure moyennesEtudiants prend en paramètre la tête de la liste des étudiants.


CORRIGES

On considérera dans les exercices, sauf cas contraire une liste chaînée de ce type :
Type Liste =  ^Cellule
Type Cellule = Structure
Info : chaîne de caractères


                           





EXOS 1- Fonction de comptage dans une liste chaînée

fonction cpterEltListeChainee(Tête : Liste) : entier
/*
* Comptage des éléments d'une liste chaînée passée en paramètre */
    Variables :
  nbElt : entier /* nombre d’éléments de la liste *
       pliste : Liste /* pointeur de parcours de la liste */
Début
  /* Initialisation des variables */
  nbElt  0 
     pliste  Tête
  /* Boucle de parcours des éléments de la liste passée en paramètre */ 

tantque pliste <> Nil  faire
   nbElt  ← nbElt + 1    /* on incrémente nbElt */ 
pliste ← pliste^.suivant  /* on passe à l’élément suivant */ 
fintantque 
retourner(nbElt)

Fin

EXOS 2

fonction cpterOccEltListeChainee(Tête : Liste, val : chaîne) : entier /* * Comptage des occurrences d’une valeur d'une liste chaînée passée en paramètre */
Variables : nbOcc : entier /* nombre d’occurrences trouvées dans la liste */
 pliste : Liste /* pointeur de parcours de la liste */
Début
nbOcc ← 0 /* Initialisation des variables */
pliste ← Tête /* Boucle de parcours des éléments de la liste passée en paramètre */
tantque pliste ≠ Nil
si pliste^.info = val alors nbOcc ← nbOcc + 1 /* on incrémente nbOcc */
 fins
i pliste ← pliste^.suivant /* on passe à l’élément suivant */
fintantque

 retourner(nbOcc)



EXOS 3-Fonction de vérification d’une liste chaînée triée

 

 

Ecrire une fonction qui vérifie si une liste chaînée est triée en ordre croissant du champ Info.

fonction estTriee(Tête : Liste) : booléen /* * renvoie vrai si la liste est triée, faux sinon */

Variables : trie : booléen /* indicateur pour l'ordre */

pliste : Liste /* pointeur de parcours */

Début /* Initialisation des variables */

trie ← vrai /* la liste est considérée triée au départ */

pliste ← Tête /* si la liste n’est pas vide */

si pliste <> Nil alors /* Boucle de parcours des éléments *

/ tantque pliste^.suivant <> Nil et trie faire

si pliste^.info <= pliste^.suivant^.info alors

 pliste ← pliste^.suivant /* on passe au suivant */

sinon trie ← faux /* la liste n’est pas triée */

finsi fintantque

 finsi retourner(trie)

fin

EXOS 4-Procédure d’insertion en tête de liste chaînée

Actions à mener :
(1)   Il faut d’abord créer une cellule d’adresse P par l’action Allouer(P). 
(2)   Une fois cette cellule créée il faut donner la valeur à l’information contenue dans ce nouvel élément de la liste. 
(3)   et (4) Enfin, il faut réaliser le chaînage de ce nouvel élément. 














procédure insererEnTete( entrée-sortie Tête : Liste, entrée val : chaîne) /* * Insère un nouvel élément dans la liste chaînée passée en paramètre */
Variables : p : Liste
Début
allouer(p) /* Création de la nouvelle cellule dans la liste */
 p^.info ← val
p^.suivant ← Tête /* liaison (3) */
Tête ← p /* liaison (4) */

 Fin



EXOS 5-Procédure d’insertion en queue de liste chaînée

Si la liste est vide ceci revient à insérer le nouvel élément en tête de liste, sinon :
Actions à mener :
(1)   Il faut d’abord créer une cellule d’adresse P par l’action Allouer(P). 
(2)   Il faut ensuite donner la valeur au champ Info de ce nouvel élément de la liste. 
(3)   et (4) Enfin, il faut réaliser le chaînage de ce nouvel élément au dernier élément de la liste. Pour ce faire il faut connaître l’adresse du dernier élément. Elle sera renvoyée par la fonction dernier, que nous écrirons ensuite, et rangée dans la variable der.













procedure InsererEnQueue( entrée-sortie Tête : Liste, entrée val : chaîne) /* Insère un nouvel élément à la fin de la liste passée en paramètre */
Variables p, der : Liste
 Début
si Tête = Nil alors /* La liste est vide */
 insererEnTete(Tête, val)
sinon / la liste n'est pas vide */
der ← dernier(liste) /* on récupère l’adresse du dernier élément */
1 allouer(p) /* création de la nouvelle cellule */
2 p^.info ← val /* stockage de la valeur dans le champ info */
3 p^.suivant ← Nil /* Liaison (3) : le nouvel élt sera le dernier */
4 der^.suivant ← p /* Liaison (4) /
 finsi Fin  

Pour la fonction dernier, qui permet de récupérer l’adresse du dernier élément de la liste, il faut parcourir tous les éléments de la liste en mémorisant à chaque fois l’adresse de la cellule précédente.
fonction dernier(Tête : Liste) : Liste
fonction dernier(Tête : Liste) : Liste /* Renvoie l’adresse du dernier élément d'une liste chaînée non vide */
 Variables q : Liste
Début q ← Tête
 tantque q^.suivant <> Nil q ← q^.suivant
fintantque
 retourner(q)

 Fin   
Pour voir la suite téléchargez la fiche complète en cliquant  ici


Aucun commentaire:

Selection

Exercices sur Les factorielles

EXOS 1 3 ! = ................................. 1 ! = ................................. 5 ! = ...................................

Autres articles du blog