Javascript的數據結構與算法(一)

VioletJack 發布于2019-08-21 11:23 / 598人閱讀

摘要：對數組中的每一項運行給定函數，返回改函數會返回的項組成的數組。將所有的數組元素鏈接成一個字符串。數組合并方法可以向一個數組傳遞數組對象或是元素。通過棧實現對正整數的二進制轉換。源碼地址的數據結構與算法一源碼

1數組 1.1方法列表

數組的常用方法如下:

concat: 鏈接兩個或者更多數據，并返回結果。

every: 對數組中的每一項運行給定的函數，如果該函數對每一項都返回true，則返回true。

filter: 對數組中的每一項運行給定函數，返回改函數會返回true的項組成的數組。

forEach: 對數組中的每一項運行給定函數，這個方法沒有返回值。

join: 將所有的數組元素鏈接成一個字符串。

indexOf: 返回第一個與給定參數相等的數組元素的索引，沒有找到則返回-1。

lastIndexOf: 返回在數組中搜索到的與給定參數相等的元素的索引里最大的值。

map: 對數組中的每一項運行給定函數，返回每次函數調用的結果組成的數組。

reverse: 顛倒數組中元素的順序，原先第一個元素現在變成最后一個，同樣原先的最后一個元素變成現在的第一個。

slice: 傳入索引值，將數組中對應索引范圍內的元素作為新元素返回。

some: 對數組中的每一項運行給定函數，如果任一項返回true，則返回true。

sort: 按照字母順序對數組排序，支持傳入指定排序方法的函數作為參數。

toString: 將數組作為字符串返回。

valueOf: 和toString相似，將數組作為字符串返回。

1.2數組合并

concat方法可以向一個數組傳遞數組、對象或是元素。數組會按照該方法傳入的參數順序連接指定數組。

    var zero = 0;
    var positiveNumbers = [1,2,3];
    var negativeNumbers = [-1,-2,-3];
    var numbers = negativeNumbers.concat(zero,positiveNumbers);
    console.log(numbers);//輸出結果： [-1, -2, -3, 0, 1, 2, 3]

1.3迭代器函數

reduce方法接收一個函數作為參數,這個函數有四個參數:previousValue、currentValue、index和array。這個函數會返回一個將被疊加到累加器的值,reduce方法停止執行后會返回這個累加器。如果要對一個數組中的所有元素求和,這就很有用了。

    var isEven = function(x){
      return (x%2 == 0)?true:false;
    }
    var numbers = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
    //every方法會迭代數組中的每個元素,直到返回false。
    var result = numbers.every(isEven);
    console.log(result);//false
    //some方法會迭代數組的每個元 素,直到函數返回true.
    result = numbers.some(isEven);
    console.log(result);//true
    //forEach對每一項運行給定的函數，沒有返回值
    numbers.forEach(function(item,index){
      console.log(item%2 == 0);
    });
    //map會迭代數組中的每個值，并且返回迭代結果
    var myMap = numbers.map(isEven);
    console.log(myMap);// [false, true, false, true, false, true, false, true, false, true, false, true, false, true, false]
    //filter方法返回的新數組由使函數返回true的元素組成
    var myFilter = numbers.filter(isEven);
    console.log(myFilter);// [2, 4, 6, 8, 10, 12, 14]
    //reduct函數
    var myReduce = numbers.reduce(function(previous,current,index){
      return previous + "" + current;
    });
    console.log(myReduce);//123456789101112131415

1.4排序

    var numbers = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
    numbers.reverse();//[15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    function compare(a,b){
      if(a > b){
        return 1;
      }
      if(a < b){
        return -1;
      }
      return 0;
    }
    //sort函數使用
    [1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9].sort(compare);

    var friends = [{
      name:"huang",
      age:30
    },{
      name:"chengdu",
      age:27
    },{
      name:"du",
      age:31
    }];
    function comparePerson(a,b){
      if(a.age > b.age){
        return 1;
      }
      if(a.age < b.age){
        return -1;
      }
      return 0;
    }
    console.log(friends.sort(comparePerson));// [Object { name="chengdu",  age=27}, Object { name="huang",  age=30}, Object { name="du",  age=31}]
    //搜索
    numbers.push(10);
    console.log(numbers.indexOf(10));//5
    console.log(numbers.lastIndexOf(10));//15
    var numbersString = numbers.join("-");
    console.log(numbersString);//15-14-13-12-11-10-9-8-7-6-5-4-3-2-1-10

2棧 2.1棧的創建

