Explication détaillée de la liste des structures de données Javascript et des compétences algorithms_javascript

Avant-propos : Dans la vie quotidienne, les gens utilisent souvent des listes. Par exemple, lorsque nous faisons parfois du shopping, afin d'acheter toutes les choses lors de nos courses, nous pouvons faire une liste des choses que nous voulons acheter avant de partir. la liste que nous utilisons. Ou lorsque nous étions à l'école quand nous étions jeunes, après chaque examen, l'école dressait la liste des classements et des relevés de notes des dix meilleurs élèves qui avaient obtenu de bons résultats à l'examen, et ainsi de suite. . Nous utilisons également des listes dans nos ordinateurs, alors où les listes peuvent-elles être utilisées ? Où n'est-il pas adapté à son utilisation ?

Convient à l'utilisation : lorsqu'il n'y a pas beaucoup d'éléments dans la liste, vous pouvez utiliser la liste, car l'efficacité est très élevée lors de la recherche ou du tri des éléments dans la liste. Au contraire : s'il y a de très nombreux éléments dans la liste. la liste, alors les listes ne conviennent plus.

1 : Définition abstraite du type de données de la liste

Afin de concevoir le type de données abstrait de la liste, nous devons donner la définition de la liste, y compris les attributs que la liste doit avoir, les opérations qui doivent être effectuées sur la liste, etc.

Une liste est un ensemble ordonné de données. Les éléments de données de chaque liste sont appelés éléments. En JavaScript, les éléments d'une liste peuvent être de n'importe quel type de données. Il n'y a pas d'accord préalable sur le nombre d'éléments pouvant être stockés dans une liste. Cependant, le nombre d'éléments est limité par la mémoire programme réellement utilisée.

Maintenant, nous voulons concevoir une liste, puis nous pouvons réfléchir à l'implémentation d'une liste et aux attributs et méthodes qu'elle doit contenir. Bien sûr, mes conceptions suivantes sont basées sur la démo du livre "Javascript Data Structure and Algorithm". Jusqu'à présent, nous pouvons apprendre à concevoir notre propre classe abstraite comme référence lorsque nous écrirons des programmes à l'avenir. La chose la plus importante pour nous d'étudier les démos du livre maintenant est d'apprendre leurs idées de conception et comment écrire du code. Ils ont les attributs suivants :

1. listSize (attribut) : utilisez une variable listSize pour enregistrer le nombre d'éléments dans la liste.
2. pos (attribut) : La position actuelle de la liste, l'index de l'élément.
3. dataStore (attribut) : initialisez un tableau vide pour enregistrer le nombre d'éléments. Si nous voulons obtenir un élément spécifique dans la liste, nous pouvons utiliser l'attribut pos ci-dessus tel que dataStore[pos];

 ;

Toutes les méthodes ; expliquées dans la liste suivante, non présentées une par une.

2 : Comment implémenter la classe list

Selon le type de données abstrait list défini ci-dessus, nous pouvons implémenter la classe List suivante via le mode prototype constructeur comme suit.

Copier le code Le code est le suivant :

fonction Liste() {
// Nombre d'éléments dans la liste
This.listSize = 0;

// Quelle est la position actuelle de la liste
Ceci.pos = 0;

// Initialise un tableau vide pour enregistrer les éléments de la liste
This.dataStore = [];

}

Liste.prototype = {
 
//Ajouter un élément à la fin de la liste
ajouter : fonction (élément) {
      var self = ceci ;
           self.dataStore[this.listSize] = element;
},

// Supprimer des éléments de la liste
Supprimer : fonction (élément) {
      var self = ceci ;
      var curIndex = self.find(element);
Si (curIndex > -1) {
                 self.dataStore.splice(curIndex,1);
​​​​​​—self.listSize;
             return true ;
>
         return false ;
},

// Rechercher l'élément dans la liste et renvoyer l'index
Rechercher : fonction (élément) {
      var self = ceci ;
for(var i = 0,dataLen = self.dataStore.length; i < dataLen; i ) {
If(self.dataStore[i] == élément) {
                   retourner i ;
            }
>
         return -1;
},
 
// Renvoie le nombre d'éléments dans la liste
longueur : fonction() {
          return this.listSize;
},

// Afficher les éléments dans la liste
toString : fonction(){
          renvoyer this.dataStore ;
},

/*
* Insérer un élément après l'élément spécifié
* @param element élément actuel
* @param elementAfter Insère l'élément actuel après cet élément
*/
​ insérer : function(element,elementAfter){
      var self = ceci ;
        var insertPos = self.find(elementAfter);
Si (insertPos > -1) {
                 self.dataStore.splice(insertPos 1,0,element);
                self.listSize;
             return true ;
>
         return false ;
},
 
// Efface tous les éléments de la liste
Effacer : function() {
          supprimer this.dataStore ;
This.dataStore = [];
This.listSize = this.pos = 0;
},
// Détermine si l'élément donné est dans la liste
contient : fonction (élément) {
      var self = ceci ;
for(var i = 0,ilen = self.dataStore.length; i < ilen; i ) {
If(self.dataStore[i] == élément) {
                   return true ;
            }
>
         return false ;
},
// Déplace l'élément actuel de la liste vers la première position
Devant : fonction(){
Ceci.pos = 0;
},
// Déplace l'élément actuel de la liste vers la dernière position
Fin : fonction(){
This.pos = this.listSize - 1;
},
// Recule la position actuelle d'une position
Précédent : function(){
Si (this.pos > 0) {
​​​​​​—this.pos;
>
},
// Avance la position actuelle d'une position
Suivant : function(){
Si(this.pos < this.listSize - 1) {
Ceci.pos;
>
},
// Renvoie la position actuelle de la liste
CurPos : fonction(){
         return this.pos;
},
//Déplacer la position actuelle vers la position spécifiée
MoveTo : fonction(n) {
This.pos = n;
},
// Renvoie l'élément à la position actuelle
GetElement:fonction(){
          return this.dataStore[this.pos];
>
};

Comme ci-dessus : implémentez une classe list, comprenant autant de méthodes que ci-dessus. Bien sûr, nous pouvons également étendre d'autres méthodes pour enrichir l'implémentation de la classe list. Le plus important est d'apprendre la méthode de codage ci-dessus.