数据结构全景

学习资料，参考 Hello 算法

什么是数据结构？

🏢 提示

是一种组织管理数据的一种方式 计算机中存储、组织数据的方式

线性结构 linear List

🏢 提示

线性结构是由n(n>=0)个元素（节点）a[0],a[1],a[2],a[3],...,a[n-1]组成的有限序列

1. 数组
2. 栈 受限的线性结构
3. 链表
4. 队列 受限的线性结构

数据结构详解

数组结构

🏢 提示

1. 几乎每种编程语言都会提供的一种原生数据结构（语言自带）
2. 可以借助数组杰鹏在来实现其他的数据结构，如 栈（stack），队列（queue），堆（heap） 优点：
3. 数组的内存通常是连续的，所以数组通过下标值访问效率非常高 缺点：
4. 当容量不足时需要扩容，会重新开辟一块新的内存空间
5. 开头或者中间位置插入元素的开销很大，后面的元素都需要位移

栈结构

🏢 提示

是一种受限的线性结构，只能从一端入栈和出栈(栈顶)，先进后出，后进先出 last in First Out （LIFO） 只能从栈顶入栈，栈底的元素无法获取，栈顺序无法修改 出栈后，相邻的元素成为栈顶

interface IStack<T> {
  push(element:T):void
  peek():T|undefined
  pop():T|undefined
  size():void
}

class  Stack<T= any> implements IStack<T> {
  private data :T[]= [] 
  push(element:T){
    this.data.push(element)
  }
  peek():T|undefined{
    return this.data[this.data.length-1]
  }
  pop():T|undefined{
    return this.data.pop()
  }
  size(){
    return this.data.length
  }
}

队列

🏢 提示

一种受限的线性结构，先进先出(FIFO,first in first out) 它只能在队列的前端(front)进行删除操作,在队列的后端(rear)进行插入操作 应用：

1. 多线程数据共享
2. 算法中会应用->二叉树层序遍历 实现方式：
3. 基于数组
4. 基于链表 —> 会更优

//还要整一个有初始化值的一个可迭代对象
interface IQueue<T=any> {
  enquque(el:T):void
  dequeue():T|undefined
  peek():T|undefined

  isEmpty():boolean
  get size(): number
}

class ArrayQueue<T> implements IQueue {
  private data:T[] = []
  enquque(el: T): void {
    this.data.unshift(el)
  }
  dequeue() {
    return this.data.pop()
  }
  peek() {
   return  this.data[this.data.length-1]
  }
  isEmpty(): boolean {
    return this.data.length>0
  }
  get size(): number {
    return this.data.length
  }
}

1. 约瑟夫环问题

import { ArrayQueue } from '../data_stuct/queue'

function josephus(n:number,m:number){
  const data = new ArrayQueue()
  for (let i = 1; i < n+1; i++) {
    data.enqueue(i)
  }
  while (data.size>1) {
    for (let j = 0; j < m; j++) {
      data.enqueue(data.dequeue())
    }
    // console.log('data.dequeue()', data.dequeue())
    data.dequeue()
  }
  console.log('data.peek()', data.peek())
}

josephus(12,9)

双端队列

循环队列

链表 LinkedList

🏢 提示

链表用于存储一系列的元素，但是实现机制和数组完全不同，链表的每个元素由自身的节点和指向下一个元素的引用（指针）组成 优点：

1. 链表中的元素在内存中不必是连续的内存空间，大小不必在创建时确定，可以无限延伸
2. 插入和删除操作时间复杂度低 O(1) 缺点：
3. 需要从头开始，才能访问任何一个元素（无法跳过第一个元素访问任何元素）
4. 无法通过下标访问元素

1. 基础实现

class LinkedNode<T> {
  next: LinkedNode<T> | null = null
  constructor(public value:T){}
}

class LinkedList<T>{
  head: LinkedNode<T>|null = null
  size = 0
  constructor(){}

  get length(){
    return this.size
  }
  }

1. append方法

 append(value:T){
    const newNode = new LinkedNode(value)
    if(!this.head){
      this.head = newNode
    } else {
      let currentNode = this.head
      while(currentNode.next){
        currentNode = currentNode.next
      }
      currentNode.next = newNode
    }
    this.size++ 

  }

1. insert方法

// 双指针法
insert(value:T,position:number):boolean {
    if(position<0|| position>this.size) return false
    
    const newNode = new LinkedNode(value)
    if(position===0){
      newNode.next = this.head
      this.head = newNode
    }else{
      let current = this.head,previous:LinkedNode<T>|null = null,index = 0
      while(index++<position && current){
        previous = current
        current =current.next
      }
      previous!.next = newNode
      newNode.next = current
    }
    this.size++
    return true
  }

1. getNode

private getNode(position:number): LinkedNode<T> | null{
    let current = this.head,index = 0
    while( index++ < position && current){
      current = current.next
    }
    return current
  }

