一只小白的数据结构与算法之路

算法概述

• 算法 algorithm 古老的概念，最早来自数学领域
• 计算机科学领域的算法，本质是一系列程序指令，用于解决特定的运算和逻辑问题。

5大特性

1. 有穷性：算法必须能执行有限个步骤后终止
2. 确切性：每一步必须有确切的定义
3. 输入项：有0个或多个输入项
4. 输出项：有一个或多个输出
5. 可行性（有效性）：算法内任何计算步骤都是可以分解成基本的可执行的操作步骤，每个步骤都可以在有限时间内完成

数据结构

• 数据结构是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。
• 包含数组、链表这样的线性数据结构，也包含树、图这样的复杂数据结构。

数组（Array）

适合读多写少的场景,最简单的内存数据结构

• 有限个相同类型变量组成的有序集
• 内存中顺序存储，可实现逻辑上顺序列表 （查找只需要计算位置便可轻松得到）

js中总有幺蛾子

• Js内存任何类型的且大小可动态调整
• Js的数组是依靠链表（或字典）实现的，存储在堆中，所以底层查找的时候需要从数组第一位开始遍历查找
• 最新的js，会为同种数据类型的数组分配连续空间了。
• 所以JS写代码的时候尽量保证数组内数据类型相同。
• ArrayBuffer 存储在栈内 不可操作，只能通过类型数组Int8Array， 或dataview操作

数组操作

• 增删改查
  • push:最后一行增加，
  • unshift:开头增加
  • pop:移除最后一位
  • shift:删除第一个
  • splice(index,nums,pros...):从index位置删除nums个元素，放入pros。。。元素
  • filter:将结果为true的结果筛选出来，生成新数组
  • forEach：和for一个效果
  • map
  • sort：默认字母排序，可以传入方法
  • reduce(function(previous,current,index){ return next_previous}) :累加器
  • for-of:for(let x of numbers){}
• 迭代器新
  • @@iterator:number[symbol.iterator]()返回{values:'val',done:true}
  • keys:numbers.keys():返回{values:'key',done:true}
  • values:numbers.values():返回{values:'val',done:true}
  • entries:numbers.entries()返回{values:[key,val],done:true}
  • from:new_array=Array.from(numbers) 复制数组
  • of:Array.of() 创建一个新数组
  • fill：Array().filll(val,start,end) 静态填充数组
  • copyWithin:array,copyWithin(index,[start,end])指定复制，将start到end的数组复制到index开始的位置
• 排序数组
  • reverse:array.reserve()数组反转
  • sort:array.sort(function(a,b){return a>b:-1,1})数组排序，字母按照ASCII排序
• 搜索
  • indexOf｜lastIndexOf
  • find｜findIndex：find(function(element，index，array){return element=2?true:false})
  • incloudes:numbers.incloudes(val,[index])查找
• 转字符串
  • toSting()
  • join()
• 类型数组

栈（Stack）

• 相对于数组在删除和添加数据的时候更为可控
• 先进后出，后进先出(LIFO)

栈的实操

1. 创建栈
   • push：添加栈顶
   • pop：移除栈顶
   • peek：但会栈顶元素
   • isEmpty：是否为空
   • clear：晴空万里
   • size：大小

// es5
function Stack(){
    let items= []
    this.push=function(elements){
        items.push(elements)
    }
    this.pop=function(){
        return items.pop();
    }
    this.peek=function(){
        return items[items.length-1]
    }
    this.isEmpty=function(){
        return items.length == 0
    }
    this.size=function(){
        return items.length
    }
    this.clear=function(){
        items = []
    }
    this.print=function(){
        console.log(items.toString())
    }
}

// es6 会暴露iterm
/*
* 节省内存
* 会暴露iterm，不能私有化，可被操作
*/
class Stack{
    constructor(){
        this.items=[]
    }
    push(elements){
        this.items.push(elements)
        console.log(this.items.toString())
    }
}

_items = Symbol()
class Stack{
    constructor(){
        this._items=[]
    }
    push(elements){
        this._items.push(elements)
        console.log(this.items.toString())
    }
}

栈能解决问题

• 回溯问题
• 进制转化实例

// 转二进制
function divideBy2(decNumber){
    let stack = new Stack(),
    binaryString=''
    while(decNumber>0){
        stack.push(Math.floor(decNumber % 2))
        decNumber = Math.floor(decNumber / 2)
        console.log(decNumber)
    }
    while(!stack.isEmpty()){
        binaryString += stack.pop().toString()
    }
    return binaryString
}

// 转任意进制
// 突然发现这东西可以做加密🔐
function baseConverter(decNumber,base=2){
    let stack = new Stack(),
    baseString='',
    digits='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ+/'
    while(decNumber>0){
        stack.push(Math.floor(decNumber%base))
        decNumber=Math.floor(decNumber/base)
    }
    while(!stack.isEmpty()){
        baseString+=digits[stack.pop()]
    }
    return baseString
}

队列（Queue）

• 先进先出，排队

// es5
function Queue(){
    let items= []
    this.enqueue=function(elements){
        items.push(elements)
    }
    this.dequeue=function(){
        return items.shift();
    }
    this.front=function(){
        return items[0]
    }
    this.isEmpty=function(){
        return items.length == 0
    }
    this.size=function(){
        return items.length
    }
    this.clear=function(){
        items = []
    }
    this.print=function(){
        console.log(items.toString())
    }
}

