Introduction: Dans la vie quotidienne, les gens utilisent souvent des listes. Par exemple, lorsque nous devons parfois faire du shopping, afin d'acheter tout ce que nous voulons acheter avant de partir, ce qui est la liste des choses que nous devons utiliser. Ou quand nous étions à l'école quand nous étions jeunes, après chaque examen, l'école répertorie les classements et les transcriptions des dix premiers étudiants de cet examen, etc. Ce sont toutes des listes de la liste. Nous utilisons également des listes dans nos ordinateurs, alors où la liste est-elle adaptée à une utilisation? Où ne convient-il pas à une utilisation?
Convient à une 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 de la liste. Au contraire, s'il y a de nombreux éléments dans la liste, il ne convient pas à l'utilisation de la liste.
1: Type de données abstrait Définition de la liste
Afin de concevoir le type de données abstrait d'une liste, nous devons donner une définition de la liste, y compris les attributs de la liste, quelles opérations 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 de la liste peuvent être de n'importe quel type de données. Il n'y a aucun accord préalable sur le nombre d'éléments qui peuvent être enregistrés dans la liste. Cependant, le nombre d'éléments est limité par la mémoire du programme lorsqu'il est réellement utilisé.
Maintenant, nous voulons concevoir une liste, alors nous pouvons penser à implémenter une liste. Quels attributs et méthodes doivent-ils contenir? Bien sûr, mes conceptions ci-dessous sont conçues sur la base des démos du livre "JavaScript Data Structures and Algorithms". Nous pouvons donc apprendre à concevoir nos propres classes abstraites comme référence lorsque nous écrivons des programmes à l'avenir. La chose la plus importante que nous apprenons sur les démos dans le livre est d'apprendre leurs idées de conception et comment écrire du code. Ils ont les attributs suivants;
1. ListSize (propriété): utilisez une variable ListSize pour enregistrer le nombre d'éléments dans la liste.
2. POS (propriété): la position actuelle de la liste, l'index de l'élément.
3. Datastore (propriété): Initialisez un tableau vide pour enregistrer le nombre d'éléments. Si nous voulons obtenir les éléments dans la liste spécifique, nous pouvons utiliser l'attribut POS ci-dessus; tels que Datastore [POS];
Toutes les méthodes; La liste suivante sera expliquée et ne sera pas présentée une par une.
Deux: comment implémenter des classes de liste
Sur la base du type de données abstrait de la liste définie ci-dessus, nous pouvons implémenter la classe de liste suivante, comme suit le modèle de prototype constructeur +.
La copie de code est la suivante:
Fonction List () {
// Nombre d'éléments dans la liste
this.listSize = 0;
// Quelle est la position actuelle de la liste
this.pos = 0;
// Initialisez un tableau vide pour enregistrer les éléments de liste
this.datastore = [];
}
List.prototype = {
// ajoute un élément à la fin de la liste
APPENDE: fonction (élément) {
var self = this;
self.datastore [this.listSize ++] = élément;
},
// supprimer les éléments de la liste
supprimer: fonction (élément) {
var self = this;
var curindex = self.find (élément);
if (curindex> -1) {
self.datastore.splice (curindex, 1);
- self.listSize;
Retour Vrai;
}
retourne false;
},
// Trouvez des éléments dans la liste pour renvoyer l'index
trouver: fonction (élément) {
var self = this;
pour (var i = 0, datalen = self.datastore.length; i <datalen; i ++) {
if (self.datastore [i] == élément) {
retour i;
}
}
retour -1;
},
// Renvoie le nombre d'éléments dans la liste
longueur: function () {
Renvoyez ce.listSize;
},
// Afficher les éléments de la liste
toString: function () {
Renvoyez ce.datastore;
},
/ *
* Insérez un élément après l'élément spécifié
* élément actuel de l'élément @param
* @param elementafter insérer l'élément actuel derrière cet élément
* /
insert: fonction (élément, élémentafter) {
var self = this;
var insertPos = self.find (elementAfter);
if (insertpos> -1) {
self.datastore.splice (insertPos + 1,0, élément);
++ self.listSize;
Retour Vrai;
}
retourne false;
},
// effacer tous les éléments de la liste
Clear: function () {
Supprimer ce.datastore;
this.datastore = [];
this.listSize = this.pos = 0;
},
// déterminer si l'élément donné est dans la liste
contient: fonction (élément) {
var self = this;
for (var i = 0, ilen = self.datastore.length; i <ilen; i ++) {
if (self.datastore [i] == élément) {
Retour Vrai;
}
}
retourne false;
},
// déplace l'élément actuel de la liste vers la première position
Front: function () {
this.pos = 0;
},
// déplace l'élément actuel de la liste vers la dernière position
end: function () {
this.pos = this.listSize - 1;
},
// déplace la position actuelle un par un
prev: function () {
if (this.pos> 0) {
- ce.pos;
}
},
// déplace la position actuelle un par un
Suivant: fonction () {
if (this.pos <this.listSize - 1) {
++ this.pos;
}
},
// retour à l'emplacement actuel de la liste
curpos: fonction () {
Renvoyez ce.pos;
},
// déplace la position actuelle vers la position spécifiée
MOVETO: fonction (n) {
this.pos = n;
},
// Renvoie l'élément à la position actuelle
getElement: function () {
renvoie this.datastore [this.pos];
}
};
Comme ci-dessus: implémentez une classe de liste, y compris autant de méthodes que ci-dessus. Bien sûr, nous pouvons également étendre d'autres méthodes pour enrichir la mise en œuvre de la classe de liste. La chose la plus importante est d'apprendre la méthode d'encodage comme ci-dessus.