1. removeAt

removeAt(position:number):LinkedNode<T>|null{
    let deleteNode = this.head
    if(position<0 || position>=this.size || this.head===null ) return deleteNode
    if(position===0){
     this.head = this.head?.next?? null
     deleteNode!.next = null
    } else {
      const tem = this.getNode(position-1)
      deleteNode = tem?.next ?? null
      tem!.next = deleteNode?.next?? null
    }

    this.size--
    return deleteNode
  }

🏢 提示

链表最重要的是分析清楚，每个节点的next指向

双向链表

循环链表

面试题

export class ListNode {
     val: number
     next: ListNode | null
     constructor(val?: number, next?: ListNode | null) {
         this.val = (val===undefined ? 0 : val)
         this.next = (next===undefined ? null : next)
     }
 }

1. 反转链表

LCR 024. 反转链表 - 力扣（LeetCode）

// 1. 循环迭代实现
function reverseList(head: ListNode | null): ListNode | null {
  if(head===null || head.next===null) return head
  let newLink:ListNode| null = null
  while(head){
    const current = head
    head = head?.next
    current.next = newLink
    newLink = current
  }
  return newLink
};
// 2. 递归实现

function reverseList(head: ListNode | null): ListNode | null {
  if(head=== null || head.next === null) return head
  const newNode = reverseList( head.next) // 先递归，然后返回链表的新的头，
  // 然后就不断在递归中传递返回
  head!.next.next = head //这里必须使用 原本的链的节点关系来修改next指向
  head.next = null
  return newNode //返回的始终是最后的节点，也就是新的head
};

1. 删除节点

面试题 02.03. 删除中间节点 - 力扣（LeetCode）

🏢 提示

实现思路： 理解链表的本质，删除节点必须知道要删除节点的前一个节点

1. 如果无法获取前一个节点，那么相当于把链表的后一个节点的值赋值给当前节点，并把当前节点的next指向后第2个节点
2. 也就是说实际上删除了后一个节点，但是把值前移了一位，实现了删除当前节点的功能

function deleteNode(node:ListNode|null){
  if(node?.next){
    node!.val = node.next!.val
    node.next = node.next!.next   
  }
}

哈希表

🏢 提示

底层仍然是由数组来实现的 字符串映射到数组的索引的方式，来储存数据 优点：

1. 插入查询删除效率高 缺点：
2. 空间利用率不高
3. 元素无序
4. 求最值慢

实现和内容暂时略去

树结构

🏢 提示

树是由n(n>=0)个节点构成的有限集合： 对于任何一颗非空树（n>0）,由如下特性：

1. 树中有一个称为‘根(root)’的特殊节点，用r表示
2. 其余节点可以分为m(m>0)个互不相交的有限集合合，T1，T2....Tm,每个集合本身又是一棵树，称为原来树的'子树(subTree)'
3. 没有子节点的节点称为叶子节点，（度为0）
4. 节点的度（Degree）：节点的子树个数 优点： 缺点：

二叉树

🏢 提示

二叉树： 每个节点最多只能 有2个子节点，这样的树称为二叉树 特性：

1. 一棵二叉树第i层最大的节点数为：2^(i-1),i>1
2. 深度为k的二叉树有最大节点总数为：2^k -1,k>1
3. 任何非空二叉树，n0表示叶节点数，n2表示度为2的非叶子节点，那么两者关系满足n0 = n2+1 存放对象时，实现valueOf方法，即可实现

完美二叉树 Perfect Binary Tree/满二叉树 Full Binary Tree

除了叶子节点外，其他所有节点的度都是2

也就是说，所有的节点需要填满

完全二叉树 complete Binary Tree

1. 除了最后一层，其他各层节点数都达到最大个数
2. 最后一层，从左到右的叶子节点连续存在，只缺右侧的若干节点
3. 完美二叉树是特殊的完全二叉树

🏢 提示

完全二叉树可以使用数组来储存 后面的堆结构也可以使用

二叉搜索树 BST （Binary Search Tree）

1. 非空左子树的所有键值小于其根节点的键值
2. 非空右子树的所有键值大于其根节点的键值
3. 左右子树本身也是二叉搜索树

二叉树的遍历

🏢 提示

先/中/后序遍历是指: 在所有的树结构中（包括子树）访问根元素值的顺序

1. 先序遍历

在所有的树结构中（包括子树）

• 先访问根元素
• 再访问所有左子树
• 再访问右子树

preOrderTraverse(){
    console.log('_preOrderTraverse')
    this._preOrderTraverse(this.root)
  }
  private _preOrderTraverse(node:TreeNode<T>|null) {
    if(node){
      console.log(node.value) // 
      this._preOrderTraverse(node.leftNode)
      this._preOrderTraverse(node.rightNode)
    }
  }

