1.4. Structures de données de base en C#


Plan de ce chapitre:   ...........

1. La classe String
Déclaration
Accès
Insertion
Concaténer des chaînes
Scanner une sous-chaîne
Convertir une chaine en tableau de caractères
Opérateurs d'égalité et d'inégalité
Rapport entre string et char
  2. Les tableaux Arrays, les matrices
    Les tableaux à une dimension
    Utiliser un tableau
    Les matrices
    Tableau dechiqueté ou en escalier
    Egalité et inégalité entre tableaux
    Affectation et recopie de tableau
    Parcours itératif for...each


3. Les collections en C#
Les tableaux dynamiques - ArrayList
Les listes chaînées - ArrayList
Les listes  à clefs triées - SortedList
Les piles et les files - Stack, Queue

 

1. La classe string

Le type de données String (chaîne de caractère) est une classe de type référence dans l'espace de noms System de .NET Framework. Donc une chaîne de type string est un objet qui n'est utilisable qu'à travers les méthodes de la classe string.

Etant donné que cette classe est très utilisée les variables de type string bénéficient d'un statut d'utilisation aussi souple que celui des autres types élémentaires par valeurs. On peut les considérer comme des listes de caractères Unicode numérotés de 0 à n-1 (si n figure le nombre de caractères de la chaîne).

Toutefois un objet string de C#  est immuable (son contenu ne change pas), on peut accédeà chaque caractère de la chaîne en la considérant comme un tableau de caractères en lecture seule.


Déclaration d'une chaîne
Déclaration d'une variable String :
string ch1 ;
ch1 = "abcdefghijk";

Déclaration d'une variable String avec initialisation :
string ch1 = "abcdefghijk";


Accès à un caractère de rang fixé d'une chaîne par  l'opérateur [ ]
(la chaîne est lue comme un tableau de char)
string ch1 = "abcdefghijk";
char car = ch1[4] ; // ici car contient la lettre 'e'

Représentation interne de l'objet ch1 de type string :


 
En fait l'opérateur [ ] est un indexeur de la classe string (cf. chapitre 3.2 indexeurs en Csharp), et il est en lecture seule :
public char this [  int index ] { get ; }

Ce qui signifie au stade actuel de compréhension de C#, qu'il est possible d'accéder en lecture seulement à chaque caractères d'une chaîne, mais qu'il est impossible de modifier un caractère grâce à l'indexeur.

char car = ch1[7] ; // l'indexeur renvoie le caractère 'h' dans la variable car
ch1[5] = car  ; // Erreur de compilation : l'écriture dans l'indexeur est interdite !!
ch1[5] = 'x'  ; // Erreur de compilation : l'écriture dans l'indexeur est interdite !! 

Le type string possède des méthodes d'insertion, modification et suppression : méthodes Insert, Copy, Concat,... Attention ces méthodes ne modifient pas la chaîne objet qui invoquent la méthode mais renvoient un autre objet de chaîne différent, obtenu après action de la méthode sur l'objet initial.

Insertion d'une chaîne dans une autre chaîne

Appel de la méthode Insert de la chaîne ch1 afin de construire une nouvelle chaîne ch2 qui est une copie de ch1 dans laquelle on a inséreré une sous-chaîne, ch1 n'a pas changé (immuabilité).

Soit :

Puis ivocation de la méthode Insert sur ch1 :

ch2 est une copie de ch1 dans laquelle on a inséreré la sous-chaîne "..x..".
 

Concaténation de deux chaînes  (opérateur + sur les chaînes)

string str1,str2,str3 ;
str1 = "bon" ;
str2 = "jour" ;
str3 = str1+str2 ;
 

On accède à la longueur d'une chaîne par la propriété int Length
string str1 = "abcdef";
int longueur;
longueur = str1.Length ; // ici longueur = 6
 

Scanner une sous-chaîne

Il est possible de connaître la position d'une sous-chaîne à l'intérieur d'une chaîne donnée grâce à la méthode (surchargée 6 fois) int IndexOf (.......)

Voici une utilisation de la surcharge int IndexOf ( string ssch) qui renvoie l'indice de la première occurrence du string ssch contenue dans str1 :

string str1 = "abcdef" , ssch="cde";
int rang;
rang = str1.IndexOf ( ssch );


Convertir une chaîne en tableau de caractères

Si l'on souhaite se servir d'une string comme un tableau de char, il faut utiliser la méthode ToCharArray qui convertit la chaîne en un tableau de caractères contenant tous les caractères de la chaîne.

Soient les lignes de programme suivantes :
string str1 = "abcdef" ;
char [ ] tCarac ;
tCarac = str1.ToCharArray( ) ;
tCarac = "abcdefghijk".ToCharArray( );

Illustrons ces lignes par des schémas de références :

string str1 = "abcdef" ;

char [ ] tCarac ;
tCarac = str1.ToCharArray( ) ;


tCarac = "abcdefghijk".ToCharArray( );


Attention :
les méthodes d'insertion, suppression, etc…ne modifient pas la chaîne objet qui invoque la méthode mais renvoient un autre objet de chaîne différent, obtenu après action de la méthode sur l'objet initial.


Opérateurs d'égalité et d'inégalité de string

L'opérateur d'égalité  = = , détermine si deux objets string spécifiés ont la même valeur, il se comporte comme sur des éléments de type de base (int, char,...)

string a , b ;
(a = = b ) renvoie true si la valeur de a est la même que la valeur de b  ; sinon il renvoie false.

public static bool operator == (  string a,  string b );

