《数据结构与算法-Javascript描述》

　　今年的上半年，项目原因大部分时间在写js，这期间把easyui，echarts，bootstrap都用了点皮毛，写的多了，自然也多了些感觉，不过仅局限于运用层面，于是决定再系统的看些javascript方面的书，强化运用能力，便有了这本~来自于国内知名公司前端工程师翻译自国外的书，见名知意用Javascript角度来讲数据结构和算法，一方面可以把javascript的基础知识加强，一方面加深数据结构以及算法的理解和应用。

全书篇幅不长，第一章简明扼要对javascript做了简单的介绍，基本语法、运算符、流程控制方面的基础知识，中间按章节依次对常用数据结构进行讲解。javascript除提供原生态的数组外，其他数据结构都需要自己实现，没有高级语言c#，java来的这么方便。常用数据结构分别是列表，栈，队列，链表，字典，散列，集合，二叉树，图，最后三章是算法相关，分别是排序算法、检索算法、以及两个高级算法，动态规划和贪心算法。

本书循序渐进，层层深入，从最基础的列表开始，到栈、队列，链表、hashtable、set、tree等的实现结合代码通俗易懂的呈现出来，并结合一些实例加强对数据结构的理解。

在看完数据结构部分章节后，并动手将书中的示例敲了一遍加深印象，与此同时还有额外的收获，对js中的this关键字有了更进一步的理解。重温了一遍数据结构在js中的实现，特别是hashtable章节，对散列过程中的碰撞做了很详细的说明，如何避免碰撞的产生和提升性能方面都给出了解决方案，为今后编写高质量代码和优化代码提供了一定的借鉴作用。

列表

<!doctype html>
<html lang="en">
 <head>
  <meta charset="UTF-8">
  <meta name="Generator" content="EditPlus®">
  <meta name="Author" content="">
  <meta name="Keywords" content="">
  <meta name="Description" content="">
  <title>Javascript-List</title>
 </head>
 <body>
  <script type="text/javascript">
    function List(){
        this.listSize=0;
        this.pos=0;
        this.dataStore=[];
        this.clear=clear;
        this.find=find;
        this.toString=toString;
        this.insert=insert;
        this.append=append;
        this.remove=remove;
        this.front=front;
        this.end=end;
        this.prev=prev;
        this.next=next;
        this.length=length;
        this.currPos=currPos;
        this.moveTo=moveTo;
        this.contains=contains;
        this.getElement=getElement;
    }

    function append(element){
        this.dataStore[this.listSize++]=element;
    }
    function find(element){
        for(var i=0;i<this.dataStore.length;i++){
            if(this.dataStore[i]==element){
                return i;
            }
        }
        return -1;
    }
    function remove(element){
        var foundAt=this.find(element);
        if(foundAt>-1){
            this.dataStore.splice(foundAt,1);
            --this.listSize;
            return true;
        }
        return false;
    }
    function length(){
        return this.listSize;
    }
    function toString(){
        return this.dataStore;
    }
    function clear(){
        delete this.dataStore;
        this.dataStore=[];
        this.listSize=this.pos=0;
    }
    function insert(element,after){
        var insertPos=this.find(after);
        if(insertPos>-1){
            this.dataStore.splice(insertPos+1,0,element);
            ++this.listSize;
            return true;
        }
        return false;
    }
    function front(){
        this.pos=0;
    }
    function end(){
        this.pos=this.listSize-1;
    }
    function prev(){
        if(this.pos>0){
            --this.pos;
        }
    }
    function next(){
        if(this.pos<this.listSize-1){
            ++this.pos;
        }
    }
    function currPos(){
        return this.pos;
    }
    function contains(element){
        for(var i=0;i<this.dataStore.length;i++){
            if(this.dataStore[i]==element){
                return true;
            }
        }
        return false;
    }
    function getElement(){
        return this.dataStore[this.pos];
    }
    var names=new List();
    names.append("123");
    names.append("456");
    names.append(1);
    names.append("789");
    console.log(names.toString());
    names.front();
    names.next();
    names.next();
    console.log(names.getElement());
  </script>
 </body>
</html>

View Code

栈

<!doctype html>
<html lang="en">
 <head>
  <meta charset="UTF-8">
  <meta name="Generator" content="EditPlus®">
  <meta name="Author" content="">
  <meta name="Keywords" content="">
  <meta name="Description" content="">
  <title>Javascript-Stack</title>
 </head>
 <body>
   <script type="text/javascript">
        function Stack(){
            this.dataStore=[];
            this.top=0;
            this.push=push;
            this.pop=pop;
            this.peek=peek;
            this.length=length;
        }
        function push(element){
            this.dataStore[this.top++]=element;
        }
        function pop(){
            return this.dataStore[--this.top];
        }

        function peek(){
            return this.dataStore[this.top-1];
        }

        function length(){
            return this.top;
        }
        function clear(){
            this.top=0;
        }

        var s=new Stack();
        s.push("1");
        s.push("2");
        console.log(s.length());
        console.log(s.pop());
        console.log(s.length());
        s.push("3");
        console.log(s.length());
        console.log(s.peek());
        s.pop();
        console.log(s.peek());

        function isPalindrome(word){
            var s=new Stack();
            for(var i=0;i<word.length;i++){
                s.push(word[i]);
            }
            var rword="";
            while(s.length()>0){
                rword+=s.pop();
            }
            if(word==rword){
                return true;
            }else{
                return false;
            }
        }

        var word="hello";
        console.log(word +" is palindrome : "+isPalindrome(word));
        word="level";
        console.log(word +" is palindrome : "+isPalindrome(word));
        word="racecar";
        console.log(word +" is palindrome : "+isPalindrome(word));
   </script>
 </body>
