Python - Structure des données

Les ordinateurs stockent et traitent les données avec une vitesse et une précision
extraordinaires. Il est donc essentiel que les données soient stockées efficacement et puissent
être consultées rapidement. Le traitement des données doit également avoir lieu dans les plus
brefs délais, mais sans perdre en précision.
Les structures de données traitent de la façon dont les données sont organisées et conservées
dans la mémoire lorsqu'un programme les traite. Il est important de noter que les données
stockées sur le disque dans le cadre de stockages persistants (comme les tables relationnelles)
ne sont pas ici appelées structure de données.
Un algorithme est un ensemble d'instructions étape par étape pour traiter les données dans un
but spécifique. Ainsi, un algorithme utilise diverses structures de données de manière logique
pour résoudre un problème informatique spécifique.
Dans ce tutoriel, nous couvrirons ces deux concepts fondamentaux de l'informatique à l'aide du
langage de programmation Python.
Ce didacticiel est conçu pour les diplômés en informatique ainsi que pour les professionnels du
logiciel qui souhaitent apprendre les structures de données et la programmation d'algorithmes en
étapes simples et faciles en utilisant Python comme langage de programmation.
Avant de poursuivre ce didacticiel, vous devez avoir une connaissance de base de l'écriture de
code en langage de programmation Python, de l'utilisation de n'importe quel IDE python et de
l'exécution de programmes Python. Si vous êtes complètement nouveau dans Python, veuillez
vous référer à notre tutoriel Python pour avoir une bonne compréhension du langage.

Python - Présentation de DS
Aperçu de la structure des données
Les structures de données sont des concepts fondamentaux de l'informatique qui aident à écrire
des programmes efficaces dans n'importe quelle langue. Python est un langage de script de haut
niveau, interprété, interactif et orienté objet, à l'aide duquel nous pouvons étudier les principes
fondamentaux de la structure de données de manière plus simple par rapport à d'autres langages
de programmation.
Dans ce chapitre, nous allons étudier un bref aperçu de certaines structures de données
fréquemment utilisées en général et comment elles sont liées à certains types de données
Python spécifiques. Il existe également des structures de données spécifiques à python qui sont
répertoriées dans une autre catégorie.

Structures de données générales

Les différentes structures de données en informatique sont divisées en gros en deux catégories
présentées ci-dessous. Nous discuterons en détail de chacune des structures de données ci-
dessous dans les chapitres suivants.

Structures de données de doublure

Ce sont les structures de données qui stockent les éléments de données de manière
séquentielle.
 Array: Il s'agit d'un agencement séquentiel d'éléments de données associés à l'index de
l'élément de données.
  Linked List: Chaque élément de données contient un lien vers un autre élément avec les
données qu'il contient.
 Stack: C'est une structure de données qui ne suit qu'un ordre de fonctionnement
spécifique. LIFO (dernier entré premier sorti) ou FILO (premier entré dernier sorti).
 Queue: Il est similaire à Stack mais l'ordre de fonctionnement est uniquement FIFO (First
In First Out).
 Matrix: Il s'agit d'une structure de données bidimensionnelle dans laquelle l'élément de
données est référencé par une paire d'indices.

Structures de données non doublées

Ce sont les structures de données dans lesquelles il n'y a pas de liaison séquentielle des
éléments de données. Toute paire ou groupe d'éléments de données peut être lié les uns aux
autres et accessible sans séquence stricte.
 Binary Tree: Il s'agit d'une structure de données dans laquelle chaque élément de
données peut être connecté à deux autres éléments de données au maximum et
commence par un nœud racine.
 Heap: Il s'agit d'un cas particulier de structure de données Tree où les données du nœud
parent sont soit strictement supérieures / égales aux nœuds enfants, soit strictement
inférieures à ses nœuds enfants.
 Hash Table: Il s'agit d'une structure de données constituée de tableaux associés les uns
aux autres à l'aide d'une fonction de hachage. Il récupère les valeurs à l'aide de clés
plutôt que d'index à partir d'un élément de données.
 Graph: .C'est un arrangement de sommets et de nœuds où certains des nœuds sont
connectés les uns aux autres par des liens.

Structures de données spécifiques à Python

Ces structures de données sont spécifiques au langage python et offrent une plus grande
flexibilité dans le stockage de différents types de données et un traitement plus rapide dans un
environnement python.
 List: Il est similaire au tableau à l'exception du fait que les éléments de données peuvent
être de types de données différents. Vous pouvez avoir à la fois des données numériques
et des données de chaîne dans une liste Python.
 Tuple: Les tuples sont similaires aux listes mais ils sont immuables, ce qui signifie que
les valeurs d'un tuple ne peuvent pas être modifiées, elles peuvent uniquement être lues.
 Dictionary: Le dictionnaire contient des paires clé-valeur comme éléments de données.
Dans les chapitres suivants, nous allons apprendre les détails de la façon dont chacune de ces
structures de données peut être implémentée en utilisant Python.

Python - Environnement DS
Python est disponible sur une grande variété de plates-formes, y compris Linux et Mac OS X.
Voyons comment configurer notre environnement Python.

Configuration de l'environnement local

Ouvrez une fenêtre de terminal et tapez "python" pour savoir s'il est déjà installé et quelle version
est installée.
 Unix (Solaris, Linux, FreeBSD, AIX, HP / UX, SunOS, IRIX, etc.)
 Gagnez 9x / NT / 2000
 Macintosh (Intel, PPC, 68 Ko)
 OS/2
  DOS (plusieurs versions)
 PalmOS
 Téléphones mobiles Nokia
 Windows CE
 Système d'exploitation Acorn / RISC
 BeOS
 Amiga
 VMS/OpenVMS
 QNX
 VxWorks
 Psion
 Python a également été porté sur les machines virtuelles Java et .NET

Obtenir Python
Le code source, les binaires, la documentation, les actualités, etc. les plus à jour et les plus
récents sont disponibles sur le site officiel de Python [Link]
Vous pouvez télécharger la documentation Python depuis [Link] La
documentation est disponible aux formats HTML, PDF et PostScript.

Installer Python
La distribution Python est disponible pour une grande variété de plates-formes. Vous devez
télécharger uniquement le code binaire applicable à votre plateforme et installer Python.
Si le code binaire de votre plateforme n'est pas disponible, vous avez besoin d'un compilateur C
pour compiler le code source manuellement. La compilation du code source offre plus de
flexibilité en termes de choix des fonctionnalités dont vous avez besoin dans votre installation.
Voici un bref aperçu de l'installation de Python sur différentes plates-formes -

Installation Unix et Linux

Voici les étapes simples pour installer Python sur une machine Unix / Linux.
 Ouvrez un navigateur Web et accédez à [Link]
 Suivez le lien pour télécharger le code source compressé disponible pour Unix / Linux.
 Téléchargez et extrayez des fichiers.
 Modification du fichier Modules / Setup si vous souhaitez personnaliser certaines options.
 exécuter le script ./configure
 make
 faire installer
Cela installe Python à l'emplacement standard / usr / local / bin et ses bibliothèques dans / usr /
local / lib / pythonXX où XX est la version de Python.

Installation de Windows
Voici les étapes pour installer Python sur une machine Windows.
 Ouvrez un navigateur Web et accédez à [Link]
 Suivez le lien pour le fichier d' installation de Windows [Link] où XYZ est la
version que vous devez installer.
 Pour utiliser ce programme d'installation [Link] , le système Windows doit
prendre en charge Microsoft Installer 2.0. Enregistrez le fichier du programme
 d'installation sur votre ordinateur local, puis exécutez-le pour savoir si votre ordinateur
prend en charge MSI.
 Exécutez le fichier téléchargé. Cela fait apparaître l'assistant d'installation Python, qui est
vraiment facile à utiliser. Acceptez simplement les paramètres par défaut, attendez que
l'installation soit terminée et vous avez terminé.

Installation sur Macintosh

Les Mac récents sont livrés avec Python installé, mais il peut être obsolète de plusieurs années.
Voir[Link] obtenir des instructions sur l'obtention de la
version actuelle ainsi que des outils supplémentaires pour prendre en charge le développement
sur Mac. Pour les Mac OS plus anciens avant Mac OS X 10.3 (publié en 2003), MacPython est
disponible.
Jack Jansen le maintient et vous pouvez avoir un accès complet à toute la documentation sur
son site Web - [Link] Vous pouvez trouver les détails
d'installation complets pour l'installation de Mac OS.

