Cours 2 - Les Tableaux dynamiques

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

---
# Inès de Courchelle
## Les Tableaux dynamiques

---
layout: false

# Avant de Commencer

## Objectif
Avant de coder, il faut réaliser une première phase d'analyse (TOUJOURS)

## Comment ?

Avec un papier et stylo

## Pourquoi ?
Pour bien réfléchir aux éléments que l'on manipule

---
# Aujourd'hui
## Objectifs
- Comprendre la différence entre un tableau dynamique et statique
- Utiliser les tableaux dynamiques
- Manipuler des chaînes de caractères avec des pointeurs

---
# Today
## Plan
1. Rappel des tableaux statiques 1D et 2D
2. Les tableaux dynamiques 1D
3. Les tableaux dynamiques 2D
4. Les tips

---
# Today
## Plan
1. .under[Rappel des tableaux statiques 1D et 2D]
2. Les tableaux dynamiques 1D
3. Les tableaux dynamiques 2D
4. Les tips

---
# Tableaux Statiques - 1D
## Définition

Ensemble de variables de même type, de même nom et caractérisé par un index

## Déclaration
```c
type nomTableau [taille]
```

## Accès aux éléments
```c
nomTableau[index]
```

.underR[Attention]
- Au débordement dans le tableau
- Le premier élément commence à l'index 0
- Les valeurs du tableau ne sont pas initialisées

---
# Tableaux Statiques - 1D
## Accès à un élement
<img src="img/monTabExemple.svg" width=500>

---
# Tableaux Statiques - 1D
## Attention au débordement
<img src="img/debordement.svg" width=500>

---
# Tableaux Statiques - 1D
.pull-left[
## Le code
```c
/* Déclaration */
int t_monTab[5];

/* Affectation */
t_monTab[0]=10;
t_monTab[1]=11;
t_monTab[2]=12;
t_monTab[3]=13;
t_monTab[4]=14;

/* Affichage */
for (int i=0;i<5;i++){
 printf("%d \n",t_monTab[i]);
}
```
]
.pull-right[
## Contenu de t_monTab

| index | valeur |
|-------|--------|
| 0     | 10     |
| 1     | 11     |
| 2     | 12     |
| 3     | 13     |
| 4     | 14     |

]
---
# Tableaux Statiques - 1D
## Mettre une variable globale
.pull-left[
```c
#include <stdio.h>
#include <stdlib.h>
/* ma variable globale */
#define TAILLE 5

int main(){
  int t_tab[TAILLE];
  t_monTab[0]=10;
  t_monTab[1]=11;
  t_monTab[2]=12;
  t_monTab[3]=13;
  t_monTab[4]=14;
  /*...*/
  return 0;
}
```
]
.pull-right[

.under[Pourquoi ?] Lorsque l'on manipule les tableaux

.under[Quand ?] Quand on veut !

.under[Comment ?]
- Définir la variable globale en dehors du main
- Donner le nom après le #define
- Mettre une valeur après son nom
- Utiliser les majuscules !
]

.underR[Attention]
```c
#define TAILLE 5
```

ça donne la taille MAX du tableau et non la taille effective

---
# Tableau 1D
## Mise en garde
- Si on déclare un tableau de taille N, alors on ne peut utiliser les indices : [0;N-1]
- Si on utilise un indice incorrect alors on essaye d’accéder à une partie de la mémoire qui n'est pas comprise dans le tableau.

## Exemple
On considère le tableau suivant :

---
# Tableau 1D
## Mise en garde
<img src="img/exempleTableau2camarchepo.png" width=500>

La case tab[5] n'existe pas !

---
# Tableau 1D
## Mise en garde

---
# Tableau 1D
## Mise en garde
#### Dans la mémoire
<img src="img/memoryStore.png" width=400>

---
# Tableaux Statiques 2D
## Définition

Ensemble de variables de même type, de même nom et caractérisées par 2 index - une Matrice

## Déclaration
```c
type nomTableau [taille1] [taille2]
```

## Accès aux éléments
```c
nomTableau[index1] [index2]
```

.underR[Attention]
- Au débordement dans le tableau
- Le premier élément commence à l'index 0
- Les valeurs du tableau ne sont pas initialisées

