JavaScript 中的数据结构

Run

每个js文件需要命名为xxx.mjs

node --experimental-modules ./demo.mjs

栈

栈是一种遵从先进后出 (LIFO) 原则的有序集合；类似于一叠书，想要拿到最下面的一本，必须移开上面的全部。

class Stack{
  constructor () {
    this.stacks = [];
  }
  push (element) {
    this.stacks.push(element);
  }
  pop () {
    return this.stacks.pop();
  }
  get peek () {
    return this.stacks[this.stacks.length -1];
  }
  get isEmpty () {
    return !this.stacks.length
  }
  get size () {
    return this.stacks.length
  }
  clear () {
    this.stacks = [];
  }
  print () {
    return this.stacks.toString()
  }
};

const stack = new Stack();
stack.push(1);
console.log(stack.isEmpty);
console.log(stack.print());

队列

与栈相反，队列是一种遵循先进先出 (FIFO / First In First Out) 原则的一组有序的项；队列在尾部添加元素，在头部移除元素，新添加的元素必须在队列的尾部。

普通队列
用javascript实现一个简单队列

class Queen {
  constructor (queens) {
    this.queens = queens || [];
  }
  enquene (element) {
    this.queens.push(element);
  }
  dequeue () {
    return this.queens.shift();
  }
  front () {
    return this.queens[0]
  }
  clear () {
    this.queens = [];
  }
  get size () {
    return this.queens.length;
  }
  get isEmpty () {
    return !this.queens.length;
  }
  print () {
    return this.queens.toString();
  }
};

const quene = new Queen();
quene.enquene(1);
console.log(quene.size);
console.log(quene.isEmpty);
console.log(quene.print());

export default Queen;

优先队列
用javascript实现一个具有优先性质的队列

import Queen from './queen.mjs';

class PriorityQueue extends Queen {
  constructor () {
    super();
  }
  enquene (element, priority) {
    const queueElement = { element, priority };
    if (this.isEmpty) {
      this.queens.push(queueElement);
    } else {
      const preIndex = this.queens.findIndex((item) => {
        queueElement.priority < item.priority;
      });
      if (preIndex === -1) {
        this.queens.splice(preIndex, 0, queueElement);
      } else {
        this.queens.push(queueElement);
      }
    }
  }
};

const priorityQueue = new PriorityQueue();
priorityQueue.enquene('name', 1);
priorityQueue.enquene('age', 2);

console.log(priorityQueue.front());

循环队列

import Queen from './queen.mjs';

class LoopQueen extends Queen {
  constructor (queens) {
    super(queens);
  }
  getIndex (index) {
    const length = this.queens.length;
    return index >= length ? (index % length) : index;
  }
  find (index) {
    return !this.isEmpty ? this.queens[this.getIndex(index)] : null;
  }
};

const loopQueen = new LoopQueen();
loopQueen.enquene(5);
loopQueen.enquene(6);
loopQueen.enquene(7);
console.log(loopQueen.find(3));
console.log(loopQueen.size);

链表

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。

单向链表

