Javascript數(shù)據(jù)結(jié)構(gòu)與算法之列表詳解

2019-11-20 12:58:22

字體：大中小

供稿：網(wǎng)友

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

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

一：列表的抽象數(shù)據(jù)類型定義

為了設(shè)計列表的抽象數(shù)據(jù)類型，我們需要給出列表的定義，包括列表應(yīng)該擁有哪些屬性，應(yīng)該在列表上執(zhí)行哪些操作等。

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

現(xiàn)在我們想設(shè)計一個列表，那么我們可以想想實現(xiàn)一個列表，他們應(yīng)該包含哪些屬性和方法，當然我下面的設(shè)計都是根據(jù) "javascript數(shù)據(jù)結(jié)構(gòu)與算法" 書上的demo來設(shè)計的，為止我們可以學(xué)習下，如果以后我們編寫程序時，該如何來設(shè)計我們自己的抽象類來作為一個參考，我們現(xiàn)在學(xué)習書上的demo最主要的是學(xué)習他們中的設(shè)計思想及編寫代碼的方式。他們有如下屬性；

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

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

二：如何實現(xiàn)列表類

根據(jù)上面定義的列表抽象數(shù)據(jù)類型，我們可以實現(xiàn)如下一個List類，如下通過構(gòu)造函數(shù)+原型模式。

復(fù)制代碼代碼如下:

function List() {
// 列表的元素個數(shù)
this.listSize = 0;

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

// 初始化一個空數(shù)組來保存列表元素
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;
    },

    // 返回列表中元素的個數(shù)
    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];
    }
};