---
# Tableaux Statiques 2D
.pull-left[
```c
/* Déclaration */
int t_monTab[2][3];

/* Affectation */
t_monTab[0][0]=24;
t_monTab[0][1]=25;
t_monTab[0][2]=26;
t_monTab[1][0]=34;
t_monTab[1][1]=35;
t_monTab[1][2]=36;

/* Affichage */
for (int i=0;i<2;i++){
 printf(" | ");
 for (int j=0;j<3;j++){
 printf("%d | ",t_monTab[i][j]);
 }
 printf("\n");
}

```
]
.pull-right[
## Contenu de t_monTab

| index | (0) | (1) | (2) |
| ---   | --- | --- | --- |
| (0)   | 24  | 25  | 26  |
| (1)   | 34  | 35  | 36  |

]

---
# Tableaux Statiques 2D
## Attention au parcours
 il nous faut 2 iterateurs : i et j

```c
/* Affichage */
 for (int i=0;i<2;i++){
 printf(" | ");
 for (int j=0;j<3;j++){
 printf("%d | ",t_monTab[i][j]);
 }
 printf("\n");
 }
```
---
# Tableaux Statiques 2D
## En Algo
#### Déclaration
```c
monTab: tableau 2D d'entiers
monTab: matrice d'entiers
```
#### Affectation
```c
monTab[0][1] ← 4;
```
#### Parcours
```c
POUR i allant de 0 à nbLignes FAIRE
 POUR i allant de 0 à nbColonnes FAIRE
 ECRIRE("monTab[i][j])
 FIN POUR
FIN POUR
```

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice1.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice2.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice3.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice4.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice5.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice6.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice7.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice8.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice9.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice10.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice11.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice12.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice13.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice14.svg" width=600>

---
# Tableaux Statiques 2D
## Parcours
<img src="img/matrice/matrice15.svg" width=600>

---
# Tableaux Statiques 2D
## En C
#### Déclaration
```c
int monTab[100][50];
```
#### Affectation
```c
monTab[0][1]= 4;
```
#### Parcours
```c
for (int i=0; i<nbLignes; i++){
 for (int j=0; j<nbColonnes;j++){
 printf("| %d ",monTab[i][j]);
 }
}
```

---
# Tableaux Statiques 2D
## Mise en garde
- Si on déclare une matrice de taille NxM, alors on ne peut utiliser les indices : [0;N-1][0;M-1]
- Si on utilise un indice incorrect alors on essaye d’accéder à une partie de la mémoire qui n'est pas comprise dans le tableau.

---
# Tableaux Statiques 2D
## Mise en garde
#### Exemple
On considère le tableau 2D suivant :

---
# Tableaux Statiques 2D
## Mise en garde

---
# Tableau 2D
## Mise en garde
<img src="img/matriceHors3.svg" width=500>

---
# Today
## Plan
1. Rappel des tableaux statiques 1D et 2D
2. .under[Les tableaux dynamiques 1D]
3. Les tableaux dynamiques 2D
4. Les tips

---
# Tableaux Dynamiques
## Pourquoi ?
- Pour gérer l'espace mémoire
- Pour créer des structures de données évolutives (listes, piles ...)

## Quand ?
- On ne connait pas la taille finale de notre tableau
- On veut faire des matrices

.pull-right[
 <img src=" https://media.giphy.com/media/MC6eSuC3yypCU/giphy.gif" width=200/>
]

## Comment ?
- Avec des *pointeurs*
- Avec des *malloc*
- Avec des *free*

---
# Création d'un tableau 1D dynamique
## Plusieurs étapes
1. Déclaration
2. Allocation
3. Affectation
4. Affichage
5. Libération

## Pourquoi ?
On doit aller chercher des cases dispos pour stocker nos différentes lignes dans le tableau

---
# Création 1D dynamique
## Que se passe t-il en mémoire pour un tableau statique ?

Le système doit trouver 4 cases contiguës vides
.pull-left[
Si le tableau est utilisé, il bloque quand même la mémoire
<center>
 <img src="img/statmemory1.svg" width=300/>
</center>
]

.pull-right[
Si le tableau n'est pas utilisé, il bloque quand même la mémoire !
<center>
 <img src="img/statmemory2.svg" width=300/>
</center>
]

---
# Création 1D dynamique
## Que se passe t-il en mémoire pour un tableau dynamique  ?

.pull-left[
Si le tableau est utilisé, il bloque la mémoire
<center>
 <img src="img/statmemory1.svg" width=300/>
</center>
]

.pull-right[
Si le tableau n'est pas utilisé, il débloque la mémoire !
<center>
 <img src="img/statememory3.svg" width=300/>
</center>
]

---
# Création 1D dynamique
## Step by Step
.pull-left-small[
1. .under[Déclaration]
2. Allocation
3. Affectation
4. Affichage
5. Libération
]
.pull-right-big[
```c
int* p_tab;
p_tab=NULL;
```
<center>
 <img src="img/declaration.svg" width=300/>
</center>
]