Configurer PATH
Les programmes et autres fichiers exécutables peuvent se trouver dans de nombreux
répertoires, de sorte que les systèmes d'exploitation fournissent un chemin de recherche qui
répertorie les répertoires dans lesquels le système d'exploitation recherche les exécutables.
Le chemin est stocké dans une variable d'environnement, qui est une chaîne nommée gérée par
le système d'exploitation. Cette variable contient des informations disponibles pour le shell de
commande et d'autres programmes.
le path La variable est nommée PATH sous Unix ou Path sous Windows (Unix est sensible à la
casse; Windows ne l'est pas).
Sous Mac OS, le programme d'installation gère les détails du chemin. Pour appeler l'interpréteur
Python à partir d'un répertoire particulier, vous devez ajouter le répertoire Python à votre chemin.

Définition du chemin sous Unix / Linux

Pour ajouter le répertoire Python au chemin d'une session particulière sous Unix -
 In the csh shell - tapez setenv PATH "$ PATH: / usr / local / bin / python" et appuyez sur
Entrée.
 In the bash shell (Linux) - tapez export ATH = "$ PATH: / usr / local / bin / python" et
appuyez sur Entrée.
 In the sh or ksh shell - tapez PATH = "$ PATH: / usr / local / bin / python" et appuyez
sur Entrée.
 Note - / usr / local / bin / python est le chemin du répertoire Python

Définition du chemin sous Windows

Pour ajouter le répertoire Python au chemin d'une session particulière dans Windows -
At the command prompt - tapez path% path%; C: \ Python et appuyez sur Entrée.
Note - C: \ Python est le chemin du répertoire Python

Variables d'environnement Python

Voici des variables d'environnement importantes, qui peuvent être reconnues par Python -
 N° Variable et description
Sr.

1 PYTHONPATH
Il a un rôle similaire à PATH. Cette variable indique à l'interpréteur Python où localiser les fichiers d
programme. Il doit inclure le répertoire de la bibliothèque source Python et les répertoires contenant l
PYTHONPATH est parfois prédéfini par le programme d'installation Python.

2 PYTHONSTARTUP
Il contient le chemin d'un fichier d'initialisation contenant le code source Python. Il est exécuté chaqu
l'interpréteur. Il est nommé .[Link] sous Unix et contient des commandes qui chargent des utilit

3 PYTHONCASEOK
Il est utilisé dans Windows pour demander à Python de trouver la première correspondance insensible
d'importation. Définissez cette variable sur n'importe quelle valeur pour l'activer.

4 PYTHONHOME
Il s'agit d'un chemin de recherche de module alternatif. Il est généralement intégré dans les répertoire
PYTHONPATH pour faciliter le changement de bibliothèques de modules.

Exécuter Python
Il existe trois façons différentes de démarrer Python -

Interprète interactif
Vous pouvez démarrer Python depuis Unix, DOS ou tout autre système qui vous fournit un
interpréteur de ligne de commande ou une fenêtre shell.
Entrer python la ligne de commande.
Commencez immédiatement à coder dans l'interpréteur interactif.

$python # Unix/Linux
or
python% # Unix/Linux
or
C:> python # Windows/DOS

Voici la liste de toutes les options de ligne de commande disponibles -

N ° Sr. Option et description

 1 -d
Il fournit une sortie de débogage.

2 -O
Il génère un bytecode optimisé (résultant en des fichiers .pyo).

3 -S
N'exécutez pas le site d'importation pour rechercher les chemins Python au démarrage.

4 -v
sortie verbeuse (trace détaillée sur les instructions d'importation).

5 -X
désactiver les exceptions intégrées basées sur les classes (utilisez simplement des chaînes); obsolè

6 -c cmd
exécuter le script Python envoyé en tant que chaîne cmd

sept file
exécuter un script Python à partir d'un fichier donné

Script depuis la ligne de commande

Un script Python peut être exécuté en ligne de commande en appelant l'interpréteur sur votre
application, comme dans ce qui suit -

$python [Link] # Unix/Linux

or

python% [Link] # Unix/Linux

or

C: >python [Link] # Windows/DOS

Note - Assurez-vous que le mode d'autorisation de fichier permet l'exécution.

Environnement de développement intégré
Vous pouvez également exécuter Python à partir d'un environnement d'interface utilisateur
graphique (GUI), si vous avez une application GUI sur votre système qui prend en charge
Python.
 Unix - IDLE est le tout premier IDE Unix pour Python.
 Windows - PythonWin est la première interface Windows pour Python et est un IDE avec
une interface graphique.
 Macintosh - La version Macintosh de Python avec l'IDE IDLE est disponible sur le site
principal, téléchargeable sous forme de fichiers MacBinary ou BinHex'd.
Si vous ne parvenez pas à configurer correctement l'environnement, vous pouvez demander
l'aide de votre administrateur système. Assurez-vous que l'environnement Python est
correctement configuré et fonctionne parfaitement.
Note - Tous les exemples donnés dans les chapitres suivants sont exécutés avec la version
Python 2.4.3 disponible sur la version CentOS de Linux.
Nous avons déjà mis en place l'environnement de programmation Python en ligne, afin que vous
puissiez exécuter tous les exemples disponibles en ligne en même temps lorsque vous apprenez
la théorie. N'hésitez pas à modifier n'importe quel exemple et à l'exécuter en ligne.

Python - Tableaux
Array est un conteneur qui peut contenir un nombre fixe d'éléments et ces éléments doivent être
du même type. La plupart des structures de données utilisent des tableaux pour implémenter
leurs algorithmes. Voici les termes importants pour comprendre le concept de Array.
 Element- Chaque élément stocké dans un tableau est appelé un élément.
 Index - Chaque emplacement d'un élément dans un tableau a un index numérique, qui
est utilisé pour identifier l'élément.

Représentation du tableau
Les tableaux peuvent être déclarés de différentes manières dans différentes langues. Ci-dessous
une illustration.

Conformément à l'illustration ci-dessus, voici les points importants à considérer.

 L'index commence par 0.
 La longueur du tableau est de 10, ce qui signifie qu'il peut stocker 10 éléments.
 Chaque élément est accessible via son index. Par exemple, nous pouvons récupérer un
élément à l'index 6 comme 9.
Opérations de base
Voici les opérations de base prises en charge par une baie.
 Traverse - imprimer tous les éléments du tableau un par un.
 Insertion - Ajoute un élément à l'index donné.
 Deletion - Supprime un élément à l'index donné.
 Search - Recherche un élément en utilisant l'index donné ou par la valeur.
 Update - Met à jour un élément à l'index donné.
Le tableau est créé en Python en important le module de tableau dans le programme python.
Ensuite, le tableau est déclaré comme indiqué eblow.

from array import *

arrayName = array(typecode, [Initializers])

Typecode sont les codes qui sont utilisés pour définir le type de valeur que le tableau contiendra.
Certains codes de type couramment utilisés sont:

Code de type Valeur

b Représente un entier signé de taille 1 octet / td>

B Représente un entier non signé de taille 1 octet

c Représente un caractère de taille 1 octet

je Représente un entier signé de taille 2 octets

je Représente un entier non signé de taille 2 octets

F Représente une virgule flottante de taille 4 octets

ré Représente une virgule flottante de taille 8 octets

Avant de regarder diverses opérations sur les tableaux, créons et imprimons un tableau en
utilisant python.
Le code ci-dessous crée un tableau nommé array1.

from array import *

array1 = array('i', [10,20,30,40,50])

for x in array1:
print(x)

Lorsque nous compilons et exécutons le programme ci-dessus, il produit le résultat suivant -

Production
10
20
30
40
50

Accès à l'élément de tableau

Nous pouvons accéder à chaque élément d'un tableau en utilisant l'index de l'élément. Le code
ci-dessous montre comment

from array import *

array1 = array('i', [10,20,30,40,50])

print (array1[0])

print (array1[2])

Lorsque nous compilons et exécutons le programme ci-dessus, il produit le résultat suivant - qui
montre que l'élément est inséré à la position d'index 1.

Production
10
30

Opération d'insertion
L'opération d'insertion consiste à insérer un ou plusieurs éléments de données dans un tableau.
En fonction de l'exigence, un nouvel élément peut être ajouté au début, à la fin ou à tout index
donné du tableau.
Ici, nous ajoutons un élément de données au milieu du tableau à l'aide de la méthode insert ()
intégrée de python.

from array import *

array1 = array('i', [10,20,30,40,50])

[Link](1,60)

for x in array1:
print(x)

Lorsque nous compilons et exécutons le programme ci-dessus, il produit le résultat suivant qui
montre que l'élément est inséré à la position d'index 1.

Production
10
60
20
30
40
50

Opération de suppression
La suppression fait référence à la suppression d'un élément existant du tableau et à la
réorganisation de tous les éléments d'un tableau.
Ici, nous supprimons un élément de données au milieu du tableau à l'aide de la méthode remove
() intégrée à python.

from array import *

array1 = array('i', [10,20,30,40,50])

[Link](40)

for x in array1:
print(x)

Lorsque nous compilons et exécutons le programme ci-dessus, il produit le résultat suivant qui
montre que l'élément est supprimé du tableau.
Production
10
20
30
50

Opération de recherche
Vous pouvez effectuer une recherche d'un élément de tableau en fonction de sa valeur ou de son
index.
Ici, nous recherchons un élément de données à l'aide de la méthode python in-built index ().

from array import *

array1 = array('i', [10,20,30,40,50])

print ([Link](40))

Lorsque nous compilons et exécutons le programme ci-dessus, il produit le résultat suivant qui
montre l'index de l'élément. Si la valeur n'est pas présente dans le tableau, le programme renvoie
une erreur.

Production
3

Opération de mise à jour

L'opération de mise à jour fait référence à la mise à jour d'un élément existant du tableau à un
index donné.
Ici, nous réaffectons simplement une nouvelle valeur à l'index souhaité que nous voulons mettre
à jour.

from array import *

array1 = array('i', [10,20,30,40,50])

array1[2] = 80

for x in array1:
 print(x)

Lorsque nous compilons et exécutons le programme ci-dessus, il produit le résultat suivant qui
montre la nouvelle valeur à la position d'index 2.

Production
10
20
80
40
50

Python - Listes
La liste est un type de données le plus polyvalent disponible en Python qui peut être écrit sous la
forme d'une liste de valeurs séparées par des virgules (éléments) entre crochets. La chose
importante à propos d'une liste est que les éléments d'une liste n'ont pas besoin d'être du même
type.
Créer une liste est aussi simple que de mettre différentes valeurs séparées par des virgules entre
crochets. Par exemple -

list1 = ['physics', 'chemistry', 1997, 2000]

list2 = [1, 2, 3, 4, 5 ]
list3 = ["a", "b", "c", "d"]

Semblables aux indices de chaîne, les index de liste commencent à 0 et les listes peuvent être
découpées, concaténées, etc.

Accès aux valeurs dans les listes

Pour accéder aux valeurs des listes, utilisez les crochets pour le découpage avec l'index ou les
index pour obtenir la valeur disponible à cet index. Par exemple -

#!/usr/bin/python

list1 = ['physics', 'chemistry', 1997, 2000]

list2 = [1, 2, 3, 4, 5, 6, 7 ]
print "list1[0]: ", list1[0]
print "list2[1:5]: ", list2[1:5]

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

list1[0]: physics
list2[1:5]: [2, 3, 4, 5]

Mise à jour des listes

Vous pouvez mettre à jour un ou plusieurs éléments de listes en donnant la tranche sur le côté
gauche de l'opérateur d'affectation, et vous pouvez ajouter des éléments dans une liste avec la
méthode append (). Par exemple -

#!/usr/bin/python

list = ['physics', 'chemistry', 1997, 2000]

print "Value available at index 2 : "
print list[2]
list[2] = 2001
print "New value available at index 2 : "
print list[2]

Note - La méthode append () est discutée dans la section suivante.

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

Value available at index 2 :

1997
New value available at index 2 :
2001

Supprimer des éléments de liste

Pour supprimer un élément de liste, vous pouvez utiliser soit l'instruction del si vous savez
exactement quel (s) élément (s) vous supprimez ou la méthode remove () si vous ne le savez
pas. Par exemple -

#!/usr/bin/python

list1 = ['physics', 'chemistry', 1997, 2000]

print list1
del list1[2]
print "After deleting value at index 2 : "
print list1

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

['physics', 'chemistry', 1997, 2000]

After deleting value at index 2 :
['physics', 'chemistry', 2000]

Note - La méthode remove () est discutée dans la section suivante.

Opérations de base sur les listes

Les listes répondent aux opérateurs + et * un peu comme des chaînes; ils signifient ici aussi la
concaténation et la répétition, sauf que le résultat est une nouvelle liste, pas une chaîne.
En fait, les listes répondent à toutes les opérations générales de séquence que nous avons
utilisées sur les chaînes dans le chapitre précédent.

Expression Python Résultats

len ([1, 2, 3]) 3

[1, 2, 3] + [4, 5, 6] [1, 2, 3, 4, 5, 6]

["Salut!"] * 4 [«Salut!», «Salut!», «Salut!», «Salut!»]

3 dans [1, 2, 3] Vrai

pour x dans [1, 2, 3]: imprimer x, 123

Python - Tuples
Un tuple est une séquence d'objets Python immuables. Les tuples sont des séquences, tout
comme les listes. Les différences entre les tuples et les listes sont que les tuples ne peuvent pas
être modifiés contrairement aux listes et les tuples utilisent des parenthèses, tandis que les listes
utilisent des crochets.
Créer un tuple est aussi simple que de mettre différentes valeurs séparées par des virgules. Si
vous le souhaitez, vous pouvez également mettre ces valeurs séparées par des virgules entre
parenthèses. Par exemple -

tup1 = ('physics', 'chemistry', 1997, 2000);

tup2 = (1, 2, 3, 4, 5 );
tup3 = "a", "b", "c", "d";

Le tuple vide est écrit comme deux parenthèses ne contenant rien -

tup1 = ();
Pour écrire un tuple contenant une seule valeur, vous devez inclure une virgule, même s'il n'y a
qu'une seule valeur -

tup1 = (50,);

Comme les indices de chaîne, les indices de tuple commencent à 0 et peuvent être découpés,
concaténés, etc.

Accéder aux valeurs dans les tuples

Pour accéder aux valeurs dans tuple, utilisez les crochets pour le découpage avec l'index ou les
index pour obtenir la valeur disponible à cet index. Par exemple -

#!/usr/bin/python

tup1 = ('physics', 'chemistry', 1997, 2000);

tup2 = (1, 2, 3, 4, 5, 6, 7 );
print "tup1[0]: ", tup1[0];
print "tup2[1:5]: ", tup2[1:5];

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

tup1[0]: physics
tup2[1:5]: [2, 3, 4, 5]

Mise à jour des tuples

Les tuples sont immuables, ce qui signifie que vous ne pouvez pas mettre à jour ou modifier les
valeurs des éléments de tuple. Vous pouvez prendre des portions de tuples existants pour créer
de nouveaux tuples comme le montre l'exemple suivant -

#!/usr/bin/python

tup1 = (12, 34.56);

tup2 = ('abc', 'xyz');

# Following action is not valid for tuples

# tup1[0] = 100;

# So let's create a new tuple as follows

tup3 = tup1 + tup2;
print tup3;

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

(12, 34.56, 'abc', 'xyz')

Supprimer les éléments de tuple

La suppression des éléments de tuple individuels n'est pas possible. Il n'y a, bien sûr, rien de mal
à assembler un autre tuple avec les éléments indésirables supprimés.
Pour supprimer explicitement un tuple entier, utilisez simplement le deldéclaration. Par exemple -

#!/usr/bin/python

tup = ('physics', 'chemistry', 1997, 2000);

print tup;
del tup;
print "After deleting tup : ";
print tup;

Cela produit le résultat suivant. Notez une exception levée, car aprèsdel tup le tuple n'existe plus
-

('physics', 'chemistry', 1997, 2000)

After deleting tup :
Traceback (most recent call last):
File "[Link]", line 9, in <module>
print tup;
NameError: name 'tup' is not defined

Opérations de base sur les tuples

Les tuples répondent aux opérateurs + et * un peu comme des chaînes; ils signifient ici aussi la
concaténation et la répétition, sauf que le résultat est un nouveau tuple, pas une chaîne.
En fait, les tuples répondent à toutes les opérations générales de séquence que nous avons
utilisées sur les chaînes dans le chapitre précédent -

Expression Python Résultats

len ((1, 2, 3)) 3

(1, 2, 3) + (4, 5, 6) (1, 2, 3, 4, 5, 6)

('Salut!',) * 4 ("Salut!", "Salut!", "Salut!", "Salut!")

 3 pouces (1, 2, 3) Vrai

pour x dans (1, 2, 3): imprimer x, 123

Python - Dictionnaire
Dans le dictionnaire, chaque clé est séparée de sa valeur par un signe deux-points (:), les
éléments sont séparés par des virgules et le tout est entouré d'accolades. Un dictionnaire vide
sans aucun élément est écrit avec seulement deux accolades, comme ceci: {}.
Les clés sont uniques dans un dictionnaire alors que les valeurs peuvent ne pas l'être. Les
valeurs d'un dictionnaire peuvent être de n'importe quel type, mais les clés doivent être d'un type
de données immuable tel que des chaînes, des nombres ou des tuples.

Accéder aux valeurs dans le dictionnaire

Pour accéder aux éléments du dictionnaire, vous pouvez utiliser les crochets familiers avec la clé
pour obtenir sa valeur. Voici un exemple simple -

#!/usr/bin/python

dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

print "dict['Name']: ", dict['Name']
print "dict['Age']: ", dict['Age']

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

dict['Name']: Zara
dict['Age']: 7

Si nous tentons d'accéder à un élément de données avec une clé, qui ne fait pas partie du
dictionnaire, nous obtenons une erreur comme suit -

#!/usr/bin/python

dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

print "dict['Alice']: ", dict['Alice']

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

dict['Alice']:
Traceback (most recent call last):
 File "[Link]", line 4, in <module>
print "dict['Alice']: ", dict['Alice'];
KeyError: 'Alice'

Mise à jour du dictionnaire

Vous pouvez mettre à jour un dictionnaire en ajoutant une nouvelle entrée ou une paire clé-
valeur, en modifiant une entrée existante ou en supprimant une entrée existante comme indiqué
ci-dessous dans l'exemple simple -

#!/usr/bin/python

dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

dict['Age'] = 8; # update existing entry
dict['School'] = "DPS School"; # Add new entry

print "dict['Age']: ", dict['Age']

print "dict['School']: ", dict['School']

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

dict['Age']: 8
dict['School']: DPS School

Supprimer les éléments du dictionnaire

Vous pouvez supprimer des éléments de dictionnaire individuels ou effacer tout le contenu d'un
dictionnaire. Vous pouvez également supprimer tout le dictionnaire en une seule opération.
Pour supprimer explicitement un dictionnaire entier, utilisez simplement le deldéclaration. Voici
un exemple simple -

#!/usr/bin/python

dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

del dict['Name']; # remove entry with key 'Name'
[Link](); # remove all entries in dict
del dict ; # delete entire dictionary

print "dict['Age']: ", dict['Age']

print "dict['School']: ", dict['School']
Cela produit le résultat suivant. Notez qu'une exception est déclenchée car aprèsdel dict le
dictionnaire n'existe plus -

dict['Age']:
Traceback (most recent call last):
File "[Link]", line 8, in <module>
print "dict['Age']: ", dict['Age'];
TypeError: 'type' object is unsubscriptable

Note - La méthode del () est discutée dans la section suivante.

Propriétés des clés de dictionnaire

Les valeurs du dictionnaire n'ont aucune restriction. Il peut s'agir de n'importe quel objet Python
arbitraire, qu'il s'agisse d'objets standard ou d'objets définis par l'utilisateur. Cependant, il n'en va
pas de même pour les clés.
Il y a deux points importants à retenir concernant les clés du dictionnaire -
(a)Plus d'une entrée par clé n'est pas autorisée. Ce qui signifie qu'aucune clé en double n'est
autorisée. Lorsque des clés en double sont rencontrées pendant l'affectation, la dernière
affectation l'emporte. Par exemple -

#!/usr/bin/python

dict = {'Name': 'Zara', 'Age': 7, 'Name': 'Manni'}

print "dict['Name']: ", dict['Name']

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

dict['Name']: Manni

(b)Les clés doivent être immuables. Ce qui signifie que vous pouvez utiliser des chaînes, des
nombres ou des tuples comme clés de dictionnaire, mais quelque chose comme ['key'] n'est pas
autorisé. Voici un exemple simple -

#!/usr/bin/python

dict = {['Name']: 'Zara', 'Age': 7}

print "dict['Name']: ", dict['Name']

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

Traceback (most recent call last):

File "[Link]", line 3, in <module>
dict = {['Name']: 'Zara', 'Age': 7};
TypeError: list objects are unhashable
Python - Tableau 2D
Un tableau à deux dimensions est un tableau dans un tableau. C'est un tableau de tableaux.
Dans ce type de tableau, la position d'un élément de données est référencée par deux indices au
lieu d'un. Il représente donc une table avec des lignes et des colonnes de données. Dans
l'exemple ci-dessous d'un tableau à deux dimensions, observez que chaque élément du tableau
lui-même est également un tableau.
Prenons l'exemple de l'enregistrement des températures 4 fois par jour, tous les jours. Parfois,
l'instrument d'enregistrement peut être défectueux et nous ne parvenons pas à enregistrer les
données. Ces données pour 4 jours peuvent être présentées sous forme de tableau
bidimensionnel comme ci-dessous.

Day 1 - 11 12 5 2
Day 2 - 15 6 10
Day 3 - 10 8 12 5
Day 4 - 12 15 8 6

Les données ci-dessus peuvent être représentées sous forme de tableau à deux dimensions
comme ci-dessous.

T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]]

