Introdução: Na vida cotidiana, as pessoas costumam usar listas. Por exemplo, quando às vezes precisamos fazer compras, para comprar todas as coisas que queremos comprar antes de ir, que é a lista das coisas que precisamos usar. Ou quando estávamos na escola quando éramos jovens, após cada exame, a escola listará o ranking e as transcrições dos dez principais alunos neste exame, etc. Essas são todas as listas da lista. Também usamos listas em nossos computadores, então onde a lista é adequada para uso? Onde não é adequado para uso?
Adequado para uso: quando não há muitos elementos na lista, você pode usar a lista porque a eficiência é muito alta ao pesquisar ou classificar os elementos da lista. Pelo contrário, se houver muitos elementos na lista, não será adequado para o uso da lista.
1: Definição de tipo de dados abstrato da lista
Para projetar o tipo de dados abstrato de uma lista, precisamos fornecer uma definição da lista, incluindo quais atributos a lista deve ter, quais operações devem ser executadas na lista, etc.
Uma lista é um conjunto ordenado de dados. Os itens de dados em cada lista são chamados de elementos. No JavaScript, os elementos da lista podem ser de qualquer tipo de dados. Não há acordo prévio sobre quantos elementos podem ser salvos na lista. No entanto, o número de elementos é limitado pela memória do programa quando realmente usado.
Agora queremos projetar uma lista, então podemos pensar em implementar uma lista. Quais atributos e métodos eles devem conter? Obviamente, meus projetos abaixo são projetados com base nas demos do livro "Estruturas e algoritmos de dados JavaScript". Para que possamos aprender a projetar nossas próprias classes abstratas como referência quando escrevemos programas no futuro. A coisa mais importante que aprendemos sobre demos no livro é aprender suas idéias de design e como escrever código. Eles têm os seguintes atributos;
1. ListSize (Propriedade): use uma variável ListSize para salvar o número de elementos na lista.
2. POS (propriedade): a posição atual da lista, o índice do elemento.
3. Datastore (Propriedade): Inicialize uma matriz vazia para salvar o número de elementos. Se queremos obter os elementos na lista específica, podemos usar o atributo POS acima; como DataStore [POS];
Todos os métodos; A lista a seguir será explicada e não será introduzida uma a uma.
Dois: como implementar classes de lista
Com base no tipo de dados abstrato da lista definido acima, podemos implementar a seguinte classe de lista, como segue através do padrão do construtor + protótipo.
A cópia do código é a seguinte:
Lista de funções () {
// Número de elementos na lista
this.Listsize = 0;
// Qual é a posição atual da lista
this.pos = 0;
// Inicialize uma matriz vazia para salvar elementos da lista
this.datastore = [];
}
List.prototype = {
// Adicione um elemento ao final da lista
Anexar: função (elemento) {
var self = this;
self.datastore [this.Listsize ++] = elemento;
},
// Remova os elementos da lista
Remover: function (elemento) {
var self = this;
var Curindex = self.find (elemento);
if (Curindex> -1) {
self.datastore.splice (Curindex, 1);
--Self.Listsize;
retornar true;
}
retornar falso;
},
// Encontre elementos na lista para retornar o índice
Encontre: function (elemento) {
var self = this;
for (var i = 0, datalen = self.datastore.length; i <datalen; i ++) {
if (self.datastore [i] == element) {
retornar i;
}
}
retornar -1;
},
// retorna o número de elementos na lista
comprimento: function () {
devolver este.Listsize;
},
// mostra elementos na lista
ToString: function () {
devolver this.datastore;
},
/*
* Insira um elemento após o elemento especificado
* elemento @param elemento atual
* @param elementofter insira o elemento atual por trás deste elemento
*/
inserir: function (elemento, elementofter) {
var self = this;
var insertpos = self.find (elementAfter);
if (insertpos> -1) {
self.datastore.splice (insertpos+1,0, elemento);
++ self.Listsize;
retornar true;
}
retornar falso;
},
// Limpe todos os elementos da lista
claro: function () {
exclua this.datastore;
this.datastore = [];
this.Listsize = this.pos = 0;
},
// determinar se o elemento fornecido está na lista
Contém: function (elemento) {
var self = this;
for (var i = 0, ilen = self.datastore.length; i <ilen; i ++) {
if (self.datastore [i] == element) {
retornar true;
}
}
retornar falso;
},
// mova o elemento atual na lista para a primeira posição
Frente: function () {
this.pos = 0;
},
// mova o elemento atual na lista para a última posição
fim: function () {
this.pos = this.Listsize - 1;
},
// mova a posição atual um por um
prev: function () {
if (this.pos> 0) {
--This.pos;
}
},
// mova a posição atual um por um
Próximo: function () {
if (this.pos <this.listsize - 1) {
++ this.pos;
}
},
// retorna ao local atual da lista
curpas: function () {
devolver this.pos;
},
// mova a posição atual para a posição especificada
moveto: function (n) {
this.pos = n;
},
// retorna o elemento na posição atual
getElement: function () {
retornar this.datastore [this.pos];
}
};
Como acima: implemente uma classe de lista, incluindo tantos métodos acima. Obviamente, também podemos estender alguns outros métodos para enriquecer a implementação da classe List. O mais importante é aprender o método de codificação como acima.