Cet opérateur est surchargé et donc il compare les valeurs effectives des chaînes et non leur références, il fonctionne comme la méthode public bool Equals( string value ) de la classe string, qui teste l'égalité de valeur de deux chaînes.

Voici un morceau de programme qui permet de tester l'opérateur d'égalité = = et la méthode Equals :

    string s1,s2,s3,ch;
    ch = "abcdef";
    s1 = ch;
    s2 = "abcdef";
    s3 = new string("abcdef".ToCharArray( ));

    System.Console.WriteLine("s1="+s1);
    System.Console.WriteLine("s2="+s2);
    System.Console.WriteLine("s3="+s3);
    System.Console.WriteLine("ch="+ch);
    if( s2 == ch )System.Console.WriteLine("s2=ch");
      else System.Console.WriteLine("s2<>ch");
    if( s2 == s3 )System.Console.WriteLine("s2=s3");
      else System.Console.WriteLine("s2<>s3");
    if( s3 == ch )System.Console.WriteLine("s3=ch");
      else System.Console.WriteLine("s3<>ch");
    if( s3.Equals(ch) )System.Console.WriteLine("s3 égal ch");
      else System.Console.WriteLine("s3 différent de ch");

Après exécution on obtient :
            s1=abcdef
            s2=abcdef
            s3=abcdef
            ch=abcdef
            s2=ch
            s2=s3
            s3=ch
            s3 égal ch


POUR LES HABITUES DE JAVA : ATTENTION

L'opérateur d'égalité == en Java (Jdk1.4.2) n'est pas surchargé, il ne fonctionne pas totalement de la même façon que l'opérateur == en C#, car il ne compare que les références. Donc des programmes en apparence syntaxiquement identiques dans les deux langages, peuvent produire des résultats d'exécution différents :
Programme Java
 Programme C#
String ch;
ch = "abcdef" ;

String s2,s1="abc" ;
s2 = s1+"def";
//-- tests d'égalité avec l'opérateur = =
if( s2 == "abcdef" )
    System.out.println ("s2==abcdef");
else System.out.println ("s2<>abcdef");
if( s2 == ch ) System.out.println     ("s2==ch");
else System.out.println ("s2<>ch");

 string ch;
ch = "abcdef" ;

string s2,s1="abc" ;
s2 = s1+"def";
//-- tests d'égalité avec l'opérateur = =
if( s2 == "abcdef" )
      System.Console.WriteLine("s2==abcdef");
else System.Console.WriteLine ("s2<>abcdef");
if( s2 == ch ) System.Console.WriteLine ("s2==ch");
else System.Console.WriteLine ("s2<>ch");
Résultats d'exécution du code Java :
     s2<>abcdef
     s2<>ch

 Résultats d'exécution du code C# :
     s2==abcdef
     s2==ch

Rapport entre string et char

Une chaîne string contient des éléments de base de type char, comment passe-t-on de l'un à l'autre type ?
 
1°) On ne peut pas considérer un char comme un cas particulier de string, le transtypage suivant est refusé comme en Java :

char car = 'r';
string s;
s = (string)car;

Il faut utiliser l'une des surcharges de la méthode de conversion ToString de la classe  Convert :

System.Object
     |__System.Convert

méthode de classe static :
   public static string ToString( char c );


Le code suivant est correct, il permet de stocker un caractère char dans une string :

char car = 'r';
string s;
s = Convert.ToString (car);


Remarque :

La classe Convert contient un grand nombre de méthodes de conversion de types. Microsoft indique que cette classe : "constitue une façon, indépendante du langage, d'effectuer les conversions et est disponible pour tous les langages qui ciblent le Common Language Runtime. Alors que divers langages peuvent recourir à différentes techniques pour la conversion des types de données, la classe Convert assure que toutes les conversions communes sont disponibles dans un format générique."


2°) On peut concaténer avec l'opérateur +, des char à une chaîne string déjà existante et affecter le résultat à une String :

string s1 , s2 ="abc" ;
char c = 'e' ;
s1 = s2 + 'd' ;
s1 = s2 + c ;
 
Toutes les écritures précédentes sont licites et acceptées par le compilateur C#, il n'en est pas de même pour les écritures ci-après :

Les écritures suivantes seront refusées : 
 		Ecritures correctes associées :
String s1 , s2 ="abc" ;
char c = 'e' ;
s1 =  'd'  +  c ; // types incompatibles

s1 =  'd'  +  'e'; // types incompatibles   

String s1 , s2 ="abc" ;
char c = 'e' ;
s1 =  "d"  + Convert.ToString ( c) ;

s1 =  "d"  +  "e";
s1 =  "d"  +  'e';
s1 =  'd'  +  "e";


