数据结构

数据结构 队列&栈&链表&集合&hash表&树&图

队列 先进先出

  class Queue {
    constructor() {
      this.arr = [];
    }
    in(ele) {
      console.log(this.arr);
      this.arr.push(ele)
      return this.arr;
    }
    out() {
      this.arr.shift();
      console.log(this.arr);
      return this.arr;
    }
  }

  let queue = new Queue();
  queue.in(1)
  queue.in(2)
  queue.in(3)
  queue.in(4)
  queue.out()

栈 先进后出

  class Stack {
    constructor() {
      this.arr = [];
    }
    in(ele) {
      console.log(this.arr);
      this.arr.push(ele)
      return this.arr;
    }
    out() {
      this.arr.pop();
      console.log(this.arr);
      return this.arr;
    }
  }

  let stack = new Stack();
  stack.in(1)
  stack.in(2)
  stack.in(3)
  stack.in(4)
  stack.out()

链表 单向链表 双向链表 循环链表

作用: 不破坏原来的数据结构,实现操作数据

//单向链表

//链表对象:
class LinkList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  //向链表中添加元素
  append(name) {
    let node = new Node(name);
    if (!this.head) {
      //没有头的时候,添加的第一个就是head
      this.head = node;
    }
    else {
      //有头的时候,找到链表的最后一个元素
      //并且将最后一个元素的next指向新的node元素
      let index = 1;//位置0已经是head了
      let lastNode = this.head;//默认最后一个节点时head
      while (index < this.length) {
        lastNode = lastNode.next;
        index += 1;
      }
      lastNode.next = node;
    }
    this.length += 1;
  }

  //向链表中插入元素
  insert(startPostion, name) {
    let node = new Node(name);
    //找到startPostion的元素
    //找到startPostion的next
    //修改这两个元素的next指向
    if (!this.head) {
      this.head = node;
    } else {
      let index = 0;
      let startPostionNode = this.head;
      let startPostionNext = this.head.next;
      while (index < startPostion) {
        startPostionNode = startPostionNode.next;
        startPostionNext = startPostionNode.next;
      }
      startPostionNode.next = node;
      node.next = startPostionNext;
    }

    this.length += 1;
  }

  delete(name) {
    //找到name对应的Node节点
    //找到该节点的上一个节点
    //修改上个节点的next
    if (!this.head) {
      return;
    }
    let find = false;
    let parentNode = this.head;
    let sonNode = null;
    while (!find) {
      if (parentNode.next) {
        if (parentNode.next.name === name) {
          //找到了该元素的上一级
          //找自己的下级
          sonNode = parentNode.next.next;
          find = true;
        } else {
          parentNode = parentNode.next;
        }
      } else {
        //没找到
        parentNode = null;
        find = true;
      }
    }
    if (find && parentNode) {
      //找到了元素
      parentNode.next = sonNode;
    }
    this.length -= 1;
  }
}

//节点对象
class Node {
  constructor(name) {
    this.name = name;
    this.next = null;
  }
}

let linkList = new LinkList();
linkList.append('zhangsan');
linkList.append('lisi');
linkList.append('wangwu');
linkList.insert(0, 'zhangsi');
linkList.delete('wangwu')
console.log(JSON.stringify(linkList));

集合 没有重复项

  class Set {
    constructor() {
      this.set = {};
    }

    add(ele) {
      if (!this.set.hasOwnProperty(ele)) {
        this.set[ele] = ele;
      }
      console.log(this.set);
      return this.set;
    }
  }

  let set = new Set();
  set.add(1)
  set.add(2)
  set.add(1)

hash表 就是 ES6的Map

树 二叉树 特点 数据不重复,小的放左边 大的放右边

//二叉树
class TwoTree {
  constructor() {
    this.root = null;
    this.level = 0;
  }
  addValue(value) {
    let newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
    }
    else {
      //如果有根节点
      let find = false;
      let currentNode = this.root;
      while (!find) {
        let left = currentNode.left;
        let right = currentNode.right;
        if (value < currentNode.val && !left) {
          //如果要放左边,并且左边是空值,则说明找到了对象
          currentNode.left = newNode;
          find = true;
        }
        else if (value > currentNode.val && !right) {
          currentNode.right = newNode;
          find = true;
        } else {
          if (value < currentNode.val) {
            currentNode = currentNode.left;
          } else if (value > currentNode.val) {
            currentNode = currentNode.right;
          }
        }
      }
    }
    console.log(JSON.stringify(this));
    
  }
}

//节点
class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

let twoTree = new TwoTree();
twoTree.addValue(100);
twoTree.addValue(60);
twoTree.addValue(150);
twoTree.addValue(50);
twoTree.addValue(70);
twoTree.addValue(140);
twoTree.addValue(160);

图 节点和节点的关系(待补充)