Liste linéaire

Algorithme
Liste fondée sur un tableau dynamique en C#

Objectif : Effectuer un travail de familiarisation avec la structure de liste dynamique adressable triée correspondant à la notion de tableau dynamique trié. Ce genre de structure cumule les avantages d'un structure de liste linéaire (insertion, ajout,...) et d'un tableau autorisant les accès direct par un index.
Il existe en C# une classe de liste triée orientée clef-valeurs qui se dénomme SortedList, toutefois à titre pédagogique nous voulons utiliser une liste chaînée simple, nous allons pour cela implanter notre propre classe de liste de noms qui contiendra une instance de classe de tableau dynamique. Une implantation plus réutilisable que nous emploierons plus tard, consistera à plutôt construire une classe de liste qui hérite de la classe de tableau dynamique.
La classe concernée se dénomme ArrayList, elle hérite de la classe object et implémente les interfaces IList, ICollection, IEnumerable, ICloneable
( public class ArrayList : IList, ICollection, IEnumerable, ICloneable )
Question n°1 initialiser et ecrire la liste
Question n°2 trier la liste par sélection
Question n°3 insérer un élément dans la liste triée
Des méthodes utiles sur les objets de classe ArrayList

Nous utilisons donc un objet ArrayList pour implanter une liste triée de noms, les éléments contenus dans la liste sont des chaînes de caractères (des noms)..
Question n°1:

Codez la méthode "initialiser" qui permet de construire la liste suivante :
Liste = ( voiture, terrien, eau, pied, traineau, avion, source, terre, xylophone, mer, train, marteau ).
Codez la méthode "ecrire" qui permet d'afficher le contenu de la liste et qui produit l'affichage suivant :

voiture, terrien, eau, pied, traineau, avion, source, terre, xylophone, mer, train, marteau,
Taille de la liste chaînée = 12

squelette proposé pour chaque méthode :

static void initialiser ( ArrayList L ) {....}
static void ecrire( ArrayList L ) {....}

Remarque importante :
Une entité de classe ArrayList est un objet. un paramètre C# de type objet est une référence, donc nous n'avons pas le problème du passage par valeur du contenu d'un ojet. En pratique cela signifie que lorsque le paramètre est un objet il à la fois en entrée et en sortie. Ici le ArrayList L est modifié par toute action interne effectuée sur lui dans les méthodes "initialiser" et "ecrire".

Remonter
Question n°2:

Ecrire une méthode permettant de trier la liste des noms par odre alphabétique croissant en utilisant l'algorithme de tri par sélection.
squelette proposé pour la méthode :

static void triSelect (ArrayList L ) {....}

Remonter
Question n°3:
Ecrire une méthode permettant d'insérer un nouveau nom dans une liste déjà triée, selon l'algorithme proposé ci-dessous :
Spécifications de l’algorithme :

L : Liste de noms déjà triée,
Elt : le nom à insérer dans la liste L.
taille(L) : le nombre d'éléments de L
début
si (la liste L est vide) ousinon ( dernierElement de la liste L £ Elt ) alors
    ajouter Elt en fin de liste L
sinon
pour i ¬ 0 jusquà taille(L)-1 faire
   si Elt £ Element de rang i de L alors
          insérer Elt à cette position ;
          sortir
   fsi
fpour
fsi
fin

squelette proposé pour la méthode :

static void inserElem (ArrayList L, string Elt ) {....}

Contenu proposé de la méthode Main avec les différents appels :

class ApplicationListeSimple {
static void Main(string[] Args)
{
   //---> la liste de noms instance de ArrayList :
   ArrayList Liste = new ArrayList(); //
   //---> contenu de la Liste - initialisation :
   initialiser(Liste);
   ecrire(Liste);
   //---> Tri de la liste
   System.Console.WriteLine("\nListe une fois triée : ");
   triSelect(Liste);
   ecrire(Liste);
   //---> Insérer un élément dans la liste triée
   string StrInserer ="trainard";
   System.Console.WriteLine("\nInsertion dans la liste de : "+StrInserer);
   inserElem(Liste, StrInserer);
   ecrire(Liste);
   //---> Contenu de la Liste - boolean remove(Object x) :
   System.Console.WriteLine("\nListe.remove('pied') : ");
   Liste.Remove("pied");
   ecrire(Liste);
   System.Console.Read();
}
}

Remonter

Voici ci-dessous les méthodes principalement utiles à la manipulation d'une telle liste:
Classe ArrayList :

public virtual int Add( objectvalue ); 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 int Count ; Obtient le nombre d'éléments réellement contenus dans ArrayList : propriété en lecture seulement.

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]

Remonter

public virtual int Add( objectvalue );	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 int Count ;	Obtient le nombre d'éléments réellement contenus dans ArrayList : propriété en lecture seulement.
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]