Cours 3 - Listes

name: inverse
layout: true
class: center, middle, inverse
---

# INFORMATIQUE 3 - CM 3
## Inès de Courchelle
## 2024-2025

![image](../img/CY-tech.png)

---
layout: false

# Rappel : Les piles
## LIFO (**L**ast **I**n **F**irst **O**ut)
Les derniers éléments ajoutés à la Pile sont recupérés en premier.
.pull-left[
- empiler
- dépiler
- vider
- compter
- inverser
- afficher

]
.pull-right[
 
<center>
 <img src="img/piles_livres.png" width=200/>
</center>
]

---
# Rappel : Les files
## FIFO (**F**irst **I**n **F**irst **O**ut)
Les premiers éléments ajoutés à la File sont recupérés en premier.

.pull-left[
- enfiler
- defiler
- vider
- inverser
- afficher
- compter
]

.pull-right[
<center>
 <img src="img/file.jpg" width=300/>
</center>

]

---
# Let's go
## Objectifs
- Étudier des structures de données liées
- Connaître les particularités des chaînes
- Appréhender des notions de gestion de données

---
# Pour représenter un circuit
<center>
<iframe width="560" height="315" src="https://www.youtube.com/embed/YdQcf9hwA8E" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
</center>

---
# Pour représenter un cycle
<center>
 <img src="img/Cycle_eau.png" width=500/>
</center>

---
# Listes chaînées simple
## Définition
<center>
 <img src="img/maillon.png" width=300/>
</center>

.pull-left[
Un maillon contient :
 - Une valeur
 - Un pointeur vers le maillon suivant

]

.pull-right[
 
<center>
 <img src="img/maillon.svg" width=200/>
</center>
]

---
# Listes Chaînées simple
## Réprésentation
<center>
 <img src="img/listeChainee1.svg" width=500/>
</center>

---
# Listes doublements chaînées
## Définition
.pull-left[
Un maillon contient :
 - Une valeur
 - Un pointeur vers le maillon suivant
 - Un pointeur vers le maillon précédent

]

.pull-right[
 
<center>
 <img src="img/maillon2.svg" width=200/>
</center>
]
---
# Listes doublements chaînées
## Réprésentation
<center>
 <img src="img/listeChaineeDouble1.svg" width=800/>
</center>

---
# Listes circulaires
- Le dernier maillon de la liste ne pointe plus sur NULL
- Toutes les listes peuvent être circulaire

#### Liste circulaire simple
<center>
 <img src="img/simpleListChaineeCirculaire.svg" width=300/>
</center>

#### Liste circulaire double
<center>
 <img src="img/simpleListChaineeDoubleCirculaire.svg" width=400/>
</center>

---
# Listes circulaires
## Liste circulaire simple

---
# Listes circulaires
## Liste circulaire double
<center>
 <img src="img/listeChaineeDoubleCirculaire.svg" width=800/>
</center>

---
# Définition de notre structure
## Dans Liste.h on va définir notre structure
.pull-left[
#### En algo
```c
STRUCTURE maillon
 donnee : entier
 suivant : maillon
FIN STRUCTURE
```
 
 
]
.pull-right[
#### En C
```c
typedef struct maillon{
 int donnee;
 struct maillon* suivant;
}maillon;

typedef maillon* teteListe;
```
]

## Dans le main, on va initialiser notre structure
```c
int main(){
    teteListe l=NULL ; /* elle ne pointe sur rien à l’état initial */
    return 0;
}
```

---
# Les opérations de bases
## Opérations primaires
- Afficher une liste
- Créer un maillon

## Insérer un maillon
  - au début de la liste
  - à la fin de la liste
  - où on veut

## Supprimer un maillon
  - au début de la liste
  - à la fin de la liste
  - où on veut

---
# Avant de commencer
## FONCTION N°1
- La fonction permettant de créer un maillon
- on va s'en servir partout

.pull-left[
#### En ALGO
```c
FONCTION creerMaillon(donnee : entier) : maillon
VARIABLES
 m : maillon
DEBUT
 m.donnee <- valeur
 m.suivant <- NULL
 retourner m
FIN
```
]
.pull-right[
#### EN C
```c
maillon* creerMaillon(int donnee){
 maillon* m;
 m = malloc(sizeof(maillon)*1);
 m->donnee=donnee
 m->suivant=NULL;
 return m;
}
```
]
---
# Avant de commencer
## Procédure N°1 : Afficher
```c
PROCEDURE afficher(maListe : maillon)
DEBUT
 SI (estListeVide(maListe)) ALORS
 ECRIRE("---")
 SINON
 ECRIRE("maillon" + maListe.donnee)
 afficher(maListe.suivant)
 FIN SI
FIN
```