對于一個棧，我們需要實現添加、刪除元素、獲取棧頂元素、已經是否為空，棧的長度、清除元素等幾個基本操作。下面是基本定義。

    function Stack(){
      this.items = [];
    }
    Stack.prototype = {
      constructor:Stack,
      push:function(element){
        this.items.push(element);
      },
      pop:function(){
        return this.items.pop();
      },
      peek:function(){
        return this.items[this.items.length - 1];
      },
      isEmpty:function(){
        return this.items.length == 0;
      },
      clear:function(){
        this.items = [];
      },
      size:function(){
        return this.items.length;
      },
      print:function(){
        console.log(this.items.toString());
      }
    }

2.2棧的基本使用

棧的基本操作。

    var stack = new Stack();
    console.log(stack.isEmpty());//true
    stack.push(5);
    stack.push(8);
    console.log(stack.peek());//8
    stack.push(11);
    console.log(stack.size());//3
    console.log(stack.isEmpty());
    stack.push(15);
    stack.pop();
    stack.pop();
    console.log(stack.size());//2
    console.log(stack.print());//5,8

通過棧實現對正整數的二進制轉換。

    function divideBy2(decNumber){
      var decStack = new Stack();
      var rem;
      var decString = "";
      while(decNumber > 0){
        rem = decNumber%2;
        decStack.push(rem);
        decNumber = Math.floor(decNumber/2);
      }
      while(!decStack.isEmpty()){
        decString += decStack.pop().toString();
      }
      return decString;
    }
    console.log(divideBy2(10));//1010

3隊列 3.1隊列的創建

隊列是遵循FIFO(First In First Out,先進先出,也稱為先來先服務)原則的一組有序的項。隊列在尾部添加新元素,并從頂部移除元素。最新添加的元素必須排在隊列的末尾。隊列要實現的操作基本和棧一樣，只不過棧是FILO(先進后出)。

    function Queue(){
      this.items = [];
    }
    Queue.prototype = {
      constructor:Queue,
      enqueue:function(elements){
        this.items.push(elements);
      },
      dequeue:function(){
        return this.items.shift();
      },
      front:function(){
        return this.items[0];
      },
      isEmpty:function(){
        return this.items.length == 0;
      },
      size:function(){
        return this.items.length;
      },
      clear:function(){
        this.items = [];
      },
      print:function(){
        console.log(this.items.toString());
      }
    }

隊列的基本使用

    var queue = new Queue();
    console.log(queue.isEmpty());//true
    queue.enqueue("huang");
    queue.enqueue("cheng");
    console.log(queue.print());//huang,cheng
    console.log(queue.size());//2
    console.log(queue.isEmpty());//false
    queue.enqueue("du");
    console.log(queue.dequeue());//huang
    console.log(queue.print());//cheng,du

3.2 優先隊列

元素的添加和移除是基于優先級的。實現一個優先隊列,有兩種選項:設置優先級,然后在正確的位置添加元素;或者用入列操作添加元素,然后按照優先級移除它們。
我們在這里實現的優先隊列稱為最小優先隊列,因為優先級的值較小的元素被放置在隊列最前面(1代表更高的優先級)。最大優先隊列則與之相反,把優先級的值較大的元素放置在隊列最前面。

3.2.1 優先隊列的定義

我們在這里使用組合繼承的方式繼承自Queue隊列。

    function PriorityQueue(){
      Queue.call(this);
    };
    PriorityQueue.prototype = new Queue();
    PriorityQueue.prototype.constructer = PriorityQueue;
    PriorityQueue.prototype.enqueue = function(element,priority){
      function QueueElement(tempelement,temppriority){
        this.element = tempelement;
        this.priority = temppriority;
      }
      var queueElement = new QueueElement(element,priority);
      if(this.isEmpty()){
        this.items.push(queueElement);
      }else{
        var added = false;
        for(var i = 0; i < this.items.length;i++){
          if(this.items[i].priority > queueElement.priority){
            this.items.splice(i,0,queueElement);
            added = true;
            break;
          }
        }
        if(!added){
            this.items.push(queueElement);
        }
      }
      
    }
    //這個方法可以用Queue的默認實現
    PriorityQueue.prototype.print = function(){
      var result ="";
      for(var i = 0; i < this.items.length;i++){
        result += JSON.stringify(this.items[i]);
      }
      return result;
    }