// es6 闭包保存
let Queue2 = (function () {
    const items = new WeakMap();
    class Queue2 {
        constructor() {
            items.set(this, []);
        }
        enqueue(element) {
            let q = items.get(this);
            q.push(element);
        }
        dequeue() {
            let q = items.get(this);
            return q.shift();
        }
    return Queue2;
})();

• 优先队列
  • 入列的时候插队enqueue
  • 出列的时候提前dequeue
  • 实际上记录的是节点

function prioriyQueue(){
    let items=[]
    function QueueItem(element,priority){
        this.priority = priority
        this.element = element
    }
    let added = false
    this.euqueue = function(element,priority){
        queueitem = new QueueItem(element,priority)
        for(let i=0;i<items.length;i++){
            if(items[i].priorty < queueitem.priority){
                items.splice(i,0,queueitem)
                added=true
                break
            }
        }
        if(!added){
            items.push(queueitem)
        }
    }
}

• 击鼓传花（循环队列♻）

function hotPotato(nameList,num){
    let queue = new Queue();
    for(let i=0;i<nameList.length;i++){
        queue.enqueue(nameList[i])
    }
    while(queue.size()>1){
        for(let i=0,i<num,i++){
            queue.enqueue(queue.dequeue())
        }
        console.log('淘汰：'+queue.dequeue())
    }
    return queue.dequeue()+'胜利✌️'
}

链表（LinkedList）

• 链表(linked list)是一种在物理上非连续、非顺序的数据结构，由若干节 点(node)所组成

• 链表操作

  • append 尾部添加
  • insert 任意位置添加
  • remove 删除
  • removeAt 从指定位置移除
  • indexOf 返回索引
  • isEmpty 是否为空
  • size 大小
  • toString 打印
  • getHead 返回头

function LinkedList() {
  let Node = function(element) {
      this.element = element;
      this.next = null;
    },
    current;
  let length = 0;
  let HEAD = null;

  this.append = function(element) {
    let node = new Node(element);
    if (HEAD == null) {
      HEAD = node;
    } else {
      current = HEAD;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    length++;
  };

  this.insert = function(element, position) {
    let node = new Node(element),
      current = HEAD,
      index = 0,
      previous;

    if (position > -1 && position < length) {
      if (position == 0) {
        node.next = current;
        HEAD = node;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = node;
        node.next = current;
      }
      length++;
      return true;
    } else {
      return false;
    }
  };

  this.remove = function(element) {
    let index = this.indexOf(element)
    return this.removeAt(index)
  };

  this.removeAt = function(position) {
    if (position > -1 && position < length) {
      let current = HEAD,
        index = 0,
        previous;
      if (position === 0) {
        HEAD = current.next;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
      }
      length--;
      return current.next;
    } else {
      return null;
    }
  };

  this.indexOf = function(element) {
      let index = -1,
      current = HEAD
      while(current){
          index++
          if(current.element===element){
              return index
          }
          current = current.next
      }
      return -1
  };

  this.size = function() {
    return length;
  };

  this.getHead = function() {
    return HEAD;
  };

  this.toString = function() {
    let current = HEAD,
      string = "";
    while (current) {
      string += current.element + (current.next ? "--->" : "");
      current = current.next;
    }
    return string;
  };
  this.print = function() {};
}

• 双向链表

function DoublyLikedList() {
  let Node = function (element) {
    this.element = element;
    this.next = null;
    this.prev = null;
  };

  let HEAD = null,
    length = 0,
    TAIL = null;

  this.append = function (element) {
    let node = new Node(element);
    if (HEAD == null) {
      HEAD = node;
      TAIL = node;
    } else {
      current  = TAIL
      current.next = node;
      node.prev = current;
      TAIL = node
    }
    length++;
    return true;
  };

  this.insert = function(position,element){
    if(position<0||position>length){
      return false
    }
    let node = new Node(element),
    curren = HEAD,
    index = 0,
    previous;
    if(postion == 0){
      if(!HEAD){
        HEAD = node
        TAIL = node
      }
      node.next = current
      current.prev = current
      HEAD = node
    }else if(position == length){
      current = TAIL
      node.prev = current
      current.next=current
      TAIL =  node
    }else{
      while(index++<position){
        previous = current
        current = current.next
      }
      previous.next = node
      node.prev = previous
      node.next = current
      current.prev = node
    }
    length++
    return true
  }

  this.remove = function(element){
    let index = this.indexOf(element)
    return this.removeAt(index)
  }

  this.removeAt = function(position){
    if(position<0|| posution>length){
      return null
    }
    let current = HEAD,
    index =  0,
    previous;
    if(position == 0){
      HEAD = cunrent.next
      if(length==1){
        TAIL = null
      }
      HEAD.prev = null
    }else if(position == length-1){
      current = TAIL
      TAIL = current.prev
      TAIL.next = null
    }else{
      while(index++<pervious){
        previous = current
        current = current.next
      }
      previous.next = current.next
      current.next.prev = previous
    }
    length--
    return current.element
  }

  this.indexOf = function(element){
    let current = HEAD,
    index = -1;
    while(current){
      index++
      if(current.element==element){
        return index
      }
      current =  current.next
    }
    return -1
  }

  this.getHead = function(){
    return HEAD
  }

  this.getTail = function(){
    return TAIL
  }

  this.toString = function () {
    let current = HEAD,
      string = "";
    while (current) {
      string += current.element + "<---->";
      current = current.next
    }
    return string
  };
}