Structures de données/Introduction
Introduction.
L'étude des structures de données fait suite à celle de l'algorithmique impérative. Une bonne connaissance stable de l'algorithmique impérative est une base essentielle à l'étude menée ici. L'étude de l'algorithmique fonctionnelle est d'une aide non-négligeable.
Nous n'avons donc utilisé jusqu'ici qu'une structure de données, le tableau. Cette structure de données pose un problème : elle occupe la mémoire en fonction de sa déclaration. Ce qui signifie que si on ignore combien l'utilisateur va nécessiter d'indice, il va falloir réserver le tableau le plus grand possible afin d'être sûr qu'il puisse contenir autant d'élément que l'utilisateur souhaitera. Il serait plus judicieux de réserver l'espace au fur et à mesure de la demande. C'est ce que l'on appelle la gestion dynamique de la mémoire (par opposition à statique).
Nous avons également vu que les tableaux sont génériques : c'est à dire qu'au moment de sa déclaration, nous pouvons dire que tous ses éléments sont d'un type donné et choisir ce type. 
Nous avons vu que les tableaux sont homogènes : c'est à dire qu'un tableau donné ne peut contenir qu'un seul type d'élément (celui précisé dans la déclaration du tableau). Nous pourrions avoir besoin d'un tableau dont certain élément serait des entiers, d'autres des chaînes, d'autres encore des booléens. Il s'agit là de la problématique de l'hétérogénéité.
Note : attention à ne pas confondre la notion de généricité avec celle d'hétérogénéité. La première désigne la capacité à contenir des éléments d'un même type que l'on peut choisir en le fixant au moment de la déclaration. La seconde désigne la capacité à contenir des éléments de types différents.
Supposons maintenant que nous devions utiliser des formes d'information qui ne font pas partie de type de bases : les listes chaînées, les matrices, rationnels, les arbres, de l'génome, les couleurs, etc. Comment créer les éléments nécessaires au stockage de tel information quand un simple tableau ou un simple enregistrement ne suffisent plus ?
Dynamicité, généricité, hétérogénéité et la création de nouveau types non-élémentaires sont autant de problèmes traités dans ce wikilivre.

Structures de données/Enregistrements
Vous devez déjà être familier avec la notion de type enregistrement qui a du être abordée lors de l'étude de l'algorithmique impérative. Voici néanmoins un rappel :
Première approche.
L'enregistrement est une façon de créer un nouveau type, ou encore un méta-type c'est-à-dire un type qui contient d'autres variables (appelées champs) de types déjà définis.
Toute variable déclarée avec ce nouveau type utilise alors une zone mémoire suffisante pour y stocker tous les champs de l'enregistrement.
Spécification.
On déclare un nouveau type dans la partie codice_1 comme suit :
 identifiant_du_type = enregistrement
 identifiant_premier_champ : type_premier_champ
 identifiant_deuxième_champ : type_deuxième_champ
 fin
on peut ensuite déclarer les variables de ce nouveau type enregistrement normalement :
 identifiant_variable : identifiant_du_type
Pour accéder à un champ de la variable enregistrement, nous utiliserons l'expression :
 identifiant_variable.identifiant_champ
Cette expression est du type de codice_2 soit codice_3.
Exemple.
Supposons que nous voulons un nouveau type couple (de deux entiers). Nous allons déclarer le type couple comme suit :
 couple = enregistrement
 a : entier
 b : entier
 fin
Supposons maintenant que nous avons le lexique suivant :
 Lexique
 c : couple
Si nous assignons :
 c.a ← 1
 c.b ← 2
 afficher(c.a) (* affichera 1 *)
