Algorithmique et Structures des Données 2: Les Listes Chaînées

Reprendre l’exercice précédant avec une liste doublement chaînée. L’ordre de l’affichage

(croissant ou décroissant) est cette fois-ci déterminé par l’utilisateur.

Exercice 5 :

Donner un algorithme qui permet la recherche d’un entier X dans une liste chaînée d’entiers.

Modifier cet algorithme pour pouvoir donner en plus, dans le cas de l’existence de l’entier

recherché, ses positions d’occurrence et sa fréquence.

Exercice 6 :

Donner un algorithme qui permet l’insertion d’un caractère dans une liste chaînée de

caractères. L’algorithme doit donner, à l’utilisateur, le choix de la position de l’insertion

(début, fin ou insertion à droite/gauche d’une position P).

Exercice 7 :

On se propose de représenter un polynôme à l’aide d’une liste simplement chaînée. Chaque

élément de la liste servira pour un monôme.

Par exemple le polynôme suivant : 3X4+2X-X3+2

sera représenté par :

3

4

2

1

-1

3

2

0

•

On suppose que le nombre de monômes est fournit par l’utilisateur.

Donner un algorithme permettant la saisie et l’affichage d’un polynôme.

Modifier cet algorithme pour pouvoir :

1. afficher la liste dans l’ordre décroissant des puissances.

2. afficher les monômes ayant une puissance paire.

1

Exercice 8 :

Une société agricole désire gérer sa clientèle automatiquement pour un produit donné. Pour ce

faire, elle identifie chaque Client par trois paramètres :

• nom qui indique le nom du client,

•

fidèle qui indique si le client est fidèle ou non à la société (si oui fidèle est mis à 1

sinon à 0)

• et prix qui indique le prix d’achat proposé par le client.

Les différents clients sont rangés dans une liste chaînée.

Le gérant de la société désire vendre son produit seulement aux clients fidèles. Il désire

particulièrement vendre avec le plus haut prix d’achat possible.

Donner l’algorithme qui permet d’aider le gérant pour faire son choix.

Exercice 9 :

On se propose de réaliser un vote du président d’un comté national d’étudiants.

Chaque candidat est identifié par son nom et un pourcentage qui indique le pourcentage des

voix pour ce candidat.

Les différents candidats sont rangés dans une liste chaînée. Le candidat élu doit posséder le

meilleur pourcentage de voix.

Donner l’algorithme qui permet de déterminer le président élu.

Exercice 10 :

I) On se propose dans cet exercice d’assurer la manipulation d’une liste chaînée d’étudiants.

L’étudiant étant identifié par les paramètres suivants : Nom, Prénom, Date de naissance,

Matricule, et Moyenne.

Donner un algorithme permettant de faire la saisie des informations concernant un nombre

inconnu d’étudiants dans une liste chaînée puis l’affichage de celui ayant la meilleure

moyenne et de celui ayant la plus mauvaise moyenne.

II) Pour déterminer le rang d’un étudiant, il suffit de parcourir la liste d’étudiants et de

compter le nombre des moyennes strictement supérieures à la sienne et de l’augmenter de 1.

Exemple : si dans la liste d’étudiants, le nombre des moyennes supérieures à 15 est de

3 alors le rang de l’étudiant ayant cette moyenne 15 est 3 +1 = 4.

Modifier l’algorithme de la question I) pour qu’il affiche le rang de chaque étudiant.

III) dans cette partie la moyenne de l’étudiant est remplacée par un tableau de taille 3 : la

première case de ce tableau représente la note en Mathématique, la deuxième case représente

la note en Physique et la troisième représente la note en Informatique.

Modifier l’algorithme de la question I) pour qu’il puisse afficher le meilleur étudiant de

chaque matière et le majeur de la classe.

2