Accès aux valeurs dans un tableau

bidimensionnel
Les éléments de données dans deux tableaux dimesnional sont accessibles à l'aide de deux
indices. Un index faisant référence au tableau principal ou parent et un autre index faisant
référence à la position de l'élément de données dans le tableau interne. Si nous ne mentionnons
qu'un seul index, tout le tableau interne est imprimé pour cette position d'index. L'exemple ci-
dessous illustre son fonctionnement.

from array import *

T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]]

print(T[0])

print(T[1][2])

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[11, 12, 5, 2]
10
Pour imprimer l'ensemble du tableau bidimensionnel, nous pouvons utiliser python for loop
comme indiqué ci-dessous. Nous utilisons la fin de la ligne pour imprimer les valeurs dans
différentes lignes.

from array import *

T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]]

for r in T:
for c in r:
print(c,end = " ")
print()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

11 12 5 2
15 6 10
10 8 12 5
12 15 8 6

Insertion de valeurs dans un tableau

bidimensionnel
Nous pouvons insérer de nouveaux éléments de données à une position spécifique en utilisant la
méthode insert () et en spécifiant l'index.
Dans l'exemple ci-dessous, un nouvel élément de données est inséré à la position d'index 2.

from array import *

T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]]

[Link](2, [0,5,11,13,6])

for r in T:
for c in r:
print(c,end = " ")
print()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

11 12 5 2
15 6 10
0 5 11 13 6
10 8 12 5
12 15 8 6

Mise à jour des valeurs dans un tableau

bidimensionnel
Nous pouvons mettre à jour l'ensemble du tableau interne ou certains éléments de données
spécifiques du tableau interne en réaffectant les valeurs à l'aide de l'index du tableau.

from array import *

T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]]

T[2] = [11,9]
T[0][3] = 7
for r in T:
for c in r:
print(c,end = " ")
print()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

11 12 5 7
15 6 10
11 9
12 15 8 6

Suppression des valeurs dans un tableau

bidimensionnel
Nous pouvons supprimer tout le tableau interne ou certains éléments de données spécifiques du
tableau interne en réaffectant les valeurs à l'aide de la méthode del () avec index. Mais au cas où
vous auriez besoin de supprimer des éléments de données spécifiques dans l'un des tableaux
internes, utilisez le processus de mise à jour décrit ci-dessus.

from array import *

T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]]

del T[3]
for r in T:
for c in r:
print(c,end = " ")
print()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

11 12 5 2
15 6 10
10 8 12 5

Python - Matrice
Matrix est un cas particulier de tableau bidimensionnel où chaque élément de données est
strictement de même taille. Ainsi, chaque matrice est également un tableau à deux dimensions
mais pas l'inverse. Les matrices sont des structures de données très importantes pour de
nombreux calculs mathématiques et scientifiques. Comme nous l'avons déjà discuté dans le
chapitre précédent, nous nous concentrerons sur les opérations de structure de données
spécifiques aux matrices dans ce chapitre.
Nous utilisons également le package numpy pour la manipulation des données matricielles.

Exemple de matrice
Prenons le cas de l'enregistrement de la température pendant 1 semaine mesurée le matin, le
midi, le soir et le midi. Il peut être présenté comme une matrice 7X5 en utilisant un tableau et la
méthode de remodelage disponible dans numpy.

from numpy import *

a = array([['Mon',18,20,22,17],['Tue',11,18,21,18],
['Wed',15,21,20,19],['Thu',11,20,22,21],
['Fri',18,17,23,22],['Sat',12,22,20,18],
['Sun',13,15,19,16]])

m = reshape(a,(7,5))
print(m)

Les données ci-dessus peuvent être représentées sous forme de tableau à deux dimensions
comme ci-dessous.

[['Mon' '18' '20' '22' '17']

['Tue' '11' '18' '21' '18']
['Wed' '15' '21' '20' '19']
['Thu' '11' '20' '22' '21']
 ['Fri' '18' '17' '23' '22']
['Sat' '12' '22' '20' '18']
['Sun' '13' '15' '19' '16']]

Accéder aux valeurs dans une matrice

Les éléments de données d'une matrice sont accessibles à l'aide des index. La méthode d'accès
est la même que la façon dont les données sont accessibles dans un tableau à deux dimensions.

from numpy import *

m = array([['Mon',18,20,22,17],['Tue',11,18,21,18],
['Wed',15,21,20,19],['Thu',11,20,22,21],
['Fri',18,17,23,22],['Sat',12,22,20,18],
['Sun',13,15,19,16]])

# Print data for Wednesday

print(m[2])

# Print data for friday evening

print(m[4][3])

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

['Wed', 15, 21, 20, 19]

23

Ajouter une ligne

from numpy import *
m = array([['Mon',18,20,22,17],['Tue',11,18,21,18],
['Wed',15,21,20,19],['Thu',11,20,22,21],
['Fri',18,17,23,22],['Sat',12,22,20,18],
['Sun',13,15,19,16]])

m_r = append(m,[['Avg',12,15,13,11]],0)

print(m_r)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[['Mon' '18' '20' '22' '17']
['Tue' '11' '18' '21' '18']
['Wed' '15' '21' '20' '19']
['Thu' '11' '20' '22' '21']
['Fri' '18' '17' '23' '22']
['Sat' '12' '22' '20' '18']
['Sun' '13' '15' '19' '16']
['Avg' '12' '15' '13' '11']]

Ajouter une colonne

Nous pouvons ajouter une colonne à une matrice en utilisant la méthode insert (). ici nous
devons mentionner l'index où nous voulons ajouter la colonne et un tableau contenant les
nouvelles valeurs des colonnes ajoutées. Dans l'exemple ci-dessous, nous ajoutons une nouvelle
colonne à la cinquième position à partir du début.

from numpy import *

m = array([['Mon',18,20,22,17],['Tue',11,18,21,18],
['Wed',15,21,20,19],['Thu',11,20,22,21],
['Fri',18,17,23,22],['Sat',12,22,20,18],
['Sun',13,15,19,16]])

m_c = insert(m,[5],[[1],[2],[3],[4],[5],[6],[7]],1)

print(m_c)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[['Mon' '18' '20' '22' '17' '1']

['Tue' '11' '18' '21' '18' '2']
['Wed' '15' '21' '20' '19' '3']
['Thu' '11' '20' '22' '21' '4']
['Fri' '18' '17' '23' '22' '5']
['Sat' '12' '22' '20' '18' '6']
['Sun' '13' '15' '19' '16' '7']]

Supprimer une ligne d'une matrice

Nous pouvons supprimer une ligne d'une matrice en utilisant la méthode delete (). Nous devons
spécifier l'index de la ligne ainsi que la valeur de l'axe qui est 0 pour une ligne et 1 pour une
colonne.
from numpy import *
m = array([['Mon',18,20,22,17],['Tue',11,18,21,18],
['Wed',15,21,20,19],['Thu',11,20,22,21],
['Fri',18,17,23,22],['Sat',12,22,20,18],
['Sun',13,15,19,16]])

m = delete(m,[2],0)

print(m)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[['Mon' '18' '20' '22' '17']

['Tue' '11' '18' '21' '18']
['Thu' '11' '20' '22' '21']
['Fri' '18' '17' '23' '22']
['Sat' '12' '22' '20' '18']
['Sun' '13' '15' '19' '16']]

Supprimer une colonne d'une matrice

Nous pouvons supprimer une colonne d'une matrice en utilisant la méthode delete (). Nous
devons spécifier l'index de la colonne ainsi que la valeur de l'axe qui est 0 pour une ligne et 1
pour une colonne.

from numpy import *

m = array([['Mon',18,20,22,17],['Tue',11,18,21,18],
['Wed',15,21,20,19],['Thu',11,20,22,21],
['Fri',18,17,23,22],['Sat',12,22,20,18],
['Sun',13,15,19,16]])

m = delete(m,s_[2],1)

print(m)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[['Mon' '18' '22' '17']

['Tue' '11' '21' '18']
['Wed' '15' '20' '19']
 ['Thu' '11' '22' '21']
['Fri' '18' '23' '22']
['Sat' '12' '20' '18']
['Sun' '13' '19' '16']]

Mettre à jour une ligne dans une matrice

Pour mettre à jour les valeurs dans la ligne d'une matrice, nous réaffectons simplement les
valeurs à l'index de la ligne. Dans l'exemple ci-dessous, toutes les valeurs des données de
thrursday sont marquées comme zéro. L'index de cette ligne est 3.

from numpy import *

m = array([['Mon',18,20,22,17],['Tue',11,18,21,18],
['Wed',15,21,20,19],['Thu',11,20,22,21],
['Fri',18,17,23,22],['Sat',12,22,20,18],
['Sun',13,15,19,16]])

m[3] = ['Thu',0,0,0,0]

print(m)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[['Mon' '18' '20' '22' '17']

['Tue' '11' '18' '21' '18']
['Wed' '15' '21' '20' '19']
['Thu' '0' '0' '0' '0']
['Fri' '18' '17' '23' '22']
['Sat' '12' '22' '20' '18']
['Sun' '13' '15' '19' '16']]

Python - Ensembles
Mathématiquement, un ensemble est une collection d'éléments qui ne sont pas dans un ordre
particulier. Un ensemble Python est similaire à cette définition mathématique avec les conditions
supplémentaires ci-dessous.
 Les éléments de l'ensemble ne peuvent pas être des doublons.
 Les éléments de l'ensemble sont immuables (ne peuvent pas être modifiés) mais
l'ensemble dans son ensemble est mutable.
 Il n'y a aucun index attaché à un élément dans un ensemble python. Ils ne prennent donc
en charge aucune opération d'indexation ou de découpage.
Définir les opérations
Les ensembles en python sont généralement utilisés pour des opérations mathématiques comme
l'union, l'intersection, la différence et le complément, etc. Nous pouvons créer un ensemble,
accéder à ses éléments et effectuer ces opérations mathématiques comme indiqué ci-dessous.

Créer un ensemble
Un ensemble est créé en utilisant la fonction set () ou en plaçant tous les éléments dans une
paire d'accolades.

Days=set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"])
Months={"Jan","Feb","Mar"}
Dates={21,22,17}
print(Days)
print(Months)
print(Dates)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant. Veuillez noter comment
l'ordre des éléments a changé dans le résultat.

set(['Wed', 'Sun', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])

set(['Jan', 'Mar', 'Feb'])
set([17, 21, 22])

Accéder aux valeurs d'un ensemble

Nous ne pouvons pas accéder aux valeurs individuelles dans un ensemble. Nous pouvons
uniquement accéder à tous les éléments ensemble comme indiqué ci-dessus. Mais nous
pouvons également obtenir une liste d'éléments individuels en parcourant l'ensemble.

Days=set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"])

for d in Days:
print(d)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant.

Wed
Sun
Fri
Tue
Mon
Thu
Sat

Ajout d'éléments à un ensemble

Nous pouvons ajouter des éléments à un ensemble en utilisant la méthode add (). Encore une
fois, comme indiqué, il n'y a pas d'index spécifique attaché à l'élément nouvellement ajouté.

Days=set(["Mon","Tue","Wed","Thu","Fri","Sat"])

[Link]("Sun")
print(Days)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant.

set(['Wed', 'Sun', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])

Suppression d'un élément d'un ensemble

Nous pouvons supprimer des éléments d'un ensemble en utilisant la méthode discard (). Encore
une fois, comme indiqué, il n'y a pas d'index spécifique attaché à l'élément nouvellement ajouté.

Days=set(["Mon","Tue","Wed","Thu","Fri","Sat"])

[Link]("Sun")
print(Days)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant.

set(['Wed', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])

Union d'ensembles
L'opération d'union sur deux ensembles produit un nouvel ensemble contenant tous les éléments
distincts des deux ensembles. Dans l'exemple ci-dessous, l'élément «Wed» est présent dans les
deux ensembles.

DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Wed","Thu","Fri","Sat","Sun"])
AllDays = DaysA|DaysB
print(AllDays)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant. Veuillez noter que le résultat
n'a qu'un seul «mariage».

set(['Wed', 'Fri', 'Tue', 'Mon', 'Thu', 'Sat'])

Intersection d'ensembles
L'opération d'intersection sur deux ensembles produit un nouvel ensemble contenant uniquement
les éléments communs des deux ensembles. Dans l'exemple ci-dessous, l'élément «Wed» est
présent dans les deux ensembles.

DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Wed","Thu","Fri","Sat","Sun"])
AllDays = DaysA & DaysB
print(AllDays)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant. Veuillez noter que le résultat
n'a qu'un seul «mariage».

set(['Wed'])

Différence d'ensembles
L'opération de différence sur deux ensembles produit un nouvel ensemble contenant uniquement
les éléments du premier ensemble et aucun du second ensemble. Dans l'exemple ci-dessous,
l'élément «Wed» est présent dans les deux ensembles, il ne sera donc pas trouvé dans
l'ensemble de résultats.

DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Wed","Thu","Fri","Sat","Sun"])
AllDays = DaysA - DaysB
print(AllDays)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant. Veuillez noter que le résultat
n'a qu'un seul «mariage».

set(['Mon', 'Tue'])

Comparer les ensembles

Nous pouvons vérifier si un ensemble donné est un sous-ensemble ou un sur-ensemble d'un
autre ensemble. Le résultat est Vrai ou Faux selon les éléments présents dans les ensembles.

DaysA = set(["Mon","Tue","Wed"])
DaysB = set(["Mon","Tue","Wed","Thu","Fri","Sat","Sun"])
SubsetRes = DaysA <= DaysB
SupersetRes = DaysB >= DaysA
print(SubsetRes)
print(SupersetRes)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant.

True
True

Python - Cartes
Python Maps, également appelé ChainMap, est un type de structure de données permettant de
gérer plusieurs dictionnaires ensemble en une seule unité. Le dictionnaire combiné contient les
paires clé et valeur dans une séquence spécifique éliminant les clés en double. La meilleure
utilisation de ChainMap est de rechercher dans plusieurs dictionnaires à la fois et d'obtenir le
mappage de paires clé-valeur approprié. Nous voyons également que ces ChainMaps se
comportent comme une structure de données de pile.

Créer une ChainMap

Nous créons deux dictionnaires et les regroupons en utilisant la méthode ChainMap de la
bibliothèque de collections. Ensuite, nous imprimons les clés et les valeurs du résultat de la
combinaison des dictionnaires. S'il existe des clés en double, seule la valeur de la première clé
est conservée.

import collections

dict1 = {'day1': 'Mon', 'day2': 'Tue'}

dict2 = {'day3': 'Wed', 'day1': 'Thu'}

res = [Link](dict1, dict2)

# Creating a single dictionary

print([Link],'\n')

print('Keys = {}'.format(list([Link]())))
print('Values = {}'.format(list([Link]())))
print()

# Print all the elements from the result

print('elements:')
for key, val in [Link]():
print('{} = {}'.format(key, val))
print()

# Find a specific value in the result

print('day3 in res: {}'.format(('day1' in res)))
print('day4 in res: {}'.format(('day4' in res)))

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant.

[{'day1': 'Mon', 'day2': 'Tue'}, {'day1': 'Thu', 'day3': 'Wed'}]

Keys = ['day1', 'day3', 'day2']

Values = ['Mon', 'Wed', 'Tue']

elements:
day1 = Mon
day3 = Wed
day2 = Tue

day3 in res: True

day4 in res: False

Réorganisation de la carte
Si nous changeons l'ordre des dictionnaires en les matraquant dans l'exemple ci-dessus, nous
voyons que la position des éléments est interchangée comme s'ils étaient dans une chaîne
continue. Cela montre à nouveau le comportement des cartes en tant que piles.

import collections

dict1 = {'day1': 'Mon', 'day2': 'Tue'}

dict2 = {'day3': 'Wed', 'day4': 'Thu'}

res1 = [Link](dict1, dict2)

print([Link],'\n')

res2 = [Link](dict2, dict1)

print([Link],'\n')

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant.

[{'day1': 'Mon', 'day2': 'Tue'}, {'day3': 'Wed', 'day4': 'Thu'}]

[{'day3': 'Wed', 'day4': 'Thu'}, {'day1': 'Mon', 'day2': 'Tue'}]

Mise à jour de la carte

Lorsque l'élément du dictionnaire est mis à jour, le résultat est instantanément mis à jour dans le
résultat de ChainMap. Dans l'exemple ci-dessous, nous voyons que la nouvelle valeur mise à
jour se reflète dans le résultat sans appliquer à nouveau explicitement la méthode ChainMap.

import collections

dict1 = {'day1': 'Mon', 'day2': 'Tue'}

dict2 = {'day3': 'Wed', 'day4': 'Thu'}

res = [Link](dict1, dict2)

print([Link],'\n')

dict2['day4'] = 'Fri'

print([Link],'\n')

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant.

[{'day1': 'Mon', 'day2': 'Tue'}, {'day3': 'Wed', 'day4': 'Thu'}]

[{'day1': 'Mon', 'day2': 'Tue'}, {'day3': 'Wed', 'day4': 'Fri'}]

Python - Listes liées

Une liste chaînée est une séquence d'éléments de données, qui sont connectés entre eux via
des liens. Chaque élément de données contient une connexion à un autre élément de données
sous la forme d'un pointeur. Python n'a pas de listes liées dans sa bibliothèque standard. Nous
implémentons le concept de listes chaînées en utilisant le concept de nœuds comme discuté
dans le chapitre précédent. Nous avons déjà vu comment nous créons une classe de nœuds et
comment parcourir les éléments d'un nœud. Dans ce chapitre, nous allons étudier les types de
listes liées connues sous le nom de listes liées individuellement. Dans ce type de structure de
données, il n'y a qu'un seul lien entre deux éléments de données. Nous créons une telle liste et
créons des méthodes supplémentaires pour insérer, mettre à jour et supprimer des éléments de
la liste.

Création d'une liste liée

Une liste chaînée est créée en utilisant la classe de nœuds que nous avons étudiée dans le
dernier chapitre. Nous créons un objet Node et créons une autre classe pour utiliser cet objet
ode. Nous transmettons les valeurs appropriées à l'objet node pour pointer vers les éléments de
données suivants. Le programme ci-dessous crée la liste liée avec trois éléments de données.
Dans la section suivante, nous verrons comment parcourir la liste chaînée.

class Node:
def __init__(self, dataval=None):
[Link] = dataval
[Link] = None

class SLinkedList:
def __init__(self):
[Link] = None

list1 = SLinkedList()
[Link] = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
[Link] = e2

# Link second Node to third node

[Link] = e3

Traverser une liste liée

Les listes chaînées isolées peuvent être parcourues uniquement dans le sens de marche à partir
du premier élément de données. Nous imprimons simplement la valeur de l'élément de données
suivant en attribuant le pointeur du nœud suivant à l'élément de données actuel.

class Node:
def __init__(self, dataval=None):
[Link] = dataval
[Link] = None

class SLinkedList:
def __init__(self):
[Link] = None

def listprint(self):
printval = [Link]
 while printval is not None:
print ([Link])
printval = [Link]

list = SLinkedList()
[Link] = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node

[Link] = e2

# Link second Node to third node

[Link] = e3

[Link]()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant:

Mon
Tue
Wed

Insertion dans une liste liée

L'insertion d'un élément dans la liste liée implique la réaffectation des pointeurs des nœuds
existants au nœud nouvellement inséré. Selon que le nouvel élément de données est inséré au
début, au milieu ou à la fin de la liste chaînée, nous avons les scénarios ci-dessous.

Insertion au début de la liste liée

Cela implique de pointer le pointeur suivant du nouveau nœud de données vers l'en-tête actuel
de la liste liée. Ainsi, la tête actuelle de la liste liée devient le deuxième élément de données et le
nouveau nœud devient la tête de la liste liée.

class Node:
def __init__(self, dataval=None):
[Link] = dataval
[Link] = None
class SLinkedList:
def __init__(self):
[Link] = None

# Print the linked list

def listprint(self):
printval = [Link]
while printval is not None:
print ([Link])
printval = [Link]
def AtBegining(self,newdata):
NewNode = Node(newdata)

# Update the new nodes next val to existing node

[Link] = [Link]
[Link] = NewNode

list = SLinkedList()
[Link] = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

[Link] = e2
[Link] = e3

[Link]("Sun")

[Link]()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant:

Sun
Mon
Tue
Wed
Insertion à la fin de la liste liée
Cela implique de pointer le pointeur suivant du dernier nœud actuel de la liste liée vers le
nouveau nœud de données. Ainsi, le dernier nœud actuel de la liste liée devient l'avant-dernier
nœud de données et le nouveau nœud devient le dernier nœud de la liste liée.

class Node:
def __init__(self, dataval=None):
[Link] = dataval
[Link] = None

class SLinkedList:
def __init__(self):
[Link] = None

# Function to add newnode

def AtEnd(self, newdata):
NewNode = Node(newdata)
if [Link] is None:
[Link] = NewNode
return
laste = [Link]
while([Link]):
laste = [Link]
[Link]=NewNode

# Print the linked list

def listprint(self):
printval = [Link]
while printval is not None:
print ([Link])
printval = [Link]

list = SLinkedList()
[Link] = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
[Link] = e2
[Link] = e3

[Link]("Thu")

[Link]()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant:

Mon
Tue
Wed
Thu

Insertion entre deux nœuds de données

Cela implique de modifier le pointeur d'un nœud spécifique pour qu'il pointe vers le nouveau
nœud. Cela est possible en passant à la fois le nouveau nœud et le nœud existant après quoi le
nouveau nœud sera inséré. Nous définissons donc une classe supplémentaire qui changera le
pointeur suivant du nouveau nœud vers le pointeur suivant du nœud central. Attribuez ensuite le
nouveau nœud au pointeur suivant du nœud du milieu.

class Node:
def __init__(self, dataval=None):
[Link] = dataval
[Link] = None

class SLinkedList:
def __init__(self):
[Link] = None

# Function to add node

def Inbetween(self,middle_node,newdata):
if middle_node is None:
print("The mentioned node is absent")
return

NewNode = Node(newdata)
 [Link] = middle_node.nextval
middle_node.nextval = NewNode

# Print the linked list

def listprint(self):
printval = [Link]
while printval is not None:
print ([Link])
printval = [Link]

list = SLinkedList()
[Link] = Node("Mon")
e2 = Node("Tue")
e3 = Node("Thu")

[Link] = e2
[Link] = e3

[Link]([Link],"Fri")

[Link]()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant:

Mon
Tue
Fri
Thu

Supprimer un élément d'une liste aimée

Nous pouvons supprimer un nœud existant en utilisant la clé de ce nœud. Dans le programme ci-
dessous, nous localisons le nœud précédent du nœud qui doit être supprimé. Puis pointez le
pointeur suivant de ce nœud vers le nœud suivant du nœud à supprimer.

class Node:
def __init__(self, data=None):
[Link] = data
 [Link] = None

class SLinkedList:
def __init__(self):
[Link] = None

def Atbegining(self, data_in):

NewNode = Node(data_in)
[Link] = [Link]
[Link] = NewNode

# Function to remove node

def RemoveNode(self, Removekey):

HeadVal = [Link]

if (HeadVal is not None):

if ([Link] == Removekey):
[Link] = [Link]
HeadVal = None
return

while (HeadVal is not None):

if [Link] == Removekey:
break
prev = HeadVal
HeadVal = [Link]

if (HeadVal == None):
return

[Link] = [Link]

HeadVal = None

def LListprint(self):
 printval = [Link]
while (printval):
print([Link]),
printval = [Link]

llist = SLinkedList()
[Link]("Mon")
[Link]("Tue")
[Link]("Wed")
[Link]("Thu")
[Link]("Tue")
[Link]()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant:

Thu
Wed
Mon

Python - Pile
Dans le dictionnaire anglais, le mot pile signifie disposer les objets sur un autre. C'est de la
même manière que la mémoire est allouée dans cette structure de données. Il stocke les
éléments de données de la même manière qu'un tas d'assiettes sont stockées les unes au-
dessus des autres dans la cuisine. Ainsi, la structure de données de pile permet des opérations à
une extrémité qui peut être appelée en haut de la pile. Nous pouvons ajouter des éléments ou
supprimer des éléments uniquement à partir de ce et de la pile.
Dans une pile, l'élément inséré en dernier dans la séquence sortira en premier car nous ne
pouvons retirer que du haut de la pile. Cette fonction est connue sous le nom de fonction Last in
First Out (LIFO). Les opérations d'ajout et de suppression des éléments sont
appeléesPUSH et POP. Dans le programme suivant, nous l'implémentons en tant que fonctions
d'ajout et de suppression. Nous supprimons une liste vide et utilisons les méthodes append () et
pop () pour ajouter et supprimer les éléments de données.

POUSSER dans une pile

class Stack:

def __init__(self):
[Link] = []
 def add(self, dataval):
# Use list append method to add element
if dataval not in [Link]:
[Link](dataval)
return True
else:
return False
# Use peek to look at the top of the stack

def peek(self):
return [Link][-1]

AStack = Stack()
[Link]("Mon")
[Link]("Tue")
[Link]()
print([Link]())
[Link]("Wed")
[Link]("Thu")
print([Link]())

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant:

Tue
Thu

POP à partir d'une pile

Comme nous savons que nous ne pouvons supprimer que l'élément de données le plus haut de
la pile, nous implémentons un programme python qui fait cela. La fonction de suppression du
programme suivant renvoie l'élément le plus haut. nous vérifions l'élément supérieur en calculant
d'abord la taille de la pile, puis nous utilisons la méthode intégrée pop () pour trouver l'élément le
plus haut.

class Stack:

def __init__(self):
[Link] = []

def add(self, dataval):

# Use list append method to add element
if dataval not in [Link]:
[Link](dataval)
return True
else:
return False

# Use list pop method to remove element

def remove(self):
if len([Link]) <= 0:
return ("No element in the Stack")
else:
return [Link]()

AStack = Stack()
[Link]("Mon")
[Link]("Tue")
[Link]("Wed")
[Link]("Thu")
print([Link]())
print([Link]())

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant:

Thu
Wed

Python - File d'attente

Nous sommes familiers avec la file d'attente dans notre vie quotidienne en attendant un service.
La structure de données de la file d'attente signifie également la même chose lorsque les
éléments de données sont disposés dans une file d'attente. Le caractère unique de la file
d'attente réside dans la manière dont les éléments sont ajoutés et supprimés. Les éléments sont
autorisés à la fin mais supprimés de l'autre extrémité. C'est donc une méthode du premier entré,
premier sorti. Une file d'attente peut être implémentée en utilisant une liste python où nous
pouvons utiliser les méthodes insert () et pop () pour ajouter et supprimer des éléments. Il n'y a
pas d'insertion car les éléments de données sont toujours ajoutés à la fin de la file d'attente.

Ajout d'éléments à une file d'attente

Dans l'exemple ci-dessous, nous créons une classe de file d'attente dans laquelle nous
implémentons la méthode First-in-First-Out. Nous utilisons la méthode d'insertion intégrée pour
ajouter des éléments de données.
class Queue:

def __init__(self):
[Link] = list()