.underR[Attention] : On utilise obligatoirement la récursivité !

---
# Avant de commencer
## Procédure N°1 : Afficher
<img src="img/afficherRec1.svg" width=750/>

---
# Avant de commencer
## Procédure N°1 : Afficher
<img src="img/afficherRec2.svg" width=750/>

---
# Avant de commencer
## Procédure N°1 : Afficher
<img src="img/afficherRec3.svg" width=750/>

---
# Avant de commencer
## Procédure N°1 : Afficher
<img src="img/afficherRec4.svg" width=750/>

---
# Avant de commencer
## Procédure N°1 : Afficher
<img src="img/afficherRec5.svg" width=750/>

---
# Avant de commencer
## Procédure N°1 : Afficher
<img src="img/afficherRec6.svg" width=750/>

---
# Avant de commencer
## Procédure N°1 : Afficher
<img src="img/afficherRec7.svg" width=750/>

---
# Avant de commencer
## Procédure N°1 : Afficher
<img src="img/afficherRec8.svg" width=750/>

---
# Les opérations de bases
## Opérations primaires
- .underV[Afficher une liste]
- .underV[Créer un maillon]

## Insérer un maillon
  - au début de la liste
  - à la fin de la liste
  - où on veut

## Supprimer un maillon
  - au début de la liste
  - à la fin de la liste
  - où on veut

---
# Insertion début

---
# Insertion début

---
# Insertion début

---
# Insertion début

---
# Insertion début
## L'algo - Procédure
```c
PROCEDURE ajouterTete(maListe : maillon
                 donnee : entier)
VARIABLES :
    m : maillon

DEBU
 m <- creerMaillon(donnee)
 m.suivant<-maListe
 maListe <- m
FIN
```
---
# Insertion début
## L'algo - Procédure
- Ce n'est pas terrible, terrible ...
- AjouterTete va nous permettre de faire de la récursivité
- Il faut donc utiliser l'algo en mode fonction !

---
# Insertion début
## L'algo - Fonction
```c
FONCTION ajouterTete(maListe : tête de liste
 donnee : entier) : tête de liste
VARIABLES
 m : maillon
DEBUT
 m <- creerMaillon(donnee)
 m. suivant <- maListe
 retourner m;
FIN
```

---
# Insertion début
## Rappel

.underR[attention] on utilise bien la compilation séparée !

.underV[Comment on compile plusieurs fichiers ?]
.arrow[] cf cours de l'année dernière

## VAR
<center>
<video src="videos/demo1.mp4" width="400" height="300" controls poster="vignette.jpg">
Cette vidéo ne peut être affichée sur votre navigateur Internet. Une version est disponible en téléchargement sous <a href="URL">adresse du lien </a> .
</video>
</center>

---
# Insertion fin

---
# Insertion fin

---
# Insertion fin

---
# Insertion fin

---
# Insertion fin

---
# Insertion fin

---
# Insertion fin
## Algo
```c
PROCEDURE ajouterFin(maListe : maillon
 donnee : entier)
VARIABLES :
 m : maillon
 temp: maillon
DEBUT
 m <- creerMaillon(donnee)
 temp <- maListe
 SI (temp!=NULL) ALORS
 TANT QUE (temp.suivant!=NULL) FAIRE
 temp <- temp.suivant
 FIN TANT QUE
 temp.suivant<-m
 SINON
 maListe <- m
 FIN SI
FIN
```
---
# Insertion fin
## Algo
<img src="https://c.tenor.com/ndBYo3UUExgAAAAC/netflix-maskey.gif" width=500>

---
# Insertion fin
## Récursivité
#### 1. La condition d'arrêt
Je suis à la fin
#### 2. La résolution du problème
J'ajoute le maillon
#### 3. L'appel récursif
Je passe au maillon suivant

