Accueil

Lexique

Unités

ALGORITHMES

Tutoriel

Sommaire Algorithmes

Il n'existe aucune autre documentation traitant intégralement de ce sujet en Pascal. C'est pourquoi il était nécessaire que je crée un document spécifique.

En Pascal, il n'existe pas de tableaux dynamiques, c'est à dire de type permettant de créer une variable tableau dont le nombre d'éléments n'est pas connu à l'avance. On ne peut utiliser que des constantes dans la déclaration de tableaux statiques. Cette constante qu'on estime est souvent largement supérieure aux besoins.

Exemple : fonctions traitant des Polynômes. Dans un modèle statique, si on n'a besoin que de 15 éléments d'un type tableau pouvant en contenir 1000, le programme réservera 985 éléments inutiles (et de la RAM inutile)

Comment créer un tableau dynamique en langage Pascal standard (norme de 1983, existant sur Alice Pascal, Turbo Pascal 3...) ? Grâce aux enregistrements et aux pointeurs! Dans un enregistrement on peut avoir des champs indiquant la taille d'un tableau, le type de données et une variable de type pointeur (de tableau).
Il y a 2 manières d'aborder la création de tableaux dynamiques avec pointeurs.

1. Soit on crée une structure ayant un pointeur sur un tableau de n éléments variables en un bloc. Ceci a l'avantage d'aller facilement vers le n-ième élément mais cela complexifie les opérations d'ajout ou suppression d'éléments. De plus cela nécessite d'avoir un espace pour accueillir n éléments contigus. Cependant cette organisation est stable durant le temps d'utilisation.
2. Soit on crée une structure de base du tableaux avec le premier élément (pointeur sur le premier de type donné) et ce premier élément pointe sur le second etc... Cette organisation est plus souple pour les opérations d'ajout et suppressions d'éléments, mais avec un éparpillement des éléments dans la RAM qui risque de poser un problème de lenteur et, de plus, l'ajout de pointeurs vers élément suivant rajoute de la RAM (4 ou 8 octets) pour chaque élément.

Nous allons donc, au moins pour les systèmes 16/32 bits (Atari ST, Amiga, Archimedes), utiliser la première option sur les tableaux de type numériques.

A. Création de Type Darray

On va définir un type DARRAY qui est un type enregistrement avec variant. Ce variant sera le type de pointeur de tableau à créer en fonction du type d'éléments voulu. Les types d'éléments sont volontairement choisis, ici, de type simple (nombres) puisque la grande majorité des opérations sur listes ne concernent que des nombres. Il va de soit que le type de pointeurs pourrait aussi être complexe (tableaux, enregistrements etc), mais dans ce cas, on choisira plutôt la 2ème option indiquée sur les items ci dessus sur la manière de créer un tableau dynamique.

CONST
    MaxIndex = 65535; {A adapter suivant votre machine}
TYPE
    MargeId = 0 .. MaxIndex;{Nombre max d'indexes possibles}
    DarrayType = (TypeBoolean, TypeShortInt, TypeInteger, TypeLongint, 
        TypeSingle, TypeDouble, TypeReal); {Vous pouvez ajouter les types numériques supplémentaire suivant votre compilateur}
    Darray = Record
        NbId : MargeId ;
        Valid : boolean ;
        Case ArrType : DarrayType of
            TypeBoolean : (Tcoef : ^ array [0..0] of boolean);
            TypeShortInt : (Tcoef : ^ array [0..0] of shortint);
            TypeInteger : (Tcoef : ^ array [0..0] of integer);
            TypeLongint : (Tcoef : ^ array [0..0] of longint);
            TypeSingle : (Tcoef : ^ array [0..0] of single);
            TypeDouble : (Tcoef : ^ array [0..0] of double);
            TypeReal : (Tcoef : ^ array [0..0] of real);
            end;
    end;

On rappelle que le type "énuméré" est une liste d'étiquettes qui, au niveau compilateur, sont initialisés à 0,1,2 etc...
Ici, TCoef sera un pointeur vers un tableau dont le type est défini par ArrType. La fonction Pascal GETMEM() réservera l'espace mémoire nécessaire lors de l'initialisation du tableau avec une fonction qu'on définiera plus loin.

Pour des raisons pratiques, on va également créer une variable de type tableau indiquant la taille d'un élément suivant son type:

VAR
    SizeElement : Array [DarrayType] of byte;

On va, au début de l'unité, initialiser ce tableau par

        SizeElement[TypeBoolean] := SizeOf(boolean);
        SizeElement[TypeShortInt] := SizeOf(ShortInt);
        SizeElement[TypeInteger] := SizeOf(Integer);
        SizeElement[TypeLongint] := SizeOf(LongInt);
        SizeElement[TypeSingle] := SizeOf(Single);
        SizeElement[TypeDouble] := SizeOf(Double);
        SizeElement[TypeReal] := SizeOf(Real);

Sachant que les étiquettes inscrites pour les Id du tableau sont définis préalablement.

B. Fonctions et procédures sur le type Darray

1. Initialisation de tableau dynamique

Cette procédure, proche de la même fonction en Free Pascal, sert à initialiser un tableau dynamique OU a en modifier la taille s'il existe déjà (champ "valid" de l'enregistrement). Contrairement à la version Free Pascal, cette version est générique quant au type de variable tableau manipulé!

