Blog ENI : Toute la veille numérique !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Algorithmique - Techniques fondamentales de programmation
  3. Techniques fondamentales de programmation
Extrait - Algorithmique - Techniques fondamentales de programmation exemples en C# - (nombreux exercices corrigés) [BTS - DUT informatique]
Extraits du livre
Algorithmique - Techniques fondamentales de programmation exemples en C# - (nombreux exercices corrigés) [BTS - DUT informatique]
1 avis
Revenir à la page d'achat du livre

Les tableaux et structures

Présentation

1. Principe et définition

a. Simplifier les variables

Jusqu’à présent, les types de données que vous avez rencontrés sont des scalaires, sauf pour les chaînes de caractères. Pour rappel un scalaire est un type de donnée qui ne représente qu’une seule variable à la fois : la variable ne représente qu’une seule et unique donnée. Un entier, un caractère, un réel, un booléen, etc., sont des scalaires. Une chaîne de caractères n’est pas un scalaire : il s’agit d’une suite, ou liste, de caractères, les uns après les autres. Une chaîne est donc une liste ordonnée par vos soins de scalaires. Les langages proposent souvent un type spécifique aux chaînes de caractères, mais c’est une facilité offerte par ceux-ci. Un langage comme le C n’en propose pas : le langage ne fait que réserver de la mémoire qui accueillera chaque caractère un à un et rien n’empêche d’y mettre autre chose. En algorithmique, vous utilisez le type alphanumérique, il vous faudra alors faire attention lors de la conversion en C. Bien heureusement, C# propose un type de ce genre, même si, comme souvent, derrière les apparences se cache une bien trompeuse réalité…

Mais alors comment se représenter une chaîne de caractères avec un type scalaire ? Il faut pour cela se rappeler comment sont placées les informations en mémoire. La mémoire de l’ordinateur est composée de cases pouvant contenir certaines informations. Ces cases sont numérotées (on parle d’adresse de la case, ou d’adresse mémoire tout simplement) et contiennent des données. Ces données représentent ce que vous voulez selon le contexte de leur utilisation. Vous pouvez par exemple partir du principe qu’elles contiennent des scalaires. Si une case mémoire contient le nombre 65, ce peut être la valeur entière 65 ou encore le code ASCII du caractère "A". Une case mémoire peut parfaitement contenir l’adresse d’une autre case mémoire : c’est un peu plus compliqué que ça en a l’air, et ce sera l’objet...

Manipulations simples

1. Recherche d’un élément

Vous disposez d’un tableau de n éléments correspondant aux prénoms de vos amis, et vous voulez savoir si l’un de ceux-ci est bien présent dans votre tableau. Il faut alors le rechercher. Le principe consiste à balayer l’intégralité du tableau à l’aide d’une structure itérative et à en sortir dès que l’élément a été trouvé ou que le nombre maximal d’indice a été dépassé. À la sortie de la boucle, il faudra de nouveau vérifier pour savoir si oui ou non l’élément a été trouvé : il se peut en effet que tout le tableau ait été parcouru et que ce soit la raison de la sortie de la boucle.


PROGRAMME RECHERCHE 
VAR 
  Tableau noms:tableau[1..10] de chaînes 
  rech:chaîne 
  i:entier 
DEBUT 
  i←1 
  Tant que i<=10 et noms[i]<>rech Faire 
    i←i+1 
  FinTantQue 
  i←i-1 
  Si nom[i]=Rech Alors 
  Afficher "Trouvé" 
  Sinon 
    Afficher "Absent" 
  FinSi 
FIN
 

Il y a la possibilité de faire différemment avec un drapeau :


PROGRAMME RECHERCHE2 
VAR 
  Tableau noms:tableau[1..10] de chaînes 
  Rech:chaîne 
  i:entier 
  trouve:booléen 
DEBUT 
  i←1 
  trouve←FAUX 
  Tant que i<=10 et trouve=FAUX Faire 
    Si nom[i]=rech Alors 
      trouve←VRAI 
    FinSi 
    i←i+1 
  FinTantQue 
  Si trouve Alors 
    Afficher "Trouvé" 
  Sinon 
    Afficher "Absent" 
  FinSi 
FIN
 

En C# :