class Node {
  constructor (element) {
    this.element = element;
    this.next = null;
  }
};
class SingleList {
  constructor () {
    this.head = null;
    this.length = 0;
  }
  append (element) {
    const node = new Node(element);
    let current = null;
    if (this.head === null) {
      this.head = node;
    } else {
      current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.length ++;
  }
  insert (position, element) {
    if (position >= 0 && position <= this.length -1) {
      const node = new Node(element);
      let current = this.head;
      let previous = null;
      let index = 0;
      if (position === 0) {
        node.next = this.head;
        this.head = node;
      } else {
        while (index ++ < position) {
          previous = current;
          current = current.next;
        }
        node.next = current;
        previous.next = node;
      }
      this.length ++;
      return true;
    }
    return false;
  }
  removeAt (position) {
    if (position > -1 && position < this.length) {
      let current = this.head;
      let previous = null;
      let index = -1;
      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;
    }
    return null;
  }
  findIndex (element) {
    let current = this.head;
    let index = -1;
    while (current) {
      if (element === current.element) {
        return index + 1;
      }
      index ++;
      current = current.next;
    }
    return -1;
  }
  remove (element) {
    const index = this.findIndex(element);
    return this.removeAt(index);
  }
  get size () {
    return this.length;
  }
  toString () {
    let current = this.head;
    let string = '';
    while (current) {
      string += current.element;
      current = current.next;
    }
    return string;
  }
};
// need use index 
const singleList = new SingleList();
singleList.append(1);
singleList.append(2);
singleList.append(3);
console.log(singleList.findIndex(3));
console.log(singleList.toString());

双向链表

class Node {
  constructor (element) {
    this.element = this.element;
    this.prev = null;
    this.next = null;
  }
};

class DoubleList {
  constructor () {
    this.head = null; 
    this.tail = null;
    this.length = 0
  }
  insert (element, position) {
    if (position >= 0 && position <= this.length) {
      const node = new Node();
      let current = this.head;
      let previous = null;
      let index = 0;

      if (position === 0) {
        if (this.head === null) {
          this.head = node;
          this.tail = node;
        } else {
          node.next = current;
          this.head = node;
          current.prev = 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;
        }
        node.next = current;
        previous.next = node
        current.prev = node
        node.prev = previous
      }
      this.length ++;
      return true;
    }
    return false;
  }
};

const doubleList = new DoubleList();
doubleList.insert(0, 1);

/**
 * @class SingleList // 单向链表： A (head) -> B -> C -> D
 *
 * @method append append E 节点，只需要把D的next指向E，E默认的next是null
 * @method insert insert E 节点，需要从头开始遍历，next是遍历推动者（需要找到index位置的前后两个节点），只要把前置位节点的next设置为节点E，节点E的next设置为后置位节点，且需要维护head的状态
 * 
 * @class DoubleList // 双向链表： A (head) <- -> B <- -> C <- -> D (tail)
 * 
 * @method insert insert E 节点，需要从头开始遍历，next是遍历推动者（需要找到index位置的前后两个节点），只要把前置位节点的next设置为E，E的prev设置为前置位节点，E的next设置为后置位节点，E的后置位节点的prev为前置位节点，且需要维护head和tail的状态
 * 
 * @class CirvcleList // 单向循环链表:     A (head) -> B -> C -> D (tail) -> A
 * 
 * @method insert insert E 节点，需要从head开始遍历, next是遍历推动者（需要找到index位置的前后两个节点），只要把前置位节点的next设置为E，E的next设置为后置位节点，需要考虑next后如果是head的情况，且需要维护head和tail的状态
 */

循环链表

import Queen from './queen.mjs';

class LoopQueen extends Queen {
  constructor (queens) {
    super(queens);
  }
  getIndex (index) {
    const length = this.queens.length;
    return index >= length ? (index % length) : index;
  }
  find (index) {
    return !this.isEmpty ? this.queens[this.getIndex(index)] : null;
  }
};

const loopQueen = new LoopQueen();
loopQueen.enquene(5);
loopQueen.enquene(6);
loopQueen.enquene(7);
console.log(loopQueen.find(3));
console.log(loopQueen.size);

集合

Set集合

集合是由一组无序且唯一（不能重复）的项组成的，是以 { value: value }的形式存储数据。

class Set {
  constructor () {
    this.items = {}
  }

  has (value) {
    return this.items.hasOwnProperty(value)
  }

  add (value) {
    if (!this.has(value)) {
      this.items[value] = value
      return true
    }     
    return false
  }

  remove (value) {
    if (this.has(value)) {
      delete this.items[value]
      return true
    }
    return false
  }

  get size() {
    return Object.keys(this.items).length
  }

  get values() {
    return Object.keys(this.items)
  }
};

const set = new Set();

set.add(1);
console.log(set.values);
console.log(set.has(1));
console.log(set.size);

/**
 * @class Set 集合是以 { value: value }的形式存储数据
 * @class Dictionary 字典是以{ key: value }的形式存储数据 
 */

字典

Dictionary字典

以 [键，值] 对为数据形态的数据结构，其中键名用来查询特定元素，类似于 Javascript 中的Object。

class Dictionary {
  constructor () {
    this.items = {}
  }

  set (key, value) {
    this.items[key] = value
  }

  get (key) {
    return this.items[key]
  }

  remove (key) {
    delete this.items[key]
  }

  get keys () {
    return Object.keys(this.items)
  }

