javascript數據結構與算法 --- 棧 vs 隊列 vs 鏈表 vs 二叉樹 vs 圖

why_rookie 發布于2019-08-26 11:33 / 1076人閱讀

摘要：數據結構前言隨著的興起將推向的一個前所未有的高度作為為建立高性能的服務端而創建的運行平臺隨著時間的推移和生態鏈的完善已經不再局部于服務端包括前端后端桌面正如在年提出的任何可以使用來編寫的應用，最終會由編寫雖然人們大多或多或少對筆者的文章有點

數據結構 前言

隨著node的興起, 將javascript推向的一個前所未有的高度, node作為為建立高性能的服務端而創建的js運行平臺隨著時間的推移和生態鏈的完善已經不再局部于服務端,包括前端,后端,桌面......
正如Jeff Atwood在2007年提出的：任何可以使用JavaScript來編寫的應用，最終會由JavaScript編寫, 雖然人們大多或多或少對筆者的文章有點斷章取義, 但無可變非的是javascript正在大行其道 ^_^,
但正如偉大的js之父親布蘭登.艾奇--(每每想起他和冰與火之歌中史塔克家族什么關系哈哈)所說js是C語言和Self語言一夜情的產物, 他的生命力與發展遠遠超出作者的預期, 間接導致設計之初并沒有過多的考慮對數據結構的支持,
但es規范制定者似乎已經察覺到了這一點, 于是最es6標準增加了set集合和map集合,有興趣的可以查閱最新的es標準,這里推薦阮一峰的es6入門筆者認為是一部不錯的教材(^_^筆者可不是做廣告),有興趣的可以查閱,下面給出連接

es6 阮一峰http://es6.ruanyifeng.com

二維數組

    Array.matrix = function(numrows, numcols, initial) {
      let arr = [];
      for (let i = 0; i < numrows; ++i) {
        let columns = [];
        for (let j = 0; j < numcols; ++j) {
          columns[j] = initial;
        }
        arr[i] = columns;
      }
      return arr;
    }

棧

    let Stack = (function(){
      function Stack() {
        this.dataStore = [];
        this.top = 0;
      }
      Stack.prototype.push = function(element) {
        this.dataStore[this.top++] = element;
      }
      Stack.prototype.peek = function() {
        return this.dataStore[this.top-1];
      }
      Stack.prototype.pop = function() {
        return this.dataStore[--this.top];
      }
      Stack.prototype.clear = function() {
        this.top = 0;
      }
      Stack.prototype.length = function() {
        return this.top;
      }
      return Stack;
    })();

隊列

    let Queue = (function () {
      function Queue() {
        this.dataStore = [];
      }
      Queue.prototype.enqueue = function(element) {
        this.dataStore.push(element);
      }
      Queue.prototype.dequeue = function() {
        return this.dataStore.shift();
      }
      Queue.prototype.front = function() {
        return this.dataStore[0];
      }
      Queue.prototype.back = function() {
        return this.dataStore[this.dataStore.length-1];
      }
      Queue.prototype.toString = function() {
        var retStr = "";
        for (var i = 0; i < this.dataStore.length; ++i) {
          retStr += this.dataStore[i] + "
";
        }
        return retStr;
      }
      Queue.prototype.empty = function() {
        if (this.dataStore.length == 0) {
          return true;
        } else {
          return false;
        }
      }
      return Queue;
    })()

優先隊列

    let PriQueue = (function() {
      function Ele(value, code) {
        this.value = value;
        this.code = code;
      }
      function PriQueue() {
        this.dataStore = [];
      }
      PriQueue.prototype.enqueue = function(element) {
        this.dataStore.push(element);
      }
      PriQueue.prototype.dequeue = function() {
        var priority = this.dataStore[0].code;
        for (var i = 1; i < this.dataStore.length; ++i) {
          if (this.dataStore[i].code < priority) {
            priority = i;
          }
        }
        return this.dataStore.splice(priority,1);
      }
      PriQueue.prototype.front = function() {
        return this.dataStore[0];
      }
      PriQueue.prototype.back = function() {
        return this.dataStore[this.dataStore.length-1];
      }
      PriQueue.prototype.toString = function() {
        var retStr = "";
        for (var i = 0; i < this.dataStore.length; ++i) {
          retStr += this.dataStore[i].name + " code: " + this.dataStore[i].code + "
";
        }
        return retStr;
      }
      PriQueue.prototype.empty = function() {
        if (this.dataStore.length == 0) {
          return true;
        } else {
          return false;
        }
      }
      return PriQueue;
    })()

