国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

數據結構 JS 版

sarva / 1119人閱讀

摘要:內容棧隊列鏈表集合字典散列表樹棧通過類封裝實現棧結構,不直接繼承數組的原生方法的原因是,數組具有某些其他數據結構的方法,為了只讓棧暴露棧的方法,還得編寫將非棧的方法封閉的代碼,多了冗余代碼,且不是面向對象編程的合理表現。

內容:棧、隊列、鏈表、集合、字典、散列表、樹

通過類封裝實現棧結構,不直接繼承數組的原生方法的原因是,數組具有某些其他數據結構的方法,為了只讓棧暴露棧的方法,還得編寫將非棧的方法封閉的代碼,多了冗余代碼,且不是面向對象編程的合理表現。

//棧,方法包括入棧操作、出棧操作、返回棧頂元素、判斷棧是否為空、清空棧、棧的長度
//這里棧實例對象的方法都可看作閉包函數,items可看作類的私有變量,只有類實例的方法來訪問,而items也是棧內容的存儲實體。
function Stack(){
    var items = [];
    this.push = function(ele){
        items.push(ele);
    };
    this.pop = function(){
        items.pop();
    };
    this.size = function(){
        return items.length;
    };
    this.clear = function(){
        items = [];
    };
    this.peek = function(){
        return items[items.length-1];
    }
    this.isEmpty = function(){
        return items.length > 0 ? false : true;
    }
}
var stack = new Stack();
console.log(stack);
stack.push(2);
console.log(stack.size());
console.log(stack.isEmpty());
隊列

基礎實現

//隊列,方法包括入隊操作、出隊操作、返回隊首元素、判斷隊列是否為空、清空隊列、隊列的長度
function Queue(){
    var items = [];
    this.inqueue = function(ele){
        items.push(ele);
    };
    this.outqueue = function(){
        items.shift();
    };
    this.size = function(){
        return items.length;
    };
    this.clear = function(){
        items = [];
    };
    this.front = function(){
        return items[0];
    }
    this.isEmpty = function(){
        return items.length > 0 ? false : true;
    }
}

優先級隊列

考慮到隊列中每個元素具有優先級,所以隊列中的元素采用對象來實現,具有兩個屬性:元素的值和元素的優先級。

//優先級隊列
function PriorityQueue(){
    var items = [];
    function QueueElement(element,priority){
        this.element = element;
        this.priority = priority;
    }
    this.inqueue = function(element,priority){
        var queueElement = new QueueElement(element,priority);
        if(this.isEmpty()){
            items.push(queueElement);
        }else{
            for(var i=0;i priority){
                    items.splice(i,0,queueElement);
                    break;
                }else if(i === (items.length-1)){
                    items.push(queueElement);
                    break;  // 這里一定要break,不然會循環插入,導致堆溢出
                }
            }
        }
    };
    this.outqueue = function(){
        items.shift();
    };
    this.size = function(){
        return items.length;
    };
    this.clear = function(){
        items = [];
    };
    this.front = function(){
        return items[0].element;
    }
    this.isEmpty = function(){
        return items.length > 0 ? false : true;
    }
    this.get = function(){
        return items;
    }
}

循環隊列/擊鼓傳花游戲

可以換個角度想:一排凳子,所有人循環去坐,擊鼓之后,坐在第一個凳子(隊頭)上的人淘汰,即下面代碼參考的思路。

