Languages fonctionnels :Structures de données

[lulubibi28]

Bonjour,

j'ai une question sur une base qu'on doit cerner en L1 , et je bloque sur les formules et les exemples:

La formule générale, pour un vecteur à une dimension, est :

Si I < N, position-relative = ((I-1) * T) + 1


Pour un vecteur à 2 dimensions ,soit L le nombre de lignes, C le nombre de colonnes, T la taille de la composante, la formule générale pour calculer la donnée d'indices [l, c] (l ligne, c colonne) est :

position-relative = ((l-1) * (C*T)) + ((c-1) * T) + 1



La mémoire, quelles que soient les unités dont elle est constituée, va bien sûr contenir plusieurs types de données. Supposons qu'une donnée figure à l'adresse 2011 ; pour savoir où elle s'arrête, il faut connaître sa taille ; chaque donnée ayant apriori une taille différente des autres, cette taille doit bien être écrite quelque part dans la mémoire ; on la fera ici arbitrairement figurer au début de la donnée, dans un en-tête (en réalité l'endroit où se trouve cette taille varie). Pour lire la donnée, nous devons donc d'abord lire la taille qu'elle occupe ; cette taille sera exprimée par une séquence de bits, à interpréter comme un nombre entier ; elle sera suivie par une séquence de bits à interpréter en fonction du type de la donnée : est-ce un nombre, un caractère, ou un ensemble de données ? L'en-tête de la donnée va contenir ces informations.

Une structure de données rigide va donc contenir deux parties : l'en-tête (en jaune dans les tableaux ci-dessous), ensemble de données indiquant la manière dont il faut lire les données, et l'ensemble des données qui suivent. Pour savoir où s'arrête l'en-tête, on peut provisoirement supposer que tous les en-têtes ont la même taille, connue par le système (stockée quelque part ailleurs dans la mémoire), ou que l'en-tête a lui-même un en-tête, qui indique sa taille.
en-tête données