Le compilateur enverra le message d'erreur suivant pour l'instruction    s1 =  'd'  +  c ;  et pour l'instruction  s1 =  'd'  +  'e';   :
[C# Erreur] : Impossible de convertir implicitement le type 'int' en 'string'

Car il faut qu'au moins un des deux opérandes de l'opérateur + soit du type string :


Pour plus d'information sur toutes les méthodes de la classe string consulter la documentation de .Net framework.

Remonter

2. Les tableaux Arrays, les matrices


Dès que l'on travaille avec de nombreuses données homogènes ( de même type) la première structure de base permettant le regroupement de ces données est le tableau. C# comme tous les langages algorithmiques propose  cette structure au programmeur. Comme pour les string et pour des raisons d'efficacité dans l'encombrement mémoire, les tableaux sont gérés par C# , comme des objets de type référence (donc sur le tas), leur type hérite de la classe abstraite System.Array..

Les tableaux C# sont indexés uniquement par des entiers  (char, int, long,…) et sur un intervalle fixe à partir de zéro.  Un tableau C# peut avoir de une ou à plusieurs dimensions, nous avons donc les variétés suivantes de tableaux dans le CLR :

Tableaux à une dimension.
Tableaux à plusieurs dimensions (matrices,…) comme en Delphi.
Tableaux déchiquetés comme en Java.


Chaque dimension d'un tableau en C# est définie par une valeur ou longueur, qui est un nombre ou une variable N entier (char, int, long,…) dont la valeur est supérieur ou égal à zéro. Lorsqu'une dimension a une longueur N, l'indice associé varie dans l'intervalle [ 0 ,  N – 1 ].

Tableau uni-dimensionnel

Ci-dessous un tableau 'tab' à une dimension, de n+1 cellules numérotées de 0 à n :



 

Remarque :

Les tableaux de C# sont des objets d'une classe dénommée Array qui est la classe de base d'implémentation des tableaux dans le CLR de .NET framework (localisation : System.Array) Cette classe n'est pas dérivable pour l'utilisateur : "public abstract class Array : ICloneable, IList, ICollection, IEnumerable".

C'est en fait le compilateur qui est autorisé à implémenter une classe physique de tableau. Il faut utiliser les tableaux selon la démarche ci-dessous en sachant que l'on dispose en plus des propriétés et des méthodes de la classe Array si nécessaire (longueur, tri, etc...)

 

Déclaration d'une variable de tableau, référence seule:

int [ ] table1;
char [ ] table2;
float [ ] table3;
...
string [ ] tableStr;


Déclaration d'une variable de tableau avec définition explicite de taille :

int [ ] table1 = new int [5];
char [ ] table2  = new char [12];
float [ ] table3  = new float [8];
...
string [ ] tableStr  = new String [9];

Le mot clef new correspond à la création d'un nouvel objet (un nouveau tableau) dont la taille est fixée par la valeur indiquée entre les crochets. Ici 4 tableaux sont crées et prêts à être utilisés : table1 contiendra 5 entiers 32 bits, table2 contiendra 12 caractères, table3 contiendra 8 réels en simple précision et tableStr contiendra 9 chaînes de type string.

On peut aussi déclarer un tableau sous la forme de deux instructions : une instruction de déclaration et une instruction de définition de taille avec le mot clef new, la seconde pouvant être mise n'importe où dans le corps d'instruction, mais elle doit être utilisée avant toute manipulation du tableau. Cette dernière instruction de définition peut être répétée plusieurs fois dans le programme, il s'agira alors à chaque fois de la création d'un nouvel objet (donc un nouveau tableau), l'ancien étant détruit et désalloué automatiquement par le ramasse-miettes (garbage collector) de C#.

int [ ] table1;
char [ ] table2;
float [ ] table3;
string [ ] tableStr;
....
table1 = new int [5];
table2  = new char [12];
table3  = new float [8];
tableStr  = new string [9];

Déclaration et initialisation avec définition implicite de taille :

int [ ] table1 = {17,-9,4,3,57};
char [ ] table2  = {'a','j','k','m','z'};
float [ ] table3  = {-15.7f, 75, -22.03f, 3 ,57 };
string [ ] tableStr  = {"chat","chien","souris","rat","vache"};

Dans cette éventualité C# crée le tableau, calcule sa taille et l'initialise avec les valeurs fournies.

Il existe en C# un attribut de la classe abstraite mère Array, qui contient la taille d'un tableau uni-dimensionnel, quelque soit son type, c'est la propriété Length en lecture seule.

Exemple :

        int [ ] table1 = {17,-9,4,3,57};
        int taille;
        taille = table1.Length; // taille = 5

Il est possible de déclarer une référence de tableau, puis de l'initialiser après uniquement ainsi :
     int [ ] table1 ; // crée une référence table1 de type tableau de type int
     table1 = new int {17,-9,4,3,57};  // instancie un tableau de taille 5 éléments reférencé par table1
      …
     table1 = new int {14,-7,9}; // instancie un autre tableau de taille 3 éléments reférencé par table1
 
L'écriture ci-dessous engendre une erreur à la compilation :
 
     int [ ] table1 ; // crée une référence table1 de type tableau de type int
     table1 =  {17,-9,4,3,57};  // ERREUR de compilation, correction :  int [ ] table1 = {17,-9,4,3,57};

 

Utiliser un tableau

Un tableau en C# comme dans les autres langages algorithmiques s'utilise à travers une cellule de ce tableau repérée par un indice obligatoirement de type entier ou un char considéré comme un entier (byte, short, int, long ou char). Le premier élément d'un tableau est numéroté 0, le dernier Length-1.

On peut ranger des valeurs ou des expressions du type général du tableau dans une cellule du tableau.

Exemple avec un tableau de type int :

int [ ] table1 = new int [5];
// dans une instruction d'affectation:
table1[0] = -458;
table1[4] = 5891;
table1[5] = 72;  <--- est une erreur de dépassement de la taille ! (valeur entre 0 et 4)


// dans une instruction de boucle:
for (int i = 0 ; i<= table1.Length-1;  i++)
 table1[i] = 3*i-1; // après la boucle: table1 = {-1,2,5,8,11}

Même exemple avec un tableau de type char :

char [ ] table2  = new char [7];

table2[0] = '?' ;
table2[4] = 'a' ;
table2[14] = '#' ;  <--- est une erreur de dépassement de la taille
for (int i = 0 ; i<= table2.Length-1;  i++) 
      table2[i] =(char)('a'+i); 
// après la boucle: table2 = {'a', 'b', 'c' ,'d', 'e', 'f'}

Remarque :

Dans une classe exécutable la méthode Main reçoit en paramètre un tableau de string nommé args qui correspond en fait aux éventuels paramètres de l'application elle-même:
                                            static void Main(string [ ] args) 


Les matrices et les tableaux multi-dimensionnels

Les tableaux C# peuvent avoir plusieurs dimensions, ceux qui ont deux dimensions sont dénommés matrices (vocabulaire scientifique). Tous ce que nous allons dire sur les matrices s'étend ipso facto aux tableaux de dimensions trois, quatre et plus.  Ce sont aussi des objets et ils se comportent comme les tableaux à une dimension tant au niveau des déclarations  qu'au niveau des utilisations. La déclaration s'effectue avec un opérateur crochet et des virgules, exemples d'une syntaxe de déclaration d'un tableau à trois dimension :  [  ,  , ] . Leur structuration est semblable à celle des tableaux Delphi-pascal.

 
Déclaration d'une matrice, référence seule:

int [ , ] table1;
char [ , ] table2;
float [ , ] table3;
...
string [ , ] tableStr;

Déclaration d'une matrice avec définition explicite de taille :

int [ , ] table1 = new int [5, 2];
char [ , ] table2  = new char [9,4];
float [ , ] table3  = new float [2;8];
...
string [ , ] tableStr  = new String [3,9];

 Exemple d'écriture de matrices de type int :

int [ , ] table1 = new int [2 , 3 ];// deux lignes de dimension 3 chacunes


// dans une instruction d'affectation:
table1[ 0 , 0 ] = -458;
table1[ 2 , 5 ] = -3;  <--- est une erreur de dépassement ! (valeur entre 0 et 1)
table1[ 1 , 4 ] = 83;  <--- est une erreur de dépassement ! (valeur entre 0 et 4)

// dans une instruction de boucle:
for (int i = 0 ; i<= 2;  i++)
   table1[1 , i ] = 3*i-1;

 // avec initialisation d'une variable dans la déclaration :

int n ;

int [ , ] table1 = new int [4 , n =3 ];// quatre lignes de dimension 3 chacunes

L' attribut Length en lecture seule, de la classe abstraite mère Array, contient en fait la taille d'un tableau en nombre total de cellules qui constituent le tableau (nous avons vu dans le cas uni-dimensionnel que cette valeur correspond à la taille de la dimension du tableau). Dans le cas d'un tableau multi-dimensionnel Length correspond au produit des tailles de chaque dimension d'indice :

int [ , ] table1 = new int [5, 2];                            table1.Length = 5 x 2 = 10
char [ , , ] table2  = new char [9,4,5];                 table2.Length = 9 x 4  x 5 = 180
float [ , , , ] table3  = new float [2,8,3,4];            table3.Length = 2 x 8 x 3 x 4= 192


Tableaux déchiquetés ou en escalier

Leur structuration est strictement semblable à celle des tableaux Java, en fait en C#  un tableau déchiqueté est composé de plusieurs tableaux unidimensionnels de taille variable. La déclaration s'effectue avec des opérateurs crochets  [ ] [ ]…  : autant de crochets que de dimensions. C# autorise comme Java, des tailles différentes pour chacun des sous-tableaux.

Ci-dessous le schéma d'un tableau T à trois dimensions en escalier :

Ce schéma montre bien qu'un tel tableau T est constitué de tableaux unidimensionnels, les tableaux composés de cases blanches contiennent des pointeurs (références). Chaque case blanche est une référence vers un autre tableau unidimensionnel, seules les cases grisées contiennent les informations utiles de la structure de données : les éléments de même type du tableau T.

Pour fixer les idées figurons la syntaxe des déclarations en C# d'un tableau d'éléments de type int nommé myArray bi-dimensionnel en escalier :

 

int n = 10;
int [ ][ ] myArray = new int [n][ ];
myArray[0] =  new int[7];
myArray[1] =  new int[9];
myArray[2] =  new int[3];
myArray[3] =  new int[4];
…
myArray[n-2] =  new int[2];
myArray[n-1] =  new int[8];

Ce tableau comporte 7+9+3+4+….+2+8 cellules utiles au stockage de données de type int, on peut le considérer comme une succession de tableaux d'int unidimensionnels (le premier ayant 7 cellules, le second ayant 9 cellules, etc…) . Les déclarations suivantes :

int n = 10;

int [ ][ ] myArray = new int [n][ ];

définissent un sous-tableau de 10 pointeurs qui vont chacun pointer vers un tableau unidimensionnel qu'il faut instancier :

 

 

myArray[0] =  new int [7];

 

instancie un tableau d'int unidimensionnel à 7 cases et renvoie sa référence qui est rangée dans la cellule de rang 0 du sous-tableau.

 

 

myArray[1] =  new int [9];

 

instancie un tableau d'int unidimensionnel à 9 cases et renvoie sa référence qui est rangée dans la cellule de rang 1 du sous-tableau.

 

Etc….

Dans le cas d'un tableau déchiqueté, le champ Length de la classe Array, contient la taille du sous-tableau uni-dimensionnel associé à la référence.

Soit la déclaration : int [ ][ ] myArray = new int [n][ ];
myArray est une référence vers un sous-tableau de pointeurs.
myArray.Length vaut 10 (taille du sous-tableau pointé)

Soit la déclaration :
myArray[0] =  new int [7];
MyArray [0] est une référence vers un sous-tableau de cellules d'éléments de type int.
myArray[0].Length vaut 7 (taille du sous-tableau pointé)

Soit la déclaration :
myArray[1] =  new int [9];
MyArray [1] est une référence vers un sous-tableau de cellules d'éléments de type int.
myArray[1].Length vaut 9 (taille du sous-tableau pointé)


C#  initialise les tableaux par défaut à 0 pour les int, byte, ... et à null pour les objets.

On peut simuler une matrice avec un tableau déchiqueté dont tous les sous-tableaux ont exactement la même dimension. Voici une figuration d'une matrice à n+1 lignes et à p+1 colonnes avec un tableau en escalier :

- Contrairement à Java qui l'accepte,  le code ci-dessous ne sera pas compilé par C# :
   int [ ][ ] table = new int [n+1][p+1];
 
- Il est nécessaire de créer manuellement tous les sous-tableaux :
 
    int [ ][ ] table = new int [n+1][ ];
    for (int i=0; i<n+1; i++)
       table[i] = new int [p+1];
 

 L'exemple précédent montre à l'évidence que si l'on souhaite réellement utiliser des matrices en C#, il est plus simple d'utiliser la notion de tableau multi-dimensionnel [ , ] que celle de tableau en escalier [ ] [ ].


Egalité et inégalité de tableaux

L'opérateur d'égalité  = =  appliqué au tableau de n'importe quel type, détermine si deux objets spécifiés ont la même référence, il se comporte dans ce cas comme la méthode Equals de la classe Object qui ne teste que l'égalité de référence

int [ ] a , b ;
(a = = b ) renvoie true si la référence a est la même que la référence b  ; sinon il renvoie false.

Le morceau de code ci-dessous créé deux tableaux de char t1 et t2, puis teste leur égalité avec l'opérateur = = et la méthode Equals :

char[ ] t1="abcdef".ToCharArray();
char[ ] t2="abcdef".ToCharArray();

 

if(t1==t2)System.Console.WriteLine("t1=t2");
  else System.Console.WriteLine("t1<>t2");
if(t1.Equals(t2))System.Console.WriteLine("t1 égal t2");
  else System.Console.WriteLine("t1 différent de t2");

Après exécution on obtient :
            t1<>t2
            t1 différent de t2

Ces deux objets (les tableaux) sont différents (leurs références pointent vers des blocs différents)bien que le contenu de chaque objet soit le même.

Affectation et recopie de tableaux

Comme les tableaux sont des objets, l'affectation de références de deux tableaux distincts donne les mêmes résultats que pour d'autres objets : les deux références de tableaux pointent vers le même objet. Donc une affectation d'un tableau dans un autre t1 = t2 ne provoque pas la recopie des éléments du tableau t2 dans celui de t1.

Si l'on souhaite que t1 soit une copie identique de t2, tout en conservant le tableau t2 et sa référence distincte il faut utiliser l'une des deux méthodes suivante de la classe abstraite mère Array :

public virtual object Clone( ) : méthode qui renvoie une référence sur une nouvelle instance de tableau contenant les mêmes éléments que l'objet de tableau qui l'invoque. (il ne reste plus qu'à transtyper la référence retournée puisque clone renvoie un type object)

public static void Copy ( Array t1 , Array t2, int long) : méthode de classe qui copie dans un tableau t2 déjà existant et déjà instancié, long éléments du tableau t1 depuis son premier élément (si l'on veut une copie complète du tableau t1 dans t2, il suffit que long représente le nombre total d'éléments soit long = t1.Length).

Dans le cas où le tableau t1 contient des références qui pointent vers des objets :

 
la recopie dans un autre tableau à travers les méthode Clone ou Copy ne recopie que les références, mais pas les objets pointés, voici un "clone" du tableau t1 de la figure précédente dans le tableau t2 :

Si l'on veut que le clonage (la recopie) soit plus complète et comprenne aussi les objets pointés, il suffit de construire une telle méthode car malheureusement la classe abstraite Array n'est pas implantable par l'utilisateur mais seulement par le compilateur et nous ne pouvons pas redéfinir la méthode virtuelle Clone).

Code source d'utilisation de ces deux méthodes sur un tableau unidimensionnel et sur une matrice :

  //-- tableau à une dimension :

 

Parcours itératifs de tableaux - foreach…in

Les instructions itératives for( …), while, do…while précédemment vues permettent le parcours d'un tableau élément par élément à travers l'indice de tableau. Il existe une instruction d'itération spécifique foreach…in qui énumère les éléments d'une collection, en exécutant un ensemble d'actions pour chaque élément de la collection.

Syntaxe


La classe Array est en fait un type de collection car elle implémente l'interface ICollection :

public abstract class Array : ICloneable, IList, ICollection, IEnumerable

Donc tout objet de cette classe (un tableau) est  susceptible d'être parcouru par un instruction foreach…in. Mais les éléments ainsi parcourus ne peuvent être utilisés qu'en lecture, ils ne peuvent pas être modifiés, ce qui limite d'une façon importante la portée de l'utilisation d'un foreach…in.

 

foreach…in dans un tableau uni-dimensionnel

Dans un tableau T à une dimension de taille long , les éléments sont parcourus dans l'ordre croissant de index en commençant par la borne inférieure 0 et en terminant par la borne supérieure long-1 (rappel : long  = T.Length ).

Dans l'exemple ci-après où un tableau uni-dimensionnel table est instancié et rempli il y a équivalence de parcours du tableau table , entre l'instruction for de gauche et l'instruction foreach de droite :

int [ ] table = new int [ 10 ]; …. Remplissage du tableau

for (int i=0; i<10; i++)

   System.Console.WriteLine ( table[i] );

foreach ( int val in table)

    System.Console.WriteLine ( val );


foreach…in dans un tableau multi-dimensionnel

Lorsque T est un tableau multi-dimensionnel microsoft indique : … les éléments sont parcourus de manière que les indices de la dimension la plus à droite soient augmentés en premier, suivis de ceux de la dimension immédiatement à gauche, et ainsi de suite en continuant vers la gauche.

Dans l'exemple ci-après où une matrice table est instanciée et remplie il y a équivalence de parcours de la matrice table, entre l'instruction for de gauche et l'instruction foreach de droite (fonctionnement identique pour les autres types de tableaux multi-dimensionnels et en escalier) :

int [ , ] table = new int [ 3 , 2 ]; …. Remplissage de la matrice

for (int i=0; i<3; i++)
  for (int j=0; j<2; i++)
   System.Console.WriteLine ( table[ i , j ] );

foreach ( int val in table)

    System.Console.WriteLine ( val );

Avantage : la simplicité d'écriture, toujours la même quelle que soit le type du tableau.
Inconvénient : on ne peut qu'énumérer en lecture les éléments d'un tableau.

 

Remonter  

3. Les Collections en C#


Généralités sur les collections

L'espace de noms System.Collections contient des interfaces et des classes qui permettent de manipuler des collections d'objets. Plus précisément, les données structurées classiques que l'on utilise en informatique comme les listes, les piles, les files d'attente,… sont représentées dans .Net framework par des classes directement utilisables du namespace System.Collections.

Quatre interfaces de cet espace de noms jouent un rôle fondamental : IEnumerable, IEnumerator, ICollection et IList selon les diagrammes d'héritage et d'agrégation suivants :


IEnumerable :

contient une seule méthode qui renvoie un énumérateur (objet de type IEnumerator) qui peut itérer sur les élément d'une collection (c'est une sorte de pointeur qui avance dans la collection, comme un pointeur de fichier se déplace sur les enregistrements du fichier) :

                  public IEnumerator GetEnumerator( );

IEnumerator :

Propriétés

public object Current {get;} Obtient l'élément en cours pointé actuellement par l'énumérateur dans la collection.

Méthodes

public bool MoveNext( ); Déplace l'énumérateur d'un élément il pointe maintenant vers l'élément suivant dans la collection (renvoie false si l'énumérateur est après le dernier élément de la collection sinon renvoie true).

