萬盛學電腦網

 萬盛學電腦網 >> 腳本專題 >> javascript >> Javascript數據結構與算法之列表詳解

Javascript數據結構與算法之列表詳解

 這篇文章主要介紹了Javascript數據結構與算法之列表詳解,本文講解了列表的抽象數據類型定義、如何實現列表類等內容,需要的朋友可以參考下

   

前言:在日常生活中,人們經常要使用列表,比如我們有時候要去購物時,為了購物時東西要買全,我們可以在去之前,列下要買的東西,這就要用的列表了,或者我們小時候上學那段時間,每次考完試後,學校都會列出這次考試成績前十名的同學的排名及成績單,等等這些都是列表的列子。我們計算機內也在使用列表,那麼列表適合使用在什麼地方呢?不適合使用在什麼地方呢?

適合使用在:當列表的元素不是很多的情況下,可以使用列表,因為對列表中的元素查找或者排序時,效率還算非常高,反之:如果列表元素非常多的情況下,就不適合使用列表了。

一:列表的抽象數據類型定義

為了設計列表的抽象數據類型,我們需要給出列表的定義,包括列表應該擁有哪些屬性,應該在列表上執行哪些操作等。

列表是一組有序的數據。每個列表中的數據項稱為元素。在javascript中,列表中的元素可以是任意數據類型。列表中可以保存多少元素並沒有事先約定。但是實際使用時元素數量受到程序內存的限制。

現在我們想設計一個列表,那麼我們可以想想實現一個列表,他們應該包含哪些屬性和方法,當然我下面的設計都是根據 "javascript數據結構與算法" 書上的demo來設計的,為止我們可以學習下,如果以後我們編寫程序時,該如何來設計我們自己的抽象類來作為一個參考,我們現在學習書上的demo最主要的是學習他們中的設計思想及編寫代碼的方式。他們有如下屬性;

1. listSize(屬性):使用一個listSize變量來保存列表中元素的個數。
2. pos(屬性): 列表的當前位置,元素的索引。
3. dataStore(屬性): 初始化一個空數組來保存元素的個數。如果我們想取得具體的列表中的元素 可以使用上面的pos屬性;如 dataStore[pos];

所有的方法;如下列表解釋,不一一介紹了。

Javascript數據結構與算法之列表詳解   三聯

二:如何實現列表類

根據上面定義的列表抽象數據類型,我們可以實現如下一個List類,如下通過構造函數+原型模式。

代碼如下:
function List() {
// 列表的元素個數
this.listSize = 0;

 

// 列表的當前位置 是第幾個
this.pos = 0;

// 初始化一個空數組來保存列表元素
this.dataStore = [];

}

List.prototype = {

// 給列表末尾添加元素
append: function(element) {
var self = this;
self.dataStore[this.listSize++] = element;
},

// 從列表中刪除元素
remove: function(element) {
var self = this;
var curIndex = self.find(element);
if(curIndex > -1) {
self.dataStore.splice(curIndex,1);
--self.listSize;
return true;
}
return false;
},

// 查找列表中的元素 返回索引
find: function(element) {
var self = this;
for(var i = 0,dataLen = self.dataStore.length; i < dataLen; i++) {
if(self.dataStore[i] == element) {
return i;
}
}
return -1;
},

// 返回列表中元素的個數
length: function() {
return this.listSize;
},

// 顯示列表中的元素
toString: function(){
return this.dataStore;
},

/*
* 在指定元素後面插入一個元素
* @param element 當前的元素
* @param elementAfter 把當前的元素插入到此元素後面
*/
insert: 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;
},

// 清空列表中的所有元素
clear: function() {
delete this.dataStore;
this.dataStore = [];
this.listSize = this.pos = 0;
},
// 判斷給定的元素是否在列表中
contains: function(element) {
var self = this;
for(var i = 0,ilen = self.dataStore.length; i < ilen; i++) {
if(self.dataStore[i] == element) {
return true;
}
}
return false;
},
// 將列表中的當前元素移動到第一個位置
front: function(){
this.pos = 0;
},
// 將列表中當前的元素移動到最後一個位置
end: function(){
this.pos = this.listSize - 1;
},
// 將當前位置 後移一位
prev: function(){
if(this.pos > 0) {
--this.pos;
}
},
// 將當前位置 前移一位
next: function(){
if(this.pos < this.listSize - 1) {
++this.pos;
}
},
// 返回列表的當前位置
curPos: function(){
return this.pos;
},
// 將當前位置移動到指定位置
moveTo: function(n) {
this.pos = n;
},
// 返回當前位置的元素
getElement:function(){
return this.dataStore[this.pos];
}
};

 

如上:實現一個列表類,包含上面的如上那麼多方法,當然我們也可以擴展一些其他的方法,來豐富實現列表類,最主要可以學習如上編碼方式。

copyright © 萬盛學電腦網 all rights reserved