---
# System prepended metadata

title: 'CP Python: Séances 13 et 14'

---



# CP Python: Séances 13 et 14


## 0) Ressources de la séance 12
* [Guide de séance](https://hackmd.io/@Tb5Z2PdeRLSnkxJEsjcLXg/HkWCjS7Tv)
* [Correctif de la QBF](https://hackmd.io/@Tb5Z2PdeRLSnkxJEsjcLXg/r1cwBFOTv) 


## 1) A préparer: Listes chaînées
### A.Théorie
- [ ] Lire les [slides *Semaine 12 - Restructuration*](https://drive.google.com/file/d/1FJWRw4MxG5i0cysI8G0w5MUocGG19Kl9/view?usp=sharing) 
- [ ] Lire la section [6 - Linked lists](https://syllabus-interactif.info.ucl.ac.be/syllabus/info1-theory/PART_III/linked_lists)
- [ ] Essayer et comprendre le code développé dans le syllabus et qui se trouve aussi dans l'annexe [Appendix - Source code of linked lists](https://syllabus-interactif.info.ucl.ac.be/syllabus/info1-theory/PART_III/appendix_code_linked_list)
- [ ] *Optionnel*: Je vous fournis également [ma synthèse](https://hackmd.io/@Tb5Z2PdeRLSnkxJEsjcLXg/SyE9Kf6aE)



| Liste chaînée | Parcours | 
| -------- | -------- | 
| ![](https://i.imgur.com/VivdfEt.png)| ![](https://i.imgur.com/MuCOcGI.png)| 
| **Points importants** | **Dessiner aide beaucoup!** NB. Attention à l'ordre des opérations.  | 
| ![](https://i.imgur.com/QdOZN8O.png)| ![](https://i.imgur.com/oM8ZZ0Q.png)




### B. Exercices: 1ere partie -> *Utiliser ce [REPL](https://repl.it/join/cwpsfrzn-guillaumegst)*
Dans les [exercices du cours](https://syllabus-interactif.info.ucl.ac.be/syllabus/info1-exercises/PART_III/MISSION_11/preparation): 
- [ ] **Répondez aux *Questions à choix multiples*  (via Inginious)**
 - [ ] **Résoudre *3. Imprimer une liste chaînée (généralisation)***
    > Dans le code donné dans l'annexe [Appendix - Source code of linked lists](https://syllabus-interactif.info.ucl.ac.be/syllabus/info1-theory/PART_III/appendix_code_linked_list) la méthode `print()` de la classe LinkedList imprime les éléments d'une liste chaînée, séparés par une espace. Par exemple:
    > 
    > ```
    > >>> l = LinkedList()
    > >>> l.add(3)
    > >>> l.add(2)
    > >>> l.add(1) 
    > >>> l.print()
    > [ 1 2 3 ]
    > ```
    > Or, normalement la convention est de séparer les éléments d'une liste par des virgules. Ajoutez une nouvelle méthode print_avec_virgule() dans la classe LinkedList qui imprime la liste comme suite:
    > 
    > ```
    > >>> l.print_avec_virgule()
    > [ 1, 2, 3 ]
    > ```
    > Attention: il n'y a pas de virgule après le dernier élément ou si on imprime une liste vide.
    > 
    > ```
    > >>> l = LinkedList()
    > >>> l.print_avec_virgule()
    > [ ]
    > ```
    > ---
    > Généralisez la méthode print_avec_virgule de l'exercice précédente par une méthode print_avec_separateur qui peut prendre n'importe quelle séparateur. Par exemple:
    > 
    > ``` 
    > >>> l.print_avec_separateur(", ")
    > [ 1, 2, 3 ]
    > >>> l.print_avec_separateur(" ")
    > [ 1 2 3 ]
    > >>> l.print_avec_separateur(" - ")
    > [ 1 - 2 - 3 ]
    > ```
- [ ] **Résoudre *9. Insérer un élément*** 
    > *Considérez qu'on désire utiliser la classe LinkedList pour stocker une liste de strings. On souhaite qu'elle soit en  permanence en ordre alphabétique croissant.*
    1. Pour la première partie utilisez [ce Jamboard](https://jamboard.google.com/d/1QX0XZxUC9dhaLTlD5lIlofqHg0_HKq0dOjSMHS7zO8k/edit?usp=sharing) pour les illustrations. 
    > -->  1. Dessinez complètement une telle liste chainée contenant les trois strings "abc", "def" et "xyz".
         ![](https://i.imgur.com/Essic9i.png)

    > --> 2. Expliquez en français et dessinez les opérations à effectuer pour ajouter un Node contenant "aaa" dans cette liste ? Idem avec "ghi" ? "def" ? "zzz" ?
    > 
    2. Implémentez `insert` dans `LinkedList`. Repartez du  *[REPL](https://repl.it/join/cwpsfrzn-guillaumegst)*, qui inclut déjà le code fourni en [Appendix - Source code of linked lists](https://syllabus-interactif.info.ucl.ac.be/syllabus/info1-theory/PART_III/appendix_code_linked_list).



- [ ] **Réfléchissez déjà à la résolution de la QBF, dont l'énoncé est disponible [ici](https://www.docdroid.net/q5Oa6TW/mission-11-qbf-pdf). Nous terminerons l'exercice ensemble en séance.**

:::info
Correction ici avec énoncé:  [DEEPNOTE](https://deepnote.com/project/2b95be22-c40d-4807-b3ec-acc946a0e44d) :rocket: 
- Alternative: [Version lecture](https://deepnote.com/publish/2b95be22-c40d-4807-b3ec-acc946a0e44d) 
- Alternative 2 (sans énoncé): [REPL](https://repl.it/@GuillaumeGst/CP-Python-Tuteur-S13)
:::


------
### C. Examen blanc -> *Utiliser ce [REPL](https://repl.it/join/hpbiumco-guillaumegst)*
Dans ce 2e REPL, résolvez tout l'examen blanc qu'on vous a fourni :-) 

:::success
<div style="text-align:center;font-size:20px;font-weight:bolde;">
 Bon travail 💪
</div>
:::


---
### Annexe: 2D-to-1D mapping :wink: 

Given x and y, and 2D array sizes `width` (for x-direction) and `height` (for y-direction), you can calculate the according index `i` in 1D space (zero-based) by

```python
i = x + width*y;
```

and the reverse operation is 

```python
x = i % width;    
# % is the "modulo operator", the remainder of i // width;
y = i // width;    
# where "//" is an integer division

```

![](https://i.imgur.com/bh9NDNU.png)
![](https://i.imgur.com/Z8ZlU34.png)