Une structure de données rigide occupera un morceau de la mémoire. Pour la stocker, il faut donc calculer sa taille (y compris celle de l'en-tête) et trouver, dans la mémoire, une place libre de cette taille, puis écrire l'en-tête et réserver l'espace nécessaire aux données : c'est ce qu'on appelle la déclaration. Une fois déclarée la structure de données, on peut ensuite écrire les données dans l'espace réservé, c'est ce qu'on appelle l'affectation. Dans les descriptions qui suivent, les représentations internes sont données à titre d'exemple (il y a plusieurs manières de représenter les structures de données) ; l'important est d'en comprendre le principe.

Il y a trois types de structures de données rigides : le scalaire, le vecteur et l'agrégat.

Le scalaire ne contient qu'une seule donnée. Son en-tête indiquera qu'il s'agit d'un scalaire, le type de la donnée (nombre par exemple), et sa taille (13 unités par exemple) ; représentation interne :
S n 13

Le vecteur (qu'on appelle aussi table ou tableau) contient une séquence de données toutes de même type et de même taille. Ces données, appelées les composantes du vecteur, sont caractérisées par leur position dans la séquence (leur adresse), appelée l'indice de la composante. L'en-tête portera indication du fait qu'il s'agit d'un vecteur, de la taille et du type des composantes, et de leur nombre.

Par exemple, les noms des jours de la semaine peuvent être enregistrés dans un vecteur de 7 composantes ; la taille des composantes se calcule à partir de la plus grande : 8 octets, comme dans dimanche, à interpréter comme des caractères (c) ; il est inutile d'indiquer la taille de l'ensemble, puisqu'elle peut être calculée (7*8, soit 56 octets) ; la représentation interne, à supposer que l'en-tête se trouve à l'adresse 11 de la mémoire (et comme par hypothèse nous avons déjà supposé que l'en-tête précède la donnée), ressemblerait à ceci :
V 7 c 8 L u n d i M a r d i M e r c r e d i J e u d i
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

La troisième ligne contient les adresses internes au vecteur. Comment trouver la troisième composante ? Il suffit de sauter les composantes précédentes (deux de 8 octets) et d'aller à la case suivante : le nom du troisième jour de la semaine commence au 17e octet (2*8+1) depuis le début des données (31e octet de la mémoire). À partir de l'adresse 72 figurent d'autres informations, appartenant à d'autres données. La fin de la représentation interne du vecteur pourrait ressembler à ceci :
V e n d r e d i S a m e d i D i m a n c h e & a b c d e
47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
33 34 35 36 37 38 39 40 41 42 43 45 45 46 47 48 49 50 51 52 53 54 55 56

Si l'utilisateur demande par erreur le 8e jour de la semaine, il ne faut pas que la machine lui réponde &abcde ; il faudra détecter, en consultant le nombre de composantes indiqué, que cette chaîne se trouve au-delà du vecteur.

L'accès aux données d'un vecteur est dit accès direct (parce qu'on saute directement à la donnée) ou accès par indice. La position relative de la donnée recherchée est calculée à partir de son indice I, de la taille des composantes T, de leur nombre N. La formule générale, pour un vecteur comme celui que nous avons vu, appelé vecteur à une dimension, est :

Si I < N, position-relative = ((I-1) * T) + 1

Il existe des types de vecteurs (ou tableaux) plus complexes. C'est le cas du calendrier des ventes ci-dessous, qui sera représenté par un vecteur à deux dimensions (ou une table à double entrée) ; pour accéder à une donnée, il faut deux indices (la ligne = l'objet, et la colonne = le mois) :
Janvier Février Mars Avril Mai
Cartes mères 5 7 9 15 18
Claviers 24 19 25 18 15
Écrans 32 28 27 12 52
Souris 57 62 58 65 35

Dans la représentation interne associée, on remplacera le nom des mois et le nom des objets par leur numéro d'ordre. Par une convention courante, on note calendrier[1,1] ou calendrier[0,0] (en C) la donnée en haut à gauche (nombre de cartes mères vendues en janvier) ; calendrier[2,3] représente le nombre de claviers vendus en mars ou (en C) le nombre d'écrans vendus en avril.

La représentation interne d'un vecteur à deux dimensions est obtenue en linéarisant le tableau, en notant dans l'en-tête le nombre de colonnes et de lignes et, comme pour les autres vecteurs, la taille (1 octet) et le type (nombre) des composantes :
V 2 5 4 n 1 5 7 9 15 18 24 19 25 18 15 32 28 27 12 52 57 62 58 65 35 " a 12 a
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Pour accéder à la donnée figurant en troisième ligne, deuxième colonne, on commence par sauter deux lignes ; chaque ligne fait 5 colonnes, de 1 octet chacune, donc on saute 10 octets ; on saute ensuite une colonne, donc un octet, et on se positionne sur la case suivante : 10+1+1, la donnée figure au 12e octet.

Soit L le nombre de lignes, C le nombre de colonnes, T la taille de la composante, la formule générale pour calculer la donnée d'indices [l, c] (l ligne, c colonne) est :

position-relative = ((l-1) * (C*T)) + ((c-1) * T) + 1

On peut généraliser cette procédure pour définir l'accès à des vecteurs à n dimensions, pour représenter des tables à n entrées. La déclaration d'un vecteur à n dimensions initialisera son en-tête de manière à pouvoir effectuer la réservation de sa place et à écrire les paramètres qui serviront pour l'accès aux données.

Les vecteurs n'admettent qu'un seul type de données : bits, caractères, nombres entiers, nombres flottants, mots, ou même vecteurs. Pour réunir des types de données distincts, on utilisera l'agrégat (appelé structure en C et en PL1, record en Pascal ou dans les bases de données).

Un bon exemple d'agrégat est celui de la feuille de soin ; elle contient des données dans deux parties (le haut de la feuille ne contient pas de données, mais indique simplement de quoi il s'agit). Chacune de ces parties contient une étiquette (mot-clé ou phrase-clé) qui indique de quoi elle traite, et qu'on appelle une rubrique ; la première contient la rubrique assuré (pour abréger) la seconde la rubrique malade. Chacune de ces rubriques contient à son tour d'autres rubriques (nom, prénom, numéro, etc.).

Pour trouver une information dans un agrégat, par exemple le nom de l'assuré, il faut indiquer le chemin à parcourir à travers les rubriques : d'abord la rubrique assuré, puis nom ; ce qu'on note par convention assuré.nom ; un agrégat est un arbre contenant l'ensemble des chemins possibles vers les données.

Certaines données contenues dans cet agrégat sont des mots ou des suites de mots, d'autres sont des nombres, d'autres encore, comme la réponse à la rubrique accident ?, sont des données binaires (oui / non), etc.

L'en-tête comporte l'indication qu'il s'agit d'un agrégat, le nombre de rubriques principales, la taille de chacune, et son nom (en réalité un nombre, pour occuper moins de place) le nombre et la taille des sous-rubriques ; pour chaque rubrique terminale, il faut indiquer la taille de la donnée et son type. Par exemple, pour un agrégat joignant un nom à 9 caractères à un numéro, nombre de 4 octets, l'en-tête comporterait :
A 2 Nom 9 c Numéro 4 n Z O R G L U B

0 4 3 5
1 2 3 4 5 6 7 8 9 10 11 12 13

Cherchons le numéro ; il y a deux rubriques, c'est la deuxième qu'on cherche, il faut donc sauter 9 caractères, plus 1 : la donnée sur 4 octets commence en position 10.




Je n'ai pas compris comment on a aboutit à ces formules et comment les utiliser .
La notion de caractère dans l'exemple 1 ,ce serait les lettres .

Le premier vecteur est à une dimension , le deuxième à 2 dimensions c'est un calendrier (ligne , colonne ).