.pull-left[
.under[remarque]
afin de gérer le pointage initial, on peut faire pointer vers *NULL* (le néant)
]
.pull-right[
<center>
 <img src="https://media.giphy.com/media/tL5HmgfZi0Qow/giphy.gif" width=200/>
</center>
]
---
# Création 1D dynamique
## Step by Step
.pull-left-small[
1. Déclaration
2. .under[Allocation]
3. Affectation
4. Affichage
5. Libération
]
.pull-right-big[
```c
int cases;
cases =5;
p_tab = malloc(cases * sizeof(int));
```
<center>
 <img src="img/allocation.svg" width=300/>
</center>
]

.under[remarque]
 
Le pointeur pointe sur le premier élément du tableau (index 0)

---
# Création 1D dynamique
## Step by Step
.pull-left-small[
1. Déclaration
2. Allocation
3. .under[Affectation]
4. Affichage
5. Libération
]
.pull-right-big[
```c
 p_tab[0]=42;
 p_tab[1]=66;
 p_tab[2]=9;
 p_tab[3]=2;
 p_tab[4]=3;
```
<center>
 <img src="img/affectation2.svg" width=300/>
</center>
]
---
# Création 1D dynamique
## Step by Step
.pull-left-small[
1. Déclaration
2. Allocation
3. Affectation
4. .under[Affichage]
5. Libération
]
.pull-right-big[
```c
for (int i=0;i<cases;i++){
 printf("i=%d p_tab[i]= %d",i,p_tab[i]);
}
```
<center>
 <img src="img/affectation2.png" width=300/>
</center>
]

---
# Création 1D dynamique
## Step by Step
.pull-left-small[
1. Déclaration
2. Allocation
3. Affectation
4. Affichage
5. .under[Libération]
]
.pull-right-big[
```c
free(p_tab);
p_tab=NULL;
```
<center>
 <img src="img/declaration.svg" width=300/>
</center>
]

---
# ATTENTION
## Il faut d'abord libérer le tableau puis faire pointer vers NULL

.pull-left[
.underR[FAUX]
```c
p_tab=NULL;
free(p_tab);
```
<center>
 <img src="img/Faux.svg" width=300/>
</center>

Ici, on a perdu l'adresse initiale du tableau, on ne pourra jamais libérer la mémoire

]

.pull-right[
.under[VRAI]

```c
free(p_tab);
p_tab=NULL;
```
<center>
 <img src="img/declaration.svg" width=330/>
</center>

Ici, on libére la mémoire, puis, on fait pointer l'adresse vers NULL

]

---
# Création 1D dynamique
## Mini Bilan
- un malloc = un free !
- deux malloc = deux free !
- ...
- n malloc = n free !

.otro-blockquote[En bref si tu as free, tu as tout compris !]

---
# Gestion des chaînes
## Rappel
- Une chaine de caractères est un tableau contenant un caractère par case.
- Une chaine de caractère en c est %s
- Un caractère en c est %c

.under[Exemple : ]
- Le mot en vrai : "tiktok"
- La chaine en C :

.pull-left-small[
| index | valeur |
|-------|--------|
| 0     | t      |
| 1     | i      |
| 2     | k      |
| 3     | t      |
| 4     | o      |
| 5     | k      |
]

.pull-right-big[
<center>
 <img src="https://media.giphy.com/media/KdIQmGHj5XfEY/giphy.gif" width=200/>
</center>

]

---
# Gestion des chaînes
## Step by Step
.pull-left-small[
1. .under[Déclaration]
2. Allocation
3. Affectation
4. Affichage
5. Libération
]
.pull-right-big[
```c
char* p_tab;
```
<center>
 <img src="img/declarationChar.png" width=300/>
</center>
]

---
# Gestion des chaînes
## Step by Step
.pull-left-small[
1. Déclaration
2. .under[Allocation]
3. Affectation
4. Affichage
5. Libération
]
.pull-right-big[
```c
char* p_tab;
int cases;
cases=5;
p_tab = malloc(cases * sizeof(char));
```

]

---
# Gestion des chaînes
## Step by Step
.pull-left-small[
1. Déclaration
2. Allocation
3. .under[Affectation]
4. Affichage
5. Libération
]
.pull-right-big[
```c
printf("Veuillez saisir une chaine \n");
scanf("%s",p_tab);
```
<img src="img/affectionChar.svg" width=300/>

]
---
# Gestion des chaînes
## Step by Step
.pull-left-small[
1. Déclaration
2. Allocation
3. Affectation
4. .under[Affichage]
5. Libération
]
.pull-right-big[
```c
printf("ma chaine : %s \n",p_tab);
```
<center>
 <img src="img/affectation2Char.png" width=300/>
</center>
]