public void Reset( ); Déplace l'énumérateur au début de la collection, avant le premier élément (donc si l'on effectue un Current on obtiendra la valeur null, car après un Reset( ), l'énumérateur ne pointe pas devant le premier élément de la collection mais avant ce premier élément !).

 ICollection :

Propriétés

public int Count {get;} Fournit le nombre d'éléments contenus dans ICollection.
public bool IsSynchronized {get;}
  		Fournit un booléen indiquant si l'accès à ICollection est synchronisé (les éléments de ICollection sont protégés de l'accès simultanés de plusieurs threads différents).
public object SyncRoot {get;}
  		Fournit un objet qui peut être utilisé pour synchroniser (verrouiller ou déverrouiller) l'accès à ICollection.

Méthode

public void CopyTo ( Array table, int index) Copie les éléments de ICollection dans un objet de type Array (table), commençant à un index fixé.

 

IList :

Propriétés

public bool IsFixedSize {get;} : indique si IList est de taille fixe.
public bool IsReadOnly {get;} : indique si IList est en lecture seule.
Les classes implémentant l'interface IList sont indexables par l'indexeur [ ].

 
Méthodes (classique de gestion de liste)

public int Add( object elt ); Ajoute l'élément elt à IList.
public void Clear( ); Supprime tous les éléments de IList.
public bool Contains( object elt ); Indique  si IList contient l'élément elt en son sein.
public int IndexOf( object elt ); Indique le rang de l'élément elt dans IList.
public void Insert( int rang , object elt ); Insère l'élément elt dans IList à la position spécifiée par rang.
public void Remove( object elt ); Supprime la première occurrence de l'objet elt de IList.
public void RemoveAt (int rang); Supprime l'élément de IList dont le rang est spécifié.

