OFPPTMAROC

Cours s4 informatique 4 : algorithmique et structures de donnees

Télécharger

Cours s4 informatique 4 : algorithmique et structures de données

Structures de données

De nombreux objets traités par les programmes ne peuvent pas être représentés à l'aide d'un seul nombre ou d'une chaîne, mais sont constitués naturellement de plusieurs informations : une date = un jour, un mois, une année ; un nombre complexe = une partie réelle, une partie imaginaire ; un tableau = l'adresse de son premier élément, sa taille physique et sa taille effective ; une sphère = un centre, un rayon ; une personne = un nom, un prénom ; une adresse = un numéro, une rue, une ville, un code postal; ... Une information élémentaire dans un objet est appelée un champ. Pour accéder à l'information contenue dans un champ d'un objet composite, il suffit d'ajouter un point au nom de l'objet et de le faire suivre du nom du champ.

Structures simples

Voici un exemple de définition et d’utilisation de structures. Il porte sur les dates, constituées de 3 informations : nom de jour (dans la semaine), jour dans le mois, mois et année.

typedef struct { /* ou typedef struct T_Date */

 int jour, mois, annee;

 char lejour[9]; /* 'lundi', ...., 'dimanche' */

} Date;

Date d1, d2;

d1.jour = 24;

d1.mois = 12;

d1.annee = 1965;

d2.annee = d1.annee+3;

printf('%d-%d-%d\n',d1.jour,d1.mois,d1.annee);}

…

Exemple : fiche de renseignement

Nous définissons un type FICHE, destiné à contenir des informations sur des personnes. Ces informations sont : nom, prénom, adresse, date de naissance, sachant qu'une adresse est constituée d'un numéro, d'un nom de rue, d'un code postal et d'une ville, alors que la date de naissance est la réunion de 3 informations : jour, mois et année. Nous définissons notre type ainsi :

#include

#include

typedef struct t_date {

int j, m;

 char a[3]; /* annee = 2 caractères + fin de chaîne = bug an 2000 :) */

} TDate;

typedef struct t_adresse {

 int numero, code;

 char *rue, *ville;

} TAdresse;

typedef struct t_fiche {

 char *nom, *prenom; /* pointeurs sur nom et prenom */

 TDate naissance; /* date de naissance */

 TAdresse *adresse; /* pointeurs sur adresse => pas présente */

} TFiche;

Nous écrivons ensuite les fonctions permettant d'initialiser une fiche. Pour réduire le risque d'erreurs, il est impératif de procéder comme dans l'exemple, c'est-à-dire de ne pas tenter d'accéder directement aux souschamps des champs, mais de passer par des objets intermédiaires qui n'ont qu'un seul niveau de décomposition et qui sont plus simples à initialiser. Certaines fonctions fonctionnent sur le mode des paramètres modifiables, ce qu'il vaut mieux éviter en principe.

…

…

Tableaux multidimensionnels

Les tableaux statiques à 2 dimensions

Ils sont utilisés pour représenter des matrices, ou toutes autres formes de données rectangulaires (images, feuilles de calcul de tableur, modèles numériques de terrain, etc...). C'est aussi de cette façon que sont organisées certains résultats d’interrogation de bases de données : un tableau d'enregistrements, chaque enregistrement étant un tableau de champs, même si ici les champs n'ont pas tous le même type (texte, valeur etc.).

Matrices

Prenons l'exemple des matrices. En mathématique, on désigne chaque élément d'une matrice par aij où i est le numéro de ligne et j celui de colonne. En programmation, il en va de même : si m est une matrice de taille M lignes et N colonnes, on la déclare à l'aide d'un tableau par :

float m[M][N];

Comme pour les tableaux mono-dimensionnels, la numérotation commence à 0 pour les lignes et pour les colonnes, donc l'élément aij est obtenu par m[i-1][j-1], ou réciproquement, l'élément m[i][j] d'un tableau est celui situé à la (i+1)ème ligne et (j+1)ème colonne. Pour illustrer nos propos, nous prenons le cas des matrices carrées 3x3, pour lesquels nous définissons un nouveau type, le type Matrice3x3.

typedef float Matrice3x3[3][3];

Matrice3x3 m1,m2;

Matrice3x3 identite= { {1.0, 0.0, 0.0},

 {0.0, 1.0, 0.0},

 {0.0, 0.0, 1.0}};

En mémoire, tous les éléments d'un tableau à 2 dimensions sont contigus : d'abord ceux de la première ligne, puis ceux de la deuxième etc. Les tableaux 2D sont donc des tableaux de tableaux. L'adresse de l'élément m[i][j] est celle du premier + (i*Nombre de colonnes) + j. Donc on peut très facilement programmer des matrices avec des tableaux à une dimension.

Matrice3x3 m;

float t[3*3];

