Javascript的數(shù)據(jù)結構與算法(二)

jlanglang 發(fā)布于2019-08-21 11:24 / 2535人閱讀

摘要：基本版的散列表實現(xiàn)在散列表中我們通過散列函數(shù)來確定鍵值對的關系。的實現(xiàn)具體看的數(shù)據(jù)結構與算法一。散列函數(shù)不超過數(shù)組的長度下面兩個值相同源碼地址的數(shù)據(jù)結構與算法二源碼

1集合 1.1集合的實現(xiàn)

集合是由一組無序且唯一(即不能重復)的項組成的。這個數(shù)據(jù)結構使用了與有限集合相同的數(shù)學概念,但應用在計算機科學的數(shù)據(jù)結構中。

集合中常用方法列表：

add(value):向集合中添加一個新的項。

remove(value):從集合中移除一個值。

has(value):如果在集合中，返回true，否則返回false。

clear():清除集合中的所有項。

size():返回集合所包含元素的數(shù)量。

values():返回一個包含集合中所有值得數(shù)組。

union(otherSet):并集操作，返回一個包含兩個集合中所有元素的新集合。

intersection(otherSet):交集操作，返回一個包含兩個集合中共有元素的新集合。

difference(otherSet):差集操作，返回一個包含左右存在于第一個集合并且不存在于第二個集合的元素的新集合。

subset(otherSet):子集操作，驗證一個給定集合是否是另一個集合的子集，返回true和false。

    function Set() {
        this.items = {};
    }
    Set.prototype = {
        constructor: Set,
        has: function(value) {
            return value in this.items;
        },
        add: function(value) {
            if (!this.has(value)) {
                this.items[value] = value;
                return true;
            }
            return false;
        },
        remove: function(value) {
            if (this.has(value)) {
                delete this.items[value];
                return true;
            }
            return false;
        },
        clear: function() {
            this.items = {};
        },
        size: function() {
            return Object.keys(this.items).length;
        },
        values: function() {
            return Object.keys(this.items);
        },
        union: function(otherSet) {
            var unionSet = new Set();
            var values = this.values();
            for (var i = 0; i < values.length; i++) {
                unionSet.add(values[i]);
            }
            values = otherSet.values();
            for (var i = 0; i < values.length; i++) {
                unionSet.add(values[i]);
            }
            return unionSet;
        },
        intersection: function(otherSet) {
            var intersectionSet = new Set();
            var values = this.values();
            for (var i = 0; i < values.length; i++) {
                if (otherSet.has(values[i])) {
                    intersectionSet.add(values[i]);
                }
            }
            return intersectionSet;
        },
        difference: function(otherSet) {
            var differenceSet = new Set();
            var values = this.values();
            for (var i = 0; i < values.length; i++) {
                if (!otherSet.has(values[i])) {
                    differenceSet.add(values[i]);
                }
            }
            return differenceSet;
        },
        subset: function(otherSet) {
            if (this.size() > otherSet.size()) {
                return false;
            } else {
                var values = this.values();
                for (var i = 0; i < values.length; i++) {
                    if (!otherSet.has(values[i])) {
                        return false;
                    }
                }
            }
            return true;
        },
    };

1.2集合的使用

    var set = new Set();
    set.add(1);
    console.log(set.values());//["1"]
    console.log(set.has(1));//true
    console.log(set.size());//1
    set.add(2);
    console.log(set.values());//["1","2"]
    console.log(set.has(2));//true
    console.log(set.size());//2
    set.remove(2);
    console.log(set.values());//["1"]