def addtoq(self,dataval):
# Insert method to add element
if dataval not in [Link]:
[Link](0,dataval)
return True
return False

def size(self):
return len([Link])

TheQueue = Queue()
[Link]("Mon")
[Link]("Tue")
[Link]("Wed")
print([Link]())

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

Suppression d'un élément d'une file

d'attente
Dans l'exemple ci-dessous, nous créons une classe de file d'attente dans laquelle nous insérons
les données, puis supprimons les données à l'aide de la méthode pop intégrée.
.

class Queue:

def __init__(self):
[Link] = list()

def addtoq(self,dataval):
# Insert method to add element
if dataval not in [Link]:
[Link](0,dataval)
return True
return False
# Pop method to remove element
def removefromq(self):
if len([Link])>0:
return [Link]()
return ("No elements in Queue!")

TheQueue = Queue()
[Link]("Mon")
[Link]("Tue")
[Link]("Wed")
print([Link]())
print([Link]())

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

Mon
Tue

Python - Dequeue
Une file d'attente à deux extrémités, ou deque, prend en charge l'ajout et la suppression
d'éléments de chaque extrémité. Les piles et les files d'attente les plus couramment utilisées sont
des formes dégénérées de deques, où les entrées et les sorties sont limitées à une seule
extrémité.

import collections

DoubleEnded = [Link](["Mon","Tue","Wed"])

[Link]("Thu")

print ("Appended at right - ")

print (DoubleEnded)

[Link]("Sun")
print ("Appended at right at left is - ")
print (DoubleEnded)

[Link]()

print ("Deleting from right - ")

print (DoubleEnded)

[Link]()

print ("Deleting from left - ")

print (DoubleEnded)
Appended at right -
deque(['Mon', 'Tue', 'Wed', 'Thu'])
Appended at right at left is -
deque(['Sun', 'Mon', 'Tue', 'Wed', 'Thu'])
Deleting from right -
deque(['Sun', 'Mon', 'Tue', 'Wed'])
Deleting from left -
deque(['Mon', 'Tue', 'Wed'])

Python - Liste liée avancée

Nous avons déjà vu Linked List dans le chapitre précédent dans lequel il n'est possible que
d'avancer. Dans ce chapitre, nous voyons un autre type de liste chaînée dans laquelle il est
possible d'avancer et de reculer. Une telle liste liée est appelée liste à double lien. Voici les
caractéristiques de la liste à double lien.
 La liste doublement liée contient un élément de lien appelé premier et dernier.
 Chaque lien porte un (des) champ (s) de données et deux champs de lien appelés next et
prev.
 Chaque lien est lié à son lien suivant en utilisant son lien suivant.
 Chaque lien est lié à son lien précédent en utilisant son lien précédent.
 Le dernier lien porte un lien nul pour marquer la fin de la liste.

Créer une liste doublement liée

Nous créons une liste doublement liée en utilisant la classe Node. Maintenant, nous utilisons la
même approche que celle utilisée dans la liste à liaison unique, mais la tête et les pointeurs
suivants seront utilisés pour une affectation correcte pour créer deux liens dans chacun des
nœuds en plus des données présentes dans le nœud.

class Node:
 def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

class doubly_linked_list:

def __init__(self):
[Link] = None

# Adding data elements

def push(self, NewVal):
NewNode = Node(NewVal)
[Link] = [Link]
if [Link] is not None:
[Link] = NewNode
[Link] = NewNode

# Print the Doubly Linked list

def listprint(self, node):
while (node is not None):
print([Link]),
last = node
node = [Link]

dllist = doubly_linked_list()
[Link](12)
[Link](8)
[Link](62)
[Link]([Link])

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

62 8 12
Insertion dans une liste doublement liée
ici, nous allons voir comment insérer un nœud dans la liste Doubly Link en utilisant le programme
suivant. Le programme utilise une méthode nommée insert qui insère le nouveau nœud à la
troisième position à partir de la tête de la liste doublement liée.

# Create the Node class

class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None

# Create the doubly linked list

class doubly_linked_list:

def __init__(self):
[Link] = None

# Define the push method to add elements

def push(self, NewVal):

NewNode = Node(NewVal)
[Link] = [Link]
if [Link] is not None:
[Link] = NewNode
[Link] = NewNode

# Define the insert method to insert the element

def insert(self, prev_node, NewVal):
if prev_node is None:
return
NewNode = Node(NewVal)
[Link] = prev_node.next
prev_node.next = NewNode
[Link] = prev_node
if [Link] is not None:
[Link] = NewNode
# Define the method to print the linked list
def listprint(self, node):
while (node is not None):
print([Link]),
last = node
node = [Link]

dllist = doubly_linked_list()
[Link](12)
[Link](8)
[Link](62)
[Link]([Link], 13)
[Link]([Link])

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

62 8 13 12

Ajout à une liste doublement liée

L'ajout à une liste doublement liée ajoutera l'élément à la fin.

# Create the node class

class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
# Create the doubly linked list class
class doubly_linked_list:

def __init__(self):
[Link] = None

# Define the push method to add elements at the begining

def push(self, NewVal):
NewNode = Node(NewVal)
 [Link] = [Link]
if [Link] is not None:
[Link] = NewNode
[Link] = NewNode

# Define the append method to add elements at the end

def append(self, NewVal):

NewNode = Node(NewVal)
[Link] = None
if [Link] is None:
[Link] = None
[Link] = NewNode
return
last = [Link]
while ([Link] is not None):
last = [Link]
[Link] = NewNode
[Link] = last
return

# Define the method to print

def listprint(self, node):
while (node is not None):
print([Link]),
last = node
node = [Link]

dllist = doubly_linked_list()
[Link](12)
[Link](9)
[Link](8)
[Link](62)
[Link](45)
[Link]([Link])

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

62 8 12 9 45

Veuillez noter la position des éléments 9 et 45 pour l'opération d'ajout.

Python - Table de hachage

Les tables de hachage sont un type de structure de données dans lequel l'adresse ou la valeur
d'index de l'élément de données est générée à partir d'une fonction de hachage. Cela rend
l'accès aux données plus rapide car la valeur d'index se comporte comme une clé pour la valeur
de données. En d'autres termes, la table de hachage stocke des paires clé-valeur, mais la clé est
générée via une fonction de hachage.
Ainsi, la fonction de recherche et d'insertion d'un élément de données devient beaucoup plus
rapide car les valeurs de clé elles-mêmes deviennent l'index du tableau qui stocke les données.
En Python, les types de données Dictionary représentent l'implémentation des tables de
hachage. Les clés du dictionnaire satisfont aux exigences suivantes.
 Les clés du dictionnaire sont hachables, c'est-à-dire qu'elles sont générées par une
fonction de hachage qui génère un résultat unique pour chaque valeur unique fournie à la
fonction de hachage.
 L'ordre des éléments de données dans un dictionnaire n'est pas fixe.
Nous voyons donc l'implémentation de la table de hachage en utilisant les types de données de
dictionnaire comme ci-dessous.

Accéder aux valeurs dans le dictionnaire

Pour accéder aux éléments du dictionnaire, vous pouvez utiliser les crochets familiers avec la clé
pour obtenir sa valeur.

# Declare a dictionary
dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

# Accessing the dictionary with its key

print "dict['Name']: ", dict['Name']
print "dict['Age']: ", dict['Age']

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

dict['Name']: Zara
dict['Age']: 7

Mise à jour du dictionnaire

Vous pouvez mettre à jour un dictionnaire en ajoutant une nouvelle entrée ou une paire clé-
valeur, en modifiant une entrée existante ou en supprimant une entrée existante comme indiqué
ci-dessous dans l'exemple simple -

# Declare a dictionary
dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}
dict['Age'] = 8; # update existing entry
dict['School'] = "DPS School"; # Add new entry
print "dict['Age']: ", dict['Age']
print "dict['School']: ", dict['School']

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

When the above code is executed, it produces the following result −

dict['Age']: 8
dict['School']: DPS School

Supprimer les éléments du dictionnaire

Vous pouvez supprimer des éléments de dictionnaire individuels ou effacer tout le contenu d'un
dictionnaire. Vous pouvez également supprimer tout le dictionnaire en une seule opération. Pour
supprimer explicitement un dictionnaire entier, utilisez simplement l'instruction del. -

dict = {'Name': 'Zara', 'Age': 7, 'Class': 'First'}

del dict['Name']; # remove entry with key 'Name'
[Link](); # remove all entries in dict
del dict ; # delete entire dictionary

print "dict['Age']: ", dict['Age']

print "dict['School']: ", dict['School']

Cela produit le résultat suivant. Notez qu'une exception est levée car après del dict, le
dictionnaire n'existe plus -

dict['Age']:
Traceback (most recent call last):
File "[Link]", line 8, in
print "dict['Age']: ", dict['Age'];
TypeError: 'type' object is unsubscriptable

Python - Arbre binaire

L'arbre représente les nœuds connectés par des arêtes. C'est une structure de données non
linéaire. Il a les propriétés suivantes.
 Un nœud est marqué comme nœud racine.
 Chaque nœud autre que la racine est associé à un nœud parent.
 Chaque nœud peut avoir un numéro d'arbitrage de nœud chid.
Nous créons une structure de données arborescente en python en utilisant le concept os node
discuté précédemment. Nous désignons un nœud comme nœud racine, puis ajoutons d'autres
nœuds en tant que nœuds enfants. Ci-dessous se trouve le programme pour créer le nœud
racine.

Créer une racine

Nous créons simplement une classe Node et ajoutons assigner une valeur au nœud. Cela
devient un arbre avec seulement un nœud racine.

class Node:

def __init__(self, data):

[Link] = None
[Link] = None
[Link] = data

def PrintTree(self):
print([Link])

root = Node(10)

[Link]()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

10

Insertion dans un arbre

Pour insérer dans un arbre, nous utilisons la même classe de nœuds créée ci-dessus et y
ajoutons une méthode d'insertion La méthode d'insertion compare la valeur du nœud au nœud
parent et décide de l'ajouter en tant que nœud gauche ou nœud droit. Enfin, la méthode
PrintTree est utilisée pour imprimer l'arborescence.

class Node:

def __init__(self, data):

[Link] = None
[Link] = None
 [Link] = data

def insert(self, data):

# Compare the new value with the parent node
if [Link]:
if data < [Link]:
if [Link] is None:
[Link] = Node(data)
else:
[Link](data)
elif data > [Link]:
if [Link] is None:
[Link] = Node(data)
else:
[Link](data)
else:
[Link] = data

# Print the tree

def PrintTree(self):
if [Link]:
[Link]()
print( [Link]),
if [Link]:
[Link]()

# Use the insert method to add nodes

root = Node(12)
[Link](6)
[Link](14)
[Link](3)

[Link]()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

3 6 12 14
Traverser un arbre
L'arbre peut être parcouru en décidant d'une séquence pour visiter chaque nœud. Comme nous
pouvons clairement le voir, nous pouvons commencer à un nœud, puis visiter le sous-arbre
gauche en premier et le sous-arbre droit ensuite. Ou nous pouvons également visiter le sous-
arbre droit en premier et le sous-arbre gauche ensuite. En conséquence, il existe différents noms
pour ces méthodes de traversée d'arbre. Nous les étudions en détail dans le chapitre
implémentation des algorithmes de parcours d'arbre ici. Algorithmes de traversée des arbres

Python - Arbre de recherche

Un arbre de recherche binaire (BST) est un arbre dans lequel tous les nœuds suivent les
propriétés mentionnées ci-dessous - Le sous-arbre gauche d'un nœud a une clé inférieure ou
égale à la clé de son nœud parent. Le sous-arbre droit d'un nœud a une clé supérieure à la clé
de son nœud parent. Ainsi, BST divise tous ses sous-arbres en deux segments; le sous-arbre
gauche et le sous-arbre droit et peuvent être définis comme -

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

Rechercher une valeur dans un arbre B

La recherche d'une valeur dans une arborescence implique la comparaison de la valeur entrante
avec la valeur sortant des nœuds. Ici aussi, nous parcourons les nœuds de gauche à droite puis
enfin avec le parent. Si la valeur recherchée ne correspond à aucune des valeurs d'exitign, nous
renvoyons le message non trouvé, sinon le message trouvé est renvoyé.

class Node:

def __init__(self, data):

[Link] = None
[Link] = None
[Link] = data

# Insert method to create nodes

def insert(self, data):

if [Link]:
if data < [Link]:
if [Link] is None:
[Link] = Node(data)
else:
[Link](data)
 elif data > [Link]:
if [Link] is None:
[Link] = Node(data)
else:
[Link](data)
else:
[Link] = data
# findval method to compare the value with nodes
def findval(self, lkpval):
if lkpval < [Link]:
if [Link] is None:
return str(lkpval)+" Not Found"
return [Link](lkpval)
elif lkpval > [Link]:
if [Link] is None:
return str(lkpval)+" Not Found"
return [Link](lkpval)
else:
print(str([Link]) + ' is found')
# Print the tree
def PrintTree(self):
if [Link]:
[Link]()
print( [Link]),
if [Link]:
[Link]()

root = Node(12)
[Link](6)
[Link](14)
[Link](3)
print([Link](7))
print([Link](14))

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

7 Not Found
14 is found

Python - tas
Le tas est une arborescence spéciale dans laquelle chaque nœud parent est inférieur ou égal à
son nœud enfant. Ensuite, cela s'appelle un tas min. Si chaque nœud parent est supérieur ou
égal à son nœud enfant, il est appelé un tas max. Il est très utile d'implémenter des files d'attente
prioritaires où l'élément de file d'attente avec un poids plus élevé reçoit plus de priorité dans le
traitement. Une discussion détaillée sur les tas est disponible sur notre site Web ici. Veuillez
d'abord l'étudier si vous débutez dans la structure de données. Dans ce chapitre, nous verrons
l'implémentation de la structure de données de tas en utilisant python.

Créer un tas
Un tas est créé en utilisant la bibliothèque intégrée de python nommée heapq. Cette bibliothèque
a les fonctions appropriées pour effectuer diverses opérations sur la structure de données du tas.
Voici une liste de ces fonctions.
 heapify - Cette fonction convertit une liste régulière en un tas. Dans le tas résultant, le
plus petit élément est poussé à la position d'index 0. Mais le reste des éléments de
données ne sont pas nécessairement triés.
 heappush - Cette fonction ajoute un élément au tas sans modifier le tas actuel.
 heappop - Cette fonction renvoie le plus petit élément de données du tas.
 heapreplace - Cette fonction remplace le plus petit élément de données par une nouvelle
