Spé

Les Listes
Operation Fonction Detail Exemple

Indice de
Dernier List[0]

i
élément

ab
Indice de
Dernier List [ len(L)-1 ]

ar
élément

.insert (indice,

La
Ajouter un
‘’élément
élément
inseret’’)

e ():Supprime la
L= [1,2,3]
L_2= L.pop()
an
Supprimer un dernier d’élément Print(L)
.pop()
élément et (n):Supprime Print(L_2)
.pop(n)
stocker l’élément d’indice
m

n [1,2]
[3]
ah

L = [1,2,3]
L_2 = L.extend(L)
Ajouter les
Print(L)
rr

éléments de
.extend(L) Print(L_2)
liste a une
autre liste
de

[]
[1,2,3]
Ab

L= [1,2,3]
Ajouter un L= L.append(4)
élément a une .append(L) Print(L)
autre liste
[1,2,3,4]

L = [1,2,3]
Chercher Index = L.index(3)
l’indice d’un .index() Print (index)
élément
2
 Les tries
Les tries Comment il fonctionne Le code Python

Exemple :[5,2,9,1,6]
Etape1 : le plus petit

i
élément est 1 nous le

ab
place au début
Etape2 : nous
Tri par continuons avec la liste

ar
sélection restante [5,2,9,6]. Le plus
petit élément est 2
on le place après le 1

La
Même chose pour les
autres étapes pour avoir
[1,2,5,6,9]

e
an
On compare les paire et
Tri par Bulle on places les éléments a
ses place correcte
m

Exemple : [5,2,9,1,6]
ah

Etape 1 : on commence
par 5 que nous
considèrent comme une
rr

Tri par liste triée

insertion Etape 2 : nous prenons
la deuxième élément 2
de

et on le comparer avec
le 5 et on le place a ca
position correcte
Ab
Les tries Comment il fonctionne Le code Python

Devise les liste jusqu’à

on auras des liste
Tri par séparer qui contient un
fusion seul élément après on
comparer et fusionne
les élément

i
ab
ar
La
Tri par
fusion
récursive
e
an
m

Etape1 :On choisi un

ah

pivot et on place les

éléments plus petite
que le pivot a gauche
de pivot et les
rr

éléments plus grand

que le pivot à droite le
de

pivot maintenant est a

Tri rapide sa place correct
Étape 2 :on répète le
Ab

processus pour les

sous tableau situer
avant et après le pivot
Étape 3 :les sous
tableau maintenant
trier il reste a combiner
les sous tableau.
 Les arbres binaires

i
ab
ar
La
e
an
m
ah
rr
de
Ab
 Opération fonction / code NB

Arbre est vide A=[]

Valeur de
A[0]
Racine

Nœud A[1] ,A[2], …

def feuille (A,i) :

i
Si Nœud(A,i) if 2i+1 > len(A)-1 and 2i-1 > len(A)-1 :

ab
représente une return False
feuille else :
return True

ar
def parent(A,i) :