  get values() {
    return Object.values(this.items)
  }
};

const dictionary = new Dictionary()
dictionary.set('zhangsan', 'zhangsan@163.com')
dictionary.set('lisi', 'lisi@163.com')
dictionary.set('wangwu', 'wangwu@163.com')

console.log(dictionary);
console.log(dictionary.keys);
console.log(dictionary.values);
console.log(dictionary.items);

散列（hash）

HashTable 哈希

根据关键码值（Key value）直接进行访问的数据结构；它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度；这个映射函数叫做散列函数，存放记录的数组叫做散列表。

class HashTable {
  constructor() {
    this.table = [];
  }
  static loseloseHashCode(key) {
    let hash = 0;
    for (let codePoint of key) {
      hash += codePoint.charCodeAt();
    }
    return hash % 37;
  }
  static djb2HashCode(key) { // 使用djb2 函数后，散列函数将不再会有冲突
    let hash = 5381
    for (let codePoint of key) {
      hash = hash * 33 + codePoint.charCodeAt();
    }
    return hash % 1013
  }
  put(key, value) {
    const position = HashTable.loseloseHashCode(key);
    this.table[position] = value;
  }

  get(key) {
    return this.table[HashTable.loseloseHashCode(key)];
  }

  remove(key) {
    this.table[HashTable.loseloseHashCode(key)] = undefined;
  }
};

const hash = new HashTable()
hash.put('Surmon', 'surmon.me@email.com');
hash.put('John', 'johnsnow@email.com');
hash.put('Tyrion', 'tyrion@email.com');

树

Tree 树

由 n（n>=1）个有限节点组成一个具有层次关系的集合；把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的，基本呈一对多关系，树也可以看做是图的特殊形式。

class Node {
  constructor (key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree  {
  constructor () {
    this.root = null;
  }
  insert (key) {
    const newNode = new Node(key);
    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }
  insertNode (parentNode, newNode) {
    if (newNode.key <  parentNode.key) {
      if (parentNode.left === null) {
        parentNode.left = newNode;
      } else {
        this.insertNode(parentNode.left, newNode);
      }
    } else {
      if (parentNode.right === null) {
        parentNode.right = newNode
      } else {
        this.insertNode(parentNode.right, newNode);
      }
    }
  }
  inOrderTraverse (callback) { // 中序遍历(是对树进行遍历的一种排序操作)
    const inOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        inOrderTraverseNode(node.left, callback);
        callback(node.key);
        inOrderTraverseNode(node.right, callback);
      }
    };
    inOrderTraverseNode(this.root, callback)
  }
  preOrderTraverse(callback) { // 先序遍历(优先于后代节点的顺序访问每个节点)
    const preOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        callback(node.key);
        preOrderTraverseNode(node.left, callback);
        preOrderTraverseNode(node.right, callback);
      }
    }
    preOrderTraverseNode(this.root, callback);
  }
  postOrderTraverse(callback) { // 后序遍历(优先访问后代节点，再访问自身，应用场景如统计folder的占用空间大小)
    const postOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        postOrderTraverseNode(node.left, callback);
        postOrderTraverseNode(node.right, callback);
        callback(node.key);
      }
    }
    postOrderTraverseNode(this.root, callback);
  }
  search (key) {
    const searchNode = (node, key) => {
      if (node === null) return false;
      if (node.key === key) return node;
      return searchNode((node.key > key) ? node.left : node.right, key);
    };
    return searchNode(this.root, key);
  }
  min (key) { 
    let currentNode = null;
    if (key) {
      currentNode = this.search(key);
    }
    const minNode = (node) => {
      return node ? (node.left ? minNode(node.left) : node) : null;
    };
    return minNode(currentNode || this.root);
  }
  max (key) {
    let currentNode = null;
    if (key) {
      currentNode = this.search(key);
    }
    const minNode = (node) => {
      return node ? (node.right ? minNode(node.right) : node) : null;
    };
    return minNode(currentNode || this.root);
  }
};

const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(9);
tree.insert(11);
tree.insert(8);
tree.insert(7);
//tree.inOrderTraverse(value => { console.log(value) });
//tree.preOrderTraverse(value => { console.log(value) });
//tree.postOrderTraverse(value => { console.log(value) });
//console.log(tree.search(8));
//console.log(tree.min());
//console.log(tree.max());

图

Graph 图

图是网络结构的抽象模型；图是一组由边连接的节点（顶点）；任何二元关系都可以用图来表示，常见的比如：道路图、关系图，呈多对多关系。