valeur fournie dans la fonction.

Créer un tas
Un tas est créé en utilisant simplement une liste d'éléments avec la fonction heapify. Dans
l'exemple ci-dessous, nous fournissons une liste d'éléments et la fonction heapify réorganise les
éléments amenant le plus petit élément à la première position.

import heapq

H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
[Link](H)
print(H)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[1, 3, 5, 78, 21, 45]

Insertion dans le tas

L'insertion d'un élément de données dans un tas ajoute toujours l'élément au dernier index. Mais
vous pouvez appliquer à nouveau la fonction heapify pour amener l'élément nouvellement ajouté
au premier index uniquement s'il est le plus petit en valeur. Dans l'exemple ci-dessous, nous
insérons le chiffre 8.

import heapq
H = [21,1,45,78,3,5]
# Covert to a heap
[Link](H)
print(H)
# Add element
[Link](H,8)
print(H)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[1, 3, 5, 78, 21, 45]

[1, 3, 5, 78, 21, 45, 8]

Suppression du tas
Vous pouvez supprimer l'élément au premier index en utilisant cette fonction. Dans l'exemple ci-
dessous, la fonction supprimera toujours l'élément à la position d'index 1.

import heapq

H = [21,1,45,78,3,5]
# Create the heap

[Link](H)
print(H)

# Remove element from the heap

[Link](H)

print(H)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[1, 3, 5, 78, 21, 45]

[3, 21, 5, 78, 45]
Remplacement dans un tas
La fonction heapreplace supprime toujours le plus petit élément du tas et insère le nouvel
élément entrant à un endroit non fixé par aucun ordre.

import heapq

H = [21,1,45,78,3,5]
# Create the heap

[Link](H)
print(H)

# Replace an element
[Link](H,6)
print(H)
[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]

Python - Graphiques
Un graphique est une représentation picturale d'un ensemble d'objets où certaines paires d'objets
sont reliées par des liens. Les objets interconnectés sont représentés par des points appelés
sommets et les liens qui relient les sommets sont appelés arêtes. Les différents termes et
fonctionnalités associés à un graphe sont décrits en détail dans notre tutoriel ici. Dans ce
chapitre, nous allons voir comment créer un graphique et y ajouter divers éléments de données à
l'aide d'un programme python. Voici les opérations de base que nous effectuons sur les
graphiques.
 Afficher les sommets du graphe
 Afficher les bords du graphique
 Ajouter un sommet
 Ajouter un bord
 Créer un graphique
Un graphique peut être facilement présenté à l'aide des types de données du dictionnaire python.
Nous représentons les sommets comme les clés du dictionnaire et la connexion entre les
sommets également appelés arêtes comme les valeurs du dictionnaire.
Jetez un œil au graphique suivant -
Dans le graphique ci-dessus
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

Nous pouvons présenter ce graphique dans un programme python comme ci-dessous.

# Create the dictionary with graph elements

graph = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}

# Print the graph

print(graph)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

{'c': ['a', 'd'], 'a': ['b', 'c'], 'e': ['d'], 'd': ['e'], 'b': ['a', 'd']}

Afficher les sommets du graphe

Pour afficher les sommets du graphe, nous trouvons simplement les clés du dictionnaire des
graphes. Nous utilisons la méthode keys ().

class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = []
[Link] = gdict

# Get the keys of the dictionary

def getVertices(self):
return list([Link]())

# Create the dictionary with graph elements

graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
 "c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}

g = graph(graph_elements)

print([Link]())

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

['d', 'b', 'e', 'c', 'a']

Afficher les bords du graphique

Trouver les arêtes du graphe est un peu plus compliqué que les sommets car nous devons
trouver chacune des paires de sommets qui ont une arête entre eux. Nous créons donc une liste
vide d'arêtes puis itérons les valeurs d'arêtes associées à chacun des sommets. Une liste est
formée contenant le groupe distinct d'arêtes trouvé à partir des sommets.

class graph:

def __init__(self,gdict=None):
if gdict is None:
gdict = {}
[Link] = gdict

def edges(self):
return [Link]()
# Find the distinct list of edges

def findedges(self):
edgename = []
for vrtx in [Link]:
for nxtvrtx in [Link][vrtx]:
if {nxtvrtx, vrtx} not in edgename:
[Link]({vrtx, nxtvrtx})
return edgename
# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}

g = graph(graph_elements)

print([Link]())

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[{'b', 'a'}, {'b', 'd'}, {'e', 'd'}, {'a', 'c'}, {'c', 'd'}]

Ajouter un sommet
L'ajout d'un sommet est simple où nous ajoutons une autre clé supplémentaire au dictionnaire
graphique.

class graph:

def __init__(self,gdict=None):
if gdict is None:
gdict = {}
[Link] = gdict

def getVertices(self):
return list([Link]())

# Add the vertex as a key

def addVertex(self, vrtx):
if vrtx not in [Link]:
[Link][vrtx] = []

# Create the dictionary with graph elements

graph_elements = { "a" : ["b","c"],
 "b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}

g = graph(graph_elements)

[Link]("f")

print([Link]())

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

['f', 'e', 'b', 'a', 'c','d']

Ajout d'un bord

Ajouter une arête à un graphe existant implique de traiter le nouveau sommet comme un tuple et
de valider si l'arête est déjà présente. Sinon, le bord est ajouté.

class graph:

def __init__(self,gdict=None):
if gdict is None:
gdict = {}
[Link] = gdict

def edges(self):
return [Link]()
# Add the new edge

def AddEdge(self, edge):

edge = set(edge)
(vrtx1, vrtx2) = tuple(edge)
if vrtx1 in [Link]:
[Link][vrtx1].append(vrtx2)
else:
 [Link][vrtx1] = [vrtx2]

# List the edge names

def findedges(self):
edgename = []
for vrtx in [Link]:
for nxtvrtx in [Link][vrtx]:
if {nxtvrtx, vrtx} not in edgename:
[Link]({vrtx, nxtvrtx})
return edgename

# Create the dictionary with graph elements

graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}

g = graph(graph_elements)
[Link]({'a','e'})
[Link]({'a','c'})
print([Link]())

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[{'e', 'd'}, {'b', 'a'}, {'b', 'd'}, {'a', 'c'}, {'a', 'e'}, {'c', 'd'}]

Python - Conception d'algorithmes

L'algorithme est une procédure étape par étape, qui définit un ensemble d'instructions à exécuter
dans un certain ordre pour obtenir la sortie souhaitée. Les algorithmes sont généralement créés
indépendamment des langages sous-jacents, c'est-à-dire qu'un algorithme peut être implémenté
dans plus d'un langage de programmation.
Du point de vue de la structure des données, voici quelques catégories importantes d'algorithmes
-
 Search - Algorithme pour rechercher un élément dans une structure de données.
 Sort - Algorithme pour trier les éléments dans un certain ordre.
 Insert - Algorithme pour insérer un élément dans une structure de données.
 Update - Algorithme pour mettre à jour un élément existant dans une structure de
données.
  Delete - Algorithme pour supprimer un élément existant d'une structure de données.

Caractéristiques d'un algorithme

Toutes les procédures ne peuvent pas être appelées un algorithme. Un algorithme doit avoir les
caractéristiques suivantes -
 Unambiguous- L'algorithme doit être clair et sans ambiguïté. Chacune de ses étapes (ou
phases) et leurs entrées / sorties doivent être claires et ne doivent conduire qu'à une
seule signification.
 Input - Un algorithme doit avoir 0 ou plus d'entrées bien définies.
 Output - Un algorithme doit avoir une ou plusieurs sorties bien définies et doit
correspondre à la sortie souhaitée.
 Finiteness - Les algorithmes doivent se terminer après un nombre fini d'étapes.
 Feasibility - Doit être réalisable avec les ressources disponibles.
 Independent - Un algorithme devrait avoir des directions pas à pas, qui devraient être
indépendantes de tout code de programmation.

Comment écrire un algorithme?

Il n'y a pas de normes bien définies pour l'écriture d'algorithmes. Il dépend plutôt du problème et
des ressources. Les algorithmes ne sont jamais écrits pour prendre en charge un code de
programmation particulier.
Comme nous savons que tous les langages de programmation partagent des constructions de
code de base comme des boucles (do, for, while), flow-control (if-else), etc. Ces constructions
communes peuvent être utilisées pour écrire un algorithme.
Nous écrivons des algorithmes étape par étape, mais ce n'est pas toujours le cas. L'écriture
d'algorithme est un processus et est exécutée une fois que le domaine du problème est bien
défini. Autrement dit, nous devons connaître le domaine du problème, pour lequel nous
concevons une solution.

Exemple
Essayons d'apprendre l'écriture d'algorithmes en utilisant un exemple.
Problem - Concevez un algorithme pour ajouter deux nombres et afficher le résultat.

step 1 − START
step 2 − declare three integers a, b & c
step 3 − define values of a & b
step 4 − add values of a & b
step 5 − store output of step 4 to c
step 6 − print c
step 7 − STOP

Les algorithmes indiquent aux programmeurs comment coder le programme. Alternativement,

l'algorithme peut être écrit comme -

step 1 − START ADD

step 2 − get values of a & b
step 3 − c ← a + b
step 4 − display c
step 5 − STOP

Dans la conception et l'analyse d'algorithmes, la deuxième méthode est généralement utilisée

pour décrire un algorithme. Cela permet à l'analyste d'analyser facilement l'algorithme en
ignorant toutes les définitions indésirables. Il peut observer quelles opérations sont utilisées et
comment le processus se déroule.
L'écriture step numbers, est facultatif.
Nous concevons un algorithme pour obtenir une solution à un problème donné. Un problème
peut être résolu de plusieurs manières.

Par conséquent, de nombreux algorithmes de solution peuvent être dérivés pour un problème
donné. L'étape suivante consiste à analyser les algorithmes de solution proposés et à mettre en
œuvre la meilleure solution appropriée.

Python - Divisez pour conquérir

Dans l'approche de division pour conquérir, le problème en cours est divisé en sous-problèmes
plus petits, puis chaque problème est résolu indépendamment. Lorsque nous continuons à
diviser les sous-problèmes en sous-problèmes encore plus petits, nous pouvons éventuellement
atteindre un stade où plus aucune division n'est possible. Ces plus petits sous-problèmes
"atomiques" (fractions) sont résolus. La solution de tous les sous-problèmes est finalement
fusionnée afin d'obtenir la solution d'un problème original.
Globalement, nous pouvons comprendre divide-and-conquer approche dans un processus en
trois étapes.

Diviser / Pause
Cette étape consiste à diviser le problème en sous-problèmes plus petits. Les sous-problèmes
doivent représenter une partie du problème d'origine. Cette étape adopte généralement une
approche récursive pour diviser le problème jusqu'à ce qu'aucun sous-problème ne soit
davantage divisible. À ce stade, les sous-problèmes deviennent de nature atomique mais
représentent encore une partie du problème réel.

Conquérir / Résoudre
Cette étape reçoit beaucoup de sous-problèmes plus petits à résoudre. Généralement, à ce
niveau, les problèmes sont considérés comme «résolus» d'eux-mêmes.

Fusionner / Combiner
Lorsque les sous-problèmes plus petits sont résolus, cette étape les combine de manière
récursive jusqu'à ce qu'ils formulent une solution du problème d'origine. Cette approche
algorithmique fonctionne de manière récursive et les étapes de conquête et de fusion
fonctionnent si étroitement qu'elles apparaissent comme une seule.

Exemples
Le programme suivant est un exemple de divide-and-conquer approche de programmation où
la recherche binaire est implémentée en utilisant python.

Implémentation de la recherche binaire

Dans la recherche binaire, nous prenons une liste triée d'éléments et commençons à rechercher
un élément au milieu de la liste. Si la valeur de recherche correspond à la valeur du milieu de la
liste, nous terminons la recherche. Sinon, nous éliminons la moitié de la liste des éléments en
choisissant de procéder avec la moitié droite ou gauche de la liste en fonction de la valeur de
l'élément recherché. Ceci est possible car la liste est triée et c'est beaucoup plus rapide que la
recherche linéaire. Ici, nous divisons la liste donnée et conquérons en choisissant la moitié
appropriée de la liste. Nous répétons cette approche jusqu'à ce que nous trouvions l'élément ou
que nous concluions à son absence dans la liste.

def bsearch(list, val):

list_size = len(list) - 1

idx0 = 0
idxn = list_size
# Find the middle most value

while idx0 <= idxn:

midval = (idx0 + idxn)// 2

if list[midval] == val:
return midval
# Compare the value the middle most value
if val > list[midval]:
idx0 = midval + 1
else:
idxn = midval - 1

if idx0 > idxn:

return None
# Initialize the sorted list
list = [2,7,19,34,53,72]

# Print the search result

print(bsearch(list,72))
print(bsearch(list,11))

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant:

5
None
Python - Récursivité
La récursivité permet à une fonction de s'appeler. Les étapes fixes du code sont exécutées
encore et encore pour de nouvelles valeurs. Nous devons également définir des critères pour
décider de la fin de l'appel récursif. Dans l'exemple ci-dessous, nous voyons une approche
récursive de la recherche binaire. Nous prenons une liste triée et donnons sa plage d'index
comme entrée à la fonction récursive.

Recherche binaire utilisant la récursivité

Nous implémentons l'algorithme de recherche binaire en utilisant python comme indiqué ci-
dessous. Nous utilisons une liste ordonnée d'éléments et concevons une fonction récursive à
intégrer dans la liste avec l'index de début et de fin en entrée. Ensuite, la fonction de recherche
binaire s'appelle elle-même jusqu'à trouver l'élément recherché ou conclut à son absence dans la
liste.

def bsearch(list, idx0, idxn, val):

if (idxn < idx0):