</html>

View Code

队列

<!doctype html>
<html lang="en">
 <head>
  <meta charset="UTF-8">
  <meta name="Generator" content="EditPlus®">
  <meta name="Author" content="">
  <meta name="Keywords" content="">
  <meta name="Description" content="">
  <title>Javascript-Queue</title>
 </head>
 <body>
  <script type="text/javascript">
    function Queue(){
        this.dataStore=[];
        this.enqueue=enqueue;
        this.dequeue=dequeue;
        this.front=front;
        this.back=back;
        this.toString=toString;
        this.empty=empty;
    }
    function enqueue(element){
        this.dataStore.push(element);
    }
    function dequeue(){
        return this.dataStore.shift();
    }
    function front(){
        return this.dataStore[0];
    }
    function back(){
        return this.dataStore[this.dataStore.length-1];
    }
    function toString(){
        var reStr="";
        for(var i=0;i<this.dataStore.length;i++){
            reStr+=this.dataStore[i]+"
";
        }
        return reStr;
    }
    function empty(){
        if(this.dataStore.length==0){
            return true;
        }else{
            return false;
        }
    }

    var q=new Queue();
    q.enqueue("1");
    q.enqueue("2");
    q.enqueue("3");
    console.log(q.toString());
    q.dequeue();
    console.log(q.toString());
    console.log("front:"+q.front());
    console.log("back:"+q.back());
  </script>
 </body>
</html>

View Code

链表

<!doctype html>
<html lang="en">
 <head>
  <meta charset="UTF-8">
  <meta name="Generator" content="EditPlus®">
  <meta name="Author" content="">
  <meta name="Keywords" content="">
  <meta name="Description" content="">
  <title>javascript-linkList</title>
 </head>
 <body>
  <script type="text/javascript">
    function Node(element){
        this.element=element;
        this.next=null;
    }
    function LList(){
        this.head=new Node("head");
        this.find=find;
        this.insert=insert;
        this.remove=remove;
        this.display=display;
        this.findPrevious=findPrevious;
    }
    function find(item){
        var currNode=this.head;
        while(currNode.element!=item){
            currNode=currNode.next;
        }
        return currNode;
    }
    function insert(newElement,item){
        var newNode=new Node(newElement);
        var current=this.find(item);
        newNode.next=current.next;
        current.next=newNode;
    }
    function display(){
        var currNode=this.head;
        while(!(currNode.next==null)){
            console.log(currNode.next.element);
            currNode=currNode.next;
        }
    }
    function findPrevious(item){
        var currNode=this.head;
        while(!(currNode.next==null)&&
         (currNode.next.element!=item)){
            currNode=currNode.next;
        }
        return currNode;
    }
    function remove(item){
        var preNode=this.findPrevious(item);
        if(!(preNode.next==null)){
            preNode.next=preNode.next.next;
        }
    }
    
    var cities=new LList();
    cities.insert("beijing","head");
    cities.insert("shanghai","beijing");
    cities.insert("shenzhen","shanghai");
    cities.display();
    cities.remove("shanghai");
    cities.display();
  </script>
 </body>
</html>

View Code

Hashtable

