:
|
Site: |
Cours VB.net |
|
E 1.3 |
Exemples:Tableaux, collections: |
 |
 |
Tri, recherche, insertion , effacement d'élément.
Le travail sur des tableaux est très intéressant. On étudiera plusieurs routines en comparant la méthode classique et les fonctions du Framework. Puis on utilisera les collections pour faire la même chose.
On verra comment:
1 -Comment utiliser un tableau ou une collection.
2 -Utiliser les TABLEAUX
A- Trier un tableau.
B- Rechercher un élément dans un tableau.
C- Effacer, insérer un élément dans un tableau.
3 - Utiliser les COLLECTIONS.
A- Trier une collection.
B- Rechercher un élément dans une collection.
C- Effacer, insérer un élément dans une collection.
4 - Utilisation particulière des tableaux.
1 - Tableaux ou collections:
Nous avons une série de 100 adresses comprenant chacune un numéro, une rue, une ville.
Dans quoi les stocker?
1- On peut utiliser un tableau à plusieurs dimensions.
Un tableau peut avoir plusieurs dimensions, cela permet plusieurs indices:
Soit un tableau T(,) de String permettant de stocker en mémoire les adresses (Numéro, Rue, Ville..)
Dim T(99,2) As String
On constate que tous les éléments ont le même type (String ici).
Numéro Rue Ville
| 32 | grande rue | Paris |
| 12 | place | Lyon |
| .. | ||
...
Le premier indice est l'indice de chaque adresse (ligne).
Le second indice, celui de la colonne, indique la nature de l'information: numéro, rue, ville.
Ainsi le numéro de l'adresse 1 est T(0,0)
On peut mettre 12 dans le numéro de la seconde adresse T(1,0)="12"
On peut mettre la ville de l'adresse 3 dans une variable:
Dim laVille As String= T(2,2)
On peut balayer toutes les villes avec une boucle, pour chercher une ville par exemple:
For i As Integer =0 To 99
If T(i,2)="Lyon" Then...
Next i
2- On peut aussi définir une structure et travailler sur un tableau 'structuré'.
Public Structure Adresse
Dim Numero As Integer
Dim Rue As String
Dim Ville As String
End Structure
Il est ensuite possible de travailler sur un tableau de variable 'structure'
Dim Adresses(99) As Adresse 'Permet de travailler sur un tableau de 100 adresses
Adresses(33).Rue="Place de la mairie"
On peut mettre la ville de l'adresse 3 dans une variable:
Dim laVille As String= Adresses(2).Ville
On peut balayer toutes les villes avec une boucle, pour chercher une ville par exemple:
For i As Integer =0 To 99
If Adresses(i).Ville ="Lyon" Then...
Next i
Un tableau a un nombre défini d'élément quand on le déclare, plus les dimensions sont grandes, plus il occupe de place, même si certains de ses éléments sont vides. Une collection ne contient que les éléments qu'on a mis.
3- On peut utiliser une collection.
Il faut créer une Classe:
Public Class Adresse
Public Numero As Integer
Public Rue As String
Public Ville As String
End Class
Déclarer une instance de cette classe.
Dim Adresse1 As New Adresse
Adresse1.Rue= "Place de la mairie"
Créer une collection.
Dim MesAdresses As New ArrayList
Y ajouter les adresses.
MesAdresses.Add ( Adresse1)
Afficher dans une MsgBox la rue du premier élément.
MsgBox(CType(MesAdresses.Item(0), Adresse).Rue)
Le top c'est de créer une collection génériques
Dim MesAdresses As New List( Of adresse)
Elle ne pourra contenir que des adresses.
MsgBox(MesAdresses.Item(0).Rue)
Le travail sur les tableaux est beaucoup plus rapide que sur les collections.
Par exemple , pour stocker 1000 string dans un tableau ou une collection, l'usage du tableau est 60% plus rapide.
En programmation fonctionnelle on utilise les tableaux par habitude, en programmation Objet on utilise bien les Collections.
2 - Utiliser les Tableaux:
A- Le Tri
Routine de Tri .
Pour trier un tableau de chaînes de caractères, il faut comparer 2 chaînes contiguës, si la première est supérieure (c'est à dire après l'autre sur le plan alphabétique)on inverse les 2 chaînes, sinon on n'inverse pas. Puis on recommence sur 2 autres chaînes en balayant le tableau jusqu'à ce qu'il soit trié.
Tout l'art des routines de tri est de faire le moins de comparaisons possible pour trier le plus vite possible.
Voyons une des routines les plus rapides, le Bubble Sort (ou tri à bulle); on le nomme ainsi car l'élément le plus grand descend progressivement au fur et à mesure jusqu'à la fin du tableau comme une bulle.(il faut imaginer la surface en bas et les bulles qui descendent!!
Une boucle interne balaye le tableau et compare 2 élément contigus et les inverse si nécessaire. Une boucle externe fait tourner la boucle interne N fois.
La boucle interne fait descendre l'élément le plus grand vers la fin du tableau, la boucle externe répète l'opération N fois permettant le tri de tous les éléments.
Private
Sub Button1_Click'Création du tableau et de son contenu non trié.
Dim T(5) As String 'élément de 0 à 4
T(0) = "toto"
T(1) = "tata"
T(2) = "tutu"
T(3) = "lolo"
T(4) = "lulu"
'Création des variables
Dim N As Integer = 5 'Nombre d'éléments
Dim i, j As Integer
Dim Temp As String 'Variable temporaire
'Routine de tri
For i = 0 To N - 1 'Boucle externe
For j = 0 To N - 1 'Boucle interne
If T(j) > T(j + 1) Then
Temp = T(j) : T(j) = T(j + 1) : T(j + 1) = Temp 'Inverser si pas dans le bon ordre
End If Next j
Next i
' Pour afficher le tableau trié dans un textbox
Dim tt As String= ""
For i = 0 To Ntt = tt + T(i) + ControlChars.CrLf
Next iTextBox1.Text = tt
End Sub
Remarque: pour inverser le contenue de 2 variables, on doit écrire
Temp=T(j): T(j)=T(j+1):T(j+1)=Temp (L'instruction qui faisait cela en VB6 et qui se nommait Swap n'existe plus)
Cette routine trie bien le tableau mais n'est pas optimisée: il n'est pas nécessaire que la boucle interne tourne de 0 à N-1 à chaque fois car après une boucle ,le dernier élément, le plus grand, est à sa place. Pour i=0 la boucle interne tourne jusqu'à N-1, pour i=1 jusqu'à N-2...
Cela donne:
For i=0 To N-1
For j=0 To N-i-1
If T(j)>T(j+1) then
Temp=T(j): T(j)=T(j+1):T(j+1)=Temp
End if
Next j
Next i
Il existe d'autres méthodes encore plus rapide (Méthode de Shell et Shell-Metzner), il existe aussi le QuickSort très performant pour les tableaux non triés , voir chapitre sur la récursivité.
Mais il y a plus simple:
Tri avec la méthode SORT du Framework.
Pour un tableau unidimensionnel.
Dim Animals(2) As String
Animals(0) = "lion"
Animals(1) = "girafe"
Animals(2) = "loup"
Array.Sort(Animals)
Et le tableau est trié!!
On rappelle que l'on ne peut pas trier un tableau multidimensionnelle, mais il y a des ruses.(voir rubrique:tableau)
Les Collections peuvent être triées automatiquement aussi.
B- Recherche dans un tableau.
Routine de recherche:
On a un tableau de string, on veut chercher ou se trouve(en quelle position) une string.
Pour une liste non triée, on n'a pas d'autres choix que de comparer la string cherchée à chaque élément du tableau, on utilisera donc une boucle:
N=4 'tableau de 5 éléments.
Dim T(N) As String 'élément de 0 à 4
T(0)="vert"
T(1)="bleu"
T(2)="rouge"
T(3)="jaune"
T(4)="blanc"
Dim i As Integer 'Variable de boucle
Dim AChercher As String= "rouge" 'String à chercher
For i=0 To N
If T(i)=AChercher then
Exit For
End if
Next i
'i contient 2
Pour une liste triée (suite ordonnée), on peut utiliser la méthode de recherche dichotomique: On compare l'élément recherché à l'élément du milieu du tableau, cela permet de savoir dans quelle moitié se situe l'élément recherché. De nouveau on compare à l'élément recherché à l'élément du milieu de la bonne moitié...jusqu'à trouver. Pour cela on utilise les variables Inf et Sup qui sont les bonnes inférieure et supérieure de la zone de recherche et la variable Milieu. On compare l'élément recherché à l'élément du tableau d'indice milieu, si il sont égaux on a trouvé , on sort; si ils sont différents on modifie Inf et Sup pour pointer la bonne plage puis on donne à Milieu la valeur du milieu de la nouvelle plage et on recommence.
Dim N As Integer
Dim T(N) As String 'élément de 0 à 4
Dim Inf, Sup, Milieu As Integer '
Dim Reponse As Integer 'contient le numero de l'élément
'ou -1 si élément non trouvé
Dim i As Integer 'Variable de boucle
Dim AChercher As String= "c" 'String à chercher
N=4 'tableau de 5 éléments.
T(0)="a"
T(1)="b"
T(2)="c"
T(3)="d"
T(4)="e"
Inf=0: Sup=N
Do
if inf>Sup then Reponse=-1: Exit Do
Milieu= INT((Inf+Sup)/2)
If Achercher=T(Milieu) then Reponse=Milieu:Exit Do
If Achercher<T(Milieu) then Sup=Milieu-1
If Achercher>T(Milieu) then Inf=Milieu+1
Loop
'Reponse =2
La recherche dichotomique est rapide car il y a moins de comparaisons.
Recherche avec les facilités du Framework.
Mais comme d'habitude VB.Net possède des propriétés permettant de rechercher dans un tableau trié ou non et cela sans avoir à écrire de routine.
Binarysearch recherche un élément dans un tableau trié unidimensionnel.(algorithme de comparaison binaire performant sur tableau trié: probablement une recherche dichotomique)
Exemple :
I=Array.BinarySearch(Mois, "Février")
IndexOf
Recherche un objet spécifié dans un tableau unidimensionnel (trié ou non), retourne l'index de la première occurrence.
Dim myIndex As Integer =
Array.IndexOf(myArray, myString)
Retourne -1 si l'élément n'est pas trouvé.
LastIndexOf fait une recherche à partir de la fin.
C- Eliminer, insérer un élément dans un tableau.
1- Éliminer un élément.
Avec une routine:
Soit un tableau de 4 String T(0), T(1), T(2),T(3).
| Toto |
| Tata |
| Tonton |
| Titi |
On veut éliminer l'élément "Tata", le second élément; il faut passer le troisième dans le second, le quatrième dans le troisième... et effacer le dernier élément du tableau.
Dim N As Integer
Dim T(N) As String 'création d'un tableau de String.
Dim i As Integer
For i= 1 To N-1
T(i)=T(i+1)
Next i
T(N-1)="" 'ne pas oublier de modifier le dernier élément
On obtient:
| Toto |
| Tonton |
| Titi |
On remarque que la boucle démarre au niveau de l'élément à enlever et pas à la fin du tableau.
Avec les facilités du Framework:
On peut décaler les éléments d'un tableau avec la méthode Copy de la Classe Array:
Il suffit de copier le tableau sur le même tableau mais décalé d'un élément.
Array.Copy(T, 2, T, 1, T.Length - 2)
T(T.Length-1)=""
On utilise ici une surcharge de Copy:
Array.Copy(Tor, indexOrigine, td, indexDestitation, nombredElements)
Tor: Tableau d'origine; Td tableau destination.
2-Insérer un élément.
Avec une routine:
Soit un tableau de 4 String T(0), T(1), T(2),T(3).
| Toto |
| Tonton |
| Titi |
On veut insérer l'élément "Tata" en seconde position, après "Toto"; il faut d'abord décaler les éléments vers la fin du tableau. Attention : il faut le faire en commençant par la fin du tableau: il faut passer l'avant dernier élément en dernière position puis l'avant avant dernier en avant dernière position.
Dim N As Integer
Dim T(N) As String 'création d'un tableau de String.
Dim i As Integer
For i= N-1 To 1 Step -1
T(i)=T(i-1)
Next i
T(1)="Tata" 'ne pas oublier d'ajouter
On obtient:
| Toto |
| Tata |
| Tonton |
| Titi |
On remarque que la boucle doit commencer à la fin du tableau et remonter.
Avec les facilités du Framework:
On peut déplacer les éléments avec la méthode Copy de Array:
On copie le tableau sur le même tableau mais décalé d'un élément.
Array.Copy(T, 1, T, 2, T.Length - 2)
T(1)="Tata"
On utilise ici une surcharge de Copy:
Array.Copy(Tor, indexOrigine, td, indexDestitation, nombredElements)
Tor: Tableau d'origine; Td tableau destination
3 - Utiliser les collections:
Relire le chapitre sur les collections.
On rappelle que nombre d'élément dans une collection n'est pas défini au départ comme dans un tableau. Dans une collection il n'y a que les éléments que l'on a ajouté.
Les éléments sont repérés grâce à un index, mais attention, si vous ajoutez un élément, cela décale l'index des éléments qui suivent.
Dim L As New ArrayList() 'On crée une collection ArrayList
L.Add("toto") 'On ajoute un élément à la collection
MsgBox(L(0)) 'On affiche le premier élément
On pourra aussi écrire L.Item(0) pour pointer le premier élément.
MsgBox(L.Count.ToString) 'On affiche le nombre d’élément.
Attention c'est le nombre d'éléments. S'il y a 3 éléments dans la ArrayList ce sont les éléments d'index 0,1,2.
A- Le Tri d'une collection.
L.Sort() 'Trie la collection
B- Recherche dans une collection.
L.Containts (élément) ' Retourne True si la liste contient élément.
Recherche d'un élément dans une collection NON TRIEE avec IndexOf:
Dim i As Integer
Dim l As New ArrayList
l.Add("toto")
l.Add("lulu")
i = l.IndexOf("lulu")
MsgBox(i.ToString)
'Affiche 1
On rappelle qu'il existe aussi LastIndexOf qui démarre par la fin et une surcharge permettant de débuter la recherche à partir d'un indice donné.
Recherche d'un élément dans une collection TRIEE avec BinarySearch:
Dim
l As New ArrayList Dim i As Integerl.Add("toto")
l.Add("lulu")
l.Sort()'Il est nécessaire que le tableau soit trié
i = l.BinarySearch("lulu")
MsgBox(i.ToString)
C- Éliminer, insérer un élément dans une collection.
L.Remove("toto") 'On enlève un élément de la liste
L.RemoveAt(0) 'On enlève l’élément 0 de la liste
Insert permet d’insérer à un index spécifié.
L.Insert( position, Ainserrer)
4 - Autre utilisation des Tableaux:
Utiliser un tableau plutôt qu'une lourde routine permet parfois de résoudre un problème de programmation .
Le principe est: plutôt que d'utiliser une multitude de test pour trouver une valeur, il est parfois préférable de mettre judicieusement les valeurs dans un tableau et ensuite de lire la bonne 'case'.
1 - Exemple 1:
J'ai besoin de savoir le nom du jour de la semaine en fonction de son numéro.
1 doit retourner "Lundi"
2 doit retourner "Mardi"
3 doit retourner "Mercredi"
..
Avec If Then
C'est pas bien élégant, en plus il faut appeler la routine à chaque fois qu'on veut le nom.
Dim J As Integer ' Contient le numéro du jour
Dim Nom As String
If J= 1 Then
Nom="Lundi"
ElseIf J= 2 Then
Nom="Mardi"
...
End If
Avec Select Case
On peut faire un Select Case, c'est pas bien élégant, en plus il faut appeler la routine à chaque fois qu'on veut le nom.
SelectCase J
Case 1
Nom="Lundi"
Case 2
Nom="Mardi"
..
End Select
Avec un tableau
C'est plus élégant de créer un tableau.
Dim Nom as String ={"Lundi", "Mardi", "Mercredi"...."Dimanche"}
Lenom= Nom (J-1)
C'est plus commode et le plus compact.
Notez que le premier élément du tableau étant l'élément 0 , il faut utiliser J-1.
Avec le Framework
On utilise pour cela une énumération:
Enum NomJour
Lundi
Mardi
Mercredi
Jeudi
Vendredi
Samedi
Dimanche
End Enum
puis
Dim
s As Type = GetType(NomJour) 'on instance sNom = [Enum].GetName(s, J) 'Paramètre: une instance de l'énumération et J; retourne le nom.
2 - Exemple 2:
J'ai besoin de connaître le risque de faire un accident vasculaire en fonction du sexe et de la tranche d'age.
10 à 20 ans , Homme doit retourner 0
...
60 à 70 ans et Femme doit retourner 20
...
Avec If Then
C'est pas bien élégant, en plus il faut appeler la routine à chaque fois.
Dim S As Integer ' Contient le sexe 0 masculin, 1 féminin
Dim A As Integer ' Contient la tranche d'age
Dim Risque As Integer
If S= 1 Then
If A=1 Then
Risque=0
ElseIf A=2 Then
Risque=3
..
End If
Else
If A=1 Then
Risque=0
ElseIf A=2 Then
Risque=3
..
End If
End If
Avec un tableau
C'est plus élégant de créer un tableau a 2 dimensions.
Les colonnes indiquent le sexe, les lignes, la tranche d'age.
Sexe Masculin Sexe Féminin
| 0 | 0 |
| 1 | 30 |
| ... | ... |
Dim Risques(,) as Integer ={{0, 0}, {1, 2}, {0, 0}, {2, 3}}
Risque= Risques(S, A)
|
|
 |
|
|