3.2.1 優先隊列的基本使用

    var priorityQueue = new PriorityQueue();
    priorityQueue.enqueue("cheng", 2);
    priorityQueue.enqueue("du", 3);
    priorityQueue.enqueue("huang", 1);
    console.log(priorityQueue.print());//{"element":"huang","priority":1}{"element":"cheng","priority":2}{"element":"du","priority":3}
    console.log(priorityQueue.size());//3
    console.log(priorityQueue.dequeue());//{ element="huang",  priority=1}
    console.log(priorityQueue.size());//2

3鏈表

數組的大小是固定的,從數組的起點或中間插入或移除項的成本很高,因為需要移動元素(盡管我們已經學過的JavaScript的Array類方法可以幫我們做這些事,但背后的情況同樣是這樣)。鏈表存儲有序的元素集合,但不同于數組,鏈表中的元素在內存中并不是連續放置的。每個元素由一個存儲元素本身的節點和一個指向下一個元素的引用(也稱指針或鏈接)組成。

相對于傳統的數組,鏈表的一個好處在于,添加或移除元素的時候不需要移動其他元素。然而,鏈表需要使用指針,因此實現鏈表時需要額外注意。數組的另一個細節是可以直接訪問任何位置的任何元素,而要想訪問鏈表中間的一個元素,需要從起點(表頭)開始迭代列表直到找到所需的元素

3.1.1鏈表的創建

我們使用動態原型模式來創建一個鏈表。列表最后一個節點的下一個元素始終是null。

    function LinkedList(){
      function Node(element){
        this.element = element;
        this.next = null;
      }
      this.head = null;
      this.length = 0;
      //通過對一個方法append判斷就可以知道是否設置了prototype
      if((typeof this.append !== "function")&&(typeof this.append !== "string")){
        //添加元素
        LinkedList.prototype.append = function(element){
          var node = new Node(element);
          var current;
          if(this.head === null){
            this.head = node;
          }else{
            current = this.head;
            while(current.next !== null){
              current = current.next;
            }
            current.next = node;
          }
          this.length++;
        };
        //插入元素，成功true，失敗false
        LinkedList.prototype.insert = function(position,element){
          if(position > -1 && position < this.length){
            var current = this.head;
            var previous;
            var index = 0;
            var node = new Node(element);
            if(position == 0){
              node.next = current;
              this.head = node;
            }else{
              while(index++ < position){
                previous = current;
                current = current.next;
              }
              node.next = current;
              previous.next = node;
            }
            this.length++;
            return true;
          }else{
            return false;
          }
        };
        //根據位置刪除指定元素，成功 返回元素， 失敗 返回null
        LinkedList.prototype.removeAt = function(position){
          if(position > -1 && position < this.length){
            var current = this.head;
            var previous = null;
            var index = 0;
            if(position == 0){
              this.head = current.next;
            }else{
              while(index++ < position){
                previous = current;
                current = current.next;
              }
              previous.next = current.next;
            }
            this.length--;
            return current.element;
          }else{
            return null;
          }
        };
        //根據元素刪除指定元素，成功 返回元素， 失敗 返回null
        LinkedList.prototype.remove = function(element){
          var index = this.indexOf(element);
          return this.removeAt(index);
        };
        //返回給定元素的索引，如果沒有則返回-1
        LinkedList.prototype.indexOf = function(element){
          var current = this.head;
          var index = 0;
          while(current){
            if(current.element === element){
              return index;
            }
            index++;
            current = current.next;
          }
          return -1;
        };
        LinkedList.prototype.isEmpty = function(){
          return this.length === 0;
        };
        LinkedList.prototype.size = function(){
          return this.length;
        };
        LinkedList.prototype.toString = function(){
            var string = "";
            var current = this.head;
            while(current){
              string += current.element;
              current = current.next;
            }
            return string;
        };
        LinkedList.prototype.getHead = function(){
          return this.head;
        };
      }
    }

3.1.2鏈表的基本使用

    var linkedList = new LinkedList();
    console.log(linkedList.isEmpty());//true;
    linkedList.append("huang");
    linkedList.append("du")
    linkedList.insert(1,"cheng");
    console.log(linkedList.toString());//huangchengdu
    console.log(linkedList.indexOf("du"));//2
    console.log(linkedList.size());//3
    console.log(linkedList.removeAt(2));//du
    console.log(linkedList.toString());//huangcheng

3.2.1雙向鏈表的創建

鏈表有多種不同的類型,這一節介紹雙向鏈表。雙向鏈表和普通鏈表的區別在于,在鏈表中, 一個節點只有鏈向下一個節點的鏈接,而在雙向鏈表中,鏈接是雙向的:一個鏈向下一個元素, 另一個鏈向前一個元素。

