Package ldc
DIU EIL 2020/2022
BLOC3 - Liste Doublement Chainée
The project has reached a stable, usable state but is no longer being actively developed;
Support/maintenance will be provided as time allows.
About The Project
L’objectif de ce projet est de développer le type de données Liste Doublement Chaînée (LDC). Il s’agit d’un enrichissement du type Liste Chainée vu pendant le cours.
Pour une LDC, un nœud est constitué :
- d’une valeur,
- d’une référence sur le nœud suivant,
- et d’une référence sur le nœud précédent.
Remarques :
- Pour le premier nœud, le nœud précédent est None.
- Pour le dernier nœud, le nœud suivant est None.
- On considérera des nœuds contenant des entiers.
- De même qu’en cours, un nœud sera défini par une liste (tableau) Python.
- Le type LDC sera confondu avec le type nœud (NoeudLDC) de cette liste.
- Une liste vide vaudra donc None.
Partie 1
- Créer la fonction CreerNoeudLDC(val,precedent,suivant) : NoeudLDC
- val (entier) : la valeur contenue dans le noeud
- precedent (NoeudLDC) : le nœud précédent. Vaut None pour un nœud en début de liste
- suivant (NoeudLDC) : le nœud suivant. Vaut None pour un nœud en fin de liste
- Créer la fonction EstNoeudLDC(n : NoeudLDC) : booleen : qui vérifie que n est bien un nœud de liste doublement chainée, c’est-à-dire que :
- n vaut None ou :
- n est une liste de 3 éléments (la fonction native isinstance sera utile)
- n[0] est un entier
- n[1] et n[2] sont aussi des NoeudLDC (fonction récursive)
- Créer les fonctions d’accès aux données, et de modifications de ces données :
- GetValLDC(n : NoeudLDC) : entier
- GetPrecedentLDC(n : NoeudLDC) : NoeudLDC
- GetSuivantLDC(n : NoeudLDC) : NoeudLDC
- Créez les fonctions suivantes :
- LongueurLDC(l) : entier (renvoie la longueur de la liste)
- InsererDebutLDC(l,val) : NoeudLDC (insère un nœud au début de la liste)
- InsererFinLDC(l,val) : NoeudLDC (insère un nœud à la fin de la liste)
- SupprimerDebutLDC(l) : NoeudLDC (supprime le premier nœud de la liste)
- SupprimerFinLDC(l) : NoeudLDC (supprime le dernier nœud de la liste)
- AccesLDC(l,p) : NoeudLDC (renvoie le nœud d’indice p dans la liste. Le premier nœud a pour indice 0)
- InsererPlaceLDC(l,val,p) : NoeudLDC (insère le nœud contenant val juste après le nœud d’indice p ; le premier nœud a pour indice 0)
- SupprimerPlaceLDC(l,p) : NoeudLDC (supprime de l le nœud d’indice p ; le premier nœud a pour indice 0)
- SupprimerValLDC(l,val) : NoeudLDC (supprime de l le premier nœud contenant val ; premier car en effet, rien n’interdit que la liste contienne des doublons)
- LDC2List(l) : tableau (renvoie la liste Python (tableau) contenant les éléments de l ; renvoie [] si l vaut None)
- List2LDC(l) : NoeudLDC (renvoie la liste doublement chainée contenant dans le même ordre les éléments de la liste Python (tableau) l ; renvoie None si l vaut [])
- Pour chaque fonction, vous chercherez à quelles conditions la fonction peut être appelée (par exemple, on ne peut pas supprimer le premier élément d’une liste vide ; ou encore, on peut vérifier le type des arguments, via l’utilisation de isinstance et EstNoeudLDC). Vous rédigerez alors une condition assert pour chacune de ces conditions, comme vu en cours, dans l’exemple de la liste simplement chainée.
Dans une partie
python if __name__ == "__main__", vous rédigerez un jeu de test vous convainquant que votre programme ne comporte pas de bug. Chaque fonction doit donc être testée.
Partie 2
Créez un nouveau fichier qui importe le précédent.
Ce fichier va définir les fonctionnalités pour faire en sorte que la liste soit triée dans l’ordre croissant
- Créer la fonction EstOrdonneeLDC(l) : booleen, qui renvoie True si la liste est croissante (doublons possibles)
- Créer la fonction TriLDC(l) : NoeudLDC qui renvoie la liste doublement chainée triée des entiers de la liste doublement chainée l. On utilisera LDC2List, puis la fonction sort de Python, puis List2LDC
- Créer la fonction InsereOrdreLDC(l,val) qui insère val à sa place dans la liste doublement chainée croissante l, de manière que l reste croissante
De même, il faudra rédiger une partie main pour tester ces deux nouvelles fonctions.
Conseils
Pensez à bien commenter vos fonctions. Pour cela, suivez les normes décrites dans les documents suivants :
Getting Started
To get a local copy up and running follow these simple steps.
Prerequisites
None
Installation
Cloner le dépot
git clone https://framagit.org/slozano54/listedoublementchainee
Ou télécharger l'archive zip.
Pour générer la documentation il faut installer le paquet python pdoc3
pip3 install pdoc
Les fichiers de la documentation sont générés dans le dossier ./docs/ldc
Usage
À la racine du projet, lancer le script python programmePrincipal.py
python3 programmePrincipal.py
- Choisir la partie à tester en tapant 1 ou 2 :
- Partie 1, choisir les tests à lancer en tapant 1, 2, 3 ou 4 :
Par exemple, les tests pour les définitions :
- Pour la partie 1, il y a un sous menu pour tester les fonctions indépendamment :
- Partie 2, choisir les tests à lancer en tapant 1, 2, 3 ou 4 :
Roadmap
See the open issues for a list of proposed features (and known issues).
Contributing
Contributions are what make the open source community such an amazing place to be learn, inspire, and create. Any contributions you make are greatly appreciated.
- Fork the Project
- Create your Feature Branch (
git checkout -b feature/AmazingFeature) - Commit your Changes (
git commit -m 'Add some AmazingFeature') - Push to the Branch (
git push origin feature/AmazingFeature) - Open a Pull Request
License
Contact
Sébastien LOZANO - Write me on gitlab
Project Link: https://framagit.org/slozano54/listedoublementchainee
Expand source code
#!/usr/bin/python3
#-*- coding: utf8 -*-
# @author : Sébastien LOZANO
# Source pour l'écriture d'un REAMDE en mardown : https://www.makeareadme.com/
# Génère la page d'accueil de la documentation pdoc3
"""
# DIU EIL 2020/2022
## BLOC3 - Liste Doublement Chainée
<!--  -->
_The project has reached a stable, usable state but is no longer being actively developed;_
_Support/maintenance will be provided as time allows._
<a href="https://framagit.org/slozano54/listedoublementchainee">
<img src="https://framagit.org/slozano54/listedoublementchainee/-/raw/master/images/logo.png" alt="Logo" width="80" height="80">
</a>
<!-- ABOUT THE PROJECT -->
## About The Project
L’objectif de ce projet est de développer le type de données **Liste Doublement Chaînée (LDC)**. Il s’agit
d’un enrichissement du type Liste Chainée vu pendant le cours.
Pour une LDC, un nœud est constitué :
- d’une valeur,
- d’une référence sur le nœud suivant,
- et d’une référence sur le nœud précédent.
Remarques :
- Pour le premier nœud, le nœud précédent est None.
- Pour le dernier nœud, le nœud suivant est None.
- On considérera des nœuds contenant des entiers.
- De même qu’en cours, un nœud sera défini par une liste (tableau) Python.
- Le type LDC sera confondu avec le type nœud (NoeudLDC) de cette liste.
- Une liste vide vaudra donc None.
### Partie 1
- Créer la fonction **CreerNoeudLDC(val,precedent,suivant) : NoeudLDC**
- **val (entier)** : la valeur contenue dans le noeud
- **precedent (NoeudLDC)** : le nœud précédent. Vaut None pour un nœud en début de liste
- **suivant (NoeudLDC)** : le nœud suivant. Vaut None pour un nœud en fin de liste
- Créer la fonction **EstNoeudLDC(n : NoeudLDC) : booleen** : qui vérifie que n est bien un nœud de liste doublement chainée, c’est-à-dire que :
- n vaut None ou :
- n est une liste de 3 éléments (la fonction native isinstance sera utile)
- n[0] est un entier
- n[1] et n[2] sont aussi des NoeudLDC (fonction récursive)
- Créer les fonctions d’accès aux données, et de modifications de ces données :
- **GetValLDC(n : NoeudLDC) : entier**
- **GetPrecedentLDC(n : NoeudLDC) : NoeudLDC**
- **GetSuivantLDC(n : NoeudLDC) : NoeudLDC**
- Créez les fonctions suivantes :
- **LongueurLDC(l) : entier** (renvoie la longueur de la liste)
- **InsererDebutLDC(l,val) : NoeudLDC** (insère un nœud au début de la liste)
- **InsererFinLDC(l,val) : NoeudLDC** (insère un nœud à la fin de la liste)
- **SupprimerDebutLDC(l) : NoeudLDC** (supprime le premier nœud de la liste)
- **SupprimerFinLDC(l) : NoeudLDC** (supprime le dernier nœud de la liste)
- **AccesLDC(l,p) : NoeudLDC** (renvoie le nœud d’indice p dans la liste. Le premier nœud a pour indice 0)
- **InsererPlaceLDC(l,val,p) : NoeudLDC** (insère le nœud contenant val juste après le nœud d’indice p ; le premier nœud a pour indice 0)
- **SupprimerPlaceLDC(l,p) : NoeudLDC** (supprime de l le nœud d’indice p ; le premier nœud a pour indice 0)
- **SupprimerValLDC(l,val) : NoeudLDC** (supprime de l le premier nœud contenant val ; premier car en effet, rien n’interdit que la liste contienne des doublons)
- **LDC2List(l) : tableau** (renvoie la liste Python (tableau) contenant les éléments de l ; renvoie [] si l vaut None)
- **List2LDC(l) : NoeudLDC** (renvoie la liste doublement chainée contenant dans le même ordre les éléments de la liste Python (tableau) l ; renvoie None si l vaut [])
- Pour chaque fonction, vous chercherez à quelles conditions la fonction peut être appelée (par exemple, on ne peut pas supprimer le premier élément d’une liste vide ; ou encore, on peut vérifier le type des arguments, via l’utilisation de isinstance et EstNoeudLDC). Vous rédigerez alors une condition assert pour chacune de ces conditions, comme vu en cours, dans l’exemple de la liste simplement chainée.
> Dans une partie ```python if __name__ == "__main__"```, vous rédigerez un jeu de test vous convainquant que votre programme ne comporte pas de bug. Chaque fonction doit donc être testée.
### Partie 2
Créez un nouveau fichier qui importe le précédent.
Ce fichier va définir les fonctionnalités pour faire en sorte que la liste soit triée dans l’ordre croissant
- Créer la fonction **EstOrdonneeLDC(l) : booleen**, qui renvoie True si la liste est croissante (doublons possibles)
- Créer la fonction **TriLDC(l) : NoeudLDC** qui renvoie la liste doublement chainée triée des entiers de la liste doublement chainée l. On utilisera LDC2List, puis la fonction sort de Python, puis List2LDC
- Créer la fonction **InsereOrdreLDC(l,val)** qui insère val à sa place dans la liste doublement chainée croissante l, de manière que l reste croissante
> De même, il faudra rédiger une partie main pour tester ces deux nouvelles fonctions.
### Conseils
Pensez à bien commenter vos fonctions. Pour cela, suivez les normes décrites dans les documents suivants :
- https://www.python.org/dev/peps/pep-0008/#comments
- https://www.python.org/dev/peps/pep-0257/
<!-- [![Product Name Screen Shot][product-screenshot]](https://example.com) -->
<!-- GETTING STARTED -->
## Getting Started
To get a local copy up and running follow these simple steps.
### Prerequisites
None
### Installation
Cloner [le dépot](https://framagit.org/slozano54/listedoublementchainee)
```shell
git clone https://framagit.org/slozano54/listedoublementchainee
```
Ou télécharger l'[archive zip](https://framagit.org/slozano54/listedoublementchainee/-/archive/master/listedoublementchainee-master.zip).
Pour générer la documentation il faut installer le paquet python [pdoc3](https://pdoc3.github.io/pdoc/)
```shell
pip3 install pdoc
```
Les fichiers de la documentation sont générés dans le dossier **./docs/ldc**
<!-- USAGE EXAMPLES -->
<!-- _For more examples, please refer to the [Documentation](https://framagit.org/slozano54/listedoublementchainee)_ -->
<!-- USAGE -->
## Usage
À la racine du projet, lancer le script python **programmePrincipal.py**
```shell
python3 programmePrincipal.py
```
- Choisir la partie à tester en tapant 1 ou 2 :
- **Partie 1**, choisir les tests à lancer en tapant 1, 2, 3 ou 4 :
Par exemple, les tests pour les définitions :
- Pour la **partie 1**, il y a un sous menu pour tester les fonctions indépendamment :
- **Partie 2**, choisir les tests à lancer en tapant 1, 2, 3 ou 4 :
<!-- ROADMAP -->
## Roadmap
See the [open issues](https://framagit.org/slozano54/listedoublementchainee/issues) for a list of proposed features (and known issues).
<!-- CONTRIBUTING -->
## Contributing
Contributions are what make the open source community such an amazing place to be learn, inspire, and create. Any contributions you make are **greatly appreciated**.
1. Fork the Project
2. Create your Feature Branch (`git checkout -b feature/AmazingFeature`)
3. Commit your Changes (`git commit -m 'Add some AmazingFeature'`)
4. Push to the Branch (`git push origin feature/AmazingFeature`)
5. Open a Pull Request
<!-- LICENSE -->
## License
[MIT](https://choosealicense.com/licenses/mit/)
<!-- CONTACT -->
## Contact
Sébastien LOZANO - Write me on gitlab
Project Link: [https://framagit.org/slozano54/listedoublementchainee](https://framagit.org/slozano54/listedoublementchainee)
"""
pass
# Pour gérer les imports relatifs
import os, sys; sys.path.append(os.path.dirname(os.path.realpath(__file__)))Sub-modules
ldc.partie1-
Toutes les méthodes permettant de travailler sur les listes doublement chainées
ldc.partie2-
Toutes les méthodes permettant de travailler sur l'ordre des listes doublement chainées
ldc.tools-
Des outils pour des trucs et des machins made in home.