Pendahuluan: Dalam kehidupan sehari -hari, orang sering menggunakan daftar. Misalnya, ketika kita kadang -kadang harus pergi berbelanja, untuk membeli semua barang yang ingin kita beli sebelum kita pergi, yang merupakan daftar hal -hal yang perlu kita gunakan. Atau ketika kami masih di sekolah ketika kami masih muda, setelah setiap ujian, sekolah akan mencantumkan peringkat dan transkrip dari sepuluh siswa teratas dalam ujian ini, dll. Ini semua adalah daftar daftar. Kami juga menggunakan daftar di komputer kami, jadi di mana daftar yang cocok untuk digunakan? Di mana tidak cocok untuk digunakan?
Cocok untuk digunakan: Ketika tidak ada banyak elemen dalam daftar, Anda dapat menggunakan daftar karena efisiensinya sangat tinggi saat mencari atau menyortir elemen dalam daftar. Sebaliknya, jika ada banyak elemen dalam daftar, itu tidak cocok untuk penggunaan daftar.
1: Definisi tipe data abstrak daftar
Untuk merancang tipe data abstrak dari suatu daftar, kita perlu memberikan definisi daftar, termasuk atribut apa yang harus dimiliki daftar, operasi apa yang harus dilakukan pada daftar, dll.
Daftar adalah set data yang dipesan. Item data dalam setiap daftar disebut elemen. Dalam JavaScript, elemen dalam daftar dapat berupa tipe data apa pun. Tidak ada kesepakatan sebelumnya tentang berapa banyak elemen yang dapat disimpan dalam daftar. Namun, jumlah elemen dibatasi oleh memori program saat benar -benar digunakan.
Sekarang kami ingin merancang daftar, maka kami dapat berpikir tentang menerapkan daftar. Atribut dan metode apa yang harus dikandungnya? Tentu saja, desain saya di bawah ini dirancang berdasarkan demo dalam buku "JavaScript Data Struktur dan Algoritma". Jadi kita dapat belajar cara merancang kelas abstrak kita sendiri sebagai referensi ketika kita menulis program di masa depan. Hal terpenting yang kita pelajari tentang demo dalam buku ini adalah mempelajari ide -ide desain mereka dan cara menulis kode. Mereka memiliki atribut berikut;
1. ListSize (properti): Gunakan variabel listsize untuk menyimpan jumlah elemen dalam daftar.
2. POS (properti): Posisi saat ini dari daftar, indeks elemen.
3. Datastore (Properti): Inisialisasi array kosong untuk menyimpan jumlah elemen. Jika kita ingin mendapatkan elemen dalam daftar tertentu, kita dapat menggunakan atribut POS di atas; seperti datastore [pos];
Semua metode; Daftar berikut akan dijelaskan, dan tidak akan diperkenalkan satu per satu.
Dua: Cara Menerapkan Kelas Daftar
Berdasarkan daftar data data abstrak yang ditentukan di atas, kami dapat mengimplementasikan kelas daftar berikut, sebagai berikut melalui pola prototipe konstruktor +.
Salinan kode adalah sebagai berikut:
daftar fungsi () {
// Jumlah elemen dalam daftar
this.listSize = 0;
// Apa posisi daftar saat ini
this.pos = 0;
// Inisialisasi array kosong untuk menyimpan elemen daftar
this.datastore = [];
}
List.prototype = {
// Tambahkan elemen ke akhir daftar
append: function (elemen) {
var self = ini;
self.datastore [this.listSize ++] = elemen;
},
// Hapus elemen dari daftar
hapus: function (elemen) {
var self = ini;
var curIndex = self.find (elemen);
if (CurIndex> -1) {
self.datastore.splice (CurIndex, 1);
--elf.listSize;
Kembali Benar;
}
mengembalikan false;
},
// Temukan elemen dalam daftar untuk mengembalikan indeks
temukan: function (elemen) {
var self = ini;
untuk (var i = 0, datalen = self.datastore.length; i <datalen; i ++) {
if (self.datastore [i] == elemen) {
Kembalikan i;
}
}
kembali -1;
},
// mengembalikan jumlah elemen dalam daftar
panjang: function () {
kembalikan this.listSize;
},
// Tampilkan elemen dalam daftar
tostring: function () {
kembalikan ini.datastore;
},
/*
* Masukkan elemen setelah elemen yang ditentukan
* elemen @param elemen saat ini
* @param ElementAfter Masukkan elemen saat ini di belakang elemen ini
*/
masukkan: function (element, elementafter) {
var self = ini;
var insertPos = self.find (elementAfter);
if (insertPos> -1) {
self.datastore.splice (insertPos+1,0, elemen);
++ self.listSize;
Kembali Benar;
}
mengembalikan false;
},
// Bersihkan semua elemen dalam daftar
CLEAR: function () {
hapus ini.datastore;
this.datastore = [];
this.listSize = this.pos = 0;
},
// Tentukan apakah elemen yang diberikan ada dalam daftar
berisi: function (elemen) {
var self = ini;
untuk (var i = 0, ilen = self.datastore.length; i <ilen; i ++) {
if (self.datastore [i] == elemen) {
Kembali Benar;
}
}
mengembalikan false;
},
// Pindahkan elemen saat ini dalam daftar ke posisi pertama
front: function () {
this.pos = 0;
},
// Pindahkan elemen saat ini dalam daftar ke posisi terakhir
end: function () {
this.pos = this.listSize - 1;
},
// Pindahkan posisi saat ini satu per satu
Sebelumnya: function () {
if (this.pos> 0) {
--Pos ini;
}
},
// Pindahkan posisi saat ini satu per satu
Berikutnya: function () {
if (this.pos <this.listSize - 1) {
++ this.pos;
}
},
// Kembali ke lokasi daftar saat ini
Curpos: function () {
kembalikan ini.pos;
},
// Pindahkan posisi saat ini ke posisi yang ditentukan
Moveto: function (n) {
this.pos = n;
},
// Kembalikan elemen pada posisi saat ini
GetElement: function () {
kembalikan this.datastore [this.pos];
}
};
Seperti di atas: Menerapkan kelas daftar, termasuk sebanyak mungkin metode di atas. Tentu saja, kami juga dapat memperluas beberapa metode lain untuk memperkaya implementasi kelas daftar. Yang paling penting adalah mempelajari metode pengkodean seperti di atas.