單向鏈表

    let LList = (function() {
      function Node(element) {
        this.element = element;
        this.next = null;
      }
    
      function LList() {
        this.head = new Node("head");
        this.foot = new Node("foot");
        this.head.next = this.foot;
      }
      LList.prototype.remove = function(item) {
        var prevNode = this.findPrevious(item);
        if (!(prevNode.next == null)) {
          prevNode.next = prevNode.next.next;
        }
      }
      LList.prototype.findPrevious = function(item) {
        var currNode = this.head;
        while ((currNode.next !== null) && (currNode.next.element != item)) {
          currNode = currNode.next;
          if (currNode.next === null) {
            currNode =null;
            break;
          }
        }
        return currNode;
      }
      LList.prototype.display = function() {
        var currNode = this.head;
        console.log(currNode.element);
        while (!(currNode.next == null)) {
          currNode = currNode.next;
          console.log(currNode.element);
        }
      }
      LList.prototype.find = function(item) {
        var currNode = this.head;
        while (currNode.element != item) {
          currNode = currNode.next;
          if (currNode === null) {
            break;
          }
        }
        return currNode;
      }
      LList.prototype.insert = function(newElement, item) {
        var newNode = new Node(newElement);
        var current = this.find(item);
        newNode.next = current.next;
        current.next = newNode;
      }
      return LList;
    })()

雙向鏈表

    let DLList = (function () {
      function Node(element) {
        this.element = element;
        this.next = null;
        this.previous = null;
      }
      function DLList() {
        this.head = new Node("head");
        this.foot = new Node("foot");
        this.head.next = this.foot;
        this.foot.previous = this.head;
      }
      DLList.prototype.find = function(item) {
        var currNode = this.head;
        while (currNode.element != item) {
          currNode = currNode.next;
          if (currNode === null) {
            break;
          }
        }
        return currNode;
      }
      DLList.prototype.insert = function(newElement, item) {
        var newNode = new Node(newElement);
        var current = this.find(item);
        newNode.next = current.next;
        newNode.previous = current;
        current.next.previous = newNode;
        current.next = newNode;
      }
      DLList.prototype.remove = function(item) {
        var currNode = this.find(item);
        if (!(currNode.next == null)) {
          currNode.previous.next = currNode.next;
          currNode.next.previous = currNode.previous;
          currNode.next = null;
          currNode.previous = null;
        }
      }
      DLList.prototype.display = function() {
        var currNode = this.head;
        console.log(currNode.element);
        while (currNode.next !== null) {
          currNode = currNode.next;
          console.log(currNode.element);
        }
      }
      return DLList;
    })()

樹

    let BST = (function () {
      let Node = (function () {
        function Node(data, left, right) {
          this.data = data;
          this.left = left;
          this.right = right;
        }
        Node.prototype.show = function () {
          return this.data;
        }
        return Node;
      })()
    
      function BST() {
        this.root = null;
      }
      BST.prototype.insert = function(data) {
        var n = new Node(data, null, null);
        if (this.root == null) {
          this.root = n;
        }
        else {
          var current = this.root;
          var parent;
          while (true) {
            parent = current;
            if (data < current.data) {
              current = current.left;
              if (current == null) {
                parent.left = n;
                break;
              }
            }
            else {
              current = current.right;
              if (current == null) {
                parent.right = n;
                break;
              }
            }
          }
        }
      }
      BST.prototype.inOrder = function(node) {
        if (!(node === null)) {
          this.inOrder(node.left);
          console.log(node.show() + " ");
          this.inOrder(node.right);
        }
      }
      BST.prototype.preOrder = function(node) {
        if (!(node === null)) {
          console.log(node.show() + " ");
          this.preOrder(node.left);
          this.preOrder(node.right);
        }
      }
      BST.prototype.postOrder = function(node) {
        if (!(node === null)) {
          this.postOrder(node.left);
          this.postOrder(node.right);
          console.log(node.show() + " ");
        }
      }
      BST.prototype.getMin = function() {
        var current = this.root;
        while (!(current.left == null)) {
          current = current.left;
        }
        return current.data;
      }
      BST.prototype.getMax = function() {
        var current = this.root;
        while (!(current.right == null)) {
          current = current.right;
        }
        return current.data;
      }
      BST.prototype.find = function(data) {
        var current = this.root;
        while (current != null) {
          if (current.data == data) {
            return current;
          }
          else if (data < current.data) {
            current = current.left;
          }
          else {
            current = current.right;
          }
        }
        return null;
      }
      BST.prototype.remove = function(data) {
        root = this.removeNode(this.root, data);
      }
      BST.prototype.removeNode = function(node, data) {
        if (node == null) {
          return null;
        }
        if (data == node.data) {
          // 沒有子節點的節點
          if (node.left == null && node.right == null) {
            return null;
          }
          // 沒有左子節點的節點
          if (node.left == null) {
            return node.right;
          }
          // 沒有右子節點的節點
          if (node.right == null) {
            return node.left;
          }
          // 有兩個子節點的節點
          var tempNode = this.getSmallest(node.right);
          node.data = tempNode.data;
          node.right = this.removeNode(node.right, tempNode.data);
          return node;
        }
        else if (data < node.data) {
          node.left = this.removeNode(node.left, data);
          return node;
        }
        else {
          node.right = this.removeNode(node.right, data);
          return node;
        }
      }
      BST.prototype.getSmallest = function(node) {
        if (node.left == null) {
          return node;
        } else {
          return this.getSmallest(node.left);
        }
     }
    
      return BST;
    })()