t[i*3+j]=m[i][j];

Tout d'abord, voyons une fonction permettant de fixer les valeurs de chaque élément d'une matrice. Pour accéder à tous les éléments, on imbrique deux boucles : pour toutes les lignes faire pour tous les éléments sur chaque colonne de la ligne courante faire  traitement de l'élément (ligne courante, colonne courante)

 finpour

finpour

Dans les exemples suivants, on utilise l'indice i pour désigner les lignes, et j pour les colonnes.

void initMatrice(Matrice3x3 m)

{

 int i,j;

 for(i=0;i<3;i++)

for(j=0;j<3;j++) {

 printf('entrez l'élément m[%d][%d] : ',i,j);

 scanf('%d', &m[i][j]);

 }

}

Table des matières

Table des matières .................... 2

Structures de données........................... 4

Structures simples............................. 4

Structures imbriquées ....................... 5

Exemple : fiche de renseignement ....................... 5

Bonne utilisation des structures................ 6

Structures récursives et croisées.......................... 8

Tableaux multidimensionnels ............................ 9

Les tableaux statiques à 2 dimensions ..................... 9

Matrices............................. 9

Matrices dynamiques ...................... 12

Tableaux mono-dimensionnels........................... 12

Tableaux de tableaux.................. 13

Quelques représentations de molécules ........................ 14

Tableaux de dimension supérieure à 2................... 14

Tris de tableaux ....................... 15

Tables .......................... 17

Définition.............................. 17

Représentation des tables........................... 17

fonction d’accès .......................... 17

Modes d’adressage..................... 17

Partage de tables........................ 18

Le rangement dispersé.................... 19

Les fonctions de hachage....................... 19

Les fonctions de hachage....................... 20

Complément : résolution des conflits de tables de hachages ................ 20

Fichiers et entrées/sorties ................... 21

Fichiers physiques, fichiers logiques....................... 21

Assignation...................... 21

Ouverture ........................ 21

Entrées/Sorties formatées........................... 22

Lecture ............................ 22

Ecriture............................ 23

Lecture et écriture formatées en C ..................... 23

Fermeture d'un fichier ............................. 23

Fichiers binaires .............................. 23

Lecture et écriture binaires en C......................... 23

Application : sauvegarde d'un tableau................ 24

Introduction à la cinématique des fichiers............... 24

Les listes chaînées .............................. 25

Généralités .......................... 25

Le type liste ......................... 25

Opérations élémentaires sur les listes .................... 26

Déclaration et initialisation ...................... 26

Test de vacuité............................ 26

Accès à la première information de la liste : la tête .................... 26

Accès à la deuxième composante : la queue ................. 26

Ajout d'un élément en tête ...................... 27

Suppression de l'élément en tête........................ 27

Autres opérations utiles sur les listes : notion de type abstrait ................... 28

Longueur d'une liste.................... 28

Ajout en queue............................ 28

Suppression du dernier élément......................... 28

Insertion en une position donnée........................ 29

Suppression d'un élément de position donnée............... 30

Insertion triée (ou sur critère quelconque)...................... 30

Exemple d'utilisation ................... 30

Structures récursives et croisées ................ 32

Chaînages multiples........................ 32

Les piles....................... 33

Modélisation de la structure ........................ 33

Introduction ..................... 33

Modélisation par liste chaînée ................ 33

Modélisation par tableau......................... 33

Opérations sur la structure.......................... 33

Introduction ..................... 33

Opérations pour la modélisation par liste chaînée...................... 34

Opérations pour la modélisation par tableau.................. 35

Conclusion........................... 36

Les files........................ 37

Modélisation de la structures....................... 37

Introduction ..................... 37

Modélisation par liste chaînée ................ 37

Modélisation par tableau circulaire ..................... 37

Opérations sur la structure.......................... 38

Introduction ..................... 38

Opérations pour la modélisation par liste chaînée...................... 38

Opérations pour la modélisation par tableau circulaire .............. 39

Conclusion........................... 40

Les arbres................................ 41

Généralités .......................... 41

Le type Arbre Binaire....................... 41

Opérations de base..................... 41

Arbres binaires ordonnés........................ 44

Application : les arbres dictionnaires .................. 45

Parcours heuristique d’arbres ..................... 47

Exemple : le jeu du taquin....................... 47

Arbres équilibrés (bien balancés)................ 48

Arbres n-aires...................... 49

Modélisation des arbres n-aires.......................... 49

Les graphes ............................. 50

Définition.............................. 50

Parcours des graphes ..................... 51

Représentation des graphes ....................... 52

Fonctions de manipulation des graphes ......................... 54

Application : graphe de représentation d'une molécule .................. 55

Plus courts chemins (à origine unique)................... 55

Algorithme de Dijkstra............................. 55

Algorithme de Bellman-Ford ................... 56