Que veut dire aussi la signification de en C et de n , présente dans le cours?

[fatal_error]

Je n'ai pas compris comment on a aboutit à ces formules et comment les utiliser .

Imagine un tableau constitué d'élement de taille T=4
Ton tableau contient 3 éléments..donc N=3

Code: Tout sélectionner

Element1   |Element2   |Element3
1  2  3  4 |5  6  7  8 |9  10  11  12

Imagine l'élément1 commence à l'adresse 1.

Comment récupérer l'adresse de début de Element3? (qui vaut 9).
Element3 est le ieme élément (i=3)
son adresse (de début) est donnée par (i-1)*T+adresse(tableau)
ou adresseTableau==1 (c'est l'adresse de début du premier élément)
application numérique:
adresse(ieme element) = (i-1)*T+adresse(tableau)
adresse(3eme element) = (3-1)*4+1=2*4+1=9

Je t'ai donné l'adresse absolue, mais l'adresse relative est assez similaire...a toi de réfléchir

Que veut dire aussi la signification de en C et de n , présente dans le cours?

A quel passage réfères tu?

[lulubibi28]

A quel passage réfères tu?

Maintenant , c'est beaucoup plus claire pour comprendre :we:

En fait , je parle de ce passage , j'ai mis les symboles en gras (PS : j’espère juste que tu vas comprendre les tableaux ,impossible de les arranger ,c le format pdf)

Il existe des types de vecteurs (ou tableaux) plus complexes. C'est le cas du calendrier des ventes ci-dessous, qui sera représenté par un vecteur à deux dimensions (ou une table à double entrée) ; pour accéder à une donnée, il faut deux indices (la ligne = l'objet, et la colonne = le mois) :
Janvier Février Mars Avril Mai
Cartes mères 5 7 9 15 18
Claviers 24 19 25 18 15
Écrans 32 28 27 12 52
Souris 57 62 58 65 35

Dans la représentation interne associée, on remplacera le nom des mois et le nom des objets par leur numéro d'ordre. Par une convention courante, on note calendrier[1,1] ou calendrier[0,0] (en C) la donnée en haut à gauche (nombre de cartes mères vendues en janvier) ; calendrier[2,3] représente le nombre de claviers vendus en mars ou (en C) le nombre d'écrans vendus en avril.

La représentation interne d'un vecteur à deux dimensions est obtenue en linéarisant le tableau, en notant dans l'en-tête le nombre de colonnes et de lignes et, comme pour les autres vecteurs, la taille (1 octet) et le type (nombre) des composantes :
V 2 5 4 n 1 5 7 9 15 18 24 19 25 18 15 32 28 27 12 52 57 62 58 65 35 " a 12 a
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

[fatal_error]

calendrier[1,1] ou calendrier[0,0] (en C)

en C (le langage de programmation) les index commencent à 0.
donc calendrier[1] qui représente le premier mois (janvier) dans le langage courant, devrait être accédé via calendrier[0] en C. (l'élément d'index 0 étant le premier élément, l'élément d'index 1 le second, etc)...

c'est pourquoi, [3] représente Mars dans le langage courant, mais le mois d'après dans le langage C (et après Mars, c'est Avril)

V 2 5 4 n 1

la def te dit:

La représentation interne d'un vecteur à deux dimensions est obtenue en linéarisant le tableau, en notant dans l'en-tête le nombre de colonnes et de lignes et, comme pour les autres vecteurs, la taille (1 octet) et le type (nombre) des composantes :

V : vecteur
2 : que représente le 2...bonne question, probablement pour dire que c'est la dim du tableau
5 : le nombre de colonnes
4 : le nombre de lignes
n : le type des composantes, n pour nombre...
1 : la taille de la plus grande composante. 1 nombre par case, donc 1

[lulubibi28]

En pratique, et surtout en informatique, il est plutot d'usage de compter les adresses à partir de 0, la formule devient donc simplement : addr_rel(element i) = i * T

par exemple pour un tableau 3x4 comme ceci : T=4 , N = 3

[[0,1,2,3], [4,5,6,7], [8,9,10,11]]

Si tu veux accéder à la case (1,3) du tableau, comment calcule t-on son adresse ?

Ce serait (1-1) * 4 = 0 , sachant que que T= 4 , et et i = 1 !

[fatal_error]

En pratique, et surtout en informatique, il est plutot d'usage de compter les adresses à partir de 0

On ne s amuse pas a compter des adresses.
On calcule une adresse pour acceder a un element.
Lorsque tu as une structure, qui a une adresse, ben pour acceder a un element de cette structure, tu es force de tenir compte de ladresse de cette structure...

Si tu veux accéder à la case (1,3) du tableau, comment calcule t-on son adresse ?

moi je veux rien acceder du tout. la formule t es par ailleurs deja donnee.

[lulubibi28]

Ok!je vais réfléchir là dessus ^^