---
# Gestion des chaînes
## Step by Step
.pull-left-small[
1. Déclaration
2. Allocation
3. Affectation
4. Affichage
5. .under[Libération]
]
.pull-right-big[
```c
free(p_tab);
p_tab=NULL;
```
<center>
 <img src="img/declaration.svg" width=300/>
</center>
]

---
# Tableau dynamique 1D
## En résumé

1. Déclaration
2. Allocation
3. Affectation
4. Traitements
5. Libération

```c
<leType>* p_tab;
p_tab = malloc(<taille> * sizeof(<leType>));
```

---
# Today
## Plan
1. Rappel des tableaux statiques 1D et 2D
2. Les tableaux dynamiques 1D
3. .under[Les tableaux dynamiques 2D]
4. Les tips

---
# Création d'un tableau 2D 1/5
## Définition
Un tableau 2D Dynamiques est un tableau de pointeurs

---
# Création d'un tableau 2D 2/5
## Déclaration + allocation

```c
int** p_tab;
int taille1;
int taille2;
taille1=4;
taille2=5;
p_tab=malloc(taille1 * sizeof (int*));
for (int i=0;i<taille1;i++){
 p_tab[i]= malloc(taille2 * sizeof (int));
 }
```

---
# Création d'un tableau 2D 3/5
## Affectation
<center>
 <img src="img/dynamique2d2.png" width=400/>
</center>

```c
for (int i=0;i<taille1;i++){
 for (int j=0;j<taille2;j++){
 p_tab[i][j]=rand()% (10-1)+1;
 }
}
 ```
---
# Création d'un tableau 2D 5/5
## Affichage
```c
 for (int i=0;i<taille1;i++){
 printf("|");
 for (int j=0;j<taille2;j++){
 printf(" %d | ",p_tab[i][j]);
 }
 printf("\n");
 }
```

---
# Création d'un tableau 2D 5/5
## Liberation

- Il faut libérer la mémoire utiliser par le pointeur n°1 puis n°2 puis ...
- Les tableaux p_tab[0] puis p_tab[1] ... n'existent plus !
```c
for (int i=0;i<taille1;i++){
 free(p_tab[i]);
}
free(p_tab);
p_tab=NULL;
 ```

---
# Today
## Plan
1. Rappel des tableaux statiques 1D et 2D
2. Les tableaux dynamiques 1D
3. Les tableaux dynamiques 2D
4. .under[Les tips]

---
# Les tips
## Dans nos utilisations de tableaux dynamiques
il faut une procédure/fonction
 - pour allouer
 - pour initialiser par défaut des valeurs
 - pour afficher
 - pour interagir avec l'utilisateur
 - ...

Sans oublier les commentaires !

---
# Attention
## Déclaration de plusieurs
Il faut déclarer sur plusieurs lignes les tableaux dynamiques

## Hein
```c
int* tab1, tab2,tab3;
```
.underR[ça marche pô !]

---
# Attention
## VAR
<video src="videos/tabs1.mp4" width="200" controls poster="vignette.jpg"> </video>

---
# Attention
## Déclaration de plusieurs
Il faut déclarer sur plusieurs lignes les tableaux dynamiques

## solution
```c
int* tab1;
int* tab2;
int* tab3;
```

---
# Attention
## VAR

---
# Changer la taille
## realloc
On peut réalouer de l'espace à un tableau dynamique déjà existant avec le mot clé realloc
## Exemple
```c
int* mesNotes;
int taille = 5;
monTab=malloc (taille * sizeof(int));
/* traitement */
....
/* on se rend compte qu'il manque deux cases supplémentaires pour 2 autres notes */
monTab=realloc (monTab, (taille+2)* sizeof(int));

```
---
# La mémoire
## Le free
.otro-blockquote[Un pointeur est une variable qui mémorise une adresse mémoire]
<center>
 <img src="https://media.giphy.com/media/KL7I5MXrcvezC/giphy.gif" width=150/>
</center>
.otro-blockquote[En bref si tu as free, tu as tout compris !]

---
# Bilan
## Today
- Comprendre la différence entre un tableau dynamique et statique
- Utiliser les tableaux dynamiques
- Manipuler des chaînes de caractères avec des pointeurs

## Les mots clés
- malloc
- free