<!doctype html>
<html lang="en">
 <head>
  <meta charset="UTF-8">
  <meta name="Generator" content="EditPlus®">
  <meta name="Author" content="">
  <meta name="Keywords" content="">
  <meta name="Description" content="">
  <title>javascript-hashtable</title>
 </head>
 <body>
  <script type="text/javascript">
    function Hashtable(){
        this.table=new Array(137);
        this.simpleHash=simpleHash;
        this.betterHash=betterHash;
        this.showStorage=showStorage;
        this.put=put;
    }
    function put(data){
        //var pos=this.simpleHash(data);
        var pos=this.betterHash(data);
        this.table[pos]=data;
    }
    function simpleHash(data){
        var total=0;
        for(var i=0;i<data.length;i++){
            total+=data.charCodeAt(i);
        }
        //console.log(data+":"+total);
        return total%this.table.length;
    }
    function showStorage(){
        var n=0;
        for(var i=0;i<this.table.length;i++){
            if(this.table[i]!=undefined){
                console.log(i+": "+this.table[i]);
            }
        }
    }
    function betterHash(data){
        const H=37;
        var total=0;
        for(var i=0;i<data.length;i++){
            total+=H*total+data.charCodeAt(i);
        }
        total=total%this.table.length;
        //console.log(total);
        if(total<0){
            total+=this.table.length-1;
        }
        return parseInt(total);
    }
    var someNames = ["David", "Jennifer", "Donnie", "Raymond","Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
    var hTable = new Hashtable();
    for (var i = 0; i < someNames.length; ++i) {
        
        //console.log(someNames[i]+":"+someNames[i].charCodeAt(i));
        hTable.put(someNames[i]);
    } 
    hTable.showStorage();
  </script>
 </body>
</html>

View Code

集合

<!doctype html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="Generator" content="EditPlus®">
    <meta name="Author" content="">
    <meta name="Keywords" content="">
    <meta name="Description" content="">
    <title>javascript-set</title>
</head>
<body>
    <script type="text/javascript">
        function Set() {
            this.dataStore = [];
            this.add = add;
            this.remove = remove;
            this.size=size;
            this.union=union;
            this.intersect=intersect;
            this.subset = subset;
            this.contains = contains;
            this.difference=difference;
            this.show = show;
        }
        function add(data) {
            if (this.dataStore.indexOf(data) < 0) {
                this.dataStore.push(data);
                return true;
            } else {
                return false;
            }
        }
        function remove(data) {
            var pos = this.dataStore.indexOf(data);
            if (pos > -1) {
                this.dataStore.splice(pos, 1);
                return true;
            } else {
                return false;
            }
        }
        function show() {
            return this.dataStore;
        }

        function contains(data) {
            if (this.dataStore.indexOf(data) > -1) {
                return true;
            } else {
                return false;
            }
        }
        function union(set) {
            var tempSet = new Set();
            for (var i = 0; i < this.dataStore.length; i++) {
                tempSet.add(this.dataStore[i]);
            }
            for (var i = 0; i < set.dataStore.length; i++) {
                if (!tempSet.contains(set.dataStore[i])) {
                    tempSet.dataStore.push(set.dataStore[i]);
                }
            }
            return tempSet;
        }
        function intersect(set) {
            var tempSet = new Set();
            for (var i = 0; i < this.dataStore.length; i++) {
                if (set.contains(this.dataStore[i])) {
                    tempSet.add(this.dataStore[i]);
                }
            }
            return tempSet;
        }

        function size() {
            return this.dataStore.length;
        }
        function subset(set) {
            if (this.size() > set.size()) {
                return false;
            } else {
                for (var i = 0; i < this.dataStore.length ; i++) {
                    if (!set.contains(this.dataStore[i])) {
                        return false;
                    }
                }
                return true;
            }
        }
        function difference(set) {
            var tempSet = new Set();
            for (var i = 0; i < this.dataStore.length; ++i) {
                if (!set.contains(this.dataStore[i])) {
                    tempSet.add(this.dataStore[i]);
                }
            } return tempSet;
        }
        //basic
        //var names = new Set();
        //names.add("David");
        //names.add("Jennifer");
        //names.add("Cynthia");

        //union
        var cis = new Set();
        //cis.add("Mike");
        //cis.add("Clayton");
        //cis.add("Jennifer");
        //cis.add("Raymond");
        //var dmp = new Set();
        //dmp.add("Raymond");
        //dmp.add("Cynthia");
        //dmp.add("Jonathan");
        //var it = new Set();
        //it = cis.union(dmp);
        //console.log(it.show());

        //intersect
        //var cis = new Set();
        //cis.add("Mike");
        //cis.add("Clayton");
        //cis.add("Jennifer");
        //cis.add("Raymond");
        //var dmp = new Set();
        //dmp.add("Raymond");
        //dmp.add("Cynthia");
        //dmp.add("Bryan");
        //var inter = cis.intersect(dmp);
        //console.log(inter.show()); // 显示 Raymond
        //console.log(names.show());
        //names.remove("David");
        //console.log(names.show());

        //subset
        //var it = new Set();
        //it.add("Cynthia");
        //it.add("Clayton");
        //it.add("Jennifer");
        //it.add("Danny");
        //it.add("Jonathan");
        //it.add("Terrill");
        //it.add("Raymond");
        //it.add("Mike");
        //var dmp = new Set();
        //dmp.add("Cynthia");
        //dmp.add("Raymond");
        //dmp.add("Jonathan");
        //if (dmp.subset(it)) {
        //    console.log("DMP is a subset of IT.");
        //} else {
        //    console.log("DMP is not a subset of IT.");
        //}

        //differencce
        var cis = new Set();
        var it = new Set();
        cis.add("Clayton");
        cis.add("Jennifer");
        cis.add("Danny");
        it.add("Bryan");
        it.add("Clayton");
        it.add("Jennifer");
        var diff = new Set();
        diff = cis.difference(it);
        console.log("[" + cis.show() + "] difference [" + it.show()+ "] -> [" + diff.show() + "]");

    </script>
</body>
</html>

View Code