Algorithmes et C appliqués aux Systèmes Numériques
Structure de données et algorithmes

John Samuel
CPE Lyon

Année: 2019-2020
Courriel: john(dot)samuel(at)cpe(dot)fr

Objectifs

1. Piles
2. Files
3. Graphes
4. Arbres
5. Algorithme de tri
6. Algorithme de recherche

Une liste de couleurs simplement chaînée

Une liste de couleurs doublement chaînée

Pile

• une structure de données
• basée sur le principe du dernier arrivé, premier sorti
• Opérations
  • Empiler
  • Dépiler
  • La pile est-elle vide?
  • Nombre d'éléments de la pile
  • Quel est l'élément de tête
  • Vider la liste

Piles: Empiler

Piles: Dépiler

File

• une structure de données
• basée sur le principe du premier entré, premier sorti
• Opérations
  • Enfiler
  • Défiler
  • La file est-elle vide?
  • Nombre d'éléments de la file

File: Enfiler

File: Défiler

Graphes

• une structure de données pour représenter la relation entre certains objets
• les objets sont souvent appelés nœuds
• la relation entre les objets est appelée une arête
• Types:
  • graphes non orientés
  • graphes orientés

Graphe non orienté

Graphe orienté

Liste d'adjacence: graphe non orienté

Liste d'adjacence: graphe orienté

Arbre: graphe non orienté, acyclique et connexe

Tri par ordre croissant: Tri à bulles

Tableau d'entiers

6

5

4

3

2

Tri par ordre croissant: Tri à bulles

1.a

5

6

4

3

2

1.b

5

4

6

3

2

1.c

5

4

3

6

2

1.d

5

4

3

2

6

Tri par ordre croissant: Tri à bulles

2.a

4

5

3

2

6

2.b

4

3

5

2

6

2.c

4

3

2

5

6

Tri par ordre croissant: Tri à bulles

3.a

3

4

2

5

6

3.b

3

2

4

5

6

Tri par ordre croissant: Tri à bulles

4.a

2

3

4

5

6

Recherche séquentielle

Tableau d'entiers

6

5

4

3

2

Recherche 3

Recherche séquentielle

1.a

6

5

4

3

2

1.b

6

5

4

3

2

1.c

6

5

4

3

2

1.d

6

5

4

3

2

Recherche dichotomique

Tableau d'entiers déjà trié

6

5

4

3

2

Recherche 3

Recherche dichotomique

1.a

6

5

4

3

2

1.b

6

5

4

3

2

Références

• Langage C, Claude Delannoy
• https://fr.wikipedia.org/wiki/Pile_(informatique)
• https://fr.wikipedia.org/wiki/Compilateur
• https://fr.wikipedia.org/wiki/G%C3%A9n%C3%A9ration_de_code_natif

Crédits d'images

• Wikimedia Commons