Name: Algorithmique - Techniques fondamentales de programmation exemples en C# - (nombreux exercices corrigés) [BTS - DUT informatique]
Rating: 5 (1 reviews)

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, un entier en 64 bits, 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 choses :

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 sur lequel s’étalent 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.

b. C# : des limites qui n’en sont pas

Le langage C#, tel que vous l’utilisez depuis le début de cet ouvrage, ne permet pas de manipuler l’adresse d’une variable. La raison en est simple : C# est un langage évolué de haut niveau, conçu de manière à éviter au développeur de devoir manipuler directement la mémoire de l’ordinateur. Dans un programme C#, la mémoire est gérée...

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 films, 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 y 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 comme C# ne le permettent pas.
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 méthode est gourmande et compliquée....

Les arbres

1. Principe

L’implémentation des arbres en C# reprend des principes quasi-identiques aux listes vues précédemment. Le code C# ne vous sera pas fourni ce coup-ci ! À 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ères grands-parents, ayant x enfants, y petits-enfants, z arrières-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 un moyen ou un autre...

Exercices

Exercice 1

Écrire l’algorithme permettant de parcourir et d’afficher les n éléments d’un tableau d’entiers, partant de son premier élément, avec un pointeur.

Exercice 2

Créer une structure de liste chaînée circulaire et y placer trois éléments. Créer la fonction permettant de retourner le premier élément, puis celle permettant de parcourir tous les éléments.

Exercice 3

Soit la structure suivante :


Structure noeud 
  valeur:entier 
  pGauche:pointeur sur noeud 
  pDroit:pointeur sur noeud 
FinStruct

et la fonction infixe suivante :


Fonction infixe(pNoeud :pointeur sur noeud) 
Début 
  Si pNoeud<>NIL Alors 
    infixe(pNoeud→pGauche) // sous-arbre gauche 
    Afficher pNoeud→valeur // racine 
    infixe(pNoeud→pDroite) // sous-arbre droit 
FinSi 
Fin

Implémenter en C# cette structure et la fonction infixe.

Exercice 4

Recherchez dans la documentation de C# le nom ArrayList. Que remarquez-vous ?

Implémentez un exemple avec les valeurs 12, "riri" et 3.14. Affichez ensuite l’ensemble du contenu.

Notions avancées