圖

    let Graph = (function() {
      function Graph(v) {
        this.vertices = v;
        this.vertexList = [];
        this.edges = 0;
        this.adj = [];
        for (var i = 0; i < this.vertices; ++i) {
          this.adj[i] = [];
          //  this.adj[i].push("");
        }
        this.marked = [];
        for (var i = 0; i < this.vertices; ++i) {
          this.marked[i] = false;
        }
        this.edgeTo = [];
      }
      Graph.prototype.addEdge = function (v, w) {
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
      }
      Graph.prototype.showGraph = function() {
        for (var i = 0; i < this.vertices; ++i) {
          let st = i + " -> " ;
          for (var j = 0; j < this.vertices; ++j ) {
            if (this.adj[i][j] != undefined) {
              st += this.adj[i][j] + " ";
            }
          }
          console.log(st);
        }
      }
      Graph.prototype.dfs = function(v) {
        this.marked[v] = true;
        if (this.adj[v] != undefined) { 
          console.log("Visited vertex: " + v);
        }
        for (const w of this.adj[v]) {
          if (!this.marked[w]) {
            this.dfs(w);
          }
        }
      }
      Graph.prototype.bfs = function(s) {
        var queue = [];
        this.marked[s] = true;
        queue.push(s); // 添加到隊尾
        while (queue.length > 0) {
          var v = queue.shift(); // 從隊首移除
          if (v !== undefined) {
            console.log("Visisted vertex: " + v);
          }
          for (var w of this.adj[v]) {
            if (!this.marked[w]) {
              this.edgeTo[w] = v;
              this.marked[w] = true;
              queue.push(w);
            }
          }
        }
        console.log(this.edgeTo);
      }
      Graph.prototype.hasPathTo = function(s, v) {
        this.bfs(s)
        return this.marked[v];
      }
      Graph.prototype.pathTo = function(s, v) {
        var source = s;
        if (!this.hasPathTo(s, v)) {
          return undefined;
        }
        var path = [];
        for (var i = v; i != source; i = this.edgeTo[i]) {
          path.unshift(i);
        }
        path.unshift(source);
        return path;
      }
      Graph.prototype.topSort = function() {
        var stack = [];
        var visited = [];
        for (var i = 0; i < this.vertices; i++) {
          visited[i] = false;
        }
        for (var i = 0; i < this.vertices; i++) {
          if (visited[i] == false) {
            this.topSortHelper(i, visited, stack);
          }
        }
        for (var i = 0; i < stack.length; i++) {
          if (stack[i] != undefined && stack[i] != false) {
            console.log(this.vertexList[stack[i]]);
          } 
        }
      }
      Graph.prototype.topSortHelper = function(v, visited, stack) {
        visited[v] = true; 
        for (var w in this.adj[v]) {
          if (!visited[w]) {
            this.topSortHelper(visited[w], visited, stack);
          }
        }
        stack.push(v);
      }
      return Graph;
    })()

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

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

編程面試的10大算法概念匯總

摘要：滿二叉樹除葉子節點以為的每個節點都有兩個孩子。完全二叉樹可以看成是可以有若干額外向左靠的葉子節點的完美二叉樹。以下是在編程面試中排名前10的算法相關的概念，我會通過一些簡單的例子來闡述這些概念。由于完全掌握這些概念需要更多的努力，因此這份列表只是作為一個介紹。本文將從Java的角度看問題，包含下面的這些概念：字符串鏈表樹圖排序遞歸 vs. 迭代動態規劃位操作概率...

shusen 2019-08-14 11:34 評論0 收藏0
一文掌握關于Java數據結構所有知識點（歡迎一起完善）

摘要：是棧，它繼承于。滿二叉樹除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。沒有鍵值相等的節點。這是數據庫選用樹的最主要原因。在我們學習Java的時候，很多人會面臨我不知道繼續學什么或者面試會問什么的尷尬情況（我本人之前就很迷茫）。所以，我決定通過這個開源平臺來幫助一些有需要的人，通過下面的內容，你會掌握系統的Java學習以及面試的相關知識。本來是想通過Gitbook的...

keithxiaoy 2019-08-15 15:54 評論0 收藏0
基礎數據結構和算法概念

摘要：數據結構程序數據結構算法數據結構基本概念數據的邏輯結構反映數據元素之間的關系的數據元素集合的表示。這兩部分信息組成數據元素的存儲映象，稱為結點。本文涉及更多的是概念，代碼部分請參考之前寫過的 2 篇博客基于 Javascript 的排序算法基于 javascript 的基本數據結構和查找算法本文主要是基礎的數據結構和算法概念，可能部分地方會涉及更高級的算法和算法，具體內容以...

fsmStudy 2019-08-23 11:52 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

zsirfs 2019-08-23 15:33 評論0 收藏0