procedure SetLength (var tab : ^Darray; TypeData : DarrayType; Nb : MargeId);
var
    taille : byte;
    i: word;
begin
    if tab^.NbId > 0 then do
        FreeMem(tab^.Tcoef, tab^.NbId*SizeElement[tab^.ArrType]);
    tab^.Valid := true;
    tab^.ArrType := TypeData;
    tab^.NbId := Nb;
    taille := SizeElement[TypeData];
    GetMem(tab^.TCoef,Nb*taille);
    for i:=0 to Nb-1 do {initialisation des éléments à 0, pas obligatoire}
        tab^.Tcoef[i]^ :=0;
end;

Cette procédure réserve la mémoire nécessaire pour Nb éléments de type TypeData. La variable tableau de type Darray qui sera initialisée est tab, sont type TypeData et sa taille nb. On utilise qu'une variable de type pointeur de tableau pour pouvoir libérer la RAM : si on avait utilisé une variable normale, la place en mémoire serait réservée pendant tout le programme.

2. Indiquer la taille d'un tableau

Il n'est pas nécessaire d'avoir une fonction pour cela. La taille est donnée par le champ Nbid de la variable.

3. Supprimer un élément de tableau

Pour cette procédure on va créer un tableau Darray dans lequel on va copier tous les éléments du tableau initial sauf l'élément d'index Id (Qui sera supprimé).

procedure DelElmtTab (var tab : ^Darray; Id : MargeId);
var
    Tab2 : ^Darray;
    i : margeId;
begin
    SetLength (tab2 , tab^.TypeData , tab^.nb-1);
    for i:=0 to Id-1 do
        tab2^.Tcoef[i]^ := tab^.Tcoef[i]^;
    for i:=Id to tab.nb-2 do
        tab2^.Tcoef[i]^ := tab^.Tcoef[i+1]^;
    FreeMem(tab¨.Tcoef);
    FreeMem(tab);
    tab := tab2; {On alloue le pointer tab2 à tab1}
end;

4. Ajouter un élément de tableau

Contrairement à la fonction précédente, ici on ajoutera un élément en fin de tableau. L'élément ajouté n'est pas de type connu, c'est pourquoi il est de type pointer ici. En revanche ce type est connu lors de l'appel à la fonction.

procedure AddElmtTab (var tab : ^Darray; Element : Pointer);
var
    Tab2 : ^Darray;
    i : margeId;
begin
    SetLength (tab2 , tab^.TypeData , tab^.nb+1);
    for i:=0 to Nb-1 do
        tab2^.Tcoef[i]^ := tab^.Tcoef[i]^;
    tab2^.Tcoef[nb]^ := Element^;
    FreeMem(tab^.Tcoef);
    FreeMem(tab);
    tab := tab2; {On alloue le pointer tab2 à tab1}
end;

5. Copier un tableau dans un autre

procedure CopyTab (var tab, Tab2: ^Darray);
var
    i : margeId;
begin
    SetLength (tab2 , tab^.TypeData , tab^.nb);
    for i:=0 to Nb-1 do
        tab2^.Tcoef[i]^ := tab^.Tcoef[i]^;
end;

Copie l'intégralité de tab ver tab2 qui sont 2 pointeurs.

Sommaire Algorithmes