return None
else:
midval = idx0 + ((idxn - idx0) // 2)
# Compare the search item with middle most value

if list[midval] > val:

return bsearch(list, idx0, midval-1,val)
elif list[midval] < val:
return bsearch(list, midval+1, idxn, val)
else:
return midval

list = [8,11,24,56,88,131]
print(bsearch(list, 0, 5, 24))
print(bsearch(list, 0, 5, 51))

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

2
None

Python - Retour en arrière

Le retour en arrière est une forme de récursivité. Mais cela implique de ne choisir qu'une option
parmi toutes les possibilités. Nous commençons par choisir une option et en revenons en arrière,
si nous atteignons un état où nous concluons que cette option spécifique ne donne pas la
solution requise. Nous répétons ces étapes en parcourant chaque option disponible jusqu'à ce
que nous obtenions la solution souhaitée.
Vous trouverez ci-dessous un exemple de recherche de tous les ordres possibles
d'arrangements d'un ensemble de lettres donné. Lorsque nous choisissons une paire, nous
appliquons un retour en arrière pour vérifier si cette paire exacte a déjà été créée ou non. Si elle
n'est pas déjà créée, la paire est ajoutée à la liste de réponses sinon elle est ignorée.

def permute(list, s):

if list == 1:
return s
else:
return [ y + x
for y in permute(1, s)
for x in permute(list - 1, s)
]

print(permute(1, ["a","b","c"]))
print(permute(2, ["a","b","c"]))

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

['a', 'b', 'c']

['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

Python - Algorithmes de traversée des

arbres
La traversée est un processus permettant de visiter tous les nœuds d'un arbre et peut également
imprimer leurs valeurs. Parce que tous les nœuds sont connectés via des bords (liens), nous
partons toujours du nœud racine (tête). Autrement dit, nous ne pouvons pas accéder de manière
aléatoire à un nœud dans un arbre. Il y a trois façons que nous utilisons pour traverser un arbre -
 Traversée en ordre
 Précommander Traversal
 Traversée post-commande

Traversée en ordre
Dans cette méthode de traversée, le sous-arbre gauche est visité en premier, puis la racine et
plus tard le sous-arbre droit. Nous devons toujours nous rappeler que chaque nœud peut
représenter un sous-arbre lui-même.
Dans le programme python ci-dessous, nous utilisons la classe Node pour créer des espaces
réservés pour le nœud racine ainsi que pour les nœuds gauche et droit. Ensuite, nous créons
une fonction d'insertion pour ajouter des données à l'arborescence. Enfin, la logique de traversée
Inorder est implémentée en créant une liste vide et en ajoutant le nœud de gauche en premier
suivi du nœud racine ou parent. Enfin, le nœud gauche est ajouté pour terminer le parcours
Inorder. Veuillez noter que ce processus est répété pour chaque sous-arbre jusqu'à ce que tous
les nœuds soient traversés.

class Node:

def __init__(self, data):

[Link] = None
[Link] = None
[Link] = data
# Insert Node
def insert(self, data):

if [Link]:
if data < [Link]:
if [Link] is None:
[Link] = Node(data)
else:
[Link](data)
elif data > [Link]:
if [Link] is None:
[Link] = Node(data)
else:
[Link](data)
else:
[Link] = data

# Print the Tree

def PrintTree(self):
if [Link]:
[Link]()
print( [Link]),
if [Link]:
[Link]()

# Inorder traversal
# Left -> Root -> Right
 def inorderTraversal(self, root):
res = []
if root:
res = [Link]([Link])
[Link]([Link])
res = res + [Link]([Link])
return res

root = Node(27)
[Link](14)
[Link](35)
[Link](10)
[Link](19)
[Link](31)
[Link](42)
print([Link](root))

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[10, 14, 19, 27, 31, 35, 42]

Précommander Traversal
Dans cette méthode de traversée, le nœud racine est visité en premier, puis le sous-arbre
gauche et enfin le sous-arbre droit.
Dans le programme python ci-dessous, nous utilisons la classe Node pour créer des espaces
réservés pour le nœud racine ainsi que pour les nœuds gauche et droit. Ensuite, nous créons
une fonction d'insertion pour ajouter des données à l'arborescence. Enfin, la logique de parcours
de précommande est implémentée en créant une liste vide et en ajoutant le nœud racine en
premier suivi du nœud gauche. Enfin, le nœud droit est ajouté pour terminer le parcours de
précommande. Veuillez noter que ce processus est répété pour chaque sous-arbre jusqu'à ce
que tous les nœuds soient traversés.

class Node:

def __init__(self, data):

[Link] = None
[Link] = None
[Link] = data
# Insert Node
 def insert(self, data):

if [Link]:
if data < [Link]:
if [Link] is None:
[Link] = Node(data)
else:
[Link](data)
elif data > [Link]:
if [Link] is None:
[Link] = Node(data)
else:
[Link](data)
else:
[Link] = data

# Print the Tree

def PrintTree(self):
if [Link]:
[Link]()
print( [Link]),
if [Link]:
[Link]()

# Preorder traversal
# Root -> Left ->Right
def PreorderTraversal(self, root):
res = []
if root:
[Link]([Link])
res = res + [Link]([Link])
res = res + [Link]([Link])
return res

root = Node(27)
[Link](14)
[Link](35)
[Link](10)
[Link](19)
[Link](31)
[Link](42)
print([Link](root))

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[27, 14, 10, 19, 35, 31, 42]

Traversée post-commande
Dans cette méthode de traversée, le nœud racine est visité en dernier, d'où le nom. Nous
traversons d'abord le sous-arbre gauche, puis le sous-arbre droit et enfin le nœud racine.
Dans le programme python ci-dessous, nous utilisons la classe Node pour créer des espaces
réservés pour le nœud racine ainsi que pour les nœuds gauche et droit. Ensuite, nous créons
une fonction d'insertion pour ajouter des données à l'arborescence. Enfin, la logique de traversée
post-ordre est implémentée en créant une liste vide et en ajoutant le nœud de gauche en premier
suivi du nœud de droite. Enfin, le nœud racine ou parent est ajouté pour terminer le parcours
post-ordre. Veuillez noter que ce processus est répété pour chaque sous-arbre jusqu'à ce que
tous les nœuds soient traversés.

class Node:

def __init__(self, data):

[Link] = None
[Link] = None
[Link] = data
# Insert Node
def insert(self, data):

if [Link]:
if data < [Link]:
if [Link] is None:
[Link] = Node(data)
else:
[Link](data)
elif data > [Link]:
if [Link] is None:
 [Link] = Node(data)
else:
[Link](data)
else:
[Link] = data

# Print the Tree

def PrintTree(self):
if [Link]:
[Link]()
print( [Link]),
if [Link]:
[Link]()

# Postorder traversal
# Left ->Right -> Root
def PostorderTraversal(self, root):
res = []
if root:
res = [Link]([Link])
res = res + [Link]([Link])
[Link]([Link])
return res

root = Node(27)
[Link](14)
[Link](35)
[Link](10)
[Link](19)
[Link](31)
[Link](42)
print([Link](root))

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[10, 19, 14, 31, 42, 35, 27]

Python - Algorithmes de tri
Le tri fait référence à l'organisation des données dans un format particulier. L'algorithme de tri
spécifie la manière d'organiser les données dans un ordre particulier. Les ordres les plus
courants sont dans l'ordre numérique ou lexicographique.
L'importance du tri réside dans le fait que la recherche de données peut être optimisée à un
niveau très élevé, si les données sont stockées de manière triée. Le tri est également utilisé pour
représenter les données dans des formats plus lisibles. Ci-dessous, nous voyons cinq de ces
implémentations de tri en python.
 Tri à bulles
 Tri par fusion
 Tri par insertion
 Tri de coquille
 Tri par sélection

Tri à bulles
Il s'agit d'un algorithme basé sur la comparaison dans lequel chaque paire d'éléments adjacents
est comparée et les éléments sont échangés s'ils ne sont pas dans l'ordre.

def bubblesort(list):

# Swap the elements to arrange in order

for iter_num in range(len(list)-1,0,-1):
for idx in range(iter_num):
if list[idx]>list[idx+1]:
temp = list[idx]
list[idx] = list[idx+1]
list[idx+1] = temp

list = [19,2,31,45,6,11,121,27]
bubblesort(list)
print(list)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[2, 6, 11, 19, 27, 31, 45, 121]

Tri par fusion

Le tri par fusion divise d'abord le tableau en deux moitiés égales, puis les combine de manière
triée.

def merge_sort(unsorted_list):
 if len(unsorted_list) <= 1:
return unsorted_list
# Find the middle point and devide it
middle = len(unsorted_list) // 2
left_list = unsorted_list[:middle]
right_list = unsorted_list[middle:]

left_list = merge_sort(left_list)
right_list = merge_sort(right_list)
return list(merge(left_list, right_list))

# Merge the sorted halves

def merge(left_half,right_half):

res = []
while len(left_half) != 0 and len(right_half) != 0:
if left_half[0] < right_half[0]:
[Link](left_half[0])
left_half.remove(left_half[0])
else:
[Link](right_half[0])
right_half.remove(right_half[0])
if len(left_half) == 0:
res = res + right_half
else:
res = res + left_half
return res

unsorted_list = [64, 34, 25, 12, 22, 11, 90]

print(merge_sort(unsorted_list))

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[11, 12, 22, 25, 34, 64, 90]

Tri par insertion
Le tri par insertion consiste à trouver le bon endroit pour un élément donné dans une liste triée.
Donc, au début, nous comparons les deux premiers éléments et les trions en les comparant.
Ensuite, nous choisissons le troisième élément et trouvons sa bonne position parmi les deux
éléments triés précédents. De cette façon, nous ajoutons progressivement plus d'éléments à la
liste déjà triée en les mettant à leur place.

def insertion_sort(InputList):
for i in range(1, len(InputList)):
j = i-1
nxt_element = InputList[i]
# Compare the current element with next one

while (InputList[j] > nxt_element) and (j >= 0):

InputList[j+1] = InputList[j]
j=j-1
InputList[j+1] = nxt_element

list = [19,2,31,45,30,11,121,27]
insertion_sort(list)
print(list)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[2, 11, 19, 27, 30, 31, 45, 121]

Tri de coquille
Shell Sort consiste à trier les éléments qui sont éloignés des autres. Nous trions une grande
sous-liste d'une liste donnée et continuons à réduire la taille de la liste jusqu'à ce que tous les
éléments soient triés. Le programme ci-dessous trouve l'écart en l'assimilant à la moitié de la
longueur de la taille de la liste, puis commence à trier tous les éléments qu'il contient. Ensuite,
nous continuons à réinitialiser l'écart jusqu'à ce que la liste entière soit triée.

def shellSort(input_list):

gap = len(input_list) // 2
while gap > 0:

for i in range(gap, len(input_list)):

temp = input_list[i]
 j = i
# Sort the sub list for this gap

while j >= gap and input_list[j - gap] > temp:

input_list[j] = input_list[j - gap]
j = j-gap
input_list[j] = temp

# Reduce the gap for the next element

gap = gap//2

list = [19,2,31,45,30,11,121,27]

shellSort(list)
print(list)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[2, 11, 19, 27, 30, 31, 45, 121]

Tri par sélection

Dans le tri par sélection, nous commençons par trouver la valeur minimale dans une liste donnée
et nous la déplaçons vers une liste triée. Ensuite, nous répétons le processus pour chacun des
éléments restants dans la liste non triée. L'élément suivant entrant dans la liste triée est comparé
aux éléments existants et placé à sa position correcte. Donc, à la fin, tous les éléments de la liste
non triée sont triés.

def selection_sort(input_list):

for idx in range(len(input_list)):

min_idx = idx
for j in range( idx +1, len(input_list)):
if input_list[min_idx] > input_list[j]:
min_idx = j
# Swap the minimum value with the compared value
 input_list[idx], input_list[min_idx] = input_list[min_idx],
input_list[idx]

l = [19,2,31,45,30,11,121,27]
selection_sort(l)
print(l)

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

[2, 11, 19, 27, 30, 31, 45, 121]

Python - Algorithmes de recherche

La recherche est une nécessité très basique lorsque vous stockez des données dans différentes
structures de données. L'approche la plus simple consiste à parcourir chaque élément de la
structure de données et à le faire correspondre à la valeur que vous recherchez. Ceci est connu
sous le nom de recherche linéaire. Il est inefficace et rarement utilisé, mais la création d'un
programme pour cela donne une idée de la façon dont nous pouvons implémenter certains
algorithmes de recherche avancés.

Recherche linéaire
Dans ce type de recherche, une recherche séquentielle est effectuée sur tous les éléments un
par un. Chaque élément est vérifié et si une correspondance est trouvée, cet élément particulier
est renvoyé, sinon la recherche se poursuit jusqu'à la fin de la structure de données.

def linear_search(values, search_for):

search_at = 0
search_res = False

# Match the value with each data element

while search_at < len(values) and search_res is False:
if values[search_at] == search_for:
search_res = True
else:
search_at = search_at + 1

return search_res

l = [64, 34, 25, 12, 22, 11, 90]

print(linear_search(l, 12))
print(linear_search(l, 91))
Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

True
False

Recherche d'interpolation
Cet algorithme de recherche fonctionne sur la position de palpage de la valeur requise. Pour que
cet algorithme fonctionne correctement, la collecte de données doit être triée et répartie de
manière égale. Initialement, la position de la sonde est la position de l'élément le plus au milieu
de la collection. Si une correspondance se produit, l'index de l'élément est renvoyé. Si l'élément
du milieu est supérieur à l'élément, la position de la sonde est à nouveau calculée dans le sous-
tableau à droite de l'élément du milieu. Sinon, l'élément est recherché dans le sous-tableau à
gauche de l'élément du milieu. Ce processus se poursuit également sur le sous-tableau jusqu'à
ce que la taille du sous-tableau soit réduite à zéro.
Il existe une formule spécifique pour calculer la position médiane qui est indiquée dans le
programme ci-dessous.

def intpolsearch(values,x ):
idx0 = 0
idxn = (len(values) - 1)

while idx0 <= idxn and x >= values[idx0] and x <= values[idxn]:

# Find the mid point

mid = idx0 +\
int(((float(idxn - idx0)/( values[idxn] - values[idx0]))
* ( x - values[idx0])))

# Compare the value at mid point with search value

if values[mid] == x:
return "Found "+str(x)+" at index "+str(mid)

if values[mid] < x:
idx0 = mid + 1
return "Searched element not in the list"

l = [2, 6, 11, 19, 27, 31, 45, 121]

print(intpolsearch(l, 2))

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

Found 2 at index 0

Python - Algorithmes de graphes

Les graphiques sont des structures de données très utiles pour résoudre de nombreux défis
mathématiques importants. Par exemple, la topologie de réseau informatique ou l'analyse des
structures moléculaires de composés chimiques. Ils sont également utilisés dans le trafic urbain
ou la planification d'itinéraire et même dans les langues humaines et leur grammaire. Toutes ces
applications ont le défi commun de parcourir le graphe en utilisant leurs arêtes et de s'assurer
que tous les nœuds des graphes sont visités. Il existe deux méthodes établies communes pour
effectuer cette traversée qui est décrite ci-dessous.

Profondeur première traversée:

Également appelé recherche en profondeur (DFS), cet algorithme parcourt un graphe dans un
mouvement de profondeur et utilise une pile pour se souvenir d'obtenir le sommet suivant pour
démarrer une recherche, lorsqu'une impasse se produit dans une itération. Nous implémentons
DFS pour un graphique en python en utilisant les types de données définis car ils fournissent les
fonctionnalités requises pour garder une trace des nœuds visités et non visités.

class graph:

def __init__(self,gdict=None):
if gdict is None:
gdict = {}
[Link] = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
if visited is None:
visited = set()
[Link](start)
print(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited

gdict = { "a" : set(["b","c"]),

"b" : set(["a", "d"]),
"c" : set(["a", "d"]),
"d" : set(["e"]),
"e" : set(["a"])
}
dfs(gdict, 'a')

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

a b d e c

Largeur première traversée

Également appelé recherche en largeur (BFS), cet algorithme parcourt un mouvement de largeur
de graphe et utilise une file d'attente pour se souvenir d'obtenir le sommet suivant pour démarrer
une recherche, lorsqu'une impasse se produit dans une itération. Veuillez visiter ce lien sur notre
site Web pour comprendre les détails des étapes BFS pour un graphique.
Nous implémentons BFS pour un graphique en python en utilisant la structure de données de file
d'attente évoquée précédemment. Lorsque nous continuons à visiter les nœuds non visités
adjacents et que nous les ajoutons à la file d'attente. Ensuite, nous commençons à retirer la file
d'attente uniquement du nœud qui n'a pas de nœuds non visités. Nous arrêtons le programme
lorsqu'il n'y a pas de prochain nœud adjacent à visiter.

import collections
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
[Link] = gdict

def bfs(graph, startnode):

# Track the visited and unvisited nodes using queue
seen, queue = set([startnode]), [Link]([startnode])
while queue:
vertex = [Link]()
marked(vertex)
for node in graph[vertex]:
if node not in seen:
[Link](node)
[Link](node)

def marked(n):
print(n)
# The graph dictionary
gdict = { "a" : set(["b","c"]),
"b" : set(["a", "d"]),
"c" : set(["a", "d"]),
"d" : set(["e"]),
"e" : set(["a"])
}

bfs(gdict, "a")

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant -

a c b d e

Python - Analyse des algorithmes

Analyse d'algorithme
L'efficacité d'un algorithme peut être analysée à deux étapes différentes, avant et après la mise
en œuvre. Ce sont les suivants -
 A Priori Analysis- Il s'agit d'une analyse théorique d'un algorithme. L'efficacité d'un
algorithme est mesurée en supposant que tous les autres facteurs, par exemple la
vitesse du processeur, sont constants et n'ont aucun effet sur l'implémentation.
 A Posterior Analysis- Il s'agit d'une analyse empirique d'un algorithme. L'algorithme
sélectionné est implémenté en utilisant le langage de programmation. Ceci est ensuite
exécuté sur la machine informatique cible. Dans cette analyse, des statistiques réelles
telles que le temps de fonctionnement et l'espace requis sont collectées.

Complexité de l'algorithme
Supposer X est un algorithme et n est la taille des données d'entrée, le temps et l'espace utilisés
par l'algorithme X sont les deux principaux facteurs qui décident de l'efficacité de X.
 Time Factor - Le temps est mesuré en comptant le nombre d'opérations clés telles que
des comparaisons dans l'algorithme de tri.
 Space Factor - L'espace est mesuré en comptant l'espace mémoire maximal requis par
l'algorithme.
La complexité d'un algorithme f(n) donne le temps de fonctionnement et / ou l'espace de
stockage requis par l'algorithme en termes de n comme la taille des données d'entrée.

Complexité spatiale
La complexité spatiale d'un algorithme représente la quantité d'espace mémoire requise par
l'algorithme dans son cycle de vie. L'espace requis par un algorithme est égal à la somme des
deux composantes suivantes -
  Une partie fixe qui est un espace nécessaire pour stocker certaines données et variables,
qui sont indépendantes de la taille du problème. Par exemple, les variables simples et les
constantes utilisées, la taille du programme, etc.
 Une partie variable est un espace requis par des variables, dont la taille dépend de la
taille du problème. Par exemple, allocation de mémoire dynamique, espace de pile de
récursivité, etc.
La complexité spatiale S (P) de tout algorithme P est S (P) = C + SP (I), où C est la partie fixe et
S (I) est la partie variable de l'algorithme, qui dépend de la caractéristique d'instance I. est un
exemple simple qui tente d'expliquer le concept -

Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop

Ici, nous avons trois variables A, B et C et une constante. D'où S (P) = 1 + 3. Maintenant,
l'espace dépend des types de données des variables données et des types de constantes et il
sera multiplié en conséquence.

Complexité temporelle
La complexité temporelle d'un algorithme représente le temps nécessaire à l'algorithme pour
s'exécuter jusqu'à son terme. Les exigences de temps peuvent être définies comme une fonction
numérique T (n), où T (n) peut être mesurée comme le nombre d'étapes, à condition que chaque
étape consomme un temps constant.

total est T (n) = c ∗ n, où c est le temps pris pour l'addition de deux bits. Ici, nous observons que
Par exemple, l'addition de deux entiers de n bits prend npas. Par conséquent, le temps de calcul

T (n) croît linéairement à mesure que la taille d'entrée augmente.

Python - Types d'algorithmes

L'efficacité et la précision des algorithmes doivent être analysées pour les comparer et choisir un
algorithme spécifique pour certains scénarios. Le processus de réalisation de cette analyse est
appelé analyse asymptotique. Il se réfère au calcul du temps d'exécution de toute opération en
unités mathématiques de calcul. Par exemple, le temps d'exécution d'une opération est calculé
comme f (n) et peut être pour une autre opération, il est calculé comme g (n2). Cela signifie que
le temps de fonctionnement de la première opération augmentera linéairement avec
l'augmentation de n et le temps de fonctionnement de la deuxième opération augmentera de
façon exponentielle lorsque n augmente. De même, le temps d'exécution des deux opérations
sera presque le même si n est significativement petit.
Habituellement, le temps requis par un algorithme relève de trois types -
 Meilleur cas - Temps minimum requis pour l'exécution du programme.
 Cas moyen - Temps moyen requis pour l'exécution du programme.
 Pire cas - Temps maximum requis pour l'exécution du programme.

Notations asymptotiques
Voici les notations asymptotiques couramment utilisées pour calculer la complexité du temps
d'exécution d'un algorithme.
 Ο Notation
 Notation Ω
  Notation θ

Big Oh Notation, Ο
La notation Ο (n) est la manière formelle d'exprimer la limite supérieure du temps d'exécution
d'un algorithme. Il mesure la complexité temporelle du cas le plus défavorable ou la durée la plus
longue qu'un algorithme peut prendre pour se terminer.

Par exemple, pour une fonction f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for
all n > n0. }

Notation oméga, Ω
La notation Ω (n) est la manière formelle d'exprimer la borne inférieure du temps d'exécution d'un
algorithme. Il mesure la meilleure complexité temporelle du cas ou le meilleur temps qu'un
algorithme peut prendre pour se terminer.

Par exemple, pour une fonction f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for
all n > n0. }
Notation thêta, θ
La notation θ (n) est la manière formelle d'exprimer à la fois la borne inférieure et la borne
supérieure du temps d'exécution d'un algorithme. Il est représenté comme suit -

θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all
n > n0. }