1. 中序遍历

• 先访问所有左子树
• 再访问根元素
• 再访问右子树

inOrderTraverse(){
    console.log('_inOrderTraverse')
    this._inOrderTraverse(this.root)
  }
  private _inOrderTraverse(node:TreeNode<T>|null){
    if(node){
      this._inOrderTraverse(node.leftNode)
      console.log( node.value) // 
      this._inOrderTraverse(node.rightNode)
    }
  }

1. 后序遍历

• 先访问所有左子树
• 再访问右子树
• 最后访问根元素

 postOrderTraverse(){
    console.log('_postOrderTraverse')
    this._postOrderTraverse(this.root)
  }
  private _postOrderTraverse(node:TreeNode<T>|null){
    if(node){
      this._postOrderTraverse(node.leftNode)
      this._postOrderTraverse(node.rightNode)
      console.log( node.value) // 
    }
  }

1. 层序遍历

• 按树的层来遍历，从顶往下访问

levelOrderTraverse(){
    //使用队列来解决
    if(!this.root) return
    const queue :TreeNode<T>[]= []
    queue.push(this.root)

    while(queue.length){
      const el = queue.shift()
      console.log( el!.value)
      if(el?.leftNode){
        queue.push(el.leftNode)
      }
      if(el?.rightNode){
        queue.push(el.rightNode)
      }
    }
    
  }

最值

1. 最大值 就是树的最右值

 
 /**最大值 */
  max():T|null{
    let current = this.root
    while(current && current.rightNode){
      current = current.rightNode
    }
    return current?.value ?? null
  }

1. 最小值 树的最左值

min():T|null{
    let current = this.root
    while(current && current.leftNode){
      current = current.leftNode
    }
    return current?.value ?? null
  }

搜索

 //迭代
 search(value:T):boolean{
   let current = this.root
   while(current){
     if(current.value == value) return true
     if(current.value > value){
      current = current.leftNode
     } else {
      current = current.rightNode
     }
   }
   return false
  }
  //递归
  

删除节点

🏢 提示

删除节点比较复杂，需要考虑的情况比较多

1. 是叶子节点
2. 有1个子节点
3. 有2个子节点

class TreeNode<T> {
  leftNode:TreeNode<T>|null = null
  rightNode:TreeNode<T>|null = null
  parent:TreeNode<T>|null = null
  get isLeft(){
    return parent && this.parent?.leftNode === this
  }
  get isRight(){
    return parent && this.parent?.rightNode === this
  }
  constructor(public value:T){ }
}

/**
   * 搜索节点
   * @param value 
   * @returns 
   */
private _search(value:T):TreeNode<T>|null {
   let current = this.root,parentNode:TreeNode<T>|null = null
   while(current){
     if(current.value == value) {
      current.parent =parentNode
      return current
     }
     parentNode = current
     if(current.value > value){
      current = current.leftNode
     } else {
      current = current.rightNode
     }
   }
   return null
  }
/**
   * 获取后继节点，右子树的最小值，也就是没有左子树
   * @param delNode  删除的节点
   */
  private getSuccessor(delNode:TreeNode<T>) {
    let current = delNode.rightNode
    let successor: TreeNode<T>|null = null
    while(current){
      successor = current
      current =current.leftNode
      if(current){
        //保留所有的父节点信息
        current.parent = successor
      }
    }
    if(successor !== delNode.rightNode){
      //当后继节点不等删除节点的右节点时，需要替换删除节点的右节点
      successor!.parent!.leftNode = successor!.rightNode
      // 也就是把后继节点的右节点，放到后继节点的父节点的左节点上
      // 如上图中删除 15时，后继节点18的存在右子树，15也存在右子树
      successor!.rightNode = delNode.rightNode
      //删除节点的右节点，放到 后继节点的右节点上
    }

    //后继节点的左节点必须指向 删除节点原来的左节点
    // 如上图中，删除7时，左子树也需要放到后继节点8的左子树，后继节点一定没有左子树
    successor!.leftNode = delNode.leftNode
    
    return successor
  }
  /**
   * 删除节点
   * @param value 
   */
  remove(value:T){
    let current = this._search(value)
    if(!current) return false

    // 1. 叶子节点
    let replaceNode:TreeNode<T>|null = null
    if(current.leftNode === null && current.rightNode === null){
      replaceNode = null
    }
    // 2. 有1个子节点
    // 是右节点，就需要把右节点保存下来
    else if(current.leftNode === null){
       replaceNode =current.rightNode 
    }
    //左节点，需要把左节点保存下来
    else if(current.rightNode === null){
      replaceNode =current.leftNode
    }
    // 3. 有2个子节点
    else {
    // 替换后继节点，后继节点的子节点处理已在getSuccessor函数中处理
      replaceNode = this.getSuccessor(current)
    }
    if(current===this.root){
    // 如果是根元素，那么直接替换根元素
      this.root =replaceNode
    }else if(current.isLeft){ 
    // 如果被删除的节点是父节点的左节点，那么替换左节点
      current.parent!.leftNode = replaceNode
    }else {
    //如果是父节点的右节点，那么替换右节点即可
      current.parent!.rightNode = replaceNode
    }
  }

