Algorithmique Et Structures de Donnees Les Listes Simplement Chainees

Alogorithmique 2
ALGORITHMIQUE ET STRUCTURES DE
DONNEES
LES LISTES SIMPLEMENT CHAINEES
Exercice 1 :
Soit Li une liste d’étudiants pour une classe donnée. Un étudiant est représenté par son :
Numéro, Nom, Prénom et sa Moyenne.
1. Proposer une structure de donnée chainée qui permet de stocker la liste des étudiants.
(La structure + la déclaration d’une liste vide).
2. Ecrire une fonction qui permet de calculer la moyenne générale d’une classe Li.
3. Ecrire un programme qui permet d’éclater une liste Li en 2 sous listes L1 et L2, de
telle sorte la première liste L1 contient seulement les étudiants Admis, et la deuxième
L2 contient les étudiants Ajournés
Correction :
Q1 : proposition d’une structure chainée
etudiant = Enregistrement
N entier
Nom : chaine[ 20]
Prenom : Chaine [20]
moyenne : réel
suivant : *etudiant
FinEnreg
Type
ListeEtu =*etudiant
Q2)calculer la moyenne générale d’une classe
Fonction CalculeMoyenneGenerale (tete : ListeEtu) : réel
Var moyenneGenerale : réel

Somme : réel
nbrEtudiant : entier
position : * etudiant
Début
position <-- tete
Somme<--0
nbrEtudiant<--0
TantQue (position <> NULL) faire

Somme<-- somme+ *position.moyenne
BEN DAKHLIA S. Page 1

Alogorithmique 2
nbrEtudiant <-- nbrEtudiant+1

position <-- *position.suivant
FinTQ
Si (nbrEtudiant >0) alors

moyenneGenerale= somme / nbrEtudiant
FinSi
CalculeMoyenneGenerale <--moyenneGenerale
Fin
Q3) éclatement de la liste
Procedure Eclate(L :listeEtu, VAR L1 :listeEtu, VAR L2 :listeEtu)
Var P,P1,P2:ListeEtu
Debut
L1←Null
L2←Null
PL
Tantque P<>Null Faire

Si *P.moyenne>=10 Alors
Si L1=Null Alors
L1←P
P1P
Sinon
*P1.Suiv←P
P1*P1.suiv
FinSi
Sinon
Si L2=Null Alors
L2←P
P2P
Sinon
*P2.Suiv←P
P2*P2.suiv
Fsi
FinSi
P*P.suivant
FinPour
Fin

Alogorithmique 2
Exercice 2 :
Type
P = *Elem
Enregistrement Elem
Info : Caractere ;
Suiv: P
Fin
Ecrire des sous algorithmes permettant de:
1. Créer Une liste de N caractères (N est un nombre entier transmis en paramètre- quel
changement doit on effectué si le nombre d’éléments n’est pas connu)
2. Insérer une valeur V à la Nième position de cette liste si elle existe.
3. Supprimer le Nième élément de cette liste s’il existe.
Correction :
Procedure création (Var L : P ; N : entier)
Variable
X: P
Co : Entier ;
Debut
L <-- Null
Pour Co de 1 à N Faire
Allouer (x)
Lire (*x. Info)
*x.Suiv <-- L
L <-- x
FinPour
Fin
Si l’on fait une insertion au début pour le premier et les autres en fin cela donnera :
Procedure création (Var L : P ; N : entier) ;
Var
X, Y: P
Co : Entier
Debut
Allouer (x)
Lire (*x. Info)
*x.Suiv <--Null
L <-- x
Pour co de 1 a N – 1 Faire
Allouer (x)

Alogorithmique 2
Lire (*x. Info)

*x.Suiv <-- Null
*Y.Suiv <-- X
Y <--*Y.Suiv /*c’est la même chose que d’écrire Y <-- X */
FinPour
Fin
Dans le cas où le nombre d’éléments n’est pas connu on doit faire appel à une boucle :
Procedure création (Var L : P)
Variable
Rep : Caracter
Debut
L <--Null
Repeter
AjoutD (L) ;
Ecrire ('Avez un autre élément à insérer (O/N) ?')
Lire (Rep)
Jusqu’à Rep = 'N'
Fin
2/ Insérer une valeur V à la Nième position de cette liste si elle existe.

