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

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

   

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

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

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

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

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

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

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

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

二：如何實現列表類

根據上面定義的列表抽象數據類型，我們可以實現如下一個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];
}
};

 

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