Université Aboubekr BELKAID

‫ﻛﻠﯿﺔ ﺍﻟﻌﻠﻭﻡ – ﺘﯿﺠﺎﻨﻲ ﻫﺩﺍﻡ‬

Faculté des Sciences
‫ﻗﺴﻡ ﺍﻹﻋﻼﻡ ﺍﻵﻟﻲ‬
Département d’informatique
Module : Algo Année universitaire 2023-2024
Classe : L2- Informatique
Réalisé par : Mr MERZOUG Mohamed
Mr ETCHIALI Abdelhak

TP N° 04

LES LISTES SIMPLEMENT CHAINEES

Exercice 1: DECLARATION ET MANIPULATION D’UNE LISTE SIMPLEMENT CHAINEE

1- Déclaration:
struct cellule{
int val;
struct cellule *suivant;
};
typedef struct cellule cellule;
typedef cellule* Liste;

2- Fonction d’initialisation d’une liste chainée:

cellule* initialiser_Liste(cellule* liste){
liste = NULL;
return liste ;}

3- Déclaration et intialisation de la liste chainée dans le programme principal (main) :

int main( ){
/* Déclarons 3 listes chaînées de façons différentes mais équivalentes */
struct cellule* ma_liste_1 = initialiser_Liste(ma_liste_1);
cellule* ma_liste_2 = initialiser_Liste(ma_liste_2);
Liste ma_liste_3 = initialiser_Liste(ma_liste_3);
return 0;
}

4- Fonction d’ajouter au début de liste:

cellule* Ajouter_Debut_Liste(cellule* liste, int valeur){

/* On crée une nouvelle cellule */

cellule* newcellule = malloc(sizeof(cellule));

/* On assigne la valeur à la nouvelle cellule */

newcellule ->val = valeur;

/*On assigne l'adresse de la liste chainée à la nouvelle cellule */

newcellule ->suivant = liste;

/*On retourne la nouvelle liste, le pointeur sur la premiere cellule */

return newcellule;
}

1
5- Fonction d’ajouter à la fin de la liste:
cellule* Ajouter_Fin_Liste(cellule* liste, int valeur){

/*On crée une nouvelle cellule */

cellule* newcellule = malloc(sizeof(cellule));

/* On assigne la valeur à la nouvelle cellule */

newcellule ->val = valeur;

/* On ajoute en fin, donc aucune cellule ne va suivre */

newcellule ->suivant = NULL;

/*Si la liste est vide, il suffit de renvoyer la cellule créée */

if(liste == NULL)
return newcellule;

/*Sinon, on parcourt la liste jusqu’ à la fin et la relie à la nouvelle cellule*/

else {
cellule* temp = liste;
while(temp->suivant != NULL)
temp = temp->suivant;
temp->suivant = newcellule;
return liste;
}
}

6- Fonction supprimer à la fin de la liste:

cellule* Supprimer_Fin_Liste(cellule* liste) {

/* Si la liste est vide, on retourne NULL */

if(liste == NULL)
return NULL;

/* Si la liste contient une seule cellule */

if(liste->suivant == NULL){

/*On le libère et on retourne NULL, la liste est vide) */

free(liste);
return NULL;}

/* Si la liste contient au moins deux cellules */

cellule* tmp = liste;
cellule* ptmp = liste;
while(tmp->suivant != NULL){/* Tant qu'on n'est pas à la derniere cellule */
ptmp = tmp; /* ptmp stock l'adresse de tmp */
tmp = tmp->suivant;/*On déplace tmp mais ptmp garde l'ancienne valeur de tmp*/
}

/*A la sortie de la boucle, tmp pointe sur la derniere cellule, et ptmp sur
l'avant-derniere. On indique que l'avant-derniere devient la fin de la liste et on
supprime la derniere cellule */
ptmp->suivant = NULL;
free(tmp);
return liste;
}

2
7- Fonction supprimer au début de la liste:
cellule* Supprimer_Debut_Liste(cellule* liste){

/*Si la liste est non vide, renvoyer l'adresse de la 2ème Cellule*/

if(liste != NULL){
cellule* NouveauEntete = liste->suivant;

/* On libère la première cellule */

free(liste);

/* retourner le nouveau entête de la liste */

return NouveauEntete;
}
else
return NULL;
}

8- Fonction Afficher une Liste Chainée:

void Afficher_Liste(cellule* liste){

if (liste==NULL)
printf(" La Liste est Vide.\n");
else{
cellule* tmp = liste;
/* Tant que l'on n'est pas au bout de la liste */
while(tmp != NULL){
/* On affiche la valeur */
printf(" %d ", tmp->val);
/* On avance vers la cellule suivante */
tmp = tmp->suivant;
}
printf("\n");
}
}