La
if A==[] or i==0:
Parent return ‘’ERROR’’ Return les parents de nœud
else:
return ((i-1)//2)

e
def left (A,i) :
an
if 2i+1 > len(A)-1:
Fils gauche de
return ‘’ERROR’’
noeud
else:
m

return A [2i+1]
ah

def Right (A,i) :

if 2i+1 > len(A)-1:
Fils droite de
return ‘’ERROR’’
nœud
else:
rr

return A [2i+2]
de

def is_root(A,i) :
Détermine Si le
if i == 0 :
nœud est un
return True
racine
Ab

else:
de l’arbre
return False

Teste
A[1]==[ ] and A[2]==[ ]
arbre = feuille

def Has_Left_Child(A,i):
Détermine Si le if 2i+1 > len(A)-1:
nœud a un fils return False
gauche else:
return True
 Opération fonction / Code NB

def Has_Left_Child(A,i):
Détermine Si le if 2i+2 > len (A)-1 :
nœud a un fils return False
droite else:
return True

def Nbr_noeud(A): On test que l’arbre n’est

if A == [ ] : pas vide

i
return 0 Si l’arbre est une feuille

ab
Nbr de nœud elif A[1] == [ ] and A[2] == [ ] : donc nbr de nœud égale
return 1 a 1 qui est le racine
else: à la fin (+1 pour le

ar
return nbr_noeud A[1] + nbr_noeud A[2]+1 racine)

def Nbr_noeud_interne(A):

La
if A == [ ]:
Ici si l’arbre est une feuille
Return 0
Nbr de nœud donc il a 0 nœud interne
elif A[1] == [ ] and A[2] == [ ] :
interne car le nœud interne à au
return 0
e
else:
moin un fils
an
return nbr_noeud A[1] +nbr_noeud A[2]+1

def nbr_feuille(A):
m

if A == [ ]:
return 0
Nbr de feuille elif A[1] == [ ] and A[2] == [ ] :
ah

return 1
else:
return nbr_feuille(A[1])+nbr_feuille(A[2])
rr

def somme_arbre(A):
de

If A == [ ]:
Somme d’arbre Return 0
Else:
Ab

Return somme_arbre(A[1])+somme_arbre(A[2])+A[0]

def recherche(A):
if A == [ ]:
return False
Chercher dans
elife x == A[0]:
un Arbre
return True
else:
return recherche(A[1]) or rechrche(A[2])
 Opération fonction / Code NB

def min_arbre(A):
if A == [ ]:
return float(‘’inf’’)
On peut écrire [return
Valeur min de else:
None] à la place de
l’arbre a = A[0]
[return float(‘’inf’’)]
b = min (A[1])
c = min (A[2])
return min (a,b,c)

i
ab
def hauteur(A) :
if A == [ ] :
return 0
Hauteur d’un

ar
else :
arbre
a = 1 + max_hauteur (A[1])
b = 1 + max_hauteur (A[2])

La
return max (a,b)

Parcoure infixe
Vous pouvez faire ça comme un exercice.
d’un arbre
e
an
Parcoure préfix
Vous pouvez faire ça comme un exercice.
d’un arbre
m

Parcoure
postfix Vous pouvez faire ça comme un exercice.
ah

d’un arbre

File: First In Last Out

rr

def affichage_largeur(A) : (FILO)

L = [A] Ajout(fin)=L. append(x)
while L! = [ ] :
de

Affiche les Supprimer(tête)=L.pop(0)

p = L.pop(0)
éléments de
print(p)
l’arbre avec
if p[1] != []:
Ab

méthode de
L.append(p[1])
FILE
if p[2] != []:
L.append(p[2])
return L
 Opération fonction / Code NB

def affichage_profendeur(A) : Pile: Last In First Out In

L = [A] (LIFO)
while L! = [ ] : Ajoute(tête)=L. append(x)
Affiche les Supprimer(fin)=L.pop()
p = L.pop()
éléments de
print(p)
l’arbre avec
if p[1] != []:
méthode de
L.append(p[1])
PILE
if p[2] != []:

i
L.append(p[2])

ab
return L

def mem(A,x) :

ar
If A == [ ]:
return False
La valeur de racine est
Chercher si x elife x == A[0]:

La
toujours superieur a la
appartient à return True
valeur de sous-arbre
l’arbre elife x < A[0]:
gauche
return mem (A[1],x)
else:
e return mem (A[2],x)
an
def Chereche_min(A):
if A == [ ]:
return False
m

Min d’un arbre elif A[1] == [ ]:

return A[0]
ah

else:
return Chereche_min(A[1])
rr

def Cherche_max(A):
if A == [ ]:
return False
de

Max d’un arbre elife A[1] == [ ]:

return A[0]
else:
Ab

return Cherche_max(A[2])
 Les graph
Type de graph

Graph non-orienter Graph orienter Graph pendrée

i
sommet

ab
50
17
20

ar
100

La
e
an
m
ah
rr

Arrêt
Lien
Arc
de
Ab
 Opération fonction / Code NB

def arrete(A,i,j) : 1 = il y a une liaison

if A[i][j] == 1: 0 = il n’y a pas de
L’arrête return True liaison
else:
return False

def voisin (A,i) :

Return la liste L== [ ]:

i
des voisin du for j in range(len(A)):

ab
sommet If A[i][j] == 1:
numéro i L.append(A):
return L

ar
def nbr_arret(A): S//2 :car qd on est
S=0 entrain de compter

La
for i in range(len(A)): les liaison on a
Nbr d’arret for j in range(len(A)): toujours 2 liaison
If A[i][j] == 1 (liaison entre 0 et 1 et
S+=1 liaison
e
return S//2 entre 1 et 0
an
def rajouter_arret[A,i,j) :
Ajouter les
A[i][j] == 1
arret
m

A[j][i] == 1
ah

Ordre de graph def ordre_graph(A):

A return len(A)
rr

def degree_sommet(A,s):
S=0
de

Degré de for I In range (len(A)):

sommet if A[i][j] == 1
S+=1
return S
Ab

def degree_max(A):
L=[ ]
Degré max for i in range( len(A)):
L.append(dedree_sommet(A,j)
return max(L)
 Opération fonction / Code NB

Vérifier si le
def sommet_adjacent(A,x,y) :
sommet est
return A[x][y] == 1
adjacent

def somme_isole(A,a) :
Vérifier si le for i in range(len(A)):
sommet est if A[a][i] ==1: a : un sommet
isolé Return False

i
return True

ab
def successeur_nonVisiter(A,s,test):
L=[ ] T= test ( enssemble

ar
Successeurs for j in range(0,len(A)): qui contient les
non-visités If A[s][j] == 1 and j not in T: sommet deja visités)
L.append(j) S : un sommet

La
return L

def parcours_largeur(A,s,T):

e
L=[s]
While L!=[ ] :
an
Affiche le graph p = L.pop(0)
en Parcours If p not in T:
BFS(FILE) print(p)
m

T.append(p)
L_1=succNonVisite(A,p,T)
L=L+L_1
ah

def parcours_profondeur(A,s,T)
L=[s]
rr

While L!=[ ] :
Affiche le graph p = L.pop()
de

enParcours If p not in T:
DFS(LIFO) print(p)
T.L.append(p)
L_1=succNonVisite(A,s,T)
Ab

L=L+L_1
 L’algèbre rationelle

i
ab
ar
La
e
an
m
ah
rr
de
Ab
Ab
de
rr
ah
m
an
e
La
ar
ab
i
 Pour plus d’info vous pouvez visiter notre groupe

WhatsApp:
https://chat.whatsapp.com/IbW4X9wXZvmG2PTpfOx7jp