数据结构（一）

[L-small]

• 数据结构说明
• 二叉树
• 图
• 堆
• 链表
• 散列表

数据结构说明

• 数组：简单，但是大小固定，插入删除成本高
• 栈：可以保存环境、十进制转二进制、反转字符串
• 队列：按序执行
• 链表：插入删除成本低
• 集合：[值、值]的存储（不允许重复），存储唯一值、其实Set就是
• 字典：[键、值]映射，存储唯一值。查找快
• 散列表：同字典。查找快
• 树：查找快
• 堆：快速查找最大值和最小值

链表

class linkList {
  constructor() {
    this.count = 0;
    this.head = undefined;
  }

  add(node) {
    if (this.head) {
      let current = this.head
      while(!current.next) {
        current = current.next;
      }
      current.next = node;
    } else {
      this.head = node
    }
    this.count++;
  },

  addEle(value, index) {
    // todo 边界处理
    const pre = this.getIndex(index - 1)
    const current = this.getIndex(index)
    const node = new Node(val)
    pre.next = node;
    node.next = current
  }

  getIndex(index) {
    let current = this.head
    while(let i = 0; i < index; i++) {
      current = current.next
    }
    return current;
  }

  remove(index) {
    if (index > this.count) {
      return false;
    } else if (index === this.count) {
      const pre = this.getIndex(index - 1)
      pre.next = undefined
      this.count--;
    } else {
      const pre = this.getIndex(index - 1);
      const next = this.getIndex(index + 1);
      pre.next = current.next
      this.count--;
    }
  }
}

class Node {
  constructor(val) {
    this.value = val
    this.next = undefined
  }
}

反转链表

递归

function reverseList(node) {
  if (node.next === null) {
    return node
  } else {
    const nextNode = reverseList(node.next);
    nextNode.next = node;
    node.next = null;
    return node;
  }
}

散列表

function hashCode(key) {
  reuturn key % 37
}
建立了一个长度37的散列表

冲突解决方法：

• 分离链接
  有冲突的则以链表的形式不断向后添加
  
• 线性探查
  有冲突则找下一位是不是空，不断找下一位直到找到空。（删除一般是软删除，会保留位置。也可以删除后移动位置，消耗多）

递归

带记忆函数的递归

function fibona(n) {
  const memo = [0, 1]
  const test1 = (n) => {
    if (memo[n] !== undefined) return memo[n];
    return memo[n] = test1(n - 1) + test1(n - 2);
  }
  return test1
}

二叉树

class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

class Tree {
  constructor() {
    this.root = null
  }

  insert(val) {
    if (val === null) {
      this.root = new Node(val)
    } else {
      this.insertNode(this.root, val)
    }
  }

  insertNode(node, val) {
    if (node.val < val) {
      // node < val
      if (node.right === null) {
        node.right = new Node(val)
      } else {
        insertNode(node.right, val)
      }
    } else {
      if (node.left === null) {
        node.left = new Node(val)
      } else {
        insertNode(node.left, val)
      }
    }
  }

  inOrderTree(node, callback) {
    if (node !== null) {
      this.inOrderTrave(node.left, callback)
      callback(node.key)
      this.inOrderTrave(node.right, callback)
    }
  }

  preOrderTree(node, callback) {
    if (node !== null) {
      callback(node.key)
      this.preOrderTree(node.left, callback)
      this.preOrderTree(node.right, callback)
    }
  }

  lastOrderTree(node, callback) {
    if (node !== null) {
      this.lastOrderTree(node.left, callback)
      this.lastOrderTree(node.right, callback)
      callback(node.key)
    }
  }

  min() {
    return this.minNode(this.root)
  }

  minNode (node) {
    let current = node;
    while(current.left === null) {
      current = current.left
    }
    return current
  }

  max() {
    return this.maxNode(this.root)
  }

  maxNode(node) {
    let current = node;
    while(current.right === null) {
      current = current.right
    }
    return current
  }

  search(val) {
    this.searchNode(this.root, val)
  }

  searchNode(node, val) {
    if (val > node.val) {
      this.searchNode(node.right, val)
    } else if (val < node.val) {
      this.searchNode(node.left, val)
    } else {
      return node
    }
  }

  remove(val) {
    this.removeNode(this.root, val)
  }

  removeNode(node, val) {
    if (val > node.val) {
      // 当小于时候，递归右侧找
      node.right = this.removeNode(node.right, val)
      return node
    } else if (val < node.val) {
      node.left = this.removeNode(node.left, val)
      return node
    } else {
      if (node.left === null && node.right === null) {
        // 当是一个叶子节点时
        node = null
        return node
      }
      // 当一边为空时
      if (node.left === null) {
        node = node.left
        return node
      } else if (node.right === null) {
        node.right = node
        return node
      }
      // 左右都有子节点的时候，取右侧最小值替换当前值，并把右侧最小值原位置删除
      const rightMin = this.minNode(node.right)
      node.val = rightMin.val
      this.removeNode(node.right, rightMin.val)
      return node
    }
  }

  BFS(root) {
    if (!root) return [];
    let res = [];
    let queue = [root];
    while(queue.length) {
      let curr = [];
      let temp = [];
      while(queue.length) {
        let node = queue.pop()
        curr.push(node)
        if (node.left) temp.push(node.left);
        if (node.right) temp.push(node.right);
      }
      res.push(curr)
      queue = temp;
    }
    return res
  }
}

图

堆

class minHeap {
  constructor() {
    this.compareFn = (a, b) => {
      if (a === b) return 0
      return a < b ? -1 : 1
    }
    this.heap = []
  }

  getLeftIndex(index) {
    return 2 * index + 1
  }

  getRightIndex(index) {
    return 2 * index + 2
  }

  getParentIndex(index) {
    return Math.floor(index - 1 / 2)
  }

  insert(index) {
    this.heap.push(index)
    this.shiftUp(index);
  }

  放入最后一位，然后依次向上比较
  shiftUp(index) {
    let parentIndex = getParentIndex(index)
    while(index > 0 && this.compareFn(this.heap[index], this.heap[parentIndex]) > 1) {
      swap(this.heap, parentIndex, index)
      index = parentIndex;
      parentIndex = this.getParentIndex(index)
    }
  }

  exact(index) {
    this.heap.shift()
    this.shiftDown(0);
  }

  // 将最大的值放入0，然后依次比较下移，完成后就完事了
  shiftDown(index) {
    let element = index
    const left = this.getLeftIndex(index)
    const right = this.getRightIndex(index)
    const size = this.heap.length

    if (left < size && this.compareFn(this.heap[element], this.heap[left]) > 1) {
      element = left
    }
    if (right < size && this.compareFn(this.heap[element], this.heap[right]) > 1) {
      element = right
    }
    if (index !== element) {
      swap(this.heap, index, element)
      this.shiftDown(element)
    }
  }

  swap(arr, a, b) {
    const temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp
  }
}