QUESTIONS:

a- Ecrire un programme qui permet de tester les fonctions précédentes.

b-Dans le même programme, ajoutez les fonctions suivantes:
1- La fonction qui permet de calculer le nombre d’éléments de la liste.(version itérative et version
récursive)
2- La fonction qui permet de calculer le nombre d’occurrences d’un élément dans la liste. (version itérative
et version récursive)
3- La fonction qui permet de retourner l’élément de la position i de la liste. (version itérative et version
récursive)
4- La fonction qui permet de chercher un élément dans la liste. (version itérative et version récursive)
5- La fonction qui permet d’ajouter un élément dans la liste dans une position i donnée.
6- La fonction qui permet de supprimer l’élément de la position i dans la liste.

3
Exercice 2:
On dispose d’une liste chainée triée par ordre croissant sur le champ entier val :

L
Val …

1. Ecrire deux fonctions récursives pour l’affichage des champs val de la liste L, une dans l’ordre croissant
et une autre dans l’ordre décroissant.
2. Ecrire une fonction qui permet d’insérer un élément dans une liste chaînée d’entier triée par ordre
croissant. La liste retournée après l’insertion de l’élément doit garder le même tri.

3. Ecrire une fonction récursive et une autre itérative qui permettent de vérifier si la liste chainée est triée
par ordre croissant.
4. Ecrire une fonction qui prend en argument une liste chaînée d’entiers triée par ordre croissant et qui
inverse l’ordre de chaînage puis renvoie la liste chaînée triée dans l’ordre décroissant.

5. Ecrire une fonction qui permet de fusionner deux listes triées dans une seule liste en gardant le même tri.
6. Ecrire un programme qui permet de tester les fonctions précédentes.

Exercice 3 :

On dispose d’une liste simplement chainée d’entiers.

1. Ecrire une fonction qui permet de dupliquer les éléments pairs d’une liste chaînée d’entiers, et de garder
les éléments impairs inchangés.
Exemple
Soit la liste <4, 5, 8, 7, 12>après l’exécution de la fonction la liste sera modifiée comme suit :
<4, 4, 5, 8, 8, 7, 12, 12>.

2. Une liste chainée A est dite incluse dans une liste chainée B si les éléments de A appartiennent à B dans
le même ordre et successivement.

Ecrire une fonction qui permet de vérifier si une liste A d’entiers est incluse dans une liste B.

3. Ecrire une fonction qui permet de purger une liste (supprimer les doublons).

4. Ecrire une fonction qui permet de renvoyer l’intersection de deux listes A et B.

5. Ecrire une fonction qui permet de tester si deux listes chainées sont identiques.

6. Ecrire un programme qui permet de tester les fonctions précédentes.

4
 Exercices Supplémentaires

Exercice 1:
On veut créer une bibliothèque de plusieurs livres sous la forme d’une liste chainée.
On se donne la structure «livre» suivante: typedef struct livre {
Réaliser les fonctions suivantes : char titre[20];
char auteur[20];
char editeur[20];
char annee[10] ;
int prix;
struct livre *suivant;
} livres;
1) Ecrire une fonction qui permet de supprimer un livre : par titre, par auteur ou par éditeur.
2) Ecrire une fonction qui permet de chercher un livre : par titre, par auteur ou par éditeur.
3) Ecrire une fonction qui permet d’afficher les livres : d’une année, d’un auteur ou d’un éditeur donnés
4) Ecrire une fonction qui permet de calculer le nombre de livres : d’une année, d’un auteur ou d’un éditeur
donnés.
5) Ecrire une fonction qui permet de retourner le nombre d’exemplaires d’un livre donné.
6) Ecrire une fonction qui permet d’afficher les livres ayant prix <= P donné.
7) Ecrire une fonction qui permet de modifier le prix d’un livre.
8) Ecrire une fonction qui retourne le livre le moins cher et le livre le plus cher.
9) Ecrire une fonction qui permet de calculer la valeur de la bibliothèque (somme des prix des livres).
- Dans le programme principal, tester les fonctions précédentes.

Exercice 2:
Soit un type de matrice carrée d’entiers.
• Proposez la structure de données nécessaire et adéquate pour représenter chaque élément de la matrice.
• Ecrire une fonction qui permet de lire une matrice carrée 5*5.
• Ecrire une fonction qui permet d’afficher la diagonale d’une matrice carrée 5*5.
• Ecrire une fonction qui permet de faire la somme de deux matrices carrées 5*5.
• Ecrire une fonction qui permet d’inverser une matrice carrée 5*5.
• Tester les fonctions précédentes dans le programme principal.