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

John Samuel
CPE Lyon

Année: 2021-2022
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
7. Table de hachage

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/Table_de_hachage
• https://fr.wikipedia.org/wiki/G%C3%A9n%C3%A9ration_de_code_natif

Crédits d'images

• Wikimedia Commons
• https://commons.wikimedia.org/wiki/File:Hachage.svg