Procedure Inserer (Var L : P ; V: caractere, N: Entier)
Variable
X, Y: P ;
Co : Entier
Debut
Si N <= 0 Alors
Ecrire ('Erreur position nulle ou négative')
Sinon
Si N = 1 Alors
Allouer (x)
*x. Info<-- V
*x.Suiv <-- L
L <--x
Sinon
Y <-- L
Co <-- 1
Tantque (Co < N-1) Et (Y <>Null) Faire
Co <--Co + 1
Y <-- *Y.Suiv
FinTantque
Si Y = Null Alors
Ecrire ('Erreur position inexistante')
Sinon
Allouer (x)
*x. Info<-- V
*x.Suiv <-- *Y.Suiv
*Y.Suiv <-- x
FinSi
FinSi

Alogorithmique 2
FinSi
Fin
3/ Supprimer le Nième élément de cette liste s’il existe.

On suppose que l’on veut récupérer la valeur de l’élément que l’on veut supprimer
physiquement dans V
Procedure Supprime (Var L : P, V: caractere ; N : Entier)
Variable
X, Y : P
Co : Entier
Debut
Si (L = Null) ou (N <= 0) Alors
Ecrire ('Erreur pas d"elément à supprimer')
Sinon
Si N = 1 Alors
V <-- *L. Info
X <-- L
L <--* L.Suiv
Liberer (X)
Sinon
Y <-- L
X <--L
Co <-- 1
Tantque (Co < N) Et (Y <>Null) Faire
Co <-- Co + 1
X <-- Y
Y <-- *Y.Suiv
FinTantque
Si Y = Null Alors
Ecrire (' Erreur pas d"elément à supprimer'')
Sinon
V <-- *Y. Info
*X.Suiv <-- *Y.Suiv
Liberer (Y)
FinSi
FinSi
FinSi
Fin
Exercice 3 :
Type
P = *Elem
Elem= Enregistrement
Info : entier
Suiv: P

Alogorithmique 2
Procedure S0 (Var Tete : P)

Variable
L1, W: P
Debut
L1 <-- Tete
Tantque L1 <>Null Faire
Si *L1.Info =0 Alors
W  *L1.Suiv
Si L1 = Tete Alors
SupprimeD (Tete)
Sinon
Si *L1.Suiv = Null Alors
SupprimeF (Tete)
Sinon
SupprimeM (Tete, L1)
FinSi
L1 W
FinSi
Sinon
L1 *L1.Suiv
FinSi
L1  Tete
Tantque L1 <>Null Faire
Ecrire (*L1.Info)
L1  *L1.Suiv
FinTantque
Fin
Exercice 4 :
Ecrire un sous algorithme qui permet de convertir un entier naturel en sa représentation
binaire en gardant les éléments binaires dans une liste (l’affichage de la liste doit donner
directement la bonne représentation exp 1000 pour 8)
Type
P = *Elem
Enregistrement Elem
Info : ntier
Suiv: P
Procedure Conver (X : entier ; Var Liste : P)

Variable
Pt : P
Debut
Liste Null
Tantque X <> 0 Faire
Allouer (Pt)
*Pt.Info X Mod 2

Alogorithmique 2
*Pt. Suiv  Liste

Liste Pt
X X Div 2
FinTantque
Fin

Algorithmique Et Structures de Donnees Les Listes Simplement Chainees

Transféré par

Droits d'auteur :

Formats disponibles

Algorithmique Et Structures de Donnees Les Listes Simplement Chainees

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Algorithmique Et Structures de Donnees Les Listes Simplement Chainees

Transféré par

Droits d'auteur :

Formats disponibles

Alogorithmique 2

Q2)calculer la moyenne générale d’une classe

Fonction CalculeMoyenneGenerale (tete : ListeEtu) : réel

Var moyenneGenerale : réel

TantQue (position <> NULL) faire

BEN DAKHLIA S. Page 1

nbrEtudiant <-- nbrEtudiant+1

Si (nbrEtudiant >0) alors

Q3) éclatement de la liste

Procedure Eclate(L :listeEtu, VAR L1 :listeEtu, VAR L2 :listeEtu)

Tantque P<>Null Faire

BEN DAKHLIA S. Page 2

2. Insérer une valeur V à la Nième position de cette liste si elle existe.

3. Supprimer le Nième élément de cette liste s’il existe.

BEN DAKHLIA S. Page 3

Lire (*x. Info)

2/ Insérer une valeur V à la Nième position de cette liste si elle existe.

BEN DAKHLIA S. Page 4

3/ Supprimer le Nième élément de cette liste s’il existe.

BEN DAKHLIA S. Page 5

Procedure S0 (Var Tete : P)

Procedure Conver (X : entier ; Var Liste : P)

BEN DAKHLIA S. Page 6

*Pt. Suiv  Liste

BEN DAKHLIA S. Page 7

Vous aimerez peut-être aussi