Les pointeurs et références

1. Rappels sur la mémoire et les données

a. Structure de la mémoire

Les précédents chapitres vous ont déjà appris énormément de choses sur la mémoire et l’organisation de son contenu :

La mémoire est découpée en octets.
Chaque octet de la mémoire dispose d’une adresse.
Une donnée peut s’étaler sur plusieurs octets, donc occuper une plage d’adresses (par exemple 4 ou 8 octets pour un réel, plus encore pour une chaîne).

Représentation d’une variable en mémoire

Une variable est un nom donné à une ou plusieurs cases. Elle nomme la zone de la mémoire contenant la donnée. La zone de la mémoire contenant la donnée est définie par deux éléments :

L’adresse de début de la donnée, c’est-à-dire l’adresse du premier octet contenant la donnée.
La taille de cette zone, c’est-à-dire le nombre d’octets constituant les données.

La taille de la zone dépend du type de la donnée. Un caractère ASCII n’occupe qu’un seul octet, un entier quatre, un entier long huit, etc.

Quand vous accédez au contenu de la variable, vous accédez au contenu de la zone mémoire qui lui est associée. La variable elle-même contient donc une autre information, l’adresse de la zone mémoire à laquelle elle est attribuée.

Par convention, un ordinateur sachant gérer beaucoup de mémoire, les adresses sont notées en hexadécimal. C’est plus simple de parler d’adresse 0x2dcf0239 que de l’adresse 768541241. Certains langages permettent d’accéder et donc de voir l’adresse de la zone mémoire d’une variable, tout simplement l’adresse de la variable.

b. PHP : des limites qui n’en sont pas

Le langage PHP utilisé depuis le début de cet ouvrage ne permet pas de connaître l’adresse de la variable. En fait, la plupart des choses décrites dans les prochaines pages seront en partie inaccessibles à ce langage. Et parmi ces choses, la possibilité d’accéder à l’adresse mémoire des diverses variables....

Les listes chaînées

1. Listes chaînées simples

a. Principe

Dans la vie quotidienne, une liste revêt plusieurs formes : une liste de courses, de tâches à effectuer, un index, un glossaire, une collection de DVD, de musiques, etc. Ces listes sont composées d’éléments individuels, liés les uns aux autres par leur type ou l’ordre que vous voulez leur donner. Pour passer d’un élément à un autre, vous descendez dans la liste dans l’ordre que vous lui avez donné.

Comment se représenter une liste, par définition linéaire, en programmation ? Vous connaissez au moins un moyen : les tableaux. Dans un tableau, vous pouvez stocker n éléments et l’ordre peut être représenté par l’indice du tableau.

Connaissez-vous un autre moyen de stocker des éléments ? Les enregistrements de types structurés le permettent et en plus vous pouvez y stocker bien plus de détails. Vous pouvez aussi créer des tableaux d’enregistrements, donc leur donner un certain ordre.

L’utilisation des tableaux pose cependant parfois des problèmes un peu complexes. Vous l’avez déjà remarqué avec les méthodes de tris.

Comment insérer un nouvel enregistrement en début de tableau ? Il n’y a pas d’indices négatifs…
Comment insérer un nouvel enregistrement en fin de tableau ? Si l’algorithmique propose un redimensionnement dynamique, les langages PHP l’autorisent.
Comment insérer un élément au milieu du tableau ? Faut-il décaler tous les éléments pour placer le nouveau à l’endroit donné ? Si oui, le tableau risque de déborder.
Et si vous supprimez un enregistrement, allez-vous de nouveau décaler le tableau pour boucher le trou ? Ou trouver une parade pour passer par-dessus ?

Vous pouvez vous arranger pour tout programmer afin de tout faire marcher avec les tableaux. C’est parfaitement possible. Mais est-ce vraiment raisonnable ? Est-ce de la programmation efficace ? Rappelez-vous qu’au chapitre Introduction à l’algorithmique, vous avez appris qu’il faut être économe en ressources. Cette...

Les arbres

1. Principe

L’implémentation des arbres en PHP reprend des principes quasi-identiques aux listes vues précédemment. Cette fois, le code PHP ne vous sera pas fourni ! À vous d’implémenter ces algorithmes, ce n’est pas très difficile.

Dans la nature, les végétaux décrivent souvent des structures dites arborescentes. L’exemple le plus évocateur est l’arbre : le tronc se décompose en plusieurs branches, se décomposant elles-mêmes en branches plus petites et ainsi de suite jusqu’aux extrémités où poussent les feuilles.

Selon le cas, après les tableaux et les listes, vous pouvez vous aussi choisir de représenter l’organisation de vos données sous forme d’arborescence en programmation. La notion d’arborescence est très courante sur votre ordinateur personnel, de nombreuses informations sont représentées, directement ou indirectement sous forme d’arborescence : les dossiers des disques durs, la structure d’une page web, la structure d’un site web, la décomposition de l’exécution d’un programme et de ses appels aux sous-programmes, bref tout ce qui peut incorporer une notion de hiérarchie peut être représenté sous forme d’une arborescence.

L’exemple le plus simple à comprendre est la généalogie. On parle d’arbre généalogique. Partant de vous (1), vous placez tout d’abord vos parents (2), puis les parents de vos parents (4), puis les parents de ces derniers (8) et ainsi de suite. Tous sont reliés par leurs liens de parenté : vous avec vos parents, parents avec grands-parents et ainsi de suite. Le schéma part de vous, mais pourrait partir de vos arrière-grands-parents, ayant x enfants, y petits-enfants, z arrière-petits-enfants (dont vous), chaque individu étant le successeur de son parent et le prédécesseur de ses enfants.

Un arbre généalogique est un arbre binaire

Comment représenter un tel arbre généalogique en programmation ? Vous disposez comme souvent de plusieurs moyens, notamment avec les bases de données, mais connaissant les listes chaînées, vous devez penser qu’il existe...

Exercices

Exercice 1

Écrire en PHP l’algorithme de tri par fusion expliqué dans la section Exemples de tri.

Exercice 2

Rechercher dans la documentation de PHP le nom SplDoublyLinkedList. Implémenter un exemple en ajoutant les quatre premières lettres de l’alphabet à la liste. Afficher ensuite l’ensemble du contenu en mode FIFO (First In First Out).

Puis afficher la première valeur, la dernière valeur et le nombre d’éléments de cette liste.

Exercice 3

Soit l’arbre suivant :

Représenter en PHP l’arbre donné en exemple. Cet arbre est un tableau multidimensionnel avec comme clé la valeur (A, B, D, etc.) et comme valeur l’enfant. Afficher la totalité de l’arbre avec la fonction var_dump().

Exercice 4