Ces quatre interfaces C# servent de contrat d'implémentation à de nombreuses classes de structures de données, nous en étudions quelques unes sur le plan pratique dans la suite du document.

Les tableaux dynamiques : classe ArrayList

Un tabeau Array à une dimension, lorsque sa taille a été fixée soit par une définition explicite, soit par une définition implicite, ne peut plus changer de taille, c'est donc un objet de taille statique.

char [ ] TableCar ;
TableCar = new char[8]; //définition de la taille et création d'un nouvel objet tableau à 8 cellules
TableCar[0] = 'a';
TableCar[1] = '#';
...
TableCar[7] = '?';


Si l'on rajoute l'instruction suivante aux précédentes

< TableCar = new char[10]; > il y a création d'un nouveau tableau de même nom et de taille 10, l'ancien tableau à 8 cellules est alors détruit. Nous ne redimensionnons pas le tableau, mais en fait nous créons un nouvel objet utilisant la même variable de référence TableCar que le précédent, toutefois la référence TableCar pointe vers le nouveau bloc mémoire :


Ce qui nous donne après exécution de la liste des instructions ci-dessous, un tableau TabCar ne contenant plus rien :

char [ ] TableCar ;
TableCar = new char[8];
TableCar[0] = 'a';
TableCar[1] = '#';
...
TableCar[7] = '?';
TableCar = new char[10];