交集、并集、子集、差集的使用。

    //并集測試
    var setA = new Set();
    setA.add(1);
    setA.add(2);
    setA.add(3);
    var setB = new Set();
    setB.add(3);
    setB.add(4);
    setB.add(5);
    setB.add(6);
    var setAB = setA.union(setB);
    console.log(setAB.values()); // ["1", "2", "3", "4", "5", "6"]
    //交集測試
    setA = new Set();
    setA.add(1);
    setA.add(2);
    setA.add(3);
    setB = new Set();
    setB.add(2);
    setB.add(3);
    setB.add(4);
    var intersectionAB = setA.intersection(setB);
    console.log(intersectionAB.values()); // ["2", "3"]
    //差集側事故
    setA = new Set();
    setA.add(1);
    setA.add(2);
    setA.add(3);
    setB = new Set();
    setB.add(2);
    setB.add(3);
    setB.add(4);
    var differenceAB = setA.difference(setB);
    console.log(differenceAB.values()); //["1"]
    //子集測試
    setA = new Set();
    setA.add(1);
    setA.add(2);
    var setB = new Set();
    setB.add(1);
    setB.add(2);
    setB.add(3);
    setC = new Set();
    setC.add(2);
    setC.add(3);
    setC.add(4);
    console.log(setA.subset(setB)); //true
    console.log(setA.subset(setC)); //false

2字典和散列表

集合、字典和散列表可以存儲不重復的值。在集合中,我們感興趣的是每個值本身,并把它當作主要元素。在字典中,我們用[鍵,值]的形式來存儲數(shù)據(jù)。在散列表中也是一樣(也是以[鍵, 值]對的形式來存儲數(shù)據(jù))。

2.1字典

集合表示一組互不相同的元素(不重復的元素)。在字典中,存儲的是[鍵,值] 對,其中鍵名是用來查詢特定元素的。字典和集合很相似,集合以[值,值]的形式存儲元素,字典則是以[鍵,值]的形式來存儲元素。字典也稱作映射。下面是字典需要實現(xiàn)的方法：

set(key,value): 向字典中添加新元素。

remove(key): 通過使用鍵值來從字典中語出鍵值對應的數(shù)據(jù)值。

has(key): 如果某個鍵值存在于這個字典中，否則返回true，反之則返回false。

get(key): 通過鍵值查詢特定的數(shù)值并且返回。

clear(): 將這個字典中的所有元素全部刪除。

size(): 返回字典中包含元素的數(shù)量。

keys(): 將字典所包含的所有鍵名以數(shù)組的形式返回。

values(): 將字典所包含的所有數(shù)值以數(shù)組的形式返回。

getItems(): 返回字典。

2.1.1字典的實現(xiàn)

    function Dictionary() {
        this.items = {};
    }
    Dictionary.prototype = {
        constructor: Dictionary,
        has: function(key) {
            return key in this.items;
        },
        set: function(key, value) {
            this.items[key] = value;
        },
        remove: function(key) {
            if (this.has(key)) {
                delete this.items[key];
                return true;
            }
            return false;
        },
        get: function(key) {
            return this.has(key) ? this.items[key] : undefined;
        },
        values: function() {
            var values = [];
            for (var key in this.items) {
                if (this.has(key)) {
                    values.push(key);
                }
            }
            return values;
        },
        clear: function() {
            this.items = {};
        },
        size: function() {
            return Object.keys(this.items).length;
        },
        keys: function() {
            return Object.keys(this.items);
        },
        getItems: function() {
            return this.items;
        }
    };

2.1.2字典的基本使用

    var dictionary = new Dictionary();
    console.log(dictionary.size()); //0
    dictionary.set("first", "huang");
    dictionary.set("second", "cheng");
    dictionary.set("third", "du");
    console.log(dictionary.has("first")); //true
    console.log(dictionary.get("second")); //cheng
    console.log(dictionary.values()); // ["first", "second", "third"]
    dictionary.remove("second");
    console.log(dictionary.keys()); //["first", "third"]
    console.log(dictionary.getItems()); //{ first="huang",  third="du"}

2.2散列表

HashTable類,也叫HashMap類,是Dictionary類的一種散列表實現(xiàn)方式。散列算法的作用是盡可能快地在數(shù)據(jù)結構中找到一個值。在之前的章節(jié)中,你已經(jīng)知道如果要在數(shù)據(jù)結構中獲得一個值(使用get方法),需要遍歷整個數(shù)據(jù)結構來找到它。如果使用散列函數(shù),就知道值的具體位置,因此能夠快速檢索到該值。散列函數(shù)的作用是給定一個鍵值,然后返回值在表中的地址。

2.2.1基本版的散列表實現(xiàn)

在散列表中我們通過散列函數(shù)來確定鍵值對的關系。基本方法如下：