雙向鏈表和鏈表的區別就是有一個tail屬性，所以必須重寫insert、append、removeAt方法。每個節點對應的Node也多了一個prev屬性。

   //寄生組合式繼承實現，詳見javascript高級程序設計第七章
   function inheritPrototype(subType, superType) {
       function object(o) {
           function F() {}
           F.prototype = o;
           return new F();
       }
       var prototype = object(superType.prototype);
       prototype.constructor = subType;
       subType.prototype = prototype;
   }
   function DoublyLinkedList() {
       function Node(element) {
           this.element = element;
           this.next = null;
           this.prev = null;
       }
       this.tail = null;
       LinkedList.call(this);
       //與LinkedList不同的方法自己實現。
       this.insert = function(position, element) {
           if (position > -1 && position <= this.length) {
               var node = new Node(element);
               var current = this.head;
               var previous;
               var index = 0;
               if (position === 0) {
                   if (!this.head) {
                       this.head = node;
                       this.tail = node;
                   } else {
                       node.next = current;
                       current.prev = node;
                       this.head = node;
                   }
               } else if (position == this.length) {
                   current = this.tail;
                   current.next = node;
                   node.prev = current;
                   this.tail = node;
               } else {
                   while (index++ < position) {
                       previous = current;
                       current = current.next;
                   }
                   previous.next = node;
                   node.next = current;
                   current.prev = node;
                   node.prev = previous;
               }
               this.length++;
               return true;
           } else {
               return false;
           }
       };
       this.append = function(element) {
           var node = new Node(element);
           var current;
           if (this.head === null) {
               this.head = node;
               this.tail = node;
           } else {
               current = this.head;
               while (current.next !== null) {
                   current = current.next;
               }
               current.next = node;
               node.prev = current;
               this.tail = node;
           }
           this.length++;
       };
       this.removeAt = function(position) {
           if (position > -1 && position < this.length) {
               var current = this.head;
               var previous;
               var index = 0;
               if (position === 0) {
                   this.head = current.next;
                   if (this.length === 1) {
                       this.tail = null;
                   } else {
                       this.head.prev = null;
                   }
               } else if (position === (this.length - 1)) {
                   current = this.tail;
                   this.tail = current.prev;
                   this.tail.next = null;
               } else {
                   while (index++ < position) {
                       previous = current;
                       current = current.next;
                   }
                   previous.next = current.next;
                   current.next.prev = previous;
               }
               this.length--;
               return current.element;
           } else {
               return false;
           }
       };
   }
   inheritPrototype(DoublyLinkedList, LinkedList);

3.2.2雙向鏈表的基本使用

    var doublyList = new DoublyLinkedList();
    console.log(doublyList.isEmpty()); //true;
    doublyList.append("huang");
    doublyList.append("du")
    doublyList.insert(1, "cheng");
    console.log(doublyList.toString()); //huangchengdu
    console.log(doublyList.indexOf("du")); //2
    console.log(doublyList.size()); //3
    console.log(doublyList.removeAt(2)); //du
    console.log(doublyList.toString()); //huangcheng

3.2.3 循環鏈表

循環鏈表可以像鏈表一樣只有單向引用,也可以像雙向鏈表一樣有雙向引用。循環鏈表和鏈表之間唯一的區別在于,最后一個元素指向下一個元素的指針(tail.next)不是引用null, 而是指向第一個元素(head)。雙向循環鏈表有指向head元素的tail.next,和指向tail元素的head.prev。

源碼地址

Javascript的數據結構與算法(一)源碼

GPU云服務器云服務器描述的數據結構與算法 javascript與js的區別 java與javascript的區別算法與數據結構

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

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

CSS技巧

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

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

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

zgbgx 2019-08-29 14:01 評論0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...

Jonathan Shieber 2019-08-29 12:33 評論0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...

SHERlocked93 2019-08-22 11:04 評論0 收藏0
Deep in JS - 收藏集 - 掘金

摘要：今天同學去面試，做了兩道面試題全部做錯了，發過來給道典型的面試題前端掘金在界中，開發人員的需求量一直居高不下。排序算法 -- JavaScript 標準參考教程（alpha） - 前端 - 掘金來自《JavaScript 標準參考教程（alpha）》，by 阮一峰目錄冒泡排序簡介算法實現選擇排序簡介算法實現 ... 圖例詳解那道 setTimeout 與循環閉包的經典面...

enali 2019-08-20 16:36 評論0 收藏0
學習JavaScript數據結構與算法（一）：棧與隊列

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

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