CHAPITRE 2

---

auteur: Philippe Moreau (U.P.J.V.)

STRUCTURES DE DONNEES

Après une introduction concernant la structure des informations, nous évoquerons:

- les principales structures de données linéaires (1)Structures de Données linéaires)

- puis un cas très particulier de structures de données non linéaires (2)les arbres binaires).

 

 

Vous trouverez également deux séries d'EXERCICES:

- Une série concernant les structures de données linéaires (Série 1)

- Une série concernant les arbres binaires (Série 2)

Ces exercices sont également accessibles à la fin des sections concernées.

 

Introduction: STRUCTURE DE L'INFORMATION

 

Pour résoudre un problème posé, il faut trouver un algorithme. Cette phase du travail s'appelle également l'analyse. Souvent, une des plus grandes difficultés rencontrées, au cours de cette analyse, consiste à cerner les données et connaître qu'elles sont les structures qui lient ces différentes données.

 

Dans le cas le plus simple, les informations se présentent comme une séquence, une liste ordonnée, linéaire d'éléments.

Exemple:

On veut établir le classement des étudiants de licence par ordre de mérite. Pour cela, les informations sont: les nom et prénom de l'étudiant et sa note finale obtenue en licence. Le seul lien entre ces informations est qu'elles arrivent dans un certain ordre (ici l'ordre décroissant des notes) les unes derrières les autres. On est donc en présence d'une liste linéaire.

 

Mais la structure unissant les différentes informations peut être beaucoup plus complexe et traduire, par exemple, des rapports hiérarchiques entre les différents éléments des informations.

Exemple 1:

Quel chemin doit on emprunter pour se rendre d'une rue à une autre dans une ville? Cette fois ci les informations sont: les carrefours et les rues reliant ces différents carrefours. La structure unissant ces différentes informations est alors une structure dite de réseau.

Exemple 2:

On veut dessiner l'arbre généalogique d'une famille. Les informations sont les différentes personnes composant cette famille. La structure unissant ces informations (lien de parenté) est alors une structure dite arborescente.

 

Dans un ordinateur:

- Les éléments d'informations consistent en un ensemble d'articles.

- Un article peut être divisé en plusieurs parties appelées zones.

- Chaque article occupera un ou plusieurs mots de la mémoire.

- L'adresse d'un article (aussi appelée pointeur sur l'article) est l'adresse mémoire (un nombre) du premier mot mémoire occupé par l'article.

Auteur: Philippe Moreau (U.P.J.V.)