Vorwort: Im täglichen Leben verwenden Menschen oft Listen, um beim Einkaufen alle Dinge zu kaufen, bevor wir gehen die Liste, die wir verwenden. Oder als wir in der Schule waren, listete die Schule nach jeder Prüfung die Ranglisten und Zeugnisse der zehn besten Schüler auf, die in der Prüfung abschnitten, und so weiter . Wir verwenden auch Listen in unseren Computern. Wo sind Listen also für den Einsatz geeignet? Wo ist es nicht einsetzbar?
Geeignet für die Verwendung: Wenn die Liste nicht viele Elemente enthält, können Sie die Liste verwenden, da die Effizienz beim Suchen oder Sortieren der Elemente in der Liste sehr hoch ist. Im Gegenteil: Wenn sehr viele Elemente vorhanden sind die Liste, dann sind Listen nicht mehr geeignet.
1: Abstrakte Datentypdefinition der Liste
Um den abstrakten Datentyp der Liste zu entwerfen, müssen wir die Definition der Liste angeben, einschließlich der Attribute, die die Liste haben soll, welche Operationen an der Liste ausgeführt werden sollen usw.
Eine Liste ist ein geordneter Datensatz. Die Datenelemente in jeder Liste werden Elemente genannt. In JavaScript können Elemente in einer Liste jeden Datentyp haben. Es gibt keine vorherige Vereinbarung darüber, wie viele Elemente in einer Liste gespeichert werden können. Allerdings ist die Anzahl der Elemente durch den tatsächlich genutzten Programmspeicher begrenzt.
Jetzt wollen wir eine Liste entwerfen, dann können wir darüber nachdenken, eine Liste zu implementieren und welche Attribute und Methoden sie enthalten soll. Natürlich basieren meine folgenden Entwürfe auf der Demo im Buch „Javascript Data Structure and Algorithm“. Bisher können wir lernen, wie wir unsere eigene abstrakte Klasse als Referenz entwerfen, wenn wir in Zukunft Programme schreiben. Das Wichtigste für uns, jetzt die Demos im Buch zu studieren, ist, ihre Designideen und das Schreiben von Code zu lernen. Sie haben die folgenden Attribute:
1. listSize (Attribut): Verwenden Sie eine listSize-Variable, um die Anzahl der Elemente in der Liste zu speichern.
2. pos (Attribut): Die aktuelle Position der Liste, der Index des Elements.
3. dataStore (Attribut): Initialisieren Sie ein leeres Array, um die Anzahl der Elemente zu speichern. Wenn wir ein bestimmtes Element in der Liste erhalten möchten, können wir das obige pos-Attribut verwenden, z. B. dataStore[pos];
Alle Methoden werden in der folgenden Liste erläutert und nicht einzeln vorgestellt.
2: So implementieren Sie die Listenklasse
Gemäß dem oben definierten abstrakten Datentyp der Liste können wir die folgende List-Klasse über den Konstruktor-Prototypmodus wie folgt implementieren.
Funktion List() {
// Anzahl der Elemente in der Liste
This.listSize = 0;
// Was ist die aktuelle Position der Liste
This.pos = 0;
// Initialisiere ein leeres Array, um Listenelemente zu speichern
This.dataStore = [];
}
List.prototype = {
//Element am Ende der Liste hinzufügen
anhängen: Funktion(Element) {
var self = this;
self.dataStore[this.listSize] = element;
},
// Elemente aus der Liste entfernen
Entfernen: Funktion(Element) {
var self = this;
var curIndex = self.find(element);
If(curIndex > -1) {
self.dataStore.splice(curIndex,1);
–self.listSize;
return true;
}
return false;
},
// Element in der Liste finden und Index zurückgeben
Suchen: Funktion(Element) {
var self = this;
for(var i = 0,dataLen = self.dataStore.length; i < dataLen; i ) {
If(self.dataStore[i] == element) {
return i;
}
}
return -1;
},
// Gibt die Anzahl der Elemente in der Liste zurück
Länge: function() {
return this.listSize;
},
// Elemente in der Liste anzeigen
toString: function(){
return this.dataStore;
},
/*
* Fügen Sie ein Element nach dem angegebenen Element
ein
* @param Element aktuelles Element
* @param elementAfter Fügt das aktuelle Element nach diesem Element
ein
*/
einfügen: function(element,elementAfter){
var self = this;
var insertPos = self.find(elementAfter);
If(insertPos > -1) {
self.dataStore.splice(insertPos 1,0,element);
self.listSize;
return true;
}
return false;
},
// Alle Elemente in der Liste löschen
Klar: function() {
delete this.dataStore;
This.dataStore = [];
This.listSize = this.pos = 0;
},
// Bestimmen Sie, ob das angegebene Element in der Liste
enthalten ist
enthält: Funktion(Element) {
var self = this;
for(var i = 0,ilen = self.dataStore.length; i < ilen; i ) {
If(self.dataStore[i] == element) {
return true;
}
}
return false;
},
// Verschiebe das aktuelle Element in der Liste an die erste Position
Vorderseite: function(){
This.pos = 0;
},
// Verschiebe das aktuelle Element in der Liste an die letzte Position
Ende: function(){
This.pos = this.listSize - 1;
},
// Aktuelle Position um eine Position nach hinten verschieben
Zurück: function(){
If(this.pos > 0) {
–this.pos;
}
},
// Aktuelle Position um eine Position nach vorne verschieben
Als nächstes: function(){
If(this.pos < this.listSize - 1) {
This.pos;
}
},
// Gibt die aktuelle Position der Liste zurück
CurPos: function(){
return this.pos;
},
//Verschieben Sie die aktuelle Position an die angegebene Position
MoveTo: Funktion(n) {
This.pos = n;
},
// Das Element an der aktuellen Position zurückgeben
GetElement:function(){
return this.dataStore[this.pos];
}
};
Wie oben: Implementieren Sie eine Listenklasse, einschließlich so vieler Methoden wie oben. Natürlich können wir auch einige andere Methoden erweitern, um die Implementierung der Listenklasse zu bereichern.