---
# Insertion fin
## Algo
```c
PROCEDURE ajouterFin(maListe : tête de liste, donnee : entier)
DEBUT
 SI (maListe.suivant=NULL) ALORS
 m <- creerMaillon(donnee)
 maListe.suivant <- m
 SINON
 maListe <- maListe.suivant
 ajouterFin(maListe,donnee)
 FIN SI
FIN
```

---
# VAR
## VIDEO
#### Problème je perds le début de la liste
<center>
<video src="videos/demo2a.mp4" width="400" height="300" controls poster="vignette.jpg">
Cette vidéo ne peut être affichée sur votre navigateur Internet. Une version est disponible en téléchargement sous <a href="URL">adresse du lien </a> .
</video>
</center>

---
# Insertion fin
## Solution N°1
- Il faut utiliser un pointeur de liste temp à l'appel de la fonction
- Mais c'est moyen !

<center>
<video src="videos/demo2b.mp4" width="400" height="300" controls poster="vignette.jpg">
Cette vidéo ne peut être affichée sur votre navigateur Internet. Une version est disponible en téléchargement sous <a href="URL">adresse du lien </a> .
</video>
</center>

---
# Insertion fin
## Solution N°2
- Utiliser la fonction ajouterDebut
- La fonction et non la procédure

## Fonction ajouterTete
```c
FONCTION ajouterTete(maListe : maillon
 donnee : entier) : maillon
DEBUT
 m <- creerMaillon(donnee)
 m.suivant <- maListe
 retourner m;
FIN
```

---
# Insertion fin
## Algo
```c
FONCTION ajouterFin(maListe : maillon
 donnee : entier) : maillon
DEBUT
 SI maListe = NULL ALORS
 retourner ajouterTete(maListe,donnee)
 SINON
 maListe.suivant <- ajouterFin(maListe.suivant,donnee)
 retourner maListe
 FIN
FIN
```
---
# Insertion fin
## Illustration
<img src="img/ajoutFin1.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin2.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin3.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin4.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin5.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin6.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin7.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin8.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin9.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin10.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin11.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin12.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin13.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin14.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin15.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin16.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin17.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin18.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin19.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin20.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin21.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin22.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin23.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin24.png" width=800>

---
# Insertion fin
## Illustration
<img src="https://c.tenor.com/jfHc6wCdVe4AAAAd/cristiano-ronaldo-goal.gif" width=400>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin25.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin26.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin27.png" width=800>

---
# Insertion fin
## Illustration
<img src="img/ajoutFin28.png" width=800>

---
# Video
## VAR
<center>
<video src="videos/demo3.mp4" width="400" height="300" controls poster="vignette.jpg">
Cette vidéo ne peut être affichée sur votre navigateur Internet. Une version est disponible en téléchargement sous <a href="URL">adresse du lien </a> .
</video>
</center>

---
# Insertion Position

---
# Insertion Position

---
# Insertion Position

---
# Insertion Position

---
# Insertion Position

---
# Insertion Position
## Algo
```c
PROCEDURE ajouterPos(maListe : maillon
 valeur : entier, pos: entier)
VARIABLES :
 m,mTemp : maillon
 temp: maillon
 i : entier
DEBUT
 m <- creerMaillon(m)
 temp <- maListe
 TANT QUE (temp.suivant!=NULL && i!=(pos-1)) FAIRE
 temp <- temp.suivant
 i <-i+1
 FIN TANT QUE
 mTemp <- temp.suivant
 m.suivant <- mTemp
 temp.suivant<-m
FIN
```

---
# Insertion Position
## c'est pas bon
<img src="https://c.tenor.com/ndBYo3UUExgAAAAC/netflix-maskey.gif" width=500>

---
# Insertion Position
## Récursivité
#### 1. La condition d'arrêt
Je suis à la bonne position OU je suis à la fin de ma liste
#### 2. La résolution du problème
J'ajoute le maillon
#### 3. L'appel récursif
Je passe au maillon suivant

---
# Insertion Position
## Récursivité
```c
FONCTION ajouterPos(maListe : maillon
                 donnee : entier, pos: entier) : maillon
DEBUT
    SI maListe=NULL OU pos=1 ALORS
        retourner ajouterTete(maListe,donnee)
    SINON
        maListe.suivant = ajouterPos(maListe.suivant,donnee,pos-1)
        retourner maListe
    FIN SI
FIN
```
---
# Insertion Position
## Récursivité