Faculté des Sciences Dhar El Mahraz Fès 2024-2025

Département de Mathématique
S4-MIP-MATH

TD 1 : Module Algorithmique et structures des données

TP 1
Création et Affichage d'une liste chainée

TP 2
Ajout dans une liste chainée : à en tète, a la fin, et au milieu

TP 3
Suppression d'un élément d'une liste chainée : à l'en tète, de la fin, et du milieu

TP 4
Concaténer deux listes chainées
Inverser l'ordre des éléments d'une liste chainée

TP 5
Trier les éléments d'une liste
Trouver le minimum d'une liste
Calculer la somme des éléments d'une liste
Calculer la moyenne des éléments d'une liste

TP 6
créer une liste circulaire contient un élément
Ajouter à l'étête
Ajouter à la fin
Ajouter au milieu
Afficher la liste

TP 7
Supprimer un élément a l'entête d une liste circulaire
Supprimer un élément à la fin d une liste circulaire
Supprimer un élément au milieu d' une liste circulaire
Corrigé TP 1
#include<stdio.h>
#include<malloc.h>
struct liste {
int donnees;
struct liste *suivant;
};
typedef liste *type_liste;
type_liste tete,ptr, parcours;
type_liste creer(type_liste tete,int n){ // n le nombre des elements de la
liste
int i,x;
tete=NULL;
for(i=0;i<n;i++){
ptr=(type_liste)malloc(sizeof(type_liste));
printf ("entrer l elment % :",i+1);
scanf("%d",&x);
ptr->donnees=x;
ptr->suivant=tete;
tete=ptr;
}
return tete;
}
void afficher(type_liste tete){
printf("tete-->");
parcours=tete;
while(parcours!=NULL){
printf("[%d]--->",parcours->donnees);
parcours=parcours->suivant;
}
printf("NULL\n");
}
main(){
tete=creer(tete,3);
afficher(tete);

}
Corrigé TP 2
#include<stdio.h>
#include<malloc.h>
struct liste {
int donnees;
struct liste *suivant;
};
typedef struct liste *type_liste;
type_liste tete,ptr, parcours;
type_liste creer(type_liste tete,int n){ // n le nombre des elements de la
liste
int i,x;
tete=NULL;
for(i=0;i<n;i++){
ptr=(type_liste)malloc(sizeof(type_liste));
printf ("entrer l elment %d :",i+1);
scanf("%d",&x);
ptr->donnees=x;
ptr->suivant=tete;
tete=ptr;
}
return tete;
}
void afficher(type_liste tete){

2
 printf("tete-->");
parcours=tete;
while(parcours!=NULL){
printf("[%d]--->",parcours->donnees);
parcours=parcours->suivant;
}
printf("NULL\n");
}
type_liste ajout_tete(type_liste tete){
int x;
printf("saisir l element qu on veut ajouter a en tete de la liste:
");
scanf("%d",&x);
ptr=(type_liste)malloc(sizeof(type_liste));
ptr->donnees=x;
ptr->suivant=tete;
tete=ptr;
return tete;}
type_liste ajout_fin(type_liste tete){
int y;
ptr=(type_liste)malloc(sizeof(type_liste));
printf("saisir l element qu on veut ajouter a la fin de la liste
");
scanf("%d",&y);
ptr->donnees=y;
ptr->suivant=NULL;
parcours=tete;
while(parcours->suivant!=NULL){ parcours =parcours->suivant;
}
parcours->suivant=ptr;
return tete;
}
type_liste ajout_milieu(type_liste tete){
int z,k; // on veut ajouter l elemnt z apres l element K
printf("saisir element qu on veut ajouter au milieu de la liste
:");
scanf("%d",&z);
printf("saisir element qu on veut ajouter apres sa postion :");
scanf("%d",&k);
parcours=tete;
while(parcours->donnees!=k &&parcours->suivant!=NULL)
parcours=parcours->suivant;

ptr=(type_liste)malloc(sizeof(type_liste));
ptr->donnees=z;
ptr->suivant=parcours->suivant;
parcours->suivant=ptr;
return tete;
}
main(){
tete=creer(tete,5);
afficher(tete);
tete=ajout_milieu(tete);
afficher(tete);
tete=ajout_milieu(tete);
afficher(tete);

Corrigé TP 3
#include<stdio.h>

3
#include<malloc.h>
struct liste {
int donnees;
struct liste *suivant;
};
typedef struct liste *type_liste;
type_liste tete,ptr,ptr1, parcours;
type_liste creer(type_liste tete,int n){ // n le nombre des elements de la
liste
int i,x;
tete=NULL;
for(i=0;i<n;i++){
ptr=(type_liste)malloc(sizeof(type_liste));
printf ("entrer l elment %d :",i+1);
scanf("%d",&x);
ptr->donnees=x;
ptr->suivant=tete;
tete=ptr;
}
return tete;
}
void afficher(type_liste tete){
printf("tete-->");
parcours=tete;
while(parcours!=NULL){
printf("[%d]--->",parcours->donnees);
parcours=parcours->suivant;
}
printf("NULL\n");
}
type_liste sup_tete(type_liste tete){
ptr=tete;
tete=ptr->suivant;
free(ptr);
return tete;
}
type_liste sup_fin(type_liste tete){
ptr=tete;
while(ptr->suivant!=NULL){
ptr1=ptr;
ptr=ptr->suivant;
}
ptr1->suivant=NULL;
free(ptr);
return tete;
}
type_liste sup_milieu(type_liste tete){
int x;
printf("saisir element qu on veut supprimer :");
scanf("%d",&x);
ptr=tete;
while(ptr->donnees!=x&&ptr->suivant!=NULL){
ptr1=ptr;
ptr=ptr->suivant;
}
if(ptr->suivant==NULL)
printf("l element %d n existe pas dans la liste \n", x);
else{
ptr1->suivant=ptr->suivant;
free(ptr);
}

4
 return tete;
}
main(){
tete=creer(tete,5);
afficher(tete);
tete=sup_milieu(tete);
afficher(tete);
}

Corrigé TP 4
#include<stdio.h>
#include<malloc.h>
struct liste {
int donnees;
struct liste *suivant;
};
typedef struct liste *type_liste;
type_liste tete,ptr,ptr1, parcours,tete1;
type_liste creer(type_liste tete,int n){ // n le nombre des elements de la
liste
int i,x;
tete=NULL;
for(i=0;i<n;i++){
ptr=(type_liste)malloc(sizeof(type_liste));
printf ("entrer l elment %d :",i+1);
scanf("%d",&x);
ptr->donnees=x;
ptr->suivant=tete;
tete=ptr;
}
return tete;
}
type_liste concatener(type_liste tete, type_liste tete1){
ptr=tete;
while(ptr->suivant!=NULL){
ptr=ptr->suivant; }
ptr->suivant=tete1;
return tete;
}
type_liste inverser(type_liste tete){
parcours=tete;
tete1=NULL;
while(parcours!=NULL){
ptr=(type_liste)malloc(sizeof(type_liste));
ptr->donnees=parcours->donnees;
ptr->suivant=tete1;
tete1=ptr;
parcours=parcours->suivant;
}
return tete1;
}
void afficher(type_liste tete){
printf("tete-->");
parcours=tete;
while(parcours!=NULL){
printf("[%d]--->",parcours->donnees);
parcours=parcours->suivant;
}
printf("NULL\n");
}

5
main(){
tete=creer(tete,5);
afficher(tete);
// tete1=creer(tete1,4);
// afficher(tete1);
// tete=concatener(tete,tete1);
// afficher(tete);
tete1=inverser(tete);
afficher(tete1);

Corrigé TP 5
#include<stdio.h>
#include<malloc.h>
struct liste {
int donnees;
struct liste *suivant;
};
typedef struct liste *type_liste;
type_liste tete,ptr,ptr1, parcours,tete1;
type_liste creer(type_liste tete,int n){ // n le nombre des elements de la
liste
int i,x;
tete=NULL;
for(i=0;i<n;i++){
ptr=(type_liste)malloc(sizeof(type_liste));
printf ("entrer l elment %d :",i+1);
scanf("%d",&x);
ptr->donnees=x;
ptr->suivant=tete;
tete=ptr;
}
return tete;
}
void afficher(type_liste tete){
printf("tete-->");
parcours=tete;
while(parcours!=NULL){
printf("[%d]--->",parcours->donnees);
parcours=parcours->suivant;
}
printf("NULL\n");
}
type_liste trier(type_liste tete){
int temps;
ptr=tete;
while(ptr->suivant!=NULL){
ptr1=ptr->suivant;
while(ptr1!=NULL){
if(ptr1->donnees<ptr->donnees){
temps=ptr->donnees;
ptr->donnees=ptr1->donnees;
ptr1->donnees=temps;
}
ptr1=ptr1->suivant;
}
ptr=ptr->suivant;
}
return tete;

6
}
int min(type_liste tete){
int min=tete->donnees;
ptr=tete->suivant;
while(ptr!=NULL){
if(ptr->donnees<min){
min=ptr->donnees;
}
ptr=ptr->suivant;
}
return min;
}
void somme_moyenne(type_liste tete){
int N=0,som=0;
float moy=0;
ptr=tete;
while(ptr!=NULL){
som=som+ptr->donnees;
N=N+1;
ptr=ptr->suivant;
}
moy=(float)som/float(N);
printf("\n la somme des %d est : %d \n",N,som);
printf("la moyenne des elements est : %f\n",moy);
}
main(){
tete=creer(tete,7);
afficher(tete);
printf("\n le minimun de la liste est : %d ", min(tete));
somme_moyenne(tete);
tete=trier(tete);
afficher(tete);
}

Corrigé TP 6
#include<stdio.h>
#include<malloc.h>
struct liste{
int donnees;
struct liste *suivant;
};
typedef struct liste *t_liste;
t_liste tete, ptr, ptr1, parcours;
t_liste creer_circulaire(t_liste tete,int x){
tete=(t_liste)malloc(sizeof(t_liste));
tete->donnees=x;
tete->suivant=tete;
return tete;
}
t_liste ajouter_tete (t_liste tete,int x){
parcours=tete->suivant;
while(parcours->suivant!=tete)
parcours=parcours->suivant;
ptr=(t_liste)malloc(sizeof(t_liste));
ptr->donnees=x;
ptr->suivant=tete;
tete=ptr;
parcours->suivant=tete;
return tete;
}
t_liste ajouter_fin(t_liste tete, int x){

7
 parcours =tete->suivant;
while(parcours->suivant!=tete)
parcours=parcours->suivant;
ptr=(t_liste)malloc(sizeof(t_liste));
ptr->donnees=x;
parcours->suivant=ptr;
ptr->suivant=tete;
return tete;
}
t_liste ajouter_milieu(t_liste tete, int x){
int y;
printf("entrer element qu on veut ajouter apres sa position:");
scanf("%d",&y);
parcours=tete->suivant;
while(parcours->donnees!=y&&parcours->suivant!=tete)
parcours=parcours->suivant;
ptr=(t_liste)malloc(sizeof(t_liste));
ptr->donnees=x;
ptr->suivant=parcours->suivant;
parcours->suivant=ptr;
return tete;
}

void afficher(t_liste tete){

printf("tete-->");
ptr=tete;
while(ptr->suivant!=tete){
printf("[%d]-->",ptr->donnees);
ptr=ptr->suivant;
}
printf("[%d]-->tete \n",ptr->donnees);
}

main(){
tete=creer_circulaire(tete,34);
afficher(tete);
for(int i=10;i<20;i++)
tete=ajouter_tete(tete,88+i);
afficher(tete);
}

Corrigé TP 7
#include<stdio.h>
#include<malloc.h>
struct liste{
int donnees;
struct liste *suivant;
};
typedef struct liste *t_liste;
t_liste tete, ptr, ptr1, parcours,parcours1;
t_liste creer_circulaire(t_liste tete,int x){
tete=(t_liste)malloc(sizeof(t_liste));
tete->donnees=x;
tete->suivant=tete;
return tete;
}
t_liste ajouter_tete (t_liste tete,int x){
parcours=tete->suivant;
while(parcours->suivant!=tete)
parcours=parcours->suivant;
ptr=(t_liste)malloc(sizeof(t_liste));

8
 ptr->donnees=x;
ptr->suivant=tete;
tete=ptr;
parcours->suivant=tete;
return tete;
}
void afficher(t_liste tete){
printf("tete-->");
ptr=tete;
while(ptr->suivant!=tete){
printf("[%d]-->",ptr->donnees);
ptr=ptr->suivant;
}
printf("[%d]-->tete \n",ptr->donnees);
}
t_liste supprimer_tete(t_liste tete){
parcours=tete->suivant;
while(parcours->suivant!=tete)
parcours=parcours->suivant;
ptr=tete;
tete=ptr->suivant;
parcours->suivant=tete;
free(ptr);
return tete;
}
t_liste supprimer_fin(t_liste tete){
parcours=tete->suivant;
while(parcours->suivant!=tete){
parcours1=parcours;
parcours=parcours->suivant;}
parcours1->suivant=parcours->suivant;
parcours1->suivant=tete;
free(parcours);
return tete;
}
t_liste supprimer_milieu(t_liste tete){
int x;
printf("saisir element qu on veut supprimer :");
scanf("%d",&x);
parcours=tete;
while(parcours->donnees!=x &&parcours->suivant!=tete){
parcours1=parcours;
parcours=parcours->suivant;}
if(parcours->suivant==tete)
printf("element %d qu on veut supprimer n existe pas dans la liste
:\n ",x);
else{
parcours1->suivant=parcours->suivant;
free(parcours);}
return tete;
}
main(){
tete=creer_circulaire(tete,34);
afficher(tete);
for(int i=10;i<20;i++)
tete=ajouter_tete(tete,88+i);
afficher(tete);
tete=supprimer_tete(tete);
afficher(tete);
tete=supprimer_fin(tete);
afficher(tete);

9
 tete=supprimer_milieu(tete);
afficher(tete);
}

10