put(key,value): 向散列表增加一個新的選項(也可能是更新散列表)。

remove(key): 根據(jù)鍵值從散列表中移除值。

get(key): 返回根據(jù)鍵值檢索到的特定值。

對于HashTable類來說,我們不需要像ArrayList類一樣從table數(shù)組中將位置也移除。由于元素分布于整個數(shù)組范圍內(nèi),一些位置會沒有任何元素占據(jù),并默認為undefined值。我們也不能將位置本身從數(shù)組中移除(這會改變其他元素的位置),否則,當下次需要獲得或移除一個元素的時候,這個元素會不在我們用散列函數(shù)求出的位置上。

    //lose-los散列函數(shù)
    function loseloseHashCode(key) {
        var hash = 0;
        for (var i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    }

    function HashTable() {
        this.table = [];
    }
    HashTable.prototype = {
        constructor: HashTable,
        put: function(key, value) {
            var position = loseloseHashCode(key);
            console.log(position + "- " + key);
            this.table[position] = value;
        },
        get: function(key) {
            return this.table[loseloseHashCode(key)];
        },
        remove: function(key) {
            this.table[loseloseHashCode(key)] = undefined;
        }
    };

    var hash = new HashTable();
    hash.put("Gandalf", "[email protected]");
    hash.put("John", "[email protected]");
    hash.put("Tyrion", "[email protected]");
    console.log(hash.get("Gandalf")); //[email protected]
    console.log(hash.get("Loiane")); //undefined
    hash.remove("Gandalf");
    console.log(hash.get("Gandalf")); //undefined

有時候,一些鍵會有相同的散列值。不同的值在散列表中對應相同位置的時候,我們稱其為沖突。當這種情況發(fā)生的時候就要去解決它。處理沖突有幾種方法:分離鏈接、線性探查和雙散列法,我們會介紹前兩種方法。對于分離鏈接和線性探查來說,只需要重寫三個方法:put、get和remove。這三個方法在每種技術實現(xiàn)中都是不同的。

2.2.2分離鏈接版散列表

為了實現(xiàn)一個使用了分離鏈接的HashTable實例,我們需要一個新的輔助類來表示將要加入LinkedList實例的元素。我們管它叫ValuePair類。LinkedList的實現(xiàn)具體看javascript的數(shù)據(jù)結構與算法(一).html)。

分離鏈接：分離鏈接法包括為散列表的每一個位置創(chuàng)建一個鏈表并將元素存儲在里面。它是解決沖突的最簡單的方法,但是它在HashTable實例之外還需要額外的存儲空間。

    function HashTable() {
        this.table = []; 
        //lose-los散列函數(shù) 
        function loseloseHashCode(key) {
            var hash = 0;
            for (var i = 0; i < key.length; i++) {
                hash += key.charCodeAt(i);
            }
            //console.log(key + " - " + (hash % 37));
            return hash % 37;
        }

        function ValuePair(key, value) {
            this.key = key;
            this.value = value;
            this.toString = function() {
                return "[" + this.key + " - " + this.value + "]";
            }
        }
        if ((typeof this.put !== "function") && (typeof this.put !== "string")) {
            HashTable.prototype.put = function(key, value) {
                var position = loseloseHashCode(key);
                if (this.table[position] === undefined) {
                    this.table[position] = new LinkedList();
                }
                this.table[position].append(new ValuePair(key, value));
            };
            HashTable.prototype.get = function(key) {
                var position = loseloseHashCode(key);
                if (this.table[position] !== undefined) {
                    var current = this.table[position].getHead();
                    while (current.next) {
                        if (current.element.key === key) {
                            return current.element.value;
                        }
                        current = current.next;
                    }
                    //第一個元素或者最后一個元素
                    if (current.element.key === key) {
                        return current.element.value;
                    }
                } else {
                    return undefined;
                }
            };
            HashTable.prototype.remove = function(key) {
                var position = loseloseHashCode(key);
                if (this.table[position] !== undefined) {
                    var current = this.table[position].getHead();
                    while (current.next) {
                        if (current.element.key === key) {
                            this.table[position].remove(current.element);
                            if (this.table[position].isEmpty()) {
                                this.table[position] = undefined;
                            }
                            return true;
                        }
                        current = current.next;
                    }
                    //檢查是否是第一個或者最后一個
                    if (current.element.key === key) {
                        this.table[position].remove(current.element);
                        if (this.table[position].isEmpty()) {
                            this.table[position] = undefined;
                        }
                        return true;
                    }
                }
                return false;
            };
        }
    }
    var hash = new HashTable();
    hash.put("Gandalf", "[email protected]");
    hash.put("John", "[email protected]");
    //下面兩個hash值相同
    hash.put("Aaron", "[email protected]");
    hash.put("Tyrion", "[email protected]");
    console.log(hash.get("Gandalf")); //[email protected]
    console.log(hash.get("Loiane")); //undefined
    hash.remove("Gandalf");
    console.log(hash.get("Gandalf")); //undefined