Comment faire pour "agrandir" un tableau pendant l'exécution

  • Il faut déclarer un nouveau tableau t2 plus grand,
  • puis recopier l'ancien dans le nouveau, par exemple en utilisant la méthode public static void Copy ( Array t1 , Array t2, int long)

IL est possible d'éviter cette façon de faire en utilisant une classe de vecteur (tableau unidimensionnel dynamique) qui est en fait une liste dynamique gérée comme un tableau.

La classe concernée se dénomme System.Collections.ArrayList, elle hérite de la classe object et implémente les interfaces  IList, ICollection, IEnumerable, ICloneable
( public class ArrayList :  IList, ICollection, IEnumerable, ICloneable;)

Un objet de classe ArrayList peut "grandir" automatiquement  d'un certain nombre de cellules pendant l'exécution, c'est le programmeur qui peut fixer la valeur d'augmentation du nombre de cellules supplémentaires dès que la capacité maximale en cours est dépassée. Dans le cas où la valeur d'augmentation n'est pas fixée, c'est la machine virtuelle du CLR qui procède à une augmentation par défaut.

Vous pouvez utiliser le type ArrayList avec n'importe quel type d'objet puisqu'un ArrayList contient des éléments de type dérivés d'object (ils peuvent être tous de types différents et le vecteur est de type hétérogène).

