javascript数据结构与算法 --- 栈 vs 队列 vs 链表 vs 二叉树 vs 图

why_rookie 发布于2019-08-26 11:33 / 1075人阅读

摘要：数据结构前言随着的兴起将推向的一个前所未有的高度作为为建立高性能的服务端而创建的运行平台随着时间的推移和生态链的完善已经不再局部于服务端包括前端后端桌面正如在年提出的任何可以使用来编写的应用，最终会由编写虽然人们大多或多或少对笔者的文章有点

数据结构 前言

随着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;
    })()

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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