import Dictionary from './dictionary.mjs';
class Graph {
  constructor() {
    this.vertices = [];
    this.adjList = new Dictionary(); // 相邻边的集合设置为字典结构
  }
  addVertex(v) {
    this.vertices.push(v);
    this.adjList.set(v, []);
  }
  addEdge(v, w) {
    this.adjList.get(v).push(w);
    this.adjList.get(w).push(v);
  }
  toString() {
    return this.vertices.reduce((r, v, i) => {
        return this.adjList.get(v).reduce((r, w, i) => {
            return r + `${w} `;
        }, `${r}\n${v} => `);
    }, '');
  }
  bfs (vertice, callback) {  // 广度优先搜索算法 （Breadth-First Search，BFS） 
    const read = [];
    const pending = [vertice || this.vertices[0]];
    const adjList = this.adjList;
    const readVertices = (vertices) => {
      vertices.forEach(key => {
        read.push(key);
        pending.shift();
        adjList.get(key).forEach(v => {
          if (!pending.includes(v) && !read.includes(v)) {
            pending.push(v);
          }
        });
        if (callback) callback(key);
        if (pending.length > 0) readVertices(pending);
      });
    };
    readVertices(pending);
  }
  bfs_input_dis_pre (vertice, callback) {
    const read = [];
    const pending = [vertice || this.vertices[0]];
    const distance = [];
    const predecessors = [];
    const adjList = this.adjList;
    const readVertices = (vertices) => {
      vertices.forEach(key => {
        read.push(key);
        pending.shift();
        distance[key] = distance[key] || 0;
        predecessors[key] = predecessors[key] || null;
        adjList.get(key).forEach(k => {
          if (!pending.includes(k) && !read.includes(k)) {
            pending.push(k);
            distance[k] = distance[key] + 1;
            predecessors[k] = key;
          }
        });
        if (callback) callback(key);
        if (pending.length > 0) readVertices(pending);
      });
    };
    readVertices(pending);
    return { distance, predecessors }
  }
  dfs(callback) {  // 深度优先搜索（Depth-First Search，DFS) 区分于广度优先搜索，不需要指定一个源顶点,核心判断条件是所有顶点是否已读
    const read = [];
    const adjList = this.adjList;
    const readVertices = (vertices) => {
      vertices.forEach(key => {
        if (read.includes(key)) return;
        read.push(key);
        if (callback) callback(key);
        if (read.length !== this.vertices.length) {
          readVertices(adjList.get(key));
        }
      });
    };
    readVertices(adjList.keys);
  }
  distance(fromVertex) {
    const vertices = this.vertices;
    const { distances, predecessors } = this.bfs2(fromVertex);
    vertices.forEach(toVertex => {
      if (!!distances[toVertex]) {
        let preVertex = predecessors[toVertex];
        let slug = '';
        while (fromVertex !== preVertex) {
          slug = `${preVertex} - ${slug}`;
          preVertex = predecessors[preVertex];
        }
        slug = `${fromVertex} - ${slug}${toVertex}`;
      }
    })
  }
  dfs_explore(callback) {
    let readTimer = 0;
    const read = [];
    const readTimes = [];
    const finishedTimes = [];
    const predecessors = [];
    const adjList = this.adjList;
    const readVertices = (vertices, predecessor) => {
      vertices.forEach(key => {
        readTimer++;
        if (adjList.get(key).every(v => read.includes(v)) && !finishedTimes[key]) {
            finishedTimes[key] = readTimer;
        }
        if (read.includes(key)) return false;
        readTimes[key] = readTimer;
        read.push(key);
        if (callback) callback(key);
        predecessors[key] = predecessors[key] || predecessor || null;
        if (read.length !== this.vertices.length) {
            readVertices(adjList.get(key), key);
        }
      })
    }
    readVertices(adjList.keys);
    return { readTimes, finishedTimes, predecessors };
  }
}

const graph = new Graph();
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'].forEach(n => 
  graph.addVertex(n)
);
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');
//graph.bfs(graph.vertices[0], (v) => {console.log('Visited vertex: ' + v)});
//console.log(graph.bfs_input_dis_pre(graph.vertices[0]));
//graph.dfs((v) => {console.log('Visited vertex: ' + v)});
console.log(graph.dfs_explore());