Les principales méthodes permettant de manipuler les éléments d'un ArrayList sont :

public virtual int Add( object value ); Ajoute un l'objet value à la fin de ArrayList.
public virtual void Insert(int index, object value); Insère un élément dans ArrayList à l'index spécifié.
public virtual void Clear(); Supprime tous les éléments de ArrayList.
public virtual void Remove(object obj); Supprime la première occurrence d'un objet spécifique de ArrayList.
 public virtual void Sort( ); Trie les éléments dans l'intégralité de ArrayList à l'aide de l'implémentation IComparable de chaque élément (algorithme QuickSort).
ArrayList Table;
Table[i] = ....; 		Accès en lecture et en écriture à un élément quelconque de rang i du tableau par Table[i] 
PROPRIETE
public virtual int Count { get ;} Vaut le nombre d'éléments contenus dans ArrayList, propriété en lecture seulement..
  [  ] Propriété indexeur de la classe, on l'utilise comme un opérateur tab[ i ]  accède à l'élément de rang i.

Voici un exemple simple de vecteur de chaînes utilisant quelques unes des méthodes précédentes :

static void afficheVector (ArrayList vect)  //affiche un vecteur de string
 {
   System.Console.WriteLine( "Vecteur taille = " + vect.Count );
   for ( int i = 0; i<= vect.Count-1; i++ )
        System.Console.WriteLine( "Vecteur[" + i + "]=" + (string)vect[ i ] );
 }

static void VectorInitialiser ( ) // initialisation du vecteur de string
{    ArrayList table = new ArrayList( );
      string str = "val:";
      for ( int i = 0; i<=5; i++ )
             table.Add(str + i.ToString( ) );
      afficheVector(table);
}

Voici le résultat de l'exécution de la méthodeVectorInitialiser :
Vector taille = 6
Vector[0] = val:0
Vector[1] = val:1
Vector[2] = val:2
Vector[3] = val:3
Vector[4] = val:4
Vector[5] = val:5


Les listes chaînées : classe ArrayList

Rappelons qu'une liste linéaire (ou liste chaînée) est un ensemble ordonné d'éléments de même type (structure de donnée homogène) auxquels on accède séquentiellement. Les opérations minimales effectuées sur une liste chaînée sont l'insertion, la modification et la suppression d'un élément quelconque de la liste.

Les listes peuvent être uni-directionnelles, elles sont alors parcourues séquentiellement dans un seul sens :


 
ou bien bi-directionnelles dans lesquelles chaque élément possède deux liens de chaînage, l'un sur l'élément qui le suit, l'autre sur l'élément qui le précède, le parcours s'effectuant en suivant l'un ou l'autre sens de chaînage :

La classe ArrayList peut servir à une implémentation de la liste chaînée uni ou bi-directionnelle; un ArrayList contient des éléments de type dérivés d'Object, la liste peut donc être hétérogène, cf exercice sur les listes chaînées.
 

Liste à clefs triées : classe SortedList

Si l'on souhaite gérer une liste triée par clef, il est possible d'utiliser la classe SortedList (localisation : System.Collections.SortedList ). Cette classe représente une collection de paires valeur-clé triées par les clés toutes différentes et accessibles par clé et par index : il s'agit donc d'une liste d'identifiants et de valeur associée à cet identifiant, par exemple une liste de personne dont l'identifiant (la clef) est un entier et la valeur associée des informations sur cette personne sont stockées dans une structure (le nom, l'âge, le genre, ...). Cette classe n'est pas utile pour la gestion d'une liste chaînée classique non rangée à cause de son tri automatique selon les clefs.

En revanche, si l'on stocke comme clef la valeur de Hashcode de l'élément, la recherche est améliorée.

Les principales méthodes permettant de manipuler les éléments d'un SortedList sont :

public virtual int Add( object key,object value ); Ajoute un élément avec la clé key et la valeur value spécifiées dans le  SortedList.
public virtual void CopyTo(  Array array,
   int arrayIndex ); 		Copie les éléments du SortedList dans une instance Array array unidimensionnelle à l'index arrayIndex spécifié (valeur de l'index dans array où la copie commence).
