2022-03-17 16:49 已编辑武汉大学前端工程师

关注

JS数据结构和算法

零基础介绍

数据结构：数据的逻辑结构、数据的物理/存储结构、数据的运算与实现。
逻辑结构的分类：----抽象的特点

1 线性结构：有且只有一个开始和结束节点，所有节点最多只有一个直接前驱和直接后继。例如线性表、栈、队列、串

非线性结构：多对多，例如树、图

2 集合、线性结构、树、图

3 ？逻辑结构有很多，还有通过不同的逻辑定义更多的数据类型，但是底层的存储结构是有限的

存储结构分类：---实现的方式

1 顺序存储结构：数组

链接存储结构：链表

索引存储结构：建立一个索引表

散列/哈希存储结构：

抽象数据类型：数据（数据对象，对象之间的关系）以及操作方法
算法的特性：有穷性、确定性（相同输入必定相同输出）、可行性、输入、输出
算法的效率：

时间复杂度--------有时间需要多练习

1、定义：又称"渐进式时间复杂度"，表示代码执行时间与数据规模n之间的增长关系。

假设执行基本语句的时间相同，执行时间T(n)可以表示为所有语句的执行次数

为了比较不同算法之间时间效率，我们用f(n)表示执行次数和数据规模n之间的关系

当n趋近于无穷大时，忽略低阶项和系数的影响，当f(n)/t(n)的比值是一个常数时，可以使用O(fn)来表示T(n)，被称为大O表示法

2、基本方法：先找出执行最多的基本语句，找到f(n)，最后大O表示

空间复杂度--------有时间需要多练习

算法1 只需要新建一个变量，而算法2新建一个长度n的数组

1 线性表----结合线性结构理解，注意前驱和后继的理解（前后只有一个元素）

1.1 线性表的链式实现

针对具体的问题分析逻辑结构和存储结构，？实际上就是类

循环链表，首尾相接的连接。空链表时，头指针的next指向自己 this.head.next=this.head?
顺序表示随机存储，链表是顺序存储？
头插法和尾插法

头插法：将需要存储的数据，每次插在链表的头部（head后面）
尾插法：每次插入在元素的尾部 1、append方法 2 使用尾指针 this.tail

2 栈和队列

栈和队列是限定插入和删除只能在端点进行的线性表，