2.2.3線性探查版散列表

另一種解決沖突的方法是線性探查。當想向表中某個位置加入一個新元素的時候,如果索引為index的位置已經(jīng)被占據(jù)了,就嘗試index+1的位置。如果index+1的位置也被占據(jù)了,就嘗試 index+2的位置,以此類推。

    function HashTable() {
        this.table = []; //lose-los散列函數(shù) 
        function loseloseHashCode(key) {
            var hash = 0;
            for (var i = 0; i < key.length; i++) {
                hash += key.charCodeAt(i);
            }
            //console.log(key + " - " + (hash % 37));
            return hash % 37;
        }

        function ValuePair(key, value) {
            this.key = key;
            this.value = value;
            this.toString = function() {
                return "[" + this.key + " - " + this.value + "]";
            }
        }
        if ((typeof this.put !== "function") && (typeof this.put !== "string")) {
            HashTable.prototype.put = function(key, value) {
                var position = loseloseHashCode(key);
                if (this.table[position] === undefined) {
                    this.table[position] = new ValuePair(key, value);
                } else {
                    var index = position + 1;
                    while (this.table[index] !== undefined) {
                        index++;
                    }
                    this.table[index] = new ValuePair(key, value);
                }
            };
            HashTable.prototype.get = function(key) {
                var position = loseloseHashCode(key);
                if (this.table[position] !== undefined) {
                    if (this.table[position].key === key) {
                        return this.table[position].value;
                    } else {
                        var index = position + 1;
                        //index不超過數(shù)組的長度
                        while (((this.table[index] === undefined) || (this.table[index].key !== key)) && (index < this.table.length)) {
                            index++;
                        }
                        if (this.table[index] && (this.table[index].key === key)) {
                            return this.table[index].value;
                        } else {
                            return undefined;
                        }
                    }
                } else {
                    return undefined;
                }
            };
            HashTable.prototype.remove = function(key) {
                var position = loseloseHashCode(key);
                if (this.table[position] !== undefined) {
                    if (this.table[position].key === key) {
                        this.table[position] = undefined;
                        return true;
                    } else {
                        var index = position + 1;
                        while ((this.table[index] === undefined) || (this.table[index].key !== key)) {
                            index++;
                        }
                        if (this.table[index].key === key) {
                            this.table[index] = undefined;
                            return true;
                        }
                    }
                } else {
                    return false;
                }
            };
        }
    }
    var hash = new HashTable();
    hash.put("Gandalf", "[email protected]");
    hash.put("John", "[email protected]");
    //下面兩個hash值相同
    hash.put("Aaron", "[email protected]");
    hash.put("Tyrion", "[email protected]");
    console.log(hash.get("Gandalf")); //[email protected]
    console.log(hash.get("Loiane")); //undefined
    console.log(hash.remove("Gandalf")); //true
    console.log(hash.get("Gandalf")); //undefined

源碼地址

Javascript的數(shù)據(jù)結構與算法(二)源碼

云服務器 GPU云服務器最小二乘法的簡潔算法最小二乘的遞歸算法描述的數(shù)據(jù)結構與算法最小二乘擬合的算法效率

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/86660.html

學習JavaScript數(shù)據(jù)結構與算法（二）：鏈表

