Auteur : ClemTB
Date : 04/07/2007
Citation :
l'intérêt est très théorique mais ce script peut se révéler utile dans l'implémentation d'une pile ou d'un tas.
Je vais mettre la version améliorée pour l'insertion ici. Il utilise la librairie math include dans la version de base de AutoIt donc devrai pas y avoir de problème (au pire suffit de ré-écrire la fonction _Min($n1,$n2) ...
Par contre pour la librairie array ... si vous lavez pas tant pis :p
J'ai des temps assez correctes (90ms pour insérer 1000 éléments, temps d'accès maximum vu 0,06ms et temps pour vider min pour vider le tableau 47ms) vu grâce à la fonction de test
Code : Tout sélectionner
#include-once
#include
#include
;************************************************************************
;* Auteur: ClemTB
;* Date: 04/07/2007
;* Pays:France
;*
;* Description:
;* Script contenant le minimum vital pour implémenter
;* un tableau dynamique a partir d'un tableau statique.
;*
;* Fonctions disponibles:
;* getListe($position) :retrouve un élément O(n)
;* addElement($element) :ajoute un élément en début de chaîne O(1)
;* deleteElement($position) :supprime un élément dans la liste O(n)
;*
;* Commentaire:
;* Je l'ai commenté du mieux que je pouvait.
;*
;*************************************************************************
;tableau de contenu 10000 enregistrements ca devrait suffire non?
Global $__Listechainee_maxEnregistrements = 1000
Global $__Listechainee_tableContenu[$__Listechainee_maxEnregistrements]
;tableau de pointeurs
Global $__Listechainee_tablePointeurs[$__Listechainee_maxEnregistrements]
Global $__Listechainee_nbEnregistrement = 0
Global $__Listechainee_debut = 0
Global $__Listechainee_minInsertion = 0
;test
test()
Func test()
$begin = TimerInit()
getListe(0) ;retourne une erreur dans la Console
ConsoleWrite("temp:" & TimerDiff($begin) & @CRLF)
getListe(1) ;retourne une erreur dans la Console
$begin = TimerInit()
deleteElement(0) ;retourne une erreur dans la Console
ConsoleWrite("temp:" & TimerDiff($begin) & @CRLF)
deleteElement(1) ;retourne une erreur dans la Console
deleteElement(2) ;retourne une erreur dans la Console
$begin = TimerInit()
addElement("premier élément inséré") ;insère un premier élément
ConsoleWrite("temp insertion du premier element:" & TimerDiff($begin) & @CRLF)
ConsoleWrite("premier élément:" & getListe(0) & Chr(13)) ;devrait afficher la première valeur
$begin = TimerInit()
deleteElement(0) ;supprime le premier élément
ConsoleWrite("temp suppression du premier element:" & TimerDiff($begin) & @CRLF)
ConsoleWrite("null ? -> " & getListe(0) & Chr(13)) ;retourne une erreur dans la Console et affiche 0(=NON)
;la boucle insère des éléments dans tout le tableau et devrait générer une erreur pour le dernier élément
$begin = TimerInit()
For $i = 0 To $__Listechainee_maxEnregistrements
If Mod($i, 100) = 0 Then ConsoleWrite("insertion n°" & $i & Chr(13))
addElement("element inseré N°" & $i)
Next
ConsoleWrite("temp d'insertion de tous les éléments:" & TimerDiff($begin) & @CRLF)
;lit tous les éléments (devrait les afficher dans l'ordre décroissant)
For $i = 0 To $__Listechainee_maxEnregistrements - 1
If Mod($i, 100) = 0 Then ConsoleWrite("lecture n°" & $i & " -> " & getListe($i) & Chr(13))
Next
$begin = TimerInit()
deleteElement(0) ;supprime le premier élément
ConsoleWrite("temp suppression tableau plein:" & TimerDiff($begin) & @CRLF)
;devrait afficher $__Listechainee_maxEnregistrements-2
$begin = TimerInit()
ConsoleWrite("lecture n°0 -> " & getListe(0) & Chr(13))
ConsoleWrite("temps d'access au premier élément tableau plein:" & TimerDiff($begin) & @CRLF)
;ajoute un élément en début
$begin = TimerInit()
addElement("Re ajout")
ConsoleWrite("temp insertion tableau plein:" & TimerDiff($begin) & @CRLF)
;devrait afficher "Re ajout"
ConsoleWrite("lecture n°0 -> " & getListe(0) & Chr(13))
;devrait afficher "élément inséré N°0"
$begin = TimerInit()
ConsoleWrite("lecture n°0 -> " & getListe($__Listechainee_maxEnregistrements - 1) & Chr(13))
ConsoleWrite("temps de lecture du dernier élément avec tableau plein:" & TimerDiff($begin) & @CRLF)
;supprime le dernier élément
$begin = TimerInit()
deleteElement($__Listechainee_maxEnregistrements - 1)
ConsoleWrite("temps de suppression du dernier élément avec tableau plein:" & TimerDiff($begin) & @CRLF)
;vidage du tableau par le premier élément, génère une erreur pour le dernier élément
$begin = TimerInit()
For $i = 0 To $__Listechainee_maxEnregistrements - 1
If Mod($i, 100) = 0 Then ConsoleWrite("suppression n°" & $i & Chr(13))
deleteElement(0)
Next
ConsoleWrite("temps de vidage du tableau : " & TimerDiff($begin) & @CRLF)
EndFunc ;==>test
;fonction d'accès
Func getListe($position)
;position en dehors du tableau = erreur
If $position >= $__Listechainee_nbEnregistrement Or $position < 0 Then
Return __ListeChaineeErreur(1, "Position en dehors du tableau")
EndIf
;init du parcours
$parcoursPointeur = $__Listechainee_debut
$parcoursPosition = 0
;parcours du tableau jusqu'à la valeur que l'on cherche
While $parcoursPosition < $position
$parcoursPointeur = $__Listechainee_tablePointeurs[$parcoursPointeur]
$parcoursPosition += 1
WEnd
Return $__Listechainee_tableContenu[$parcoursPointeur]
EndFunc ;==>getListe
;fonction d'écriture
Func addElement($element)
;si le tableau est plein on plante
If $__Listechainee_maxEnregistrements < $__Listechainee_nbEnregistrement Then
Return __ListeChaineeErreur(2, "Tableau plein")
EndIf
If $element = "" Then
Return __ListeChaineeErreur(2, "Ajout d'un élément interdit")
EndIf
;init du parcours
$parcoursPosition = $__Listechainee_minInsertion
;parcours du tableau jusqu'à la fin ou jusqu'à ce qu'on tombe sur un élément vide
While $parcoursPosition < $__Listechainee_maxEnregistrements And (Not $__Listechainee_tableContenu[$parcoursPosition] = "")
$parcoursPosition += 1
WEnd
;si on est arrivés a la fin du tableau ... ben erreur.. mais ça devrait pas arriver normalement
If $parcoursPosition >= $__Listechainee_maxEnregistrements Then
Return __ListeChaineeErreur(2, "Tableau plein")
EndIf
;sinon on est tombé sur un élément vide !! super on insère notre maillon 1
;enregistrement de l'élément
$__Listechainee_tableContenu[$parcoursPosition] = $element
;mise en place du chainage
$__Listechainee_tablePointeurs[$parcoursPosition] = $__Listechainee_debut
;initialisation du debut
$__Listechainee_debut = $parcoursPosition
;positionnement de l'element le plus loin (non fragmenté)
$__Listechainee_minInsertion = $parcoursPosition
;incrément du décompte
$__Listechainee_nbEnregistrement += 1
Return 1
EndFunc ;==>addElement
;suppression d'un élément
Func deleteElement($position)
;position en dehors du tableau = erreur
If $position > $__Listechainee_nbEnregistrement Or $position < 0 Or $__Listechainee_nbEnregistrement = 0 Then
Return __ListeChaineeErreur(3, "Position en dehors du tableau")
EndIf
If $position = 0 Then
$__Listechainee_tableContenu[$__Listechainee_debut] = ""
$__Listechainee_debut = $__Listechainee_tablePointeurs[$__Listechainee_debut]
$__Listechainee_nbEnregistrement -= 1
$__Listechainee_minInsertion = 0
Return 1
EndIf
;init du parcours
$parcoursPointeur = $__Listechainee_debut
$parcoursPosition = 0
;parcours du tableau jusqu'à la valeur qu'on cherche
While $parcoursPosition + 1 < $position
$parcoursPointeur = $__Listechainee_tablePointeurs[$parcoursPointeur]
$parcoursPosition += 1
WEnd
;decalage
$__Listechainee_tableContenu[$parcoursPointeur] = ""
$__Listechainee_tablePointeurs[$parcoursPointeur] = $__Listechainee_tablePointeurs[$__Listechainee_tablePointeurs[$parcoursPointeur]]
$__Listechainee_nbEnregistrement -= 1
$__Listechainee_minInsertion = _Min($parcoursPointeur, $__Listechainee_minInsertion)
Return 1
EndFunc ;==>deleteElement
;centralisation des erreurs
Func __ListeChaineeErreur($IDFuncError, $message)
;aucun traitement pour l'instant
ConsoleWrite($message & Chr(10) & Chr(13))
Return 0
EndFunc ;==>__ListeChaineeErreur