//循環隊列
//擊鼓傳花游戲,以固定循環次數來模擬每輪擊鼓的固定時長,該游戲會一輪一輪迭代,每輪淘汰一人,直到只剩最后一人即為勝者
function hotPotato(namelist,num){
    var queue = new Queue();
    for(var i=0;i 1){
        for(i=0;i
鏈表

由于鏈表中每個元素都有指向下一個元素的指針,所以鏈表中每個元素利用對象來實現,對象具有兩個屬性:元素的值和指向下一個元素的指針;在指定位置插入或刪除元素,都需要注意與前一個和后一個元素之間指針的關系;

//鏈表,元素在內存中非連續放置,方法包括鏈表尾部加入/刪除元素,鏈表指定位置加入/刪除元素,找出元素在鏈表中的索引,鏈表是否為空,鏈表的長度
function LinkedList(){
    var head = null;//鏈表第一個元素的引用
    var length = 0;//鏈表的長度,不然尋求size很麻煩
    var end = null;//鏈表最后一個元素的引用,方便插入/刪除元素
    function Node(element){
        this.element = element;
        this.next = null;
    }
    //從鏈表尾部加入node元素
    this.appendList = function(element){
        var node = new Node(element);
        if(head === null){
            head = node;
        }else{
            end.next = node;
        }
        end = node;
        length++;
    };
    //從鏈表指定位置加入node元素,0表示在鏈表頭插入該元素
    this.appendListAt = function(position,element){
        var node = new Node(element);
        if(position > 0){
            var frontNode = this.findNodeAt(position);
            var afterNode = frontNode.next;
            frontNode.next = node;
            node.next = afterNode;
            length++;
        }else if(position === 0){
            node.next = head;
            head = node;
            length++;
        }
    };
    //從鏈表尾部刪除node元素
    this.removeList = function(){
        if(head !== null){
            var findNode = this.findNodeAt(length-1);
            end = findNode;
            findNode.next = null;
            length--;
        }
    };
    //從鏈表指定位置刪除node元素
    this.removeListAt = function(position){
        if(position > 1){ //永遠檢測用戶輸入
            var frontNode = this.findNodeAt(position-1);
            var afterNode = frontNode.next.next;
            frontNode.next = afterNode;
            length--;
        }else if(position = 1){
            head = head.next;
            length--;
        }
    };
    //鏈表的大小
    this.size = function(){
        return length;
    };
    this.isEmpty = function(){
        return head === null ? true : false;
    }
    this.toString = function(){
        var iterNode = head;
        var outString = [];
        outString.push(head.element);
        for(var i=1;i 1){
            iterNode = iterNode.next;
            position--;
        }
        return iterNode;
    }
}
集合

采用對象來實現集合,對象的屬性存放元素值,因為對象中的屬性無序,可以很好地模擬集合的特性

//集合,集合類的方法包括添加/刪除元素,是否有某值,清除集合,集合大小
function Set(){
    var items = {};
    this.has = function(value){
        return items.hasOwnProperty(value);
    }
    //向集合中添加元素
    this.add = function(value){
        if(!this.has(value)){
            items[value] = value;
            return true;
        }
        return false;
    }
    //刪除集合中的元素
    this.remove = function(value){
        if(this.has(value)){
            delete items[value];  // 刪除元素的屬性
        }
        return false;
    }
    this.size = function(){
        return Object.keys(items).length;
    }
    this.clear = function(){
        items = {};
    }
    this.values = function(){
        return Object.keys(items); //返回對象自身中可枚舉屬性
    }

    //集合的交集,并集,差集,子集方法
    //并集
    this.union = function(setB){
        var setAvalues = this.values();
        var setUnion = new Set();
        for(var i=0;i
字典

有集合的實現類似

//采用對象來實現字典,以key-value的形式存儲,因為對象中的屬性無序,字典的方法包括通過key來添加/刪除元素,是否有某值,清除字典,字典大小
function Dictionary(){
    var items = {};
    this.has = function(key){
        return items.hasOwnProperty(key);
    }
    //向字典中添加元素
    this.set = function(key,value){
        if(!this.has(key)){
            items[key] = value;
            return true;
        }
        return false;
    }
    //刪除字典中的元素
    this.remove = function(key){
        if(this.has(key)){
            delete items[key];
            return true;
        }
        return false;
    }
    //獲取固定的值
    this.get = function(key){
        return this.has(key) ? items[key] : undefined;
    }
    this.size = function(){
        return Object.keys(items).length;
    }
    this.clear = function(){
        items = {};
    }
    this.keys = function(){
        return Object.keys(items); //返回對象自身中可枚舉屬性
    }
    this.values = function(){
        var res = [];
        for(key in items){
            if(items.hasOwnProperty(key)){
                res.push(items[key]);
            }
        }
        return res;
    }
    //獲取整個字典對象
    this.getItems = function(){
        return items; 
    }

}
二叉搜索樹

二叉搜索樹中每個節點都有三個屬性。值,左引用,右引用。

注意在實現時,拿到節點對象的引用,并不能對節點本身進行刪除,最好刪除節點的方法是將上一個節點的引用指向置為null,并將節點對象的引用置為null(釋放內存,通知垃圾回收)

//二叉搜索樹
function BinarySearchTree(){
    var rootNode = null;
    function TreeNode(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
    //向樹中插入新節點
    this.insert = function(key){
        var treeNode = new TreeNode(key);
        if(rootNode === null){
            rootNode = treeNode;
        }else{
            insertNode(rootNode,treeNode);
        }
    }
    function insertNode(node,treeNode){
        if(treeNode.key < node.key){
            if(node.left === null){
                node.left = treeNode;
            }else{
                insertNode(node.left,treeNode);
            }
        }else if(treeNode.key > node.key){
            if(node.right === null){
                node.right = treeNode;
            }else{
                insertNode(node.right,treeNode);
            }
        }
    }
    //先序遍歷
    this.preOrderTraverse = function(){
        if(rootNode === null){
            console.log("沒有節點");
        }else{
            pretraverse(rootNode);
        }
    }
    function pretraverse(node){
        if(node !== null){
            pretraverse(node.left);
            console.log(node.key);
            pretraverse(node.right);
        }
    }
    //中序遍歷
    this.inOrderTraverse = function(){
        if(rootNode === null){
            console.log("沒有節點");
        }else{
            intraverse(rootNode);
        }
    }
    function intraverse(node){
        if(node !== null){
            console.log(node.key);
            intraverse(node.left);
            intraverse(node.right);
        }
    }
    //后序遍歷
    this.posOrderTraverse = function(){
        if(rootNode === null){
            console.log("沒有節點");
        }else{
            postraverse(rootNode);
        }
    }
    function postraverse(node){
        if(node !== null){
            postraverse(node.left);
            postraverse(node.right);
            console.log(node.key);
        }
    }
    //移除樹中的節點
    this.remove = function(key){
        rootNode = removeNode(rootNode,key);
    }
    function removeNode(node,key){
        if(node === null){
            return null;
        }
        if(key < node.key){
            node.left = removeNode(node.left,key);
            return node; //與下面三個return node的功能都是保證removeNode的返回值為刪除節點后樹的根節點
        }else if(key > node.key){
            node.right = removeNode(node.right,key);
            return node;
        }else{
            if(node !== null){ //考慮到被刪除節點的三種情況
                if((node.left === null) && (node.right === null)){
                    node = null;//這里只是為了垃圾回收node,下面作用都類似
                    return node;//這里才是刪除的功能,這里的返回是為了讓node.left = removeNode(node.left,key);中node.left=null;
                }else if((node.left === null) && (node.right !== null)){
                    var temp = node.right;
                    node = null;
                    return temp;
                }else if((node.left !== null) && (node.right === null)){
                    var temp = node.left;
                    node = null;
                    return temp;
                }else if((node.left !== null) && (node.right !== null)){
                    var findNode = findMin(node.right);
                    node.key = findNode.key;
                    node.right = removeNode(node.right,findNode.key);
                    return node;
                }
            }
        }
    }
    function findMin(node){
        while(node.left !== null){
            node = node.left;
        }
        return node;
    }
    //查找某個節點
    this.search = function(key){
        var node = rootNode;
        while((node !== null) && (node.key !== key)){
            if(key < node.key){
                node = node.left;
            }else if(key > node.key){
                node = node.right;
            }
        }
        return (node !== null) ? true : false;
    }
    //獲取樹中最小值
    this.min = function(){
        var node = rootNode;
        while(node.left !== null){
            node = node.left;
        }
        return node.key;
    }
    //獲取樹中最大值
    this.max = function(){
        var node = rootNode;
        while(node.right !== null){
            node = node.right;
        }
        return node.key;
    }
    this.getRootNodeKey = function(){
        return rootNode.key;
    }
}

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/108666.html

相關文章

  • 那些年,我的前端/Java后端書單

    摘要:全文為這些年,我曾閱讀深入理解過或正在閱讀學習即將閱讀的一些優秀經典前端后端書籍。當然,如果您喜歡這篇文章,可以動手點點贊或者收藏。 全文為這些年,我曾閱讀、深入理解過(或正在閱讀學習、即將閱讀)的一些優秀經典前端/Java后端書籍。全文為純原創,且將持續更新,未經許可,不得進行轉載。當然,如果您喜歡這篇文章,可以動手點點贊或者收藏。 基礎 基礎書籍 進階 進階階段,深入學習的書...

    fxp 評論0 收藏0
  • 那些年,我的前端/Java后端書單

    摘要:全文為這些年,我曾閱讀深入理解過或正在閱讀學習即將閱讀的一些優秀經典前端后端書籍。當然,如果您喜歡這篇文章,可以動手點點贊或者收藏。 全文為這些年,我曾閱讀、深入理解過(或正在閱讀學習、即將閱讀)的一些優秀經典前端/Java后端書籍。全文為純原創,且將持續更新,未經許可,不得進行轉載。當然,如果您喜歡這篇文章,可以動手點點贊或者收藏。 基礎 基礎書籍 進階 進階階段,深入學習的書...

    Tecode 評論0 收藏0
  • 那些年,我的前端/Java后端書單

    摘要:全文為這些年,我曾閱讀深入理解過或正在閱讀學習即將閱讀的一些優秀經典前端后端書籍。當然,如果您喜歡這篇文章,可以動手點點贊或者收藏。 全文為這些年,我曾閱讀、深入理解過(或正在閱讀學習、即將閱讀)的一些優秀經典前端/Java后端書籍。全文為純原創,且將持續更新,未經許可,不得進行轉載。當然,如果您喜歡這篇文章,可以動手點點贊或者收藏。 基礎 基礎書籍 進階 進階階段,深入學習的書...

    VPointer 評論0 收藏0
  • 那些年,我的前端/Java后端書單

    摘要:全文為這些年,我曾閱讀深入理解過或正在閱讀學習即將閱讀的一些優秀經典前端后端書籍。當然,如果您喜歡這篇文章,可以動手點點贊或者收藏。 全文為這些年,我曾閱讀、深入理解過(或正在閱讀學習、即將閱讀)的一些優秀經典前端/Java后端書籍。全文為純原創,且將持續更新,未經許可,不得進行轉載。當然,如果您喜歡這篇文章,可以動手點點贊或者收藏。 基礎 基礎書籍 進階 進階階段,深入學習的書...

    idealcn 評論0 收藏0
  • 資源大放送

    摘要:這是我收集的一些資源,分享給大家,全部放在百度網盤,有需要的請轉存到自己的網盤或者下載,以免網盤鏈接失效,另外還有幾百的視頻文件存在網盤,需要的加全部分享在空間,自己可以去下載與權威指南配套源碼禪意花園高清源碼基礎教程權威指南參考手冊鋒利 這是我收集的一些資源,分享給大家,全部放在百度網盤,有需要的請轉存到自己的網盤或者下載,以免網盤鏈接失效,另外還有幾百G的視頻文件存在網盤,需要的加...

    lidashuang 評論0 收藏0
  • 你需要的前端進階書籍清單,分享下載

    摘要:寫在前面目前專注深入學習,特花了點時間整理了一些前端學習相關的書籍。大致分為以下大系列系列系列基礎系列應用系列進階系列類庫系列框架系列。這些書籍在這里免費提供下載,有興趣的一起學習。 寫在前面 目前專注深入JavaScript學習,特花了點時間整理了一些前端學習相關的書籍。 大致分為以下7大系列:CSS系列、DOM系列、JavaScript基礎系列、JavaScript應用系列、Ja...

    yuanzhanghu 評論0 收藏0

發表評論

0條評論

sarva

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<