Notations asymptotiques courantes

Voici une liste de quelques notations asymptotiques courantes -

constant - Ο (1)

logarithmique - Ο (log n)

linéaire - Ο (n)

n log n - Ο (n log n)

quadratique - Ο (n 2 )

cubique - Ο (n 3 )

polynôme - n Ο (1)

exponentiel - 2 Ο (n)
Python - Classes d'algorithmes
Les algorithmes sont des étapes sans ambiguïté qui devraient nous donner une sortie bien
définie en traitant zéro ou plusieurs entrées. Cela conduit à de nombreuses approches dans la
conception et l'écriture des algorithmes. Il a été observé que la plupart des algorithmes peuvent
être classés dans les catégories suivantes.

Algorithmes gourmands
Les algorithmes gourmands tentent de trouver une solution optimale localisée, qui peut
éventuellement conduire à des solutions optimisées globalement. Cependant, les algorithmes
généralement gourmands ne fournissent pas de solutions globalement optimisées.
Les algorithmes gourmands recherchent donc une solution simple à ce moment-là sans tenir
compte de son impact sur les étapes futures. C'est similaire à la façon dont les humains résolvent
les problèmes sans passer par les détails complets des entrées fournies.
La plupart des algorithmes de mise en réseau utilisent l'approche gourmande. Voici une liste de
quelques-uns d'entre eux -
 Problème de vendeur itinérant
 Algorithme d'arbre couvrant minimal de Prim
 Algorithme d'arbre couvrant minimal de Kruskal
 Algorithme minimal Spanning Tree de Dijkstra

Diviser et conquérir
Cette classe d'algorithmes consiste à diviser le problème donné en sous-problèmes plus petits,
puis à résoudre chacun des sous-problèmes indépendamment. Lorsque le problème ne peut pas
être subdivisé davantage, nous commençons à fusionner la solution à chacun des sous-
problèmes pour arriver à la solution du problème le plus important.
Les exemples importants d'algorithmes de division et de conquête sont:
 Tri par fusion
 Tri rapide
 Algorithme d'arbre couvrant minimal de Kruskal
 Recherche binaire

Programmation dynamique
La programmation dynamique implique de diviser le plus gros problème en plus petits, mais
contrairement à diviser pour vaincre, elle n'implique pas de résoudre chaque sous-problème
indépendamment. Les résultats de sous-problèmes plus petits sont plutôt mémorisés et utilisés
pour des sous-problèmes similaires ou se chevauchant. La plupart du temps, ces algorithmes
sont utilisés pour l'optimisation. Avant de résoudre le sous-problème en cours, l'algorithme
dynamique essaiera d'examiner les résultats des sous-problèmes précédemment résolus.
les algorithmes dynamiques sont motivés pour une optimisation globale du problème et non pour
l'optimisation locale.
Les exemples importants d'algorithmes de programmation dynamique sont:
 Série de numéros de Fibonacci
 Problème de sac à dos
 La tour de Hanoi

Python - Analyse amortie

L'analyse amortie consiste à estimer le temps d'exécution de la séquence d'opérations dans un
programme sans prendre en considération l'étendue de la distribution des données dans les
valeurs d'entrée. Un exemple simple est que la recherche d'une valeur dans une liste triée est
plus rapide que dans une liste non triée. Si la liste est déjà triée, peu importe la répartition des
données. Mais bien sûr, la longueur de la liste a un impact car elle décide du nombre d'étapes
que l'algorithme doit franchir pour obtenir le résultat final.
Nous voyons donc que si le coût initial d'une seule étape d'obtention d'une liste triée est élevé,
alors le coût des étapes ultérieures de recherche d'un élément devient considérablement faible.
Ainsi, l'analyse amortie nous aide à trouver une limite sur le temps d'exécution le plus
défavorable pour une séquence d'opérations. Il existe trois approches de l'analyse amortie.
 Accounting Method- Il s'agit d'attribuer un coût à chaque opération effectuée. Si
l'opération réelle se termine plus rapidement que le temps imparti, un crédit positif est
accumulé dans l'analyse. Dans le scénario inverse, ce sera un crédit négatif. Pour garder
une trace de ces crédits accumulés, nous utilisons une structure de données en pile ou
en arbre. Les opérations qui sont effectuées tôt (comme le tri de la liste) ont un coût
amorti élevé, mais les opérations qui sont en retard dans la séquence ont un coût amorti
inférieur à mesure que le crédit accumulé est utilisé. Le coût amorti est donc une limite
supérieure du coût réel.
 Potential Method- Dans cette méthode, le crédit enregistré est utilisé pour des
opérations futures en tant que fonction mathématique de l'état de la structure de
données. L'évaluation de la fonction mathématique et le coût amorti doivent être égaux.
Ainsi, lorsque le coût réel est supérieur au coût amorti, le potentiel diminue et il est utilisé
pour des opérations futures qui sont coûteuses.
 Aggregate analysis - Dans cette méthode, nous estimons la limite supérieure du coût
total de n étapes. Le coût amorti est une simple division du coût total et du nombre
d'étapes (n).

Python - Justification de l'algorithme

Afin de prétendre qu'un algorithme est efficace, nous avons besoin de quelques outils
mathématiques comme preuve. Ces outils nous aident à fournir une explication
mathématiquement satisfaisante sur les performances et la précision des algorithmes. Vous
trouverez ci-dessous une liste de certains de ces outils mathématiques qui peuvent être utilisés
pour justifier un algorithme par rapport à un autre.
 Direct Proof:
C'est une vérification directe de l'énoncé en utilisant les calculs directs. Par exemple, la
somme de deux nombres pairs est toujours un nombre pair. Dans ce cas, ajoutez
simplement les deux nombres que vous étudiez et vérifiez le résultat comme pair.
 Proof by induction:
Ici, nous commençons par une instance spécifique d'une vérité, puis nous la généralisons
à toutes les valeurs possibles qui font partie de la vérité. L'approche consiste à prendre
un cas de vérité vérifiée, puis à prouver qu'elle est également vraie pour le cas suivant
pour la même condition donnée. Par exemple, tous les nombres positifs de la forme 2n-1
sont impairs. Nous le prouvons pour une certaine valeur de n, puis le prouvons pour la
valeur suivante de n. Cela établit l'énoncé comme généralement vrai par la preuve de
l'induction.
 Proof by contraposition:
Cette preuve est basée sur la condition Si Non A implique Non B alors A implique B. Un
exemple simple est que si le carré de n est pair, alors n doit être pair. Parce que si le
carré sur n n'est pas pair, alors n n'est pas pair.
 Proof by exhaustion:
Ceci est similaire à la preuve directe, mais il est établi en visitant chaque cas séparément
et en prouvant chacun d'eux. Un exemple d'une telle preuve est le théorème des quatre
couleurs.