avl树

红黑树

图结构

堆结构

使用数组来存储，是一个完全二叉树

🏢 提示

公式 最后一个非叶子节点 Math.floor((size-1)/2) I的左节点 2*i +1 I的右节点 2*i +2 关键思路：

1. 上滤操作 用于插入数据时，放在数组最后位置，然后与父节点比较，交互，直到小于父节点
2. 下滤操作 用于提取元素，与子节点比较，交换，知道小于子节点
3. 原地建堆 自底而上的建堆方法，找到最后一个非叶子节点（也就是叶子节点与非叶子节点的分界，小于这个索引的都是非叶子节点，大于都是叶子节点），然后下滤，递归去下滤其他非叶子节点

最大堆

所有的父节点比子节点大的完全二叉树

最小堆

所有父节点都比子节点小的完全二叉树

代码实现

已兼容最大堆和最小堆

class Heap<T> {
  private data:T[]=[]
  /**最大堆 */
  private isMax: boolean
  constructor(arr:T[]=[],isMax = true){
    this.isMax = isMax
    if(arr.length>0){
      this.buildheap(arr)
    }
  }
  get lenght(){
    return this.data.length
  }
  

  isEmpty(){
    return this.lenght <= 0
  }

  /**
   * 插入一个元素
   * @param value 
   */
  insert(value:T){
    this.data.push(value)
    // 上滤操作
    this.heapify_up(this.lenght-1)
  }

  extract():T|null {
    if(this.isEmpty()) return  null
    this.swap(0,this.lenght-1) //交换顺序
    const res = this.data.pop()! //弹出元素
    this.heapify_down(0) //堆顶元素下滤
    return res
  }

  buildheap(arr:T[],isMax = true){
    this.data = arr
    this.isMax = isMax
    let i = this.get_parent(this.lenght-1)
    // i === 0 的时候，说明已经到根节点了，下滤一次后即可退出
    while(i>=0){
      this.heapify_down(i) //非叶子节点元素下滤
      i-- 
      // 最后一个非叶子节点往前，都是非叶子节点，[0, Math.floor((lenght-1)/2) ] 区间都是非叶子节点的索引，
      // [Math.floor((lenght-1)/2)+1,lenght-1]都是叶子节点
    }
 
  }
  /**
   * 下滤
   * @param i 
   */
  heapify_down(i:number){
    
    let maxIndex = i //假设当前的就是最大的
    while (true){
      const leftIndex = this.get_left(i)
      const rightIndex = this.get_right(i)
      if( leftIndex < this.lenght  && this.compare_fn(maxIndex,leftIndex)) maxIndex = leftIndex // 左子节点索引没有越界，且大于当前的最大值
      if( rightIndex < this.lenght && this.compare_fn(maxIndex,rightIndex)) maxIndex = rightIndex // 右子节点索引没有越界，且大于当前的最大值
      if(maxIndex===i){ // 说明左右子节点不大于的当前节点了，即可退出
        break
      }
      this.swap(i,maxIndex) // 最大值的子节点与当前节点 交换
      i = maxIndex // 拿最大值的子节点的索引，再次执行下滤
    }

  }

  /**
   * 上滤
   * @param i 
   */
  heapify_up(start:number){
    /**
     * 两个退出条件
     * 1. 子节点的值小于父节点，说明已经符合条件
     * 2. 当前节点已经是根节点了，说明上滤到堆顶了
     */
    let index = start
    while( index>0 ){
      let parentIndex = this.get_parent(index)
      if(this.compare_fn(index,parentIndex)){
        break
      }else{
        this.swap(index,parentIndex)
        index = parentIndex
      }
    }
  }
  /**
   * 
   */
  swap(i:number,j:number){
    const temp = this.data[i]
    this.data[i]=this.data[j]
    this.data[j] = temp

  }
  /**
   * 比较索引的值是否已在正确的位置，兼容最大堆和最小堆
   * @param i myIndex
   * @param j parentIndex
   */
  compare_fn(i:number,j:number):boolean {
    if(this.isMax){
      return this.data[i] <= this.data[j]
    }else{

      return this.data[i] >= this.data[j]
    }
  }

  get_parent(i:number):number {
    return Math.floor((i-1)/2) 
  }
  get_left(i:number):number {
    return 2*i + 1 
  }
  get_right(i:number):number {
    return 2*i + 2 
  }
  print(){
    console.log('this.data', this.data)
  }
}