Un exemple d'implémentation : les rationnels.
Nous souhaitons implémenter le type rationnel. Pour cela, nous allons utiliser un type enregistrement composé de deux champs de types entier : numérateur et dénominateur.
Ensuite, nous réaliserons :
 rationnel = enregistrement
 num : entier (* numérateur *)
 den : entier (* dénominateur *)
 fin
 (* Constructeur *)
 fonction creerRationnel(a, b : entiers)
 lexique
 nouveauRationnel : rationnel
 debut
 si b=0 alors
 erreur("le dénominateur ne peut être nul")
 sinon
 nouveauRationnel.num ← a
 nouveauRationnel.den ← b
 finsi
 fin
 (* Accesseur *)
 fonction numerateur(r : rationnel)
 retourner r.num
 fin
 (* Accesseur *)
 fonction dénominateur(r : rationnel)
 retourner r.den
 fin
 fonction calculPgcd(a,b : entier)
 lexique
 t : entier
 debut
 si a < b alors
 t ← a
 a ← b
 b ← t
 finsi
 tant que b > 1
 t ← a modulo b
 si t=0 alors
 retourner b
 finsi
 a ← b
 b ← t
 fin tant que
 retourner b
 fin
 (* Simplifier la fraction *)
 fonction reduire(r : rationnel)
 lexique
 pgcd : entier
 debut
 pgcd ← calculPgcd(r.num, r.den)
 r.num ← r.num / pgcd
 r.den ← r.den / pgcd
 retourner r
 fin
 (* Prédicat d'égalité *)
 fonction sontEgaux(p,q : rationnel)
 lexique
 p_reduit : rationnel (* forme réduite de p *)
 q_reduit : rationnel (* forme réduite de q *)
 début
 p_reduit ← reduire(p)
 q_reduit ← reduire(q)
 retourner (p_reduit.num = q_reduit.num) et (p_reduit.den = q_reduit.den)
 fin
 (* Prédicat de nullité *)
 fonction estNul(r : rationnel)
 debut
 retourner (r.num = 0)
 fin
 (* Calcul de la somme *)
 fonction somme(p, q : rationnel)
 debut
 (* a/b + c/d = ( a*d+c*b)/(b*d) *)
 retourner reduire(creerRationnel(p.num*q.den+q.num*p.den, p.den*q_den))
 fin

Algorithmique impérative/Enregistrements

Première approche.
L'enregistrement est une façon de créer un nouveau type, ou encore un méta-type, c'est-à-dire un type qui contient d'autres variables de types déjà définis.
Spécification.
On déclare un nouveau type dans la partie codice_1 comme suit :
 identifiant_du_type = enregistrement
 identifiant_première_sous_valeur : type_de_la_première_sous_valeur
 identifiant_deuxième_sous_valeur : type_de_la_deuxième_sous_valeur
 fin
on peut ensuite déclarer normalement les variables de ce nouveau type :
 identifiant_variable : identifiant_du_type
Pour accéder à une sous-valeur de la variable, nous utiliserons l'expression :
 identifiant_variable.identifiant_sous_valeur
Cette expression est du type de codice_2.
Exemple.
Supposons que nous voulions un nouveau type couple (de deux entiers). Nous allons déclarer le type couple comme suit :
 couple = enregistrement
 a : entier
 b : entier
 fin
Supposons maintenant que nous avons le lexique suivant :
 Lexique
 c : couple
Si nous assignons :
 c.a ← 1
 c.b ← 2
 afficher(c.a) (* affichera 1 *)
Le projet sur les dates propose un travail complet sur le sujet.
Utilisation.
Cela n'est pas obligatoire en algorithmique impérative, mais pour travailler sur un nouveau type , il convient de définir quelques fonctions élémentaires pour créer une variable à partir de ses sous-valeurs. Remarquez que les types de paramètres seront semblables aux types des sous-variables de nouveau type (exception faite dans le cas de sous-valeurs par défaut...).
Exemple.
Pour reprendre notre exemple, nous pourrions créer une fonction :
 fonction creerCouple(m, n : entiers)
 (* créer un couple à partir de ses deux éléments *)
 lexique
 NouveauCouple : couple
 debut
 NouveauCouple.a ← m
 NouveauCouple.b ← n
 renvoyer NouveauCouple
 fin