class chap5_recherche 
{ 
    static void Main(string[] args) 
    { 
        int[] t = { 10, 20, 14, 25, 17, 8, 10, 12, 15, 5, 41, 19, 2, 6, 21 }; 
        int i = 0, rech; 
        bool trouve = false; 
 
        rech = 15; 
 
        while (i < t.Length && !trouve) 
        { 
            if (t[i] == rech) trouve = true; 
            i++; ...

Algorithmes avancés

1. Les algorithmes de tri

a. Principe

Vous avez pu voir dans les exemples précédents l’intérêt des tableaux pour le stockage de valeurs multiples. Mais suivant le cas, il peut être utile d’avoir besoin d’obtenir une liste ordonnée de valeurs par ordre croissant ou décroissant. Autrement dit vous voulez trier le contenu du tableau. Prenez le cas d’un professeur souhaitant trier les notes de ses élèves de la plus basse à la plus haute, ou des résultats d’un tirage du loto pour le rendre plus lisible.

Imaginez un tirage du loto de cinq numéros, évidemment tous différents, dont les valeurs s’étalent entre 1 et 49. Voici l’état initial du tableau suite au tirage au sort :

48

17

25

9

34

Il existe plusieurs méthodes permettant de trier ces différentes valeurs. Elles ont toutes leurs qualités et leurs défauts. Ainsi une méthode sera lente, l’autre sera plus gourmande en mémoire, et ainsi de suite. C’est leur complexité qui détermine leur usage notamment pour de grandes plages de valeurs.

Dans les algorithmes suivants, la variable Cpt contient le nombre d’éléments du tableau initial et t[] est le tableau.

Il est intéressant de prendre en compte la complexité de ces divers algorithmes, bien que cette notion présentée au premier chapitre, ne soit généralement pas (ou peu) abordée dans les premières années d’études en informatique. Les algorithmes ont souvent une complexité proche. Pourtant à l’usage, un tri shell est plus rapide qu’un tri par sélection, tout dépend du nombre d’éléments et l’éventuel ordre de ceux-ci au départ.

b. Le tri par création

Le tri par création ne sera abordé que du point de vue théorique. En effet, si cette méthode semble simple, elle est en fait lourde et compliquée. Si on demande à un débutant en programmation comment trier un tableau, il vous proposera très certainement de créer un deuxième tableau dans lequel on placera au fur et à mesure les éléments du premier tableau dans l’ordre croissant.

C’est une très...

Structures et enregistrements

1. Principe

Les tableaux sont certes très pratiques, mais ils ne permettent pas toujours de répondre efficacement à tous les besoins de stockage. Un tableau est une structure de données dont tous les éléments sont de même type. Que faire quand vous avez besoin de placer dans une structure de type tableau des enregistrements de types différents ?

Comme exemple concret, prenez un catalogue de produits dans un magasin spécialisé. Un article est décrit à l’aide d’une référence, un nom (libellé) et un prix. Les deux premiers sont des chaînes de caractères, le dernier un nombre réel. Comment se représenter cela avec des tableaux ? Il faudrait trois tableaux : un pour les références, un autre pour les libellés et un troisième pour les prix. L’indice de l’article devrait être identique pour les trois tableaux.

C’est possible, faisable, mais en pratique totalement ingérable dès qu’il s’agit d’aller un peu plus loin que de simples traitements. Quid des tris ? Quid des recherches ? Cela devient difficile. Il faudrait donc une sorte de méta-type particulier qui pourrait regrouper en un seul ensemble des variables de types différents.

Ces méta-types existent. Ils s’appellent des structures, ou types structurés, et permettent de décrire des enregistrements. Les enregistrements sont en fait des structures de données composées d’éléments de types différents ou non. Ces structures composées de plusieurs éléments forment une entité unique qui est appelée un type structuré.

Autrement dit, vous pouvez créer vos propres types de données en combinant d’autres éléments de types différents ou non, et créer des variables de ce nouveau type, qu’on appelle des enregistrements. Les différents éléments contenus dans un type structuré sont appelés des champs.

2. Déclaration

a. Type structuré

Le type structuré est opposable aux types dit primitifs vus jusqu’à présent. Un type structuré peut contenir des éléments de types primitifs (entiers, réels...

Exercices

Exercice 1

Donnez un algorithme (et le code C# associé) qui permet de trouver le nombre d’occurrences d’une valeur entière dans un tableau de 20 valeurs.

Exercice 2

Comment déterminer si un tableau d’entiers à une dimension est trié par ordre croissant ? Donnez l’algorithme et le code C#.

Exercice 3

Une matrice mathématique peut être représentée par un tableau à deux dimensions. La somme de deux matrices mathématiques de même type est l’addition de chaque élément de la première avec l’élément correspondant de la seconde.

Indiquez comment représenter une matrice.

Effectuez l’addition de deux matrices de taille identique (par exemple d’une taille de 3x2) et placer le résultat dans une troisième matrice.

Exercice 4

Reprendre l’algorithme du tri par insertion, mais pour un tri décroissant (du plus grand au plus petit). Puis, à l’aide d’un booléen appelé croissant, modifiez l’algorithme et le code C# pour accepter les deux sens de tri.

Exercice 5

Dans une école primaire, une classe a un niveau, un instituteur, et contient 20 élèves. Chaque élève a un nom, un prénom, une date de naissance, et aura dix notes dans l’année. Il y a cinq classes.

Donnez les structures des enregistrements...