栈按照存储方式也有顺序栈和链式栈，链栈的插入删除只在栈顶的头部进行(修改指向）

栈与递归：递归问题用分治法求解，分治法就是针对一个复杂问题，可以拆分成为几个类似的子问题来求解

3 串、数组和广义表

串就是字符串，里面的内容都是字符

串的模式匹配算法（找匹配的子串）：

1 BF算法（暴力算法）

2 KMP算法？？？https://www.pianshen.com/article/49661491657/

计算next的方法可以参考王卓的视频，计算nextval的方法可以参考链接

   // 计算nextval数组
    function nextVal(str) {
        len = str.length
        let next = [0,1]
        let nv=[0]
        for (let i = 2; i <len; i++) {
        let tem=str.slice(0,i)
        let n=1
        let k=1
        for (k=1;k<tem.length;k++){
            if (tem.slice(0,k)==tem.slice(tem.length-k,tem.length)){
                n=k+1
            }
        }
        next.push(n)
        }
        for(let j=1;j<len;j++){
            let idx=next[j]
            if(str[j]==str[idx-1]){
                nv.push(next[idx-1])
            }else{
                nv.push(next[j])
            }
        }
        return nv;
    }
     

    // source 源字符串
    // match 要匹配的字符串
    // res 保存匹配位置的数组
    function search(source, match) {
        let next = nextVal(match),
            m = source.length,
            n = match.length,
            i = 0,
            j = 0,
            res = [];
        while (i < m - n  && j< n) {
            if (source[i] === match[j]) {
                i++;
                j++;
            } else if(j>0){
                    j = next[j - 1];
            }else{
                i++
            }
        }
        if (j==n)  {return true}
        else {return false};
    }

    let source = '1234456',
        match = '121212';

    let res = search(source, match);
    console.log(res)

广义表：又称列表lists,它有长度和深度

4 树和二叉树

二叉树不是树的特殊情况，二叉树哪怕只有一个节点仍要区分左右子树，但是树只剩下一个节点则不需要

哈夫曼树获取不等长的前缀码？
二叉树求解表达式的值

二叉树的顺序存储：根据下标在满二叉树的位置的编号存储（比较浪费空间）

在n个节点的二叉链表中，必有2n个链域（左右节点），有n-1个链域存放指针，剩下n+1个空指针域

已知先序和中序/中序和后序确定二叉树

进行遍历的时候，除了使用递归以外，也可以尝试栈+循环的方式

二叉树的层序遍历
线索二叉树，利用链表中的空指针域，如果某个节点的左指向为空，可以将其指向其前驱。如果某个节点的右指向为空，可以将其指向其后继，

此时为了区分指向子节点还是前驱后继，需要增设ltag与rtag

树的双亲表示法，孩子表示法，儿子兄弟表示法（将树转换成二叉树，加线，抹线，旋转）
哈夫曼树，带权路径长度最短的树

路径长度：节点的路径长度，树的路径长度（从树根到每个节点的路径长度之和），节点相同的二叉树中，完全二叉树是路径长度最短的二叉树
带权路径长度：节点的带权路径长度（路径长度×权），树的带权路径长度（从树根到每个叶子节点的路径长度之和）

满二叉树不一定是哈夫曼树，权值越大的叶子离根越近，哈夫曼树不唯一

？构造哈夫曼树

利用哈夫曼树进行编码：根据权重构建哈弗曼树，左分支的边代表0,右分支的边代表1

哈夫曼编码可以保证前缀编码，从树的角度，被表示的字符都位于叶子节点，不会路过其他字符代表的编码

能够保证字符编码总长最短

5 图

网：有权图

联通图：对任意两个顶点U、V都存在你从U到V的路径

图没有顺序存储结构，但是可以使用二维数组构成的领接矩阵表示：顶点数据Vexs,以及矩阵Edge[i][j](如果i,j之间存在边则为1.否则为0，如果是有向图发出时才为1）

链式的领接表：对于有向图，找出度使用领接表；找入度使用逆领接表

图的遍历：从某一节点出发，遍历所有节点，且每个节点只被访问一次

图的应用：

*** 最小生成树：所有顶点均由边联通，但是不存在回路；生成树是图的极小联通子图，n个节点有n-1条边；深度/广度优先生成树（按遍历顺序不重复即可）

权重之和最小的生成树被称为最小代价生成树。--------------针对城市之间修铁路之间的问题

？MST性质：

普里姆prim算法：每次找到距离最小生成树节点最近（最小生成树中所有节点都参与比较）的那个节点；针对点，稠密图

克鲁斯卡尔算法：先不要边，把边按照从小到大排序，在不形成环的条件下，添加进去；针对边，稀疏图

*** 最短路径：A到B权重和最小的路径（可以不用包含所有的点）

？迪杰斯特拉算法：单源最短路径

？弗洛伊德算法：所有顶点间的最短路径

*** 拓扑排序：有向无环图------工作流程等问题

AOV ：有向，无回路；顶点表示排序的网，用于拓扑排序；如果经过拓扑排序还有结点剩下，说明有环存在

AOE 边表示排序的网，用于关键路径

关键活动：活动的最早发生时间和最晚发生时间相等

6 散列表/哈希表

散列表：用散列方法构造的表

散列方法：选取某个函数（散列函数），依据该函数按关键字计算元素存储的位置，并按此存放。

冲突：不同的关键码映射到同一个散列地址

散列函数：尽可能简单，尽可能均匀分布，可能尽量解决冲突

一定义一个栈

在给函数定义一个方法时，可以使用引用方式，也可以使用原型的方式，但是由于使用引用的方式会导致每次new对象时都会占用内存，因此推荐原型的方式。
定义原型时使用Stack.prototype而不是this.protoType
有些方法需要有返回值

function Stack(){
    this.items=[]
    //push 
    Stack.prototype.push=function(element){
        this.items.push(element)
    }
    //push
    Stack.prototype.pop=function(element){
        return this.items.pop()
    }
    //peek 输出栈顶元素
    Stack.prototype.peek=function(){
        return this.items[this.items.length-1]
    }
    //判断是否为空
    Stack.prototype.isEmpty=function(){
        return this.items.length==0
    }
    //toString方法
    Stack.prototype.toString=function(){
        return this.items.join("")
    }
}

1 利用栈的性质实现十进制转化为二进制

function dev2bin(n){ 
    var res=[] 
    while(n>0){ 
        res.unshift(n%2) 
        n=Math.floor(n/2) 
    } 
    return res.join("") 
} 
// 对循环条件的认识

2 括号匹配的检验

左括号的话就入栈，右括号的话就要看和栈顶的元素是否匹配，如果不匹配就失败，匹配的话将栈顶的元素出栈，继续下一轮比较

3 表达式求值

二定义一个队列

1 实现击鼓传花

function jg(arr,n){
    while(arr.length>1){
        for(let i=0;i<n-1;i++){
            arr.push(arr.shift())
        }
        arr.shift()
    }
    return arr[0]
}

核心点：将队列中的第一个删除的同时，放入队列的尾部

三优先级队列

每个元素不再只是数据，而是包含数据的优先级
在添加时根据优先级添加到正确的位置
使用场景：飞机的头等舱、具有优先级的线程
定义一个数组，数组里面是定义的一个内部类，有值和优先级两种属性，插入的时候如果为空直接插入，不为空需要根据优先级splice
可以用二维数组代替

四链表

1 append方法

function linkedList(){ 
    function node(data){ 
    this.data=data 
    this.next=null 
    } 
    this.header=null 
    this.length=0 
    //append方法  
    linkedList.prototype.append=function(data){ 
    var newNode=new node(data) 
    if (this.length==0){ 
        this.header=newNode 
    }else{ 
        var current=this.header 
        while(current.next){ 
            current=current.next 
        } 
       current.next=newNode 
    } 
    this.length +=1 //注意不要漏掉了 
    } 
    //tostring方法 
    linkedList.prototype.toString=function(){ 
        var res="" 
        var current=this.header 
        while(current){ //注意此处的判断条件 
            res=res+current.data 
            current=current.next 
        } 
        return res 
    } 
    //insert方法 
    linkedList.prototype.insert=function(pos,data){ 
        if (pos<0 || pos>this.length) return false 
        var newNode=new node(data) 
        var current=this.header 
        if (pos==0){ 
            newNode.next=this.header 
            this.header=newNode 
        }else{     for (let i=0;i<pos-1;i++){  //次数的判定:1从特殊点0判定等，如果是找到当前是pos,找到当前的一个则是pos-1 
               current=current.next 
                } 
newNode.next=current.next 
current.next=newNode 
} 
this.length+=1 
} 
//removeAt方法
linkedList.prototype.removeAt=function(pos){ 
if (pos<0 || pos>=this.length) return false 
var current=this.header 
if (pos==0) {this.header=this.header.next} 
else{ 
for (let i=0;i<pos-1;i++){ 
current=current.next 
} 
current.next=current.next.next  // 也可以定义两个指针，将前面一个节点定位为previous 
} 
this.length-=1 
} 
}

五双向链表

对链表的理解要摆脱之前数组的影响，彼此之间的关系主要是通过引用

function doulyLinkedlist(){
    this.head=null
    this.tail=null
    this.length=0
    function node(data){
        this.data=data
        this.next=null
        this.prev=null
    }
    doulyLinkedlist.prototype.append=function(data){
        var newNode=new node(data)
        if (this.length==0){
            this.head=newNode
            this.tail=newNode
            
        }else{
            newNode.prev=this.tail
            this.tail.next=newNode
            this.tail=newNode
        }
        this.length+=1
    }
    doulyLinkedlist.prototype.insert=function(pos,data){
        if (pos<0 || pos>this.length) {
            return false
        }
        var newNode=new node(data)
        if (pos==0){
            newNode.next=this.head
            this.head.prev=newNode
            this.head=newNode
        }else if(pos==this.length){
            newNode.prev=this.tail
            this.tail.next=newNode
            this.tail=newNode
        }else{
            var current=this.head
            for (let i=0;i<pos;i++){
                current=current.next
            }
            newNode.next=current
            newNode.prev=current.prev//先给新节点添加属性，更加安全
            current.prev.next=newNode
            current.prev=newNode
        }
        this.length+=1
    }
    doulyLinkedlist.prototype.toString=function(){
        var res=""
        var current=this.head
        while(current){
            res+=current.data
            current=current.next
        }
        return res
    }
}

六集合

1 j集合的操作：set的常用方法

add remove has clear size values

function Set(){
    this.items={}
    Set.prototype.has=function(data){
        return this.items.hasOwnProperty(data)
    }
    Set.prototype.add=function(data){
        if (this.has(data)) return false
        else{
            this.items[data]=data 
        }

    }
    Set.prototype.remove=function(data){
        if (!this.has(data)) return false
        else{
            delete this.items[data]
            //this.items[data]=undefined
        }
    }
    Set.prototype.clear=function(){
        this.items={}
    }
    Set.prototype.size=function(){
        return Object.keys(this.items).length
        // Object.values(this.items).length
    }
    Set.prototype.values=function(){
        return Object.values(this.items) //返回的是字符串类型
        // Object.values(this.items).length 返回的是数字类型
    }
}

2 集合之间的操作

function Set(){
    this.items={}
    ...
    // 并集
    Set.prototype.union=function(otherSet){
        var res=new Set()  //需要返回新的集合元素
        for(let i of this.values()){
            res.add(i)  //add方法包含是否重复
        }
        for(let j of otherSet.values()){
            res.add(j)
        }
        return res
    }
    // 交集
    //充分利用写好的has,add等属性
    ...
}

七字典

对象中的键只能是string或者是symbol，但是字典里的key可以是任意的类型

八哈希表

哈希化

哈希函数

哈希表

解决哈希冲突的方法：

1 链地址法：数组中的每个元素的类型是链表或者数组，这样当通过哈希函数得到的索引重复时，将重复的元素按照链表或者数组的形式放置

2 开放地址法 :当索引重复时，在数组中搜素空白的位置，然后将重复的值放在空白处

ps:在真实开发中使用链地址法比较多，因为不会随着添加地址后性能下降

function hashTable(){
    this.storage=[]
    this.count=0
    this.limit=7
    hashTable.prototype.hashFunc=function(str,size){
    var hashCode=0
    for (let i=0;i<str.length;i++){
        hashCode=hashCode*37+str.charCodeAt(i)
    }
    var res=hashCode%size
    return res
    }
    hashTable.prototype.put=function(key,value){
        //根据key获取对应的index
        var index=this.hashFunc(key,this.limit)
        //根据Index获取对应的bucket
        var bucket=this.storage[index]
        //判断bucket是否为空
        if (bucket==null){
            bucket=[]
            this.storage[index]=bucket
        }
        //判断是否是修改数据
        for(let i=0;i<bucket.length;i++){
            var tuple=bucket[i]
            if(tuple[0]==key){
                tuple[1]=value
                return
            }
        }
        //进行添加操作
        bucket.push([key,value])
        this.count+=1
    }
    hashTable.prototype.get=function(key){
        var index=this.hashFunc(key,this.limit)
        var bucket=this.storage[index]
        if (bucket==null) return null
        for(let i=0;i<bucket.length;i++){
            var tuple=bucket[i]
            if(tuple[0]==key){
                return tuple[1]
            }
        }
        return null  //最后仍然没找到
    }
}

判断一个是否是质数

常规方法：遍历到n-1，看余数是不是0
高效的方法：遍历到sqrt(n)

九树结构

将一个树使用儿子兄弟表示法（节点内只定义左边第一个子结点，和这个子结点的右边的第一个兄弟节点），然后旋转45°，就变成了二叉树
所有的树本质上都可以通过二叉树模拟出来
重要性质：

一个二叉树的第I层的最大子结点的个数是2^(i-1)
深度为k的二叉树有最大节点总数为2^k-1
对任何非空的二叉树的，n0表示叶子节点的个数，n2表示度为2的非叶结点的个数，则n0=n2+1
完美二叉树（满二叉树），完全二叉树（每个节点的位置要和满二叉树一样/除第 h 层外，其它各层是满的，第 h 层所有的结点都连续集中在最左边）

存储方式：对于完全二叉树，使用数组（可以计算每个节点的索引值），否则使用链表

5. 二叉搜索树：左子树的值小于根节点的值，右子树的值大于根节点，左右子树同时也是二叉搜索树

function binarySearchTree(){
    function node(key){
        this.key=key
        this.left=null
        this.right=null
    }
    this.root=null
    binarySearchTree.prototype.insert=function(key){
        var newNode=new node(key)   //递归
        if (this.root==null){this.root=newNode}
        else{
            this.insertNode(this.root,newNode)
        }
    }
    binarySearchTree.prototype.insertNode=function(node,newNode){
        if(node.key>newNode.key){
            if(node.left==null){
                node.left=newNode
            }else{
                this.insertNode(node.left,newNode)
            }
        }else{
            if(node.right==null){
                node.right=newNode
            }else{
                this.insertNode(node.right,newNode)
            }
        }
    }
    //先序遍历
    binarySearchTree.prototype.xian=function(){
         this.xianNode(this.root)
         return res

    }
    var res=[]
    binarySearchTree.prototype.xianNode=function(node){
        if (node!=null){       
                  res.push(node.key)       
                  this.xianNode(node.left)
            this.xianNode(node.right)
        }
    }
    //最小值
    binarySearchTree.prototype.min=function(){
        var current=this.root
        while(current.left!=null){
            current=current.left
        }
        return current.key  //为了防止节点里的key为空，可以给出默认值
        
    }
    //搜索一个值
    binarySearchTree.prototype.search=function(key){
        var node=this.root
        while(node!=null){ //while基本可以替代递归
            if(key==node.key){
                return true
            }else if(key < node.key){
                node=node.left
            }else{
                node=node.right
            }
        }
        return false
    }
}

删除节点，分为0节点，一个节点，两个节点三种情况（删除节点靠的是删除节点之间的联系）

function binarySearchTree(){
    function node(key){
        this.key=key
        this.left=null
        this.right=null
    }
    this.root=null
    binarySearchTree.prototype.insert=function(key){
        var newNode=new node(key)   //递归
        if (this.root==null){this.root=newNode}
        else{
            this.insertNode(this.root,newNode)
        }
    }
    binarySearchTree.prototype.insertNode=function(node,newNode){
        if(node.key>newNode.key){
            if(node.left==null){
                node.left=newNode
            }else{
                this.insertNode(node.left,newNode)
            }
        }else{
            if(node.right==null){
                node.right=newNode
            }else{
                this.insertNode(node.right,newNode)
            }
        }
    }
    //删除节点
    binarySearchTree.prototype.remove=function(key){
        var current=this.root
        var parent=null
        var isLeftChild=true
        while(current.key!=key){
            parent=current
            if(key<current.key){
                current=current.left  
                isLeftChild=true
            }else{
                current=current.right  
                isLeftChild=false   
            }
            if(current==null) return false
        }
        //删除叶子节点
        if(current.left==null && current.right==null){
            if (current==this.root){
                this.root=null   //注意根节点
            }else if(isLeftChild){
                parent.left=null
            }else{
                parent.right=null
            }
        }
        //删除的节点有一个子结点
        else if(current.left!=null && current.right==null){
            if (current==this.root){
                this.root=this.root.left //注意根节点
            }else{
                if(isLeftChild){parent.left=current.left}
                else{parent.right=current.left}
            }
        }else if(current.left==null && current.right!=null){
            if (current==this.root){
                this.root=this.root.right
            }else{
                if(isLeftChild){parent.left=current.right}
                else{parent.right=current.right}
            }
        }
        //删除有两个节点的节点，找到前驱或者后继，
        else{
            var successor=this.getSuccessor(current)
            if(isLeftChild){
                parent.left=successor
            }else{
                parent.right=successor
            }
            successor.left=current.left//将删除节点的左子树转移到后继节点，对删除节点父子节点的关系进行调整
        }

    }
            //找到后继的方法
    binarySearchTree.prototype.getSuccessor=function(dnode){
        //定义变量找到保存的后继
        var successor=dnode
        var succcessorParent=dnode
        var current=dnode.right//找到是后继不是前驱
        //循环查找
        while(current!=null){
            successor=current.left
            succcessorParent=current
            current=current.left
        }
        //判断后继节点是否就是dnode节点的右节点，对后继节点的父子节点关系进行调整
        if(successor!=dnode.right){
            succcessorParent.left=successor.right
            successor.right=dnode.right
        }
        return successor
    }

}

二叉树在某些情况下会变成非平衡树（左右子孙节点数目相差很多），极端时甚至会变成链表

红黑树的三种变化方式：变色，左旋转，右旋转

十图

图的术语：顶点，边，相邻顶点（由一条边连接起来的顶点），度（相邻顶点的数量），路径（简单路径不包含重复顶点，回路的第一个和最后一个顶点相同）
有向图和无向图，有权图和无权图
领接矩阵：当是稀疏矩阵时，存在内存浪费
邻接表：计算出度（指向别人）比较简单，计算入度比较麻烦

https://blog.csdn.net/xiaoguoyangguang/article/details/117334087?spm=1001.2014.3001.5501

图的遍历方法：广度优先遍历（BFS）和深度优先遍历(DFS)

BFS:基于队列，队列的顶点先被搜索
DFS：基于栈或者递归，通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问
白色表示未被访问，灰色表示被访问过，但是没被探索，黑色表示访问且被探索过

广度优先遍历----和树的层序遍历很相似
深度优先遍历----和先序遍历很相似

function graph(){
    this.vert=[]
    this.edge={}
    graph.prototype.addv=function(v){
        this.vert.push(v)
        this.edge[v]=[]
    }
    graph.prototype.adde=function(v1,v2){
        this.edge[v1].push(v2)
        this.edge[v2].push(v1)
    }
    graph.prototype.toString=function(){
        var res=""
        //遍历所有顶点以及顶点对应的边
        for (let i=0;i<this.vert.length;i++){
            res=res+(this.vert)[i]+"=>"
            for (let j=0;j<Object.values(this.edge)[i].length;j++){
                res=res+Object.values(this.edge)[i][j]
            }
            res=res+"\n"  
        }
        return res
    }
    //初始化颜色
    graph.prototype.initColor=function(){
        var colors={}
        for(let i=0;i<this.vert.length;i++){
            colors[this.vert[i]]="white"
        }
        return colors
    }
    //广度优先遍历
    graph.prototype.bfs=function(initv,handler){
        var colors=this.initColor()
        var queue=[]
        queue.push(initv)
        //循环从队列中取出元素
        while(queue.length>0){
            //从队列中取出第一个顶点
            var v=queue.shift()
            //获取和顶点相邻的其他顶点
            var vlist=this.edge[v]
            //将v的颜色设置为灰色
            colors[v]="gray"
            //遍历所有的顶点并加到队列中
            for(let i=0;i<vlist.length;i++){
                var e=vlist[i]
                if(colors[e]=="white"){
                    colors[e]="gray"
                    queue.push(e)
                }
            }
            handler(v)
            colors[v]="black"
        }
    }
    //深度优先遍历
    graph.prototype.dfs=function(handler){
        var colors=this.initColor()
        this.dfsVisit(this.vert[0],colors,handler)
    }
    graph.prototype.dfsVisit=function(v,colors,handler){
        colors[v]="gary"
        handler(v) //相当于一个容器
        //访问V相连的顶点
        var vlist=this.edge[v]
        for(let i=0;i<vlist.length;i++){
            var e=vlist[i]
            if(colors[e]=="white"){
                this.dfsVisit(e,colors,handler)
            }
        }
    }
}
var a=new graph()
a.addv("A")
a.addv("B")
a.addv("C")
a.addv("D")
a.addv("E")
a.addv("F")
a.adde("A","B")
a.adde("A","C")
a.adde("A","D")
a.adde("C","D")
a.adde("C","E")
a.adde("D","F")
var res=""
a.dfs(function(node){
    res += node +" "
})
console.log(res)