摘要：實現(xiàn)移除給定的元素要移除的元素返回值表示移除成功方法說明移除單向鏈表中某個位置的元素。的前端樂園原文鏈接寒假前端學習學習數(shù)據(jù)結構與算法二鏈表本系列的第一篇文章: 學習JavaScript數(shù)據(jù)結構與算法（一），棧與隊列第二篇文章：學習JavaScript數(shù)據(jù)結構與算法（二）：鏈表第三篇文章：學習JavaScript數(shù)據(jù)結構與算法（三）：集合第四篇文章：學習JavaScript數(shù)據(jù)結構與...

lolomaco 2019-08-22 11:00 評論0 收藏0
CSS技巧

摘要：技巧使你的更加專業(yè)這是上關于技巧的一篇譯文，另外你也可以在本項目看到原文。列舉了一些很實用的技巧，比如給空內(nèi)容的標簽添加內(nèi)容，逗號分隔列表等等。排序算法看源碼，把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現(xiàn)。成為專業(yè)程序員路上用到的各種優(yōu)秀資料、神器及框架成為一名專業(yè)程序員的道路上，需要堅持練習、學習與積累，技術方面既要有一定的廣度，更要有自己的深度。 Java...

DangoSky 2019-08-22 11:15 評論0 收藏0
CSS技巧

摘要：技巧使你的更加專業(yè)這是上關于技巧的一篇譯文，另外你也可以在本項目看到原文。列舉了一些很實用的技巧，比如給空內(nèi)容的標簽添加內(nèi)容，逗號分隔列表等等。排序算法看源碼，把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現(xiàn)。成為專業(yè)程序員路上用到的各種優(yōu)秀資料、神器及框架成為一名專業(yè)程序員的道路上，需要堅持練習、學習與積累，技術方面既要有一定的廣度，更要有自己的深度。 Java...

zgbgx 2019-08-29 14:01 評論0 收藏0
學習JavaScript數(shù)據(jù)結構與算法（四）：二叉搜索樹

摘要：像剛才的這幅圖，就是二叉搜索樹。而我們本文要學習的內(nèi)容，就是如何寫一個二叉搜索樹。但在二叉搜索樹中，我們把節(jié)點成為鍵，這是術語。前端路漫漫，且行且歌的前端樂園原文鏈接寒假前端學習學習數(shù)據(jù)結構與算法四二叉搜索樹本系列的第一篇文章: 學習JavaScript數(shù)據(jù)結構與算法（一），棧與隊列第二篇文章：學習JavaScript數(shù)據(jù)結構與算法（二）：鏈表第三篇文章：學習JavaScript數(shù)據(jù)...

ingood 2019-08-19 17:26 評論0 收藏0
JavaScript的數(shù)據(jù)結構與算法（二） —— 隊列

摘要：簡介隊列遵循的是先進先出的原則的一組有序的項。隊列從尾部添加新元素，并從頂部移除元素，最新添加的元素必須排列在隊列的末尾。它的想法來自于生活中排隊的策略。隊列不做任何變動。簡介隊列遵循的是FIFO（先進先出）的原則的一組有序的項。隊列從尾部添加新元素，并從頂部移除元素，最新添加的元素必須排列在隊列的末尾。它的想法來自于生活中排隊的策略。顧客在付款結賬的時候，按照到來的先后順序排...

xingqiba 2019-08-21 17:12 評論0 收藏0
學習JavaScript數(shù)據(jù)結構與算法（一）：棧與隊列

摘要：之數(shù)組操作接下來就是數(shù)據(jù)結構的第一部分，棧。以字符串顯示棧中所有內(nèi)容方法的實現(xiàn)說明需要往棧中添加新元素，元素位置在隊列的末尾。的前端樂園原文鏈接寒假前端學習學習數(shù)據(jù)結構與算法，棧與隊列本系列的第一篇文章: 學習JavaScript數(shù)據(jù)結構與算法（一），棧與隊列第二篇文章：學習JavaScript數(shù)據(jù)結構與算法（二）：鏈表第三篇文章：學習JavaScript數(shù)據(jù)結構與算法（三）：集合第...

Flink_China 2019-08-19 17:23 評論0 收藏0