Scribd
Importer
412 vues2 pages

TP Listes Chaînées et Structures de Données

Ce document présente trois exercices sur les listes chaînées, les files d'attente et les piles. Le premier exercice concerne une file d'attente de cinéma, le deuxième une liste simplement chaînée, et le troisième modélise une file de piles d'assiettes sales dans une cuisine.

Transféré par

Mohammed Rammeh
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
412 vues2 pages

TP Listes Chaînées et Structures de Données

Ce document présente trois exercices sur les listes chaînées, les files d'attente et les piles. Le premier exercice concerne une file d'attente de cinéma, le deuxième une liste simplement chaînée, et le troisième modélise une file de piles d'assiettes sales dans une cuisine.

Transféré par

Mohammed Rammeh
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Licence 3 IST

Informatique

TP 9 : LISTES CHAINEES,
FILES DATTENTE, PILES

`res
Table des matie
But
Exercice 1 : file dattente au cinema
Exercice 2 : liste simplement chainee
Exercice 3 : Liste et pile ou comment gerer sa vaisselle sale ?

1
1
1
2

But
` travers les
Vous devez maitriser `
a la fin de cette seance la manipulation des listes chainees. A
listes chainees, vous devez etre capable de gerer les structures de file et de pile.
ma
Exercice 1 : file dattente au cine
Considerons une file dattente devant un cinema. La file initialement vide se remplit au fur et `a
mesure que les individus arrivent avec une gestion particuli`ere liee au fait que si un nouvel individu
apercoit dans la file un ami, alors il se joint `a lui pour attendre.
Pour manipuler cette liste dattente, vous considererez que les individus sont representes par
des entiers. Deux amis seront alors deux entiers identiques. La structure de donnees utilisee pour
representer la liste devra donc integrer non seulement lindividu, mais aussi le nombre doccurrences
associe.
(1) Proposez une structure de donnees permettant de gerer une telle file

(2) Ecrire
la fonction permettant dajouter un nouvel individu dans une telle file

(3) Ecrire
la fonction permettant de retirer le premier individu dune telle file
e
Exercice 2 : liste simplement chaine
Soit une liste simplement chainee dont chaque maillon est defini de la mani`ere suivante :
typedef struct s_maillon {int valeur ; struct s_maillon * suivant ; } t_maillon

(1) Ecrire
une fonction qui calcule la somme des elements de la liste simplement chainee. Par
exemple, la liste composee des entiers 23, 52, 31, 45, 59 aura pour somme 210.
M. Kowalski

es, files dattente, piles


TP 9 : listes chaine

Informatique

(2) Ecrire
une procedure qui inverse la liste simplement chainee. Par exemple, la liste composee
consecutivement des entiers 23, 52, 31, 45, 59 sera inversee de la mani`ere suivante : 59 ,45,
31, 52, 23.
rer sa vaisselle sale ?
Exercice 3 : Liste et pile ou comment ge
Nous voulons modeliser une file constituee de piles dassiettes sales dans une cuisine de restaurant.
Chaque pile dassiettes est posee au fur et `a mesure quelles arrivent en cuisine dans une file. Le
plongeur nettoie les assiettes en les prenant, une par une, sur le dessus de la premi`ere pile stockee.
(1) Proposez une structure de donnees qui permette de modeliser le probl`eme.

(2) Ecrivez
un algorithme permettant dajouter une pile dassiettes.

(3) Ecrivez
un algorithme permettant au plongeur de retirer une assiette pour la nettoyer (dans
la premi`ere pile introduite).

Vous aimerez peut-être aussi