public virtual void Clear( ); Supprime tous les éléments de SortedList.
public virtual object GetByIndex( int index ); Obtient la valeur à l'index spécifié de la liste SortedList.
public virtual object GetKey( int index ); Obtient la clé à l'index spécifié de SortedList.
public virtual int IndexOfValue( object value ); Retourne l'index de base zéro de la première occurrence de la valeur value spécifiée dans SortedList.
public virtual int IndexOfKey( object key ); Retourne l'index de base zéro de la clé key spécifiée dans SortedList.
public virtual void Remove( object key ); Supprime de SortedList l'élément ayant la clé key spécifiée.
public virtual void RemoveAt( int index ); Supprime l'élément au niveau de l'index spécifié de SortedList.
public virtual IList GetValueList ( ); Obtient  un objet de liste IList en lecture seule contenant toutes les valeurs triées dans le même ordre que dans le SortedList.
PROPRIETE
public virtual int Count { get ; } Vaut le nombre d'éléments contenus dans SortedList, propriété en lecture seulement.
 [  ] Propriété indexeur de la classe, on l'utilise comme un opérateur tab[ i ]  accède à l'élément dont la clef vaut i.
public virtual ICollection Values { get; } Obtient dans un objet de ICollection les valeurs dans SortedList. (les éléments de ICollection sont tous triés dans le même ordre que les valeurs du SortedList)
public virtual ICollection Keys { get; } Obtient dans un objet de ICollection les clés dans SortedList. (les éléments de ICollection sont tous triés dans le même ordre que les clefs du SortedList)

Exemple d'utilisation d'un SortedList  :

   SortedList Liste = new SortedList ( );
   Liste.Add(100,"Jean");
   Liste.Add(45,"Murielle");
   Liste.Add(201,"Claudie");
   Liste.Add(35,"José");
   Liste.Add(28,"Luc");

    //----> Balayage complet de la Liste par index :
   for (int i=0; i<Liste.Count; i++)
     System.Console.WriteLine( (string)Liste.GetByIndex(i) );

   //----> Balayage complet de la collection des valeurs :
   foreach(string s in Liste.Values)
     System.Console.WriteLine( s );

   //----> Balayage complet de la collection des clefs :
   foreach(object k in Liste.Keys)
    System.Console.WriteLine( Liste[k] );

  //----> Balayage complet de l'objet IList retourné :
  for (int i = 0; i < Liste.GetValueList( ).Count; i++)
     System.Console.WriteLine( Liste.GetValueList( ) [ i ] );

Soit la représentation suivante (attention à la confusion entre clef et index) :


Les trois boucles affichent dans l'ordre :
           Luc
           José
           Murielle
           Jean
           Claudie

 

Piles Lifo, files Fifo : classes Stack et Queue

La classe "public class Stack : ICollection, IEnumerable, ICloneable" représente une pile Lifo :

public virtual object Peek ( ); Renvoie la référence de l'objet situé au sommet de la pile.
public virtual object Pop( ); Dépile la pile (l'objet au sommet est enlevé et renvoyé)
public virtual void Push( object elt ); Empile un objet au sommet de la pile.
public virtual object [ ] ToArray( ); Recopie toute la pile dans un tableau d'objet depuis le sommet jusqu'au fond de la pile (dans l'ordre du dépilement).

La classe "public class Queue : ICollection, IEnumerable, ICloneable" représente une file Fifo :
public virtual object Peek ( ); Renvoie la référence de l'objet situé au sommet de la file.
public virtual object Dequeue( ); L'objet au début de la file est enlevé et renvoyé.
public virtual void Enqueue ( object elt ); Ajoute un objet à la fin de la file.
public virtual object [ ] ToArray( ); Recopie toute la file dans un tableau d'objet depuis le début de la fifo jusqu'à la fin de la file.

Ces deux classes font partie du namespace System.Collections :

System.Collections.Stack
System.Collections.Queue

Exemple d'utilisation d'une Lifo de type Stack

Construisons une pile de string possédant une méthode getArray permettant d'empiler immédiatement dans la pile tout un tableau de string.

Le programme ci-dessous rempli avec les chaînes du tableau t1 grâce à la méthode getArray , la pile Lifo construite. On tente ensuite de récupérer le contenu de la pile sous forme d'un tableau de chaîne t2 (opération inverse) en utilisant la méthode ToArray. Le compilateur signale une erreur :



En effet la méthode ToArray renvoie un tableau d'object et non un tableau de string. On pourrait penser à transtyper explicitement   :

    t2 = ( string [ ] ) piLifo.ToArray( ) ;

en ce cas C# réagit comme Java, en acceptant la compilation, mais en générant une exception de cast invalide, car il est en effet dangereux d'accepter le transtypage d'un tableau d'object en un tableau de quoique ce soit, car chaque object du tableau peut être d'un type quelconque et tous les types peuvent être différents !


Il nous faut donc construire une méthode qui ToArray  effectue le transtypage de chaque cellule du tableau d'object et renvoie un tableau de string, or nous savons que la méthode de classe Array nommée Copy un tableau t1 vers un autre tableau t2 en effectuant éventuellement le transtypage des cellules : Array.Copy(t1 , t2 , t1.Length)

Voici le code de la nouvelle méthode ToArray :

Nous avons mis le qualificateur new car cette méthode masque la méthode mère de la classe Stack, nous avons maintenant une pile Lifo de string, construisons de la même manière la classe Fifo de file de string dérivant de la classe Queue avec une méthode getArray et la méthode ToArray redéfinie :

 

Remonter