重新認識數據結構

1. 概念#

數據結構與算法是計算機科學的重要基礎知識。
數據結構是指相互之間存在一種或多種特定關係的數據元素的集合。它涉及數據的存儲、組織和管理。常見的數據結構包括數組、鏈表、棧、隊列、樹、圖等。
算法是完成特定任務的步驟或指令的序列。它本質上是對數據操作的一種描述。算法主要包含輸入、輸出以及轉換輸入為輸出的步驟。
數據結構與算法之間有著密不可分的關係。算法的設計取決於所選的數據結構，不同的數據結構適用於不同的算法。而數據結構的組織方式直接影響算法的效率。
掌握數據結構與算法對開發高質量程序非常重要。它們是評估開發人員技術能力的重要標準。數據結構與算法知識也是面試中的常見考點。許多編程語言都需要實現和使用各種數據結構與算法。
所以數據結構與算法是每個程序員必備的基礎知識，需要通過大量的學習、練習和使用才能真正掌握。它們是開發人員必須重點提高的核心競爭力之一。

數據結構構成#

1. 棧結構
2. 隊列
3. 數組
4. 鏈表
5. 樹
6. 圖
7. 堆結構

1.1 棧結構的實現#

實現方法：基於數組和基於鏈表，由於 ts/js 中不存在鏈表，需要重新實現。

interface IStack<T>{
  push():void;
  pop():void;
  size():number
  peek():T
  isEmpty():bollean
}

class Stack<T=any> immplements IStack{
  private arr:T[]=[]
  push(element:T):void{
     this.arr.push(element)
  }
  pop():void{
     this.arr.pop()
  }
  size():number{
    return this.arr.length();
  }
  peek():T|undefined{
    return this.arr.pop()
  }
  isEmpty():bollean{
    return this.arr.length===0?true:false
  }
}

面試題 1. 實現一個十進制轉二進制的函數#

function toBinary(count:number):string{
  let stack =new Stack()
  let binary=""
  while(count>0){
    stack.push(count%2)   
    count= Math.floor((count/2))
  }
  while(!stack.isEmpty()){
    binary+=stack.pop()
  }
  return binary;
}

面試題 2. 實現字符 “（”，“{”，“[” 與 "}","]",#

")" 對稱
例如： valid ("(){}[]") true
valid("({[]})") true
valid("{()]}") false

function valid(str:string):boolean{
  const stack=new Stack()
  for(let i=0;i<str.length;i++){
    switch(str[i]){
      case "(":
        stack.push(")")
        break;
      case "{":
        stack.push("}")
        break;
      case "[";
        stack.push("]")
        break;
      default:
         if(str[i]!==stack.pop()) return false
        
    }
  }
  return stack.isEmpty()
}

擊鼓傳花#

1. 一群人圍著圈，開始數，當停止時，數數該人被淘汰，並得出最後一個勝利者的初始位置。

思路：根據隊列依次出棧，若不為叫到人，則再進棧。#

function findLast(arr:string[],loop:number){
  if (arr.length === 0) return -1;
  const queue=new Queue()
  for(let i=0;i<arr.length;i++){
     queue.enqueue(arr[i])
  }
  while(queue.size()>1){
  for(let i=1;i<loop;i++){
    const name=queue.dequeue()
    queue.enqueue(name)
  }
  queue.dequeue()
  }
  return queue.dequeue()
}

鏈表結構#

概念：和數組一樣是線性結構可用於存儲一系列元素，但列表和數組的實現機制完全不同，在什麼場景下用到數組或鏈表，取決於應用場景的操作。

數組：在空間內分配一塊固定大小的連續空間用於存儲數據，但當在數組前、中插入元素時，所有的之後的元素都要向後移動相應的內存地址，如果數組元素特別多的情況下，開銷會很大。

鏈表：鏈表不需要在創建時就確定大小，根據 head 指針指向鏈表中 next 的元素，head=>next=>next2=>next3=>next4
當設計到大量刪除、插入操作時，只需要改變 next 的指針指向即可，時間複雜度為 O (1) ，但他的缺點很明顯，數組通過索引即可尋址，但鏈表需要走頭開始。

鏈表的實現#

class Node<T=any>{
  value:T;
  next:Node<T>|null
  constructor(value:T){
    this.value=value
  }
}
class LinkList<T>{
  head:T|null=null;
  size:number=0;
  get length():number{
    return this.size
  }
  add(element):void{
    const newNode=new Node<T>(element)
    if(!this.head){
      this.head=newNode
    }else{
      let current=this.head
      while(current.next){
        current=current.next
      }
      current.next=newNode
    }
    this.size++
  }
  traverse(){
   let values:T[]=[]
   let current=this.head
   while(current){
      values.push(current.value)
      current=current.next
   }
    console.log(values.join("->"))
  }
  insert(elememt:T,position:number):boolean{
    if(position<0||position>this.size) return false
    const value=new Node(element)
    if(position===0){
      value.next=this.head
      this.head=value
    }else{
      let prev:Node<T>|null=null
      let current=this.head
      let index=0
      while(index++<position){
        prev= current;
        current=current.next
      }
      prev.next=value
      value.next=current
    }
    this.size++
    return true
  }
  //刪除某個位置節點
  removeAt(position:number):T|null{
    if(position<0||position>=this.size)
      return null
    if(position===0){
      this.head=this.head.next
    }else{
      let prev:Node<T>|null=null
      let current =this.head
      let index=0
      while(index++<position){
        prev=current
        current=current.next
      }
      prev.next=current?.next ?? null
    }
    this.size--;
    return null;
  }
  //獲取某個位置的節點
  get(position:number):T|null{
     if(position>size||position<0) return null
    let current=this.head
    let index=0
    while(index++<position){
      current=current.next ?? null
    }
    return current.value??null
  }
  //更新某個節點的元素
  update(element:T,position:number):boolean{
    if(position>=size||position<0) return false
    let current=this.head
    let index=0
    while(index++<position&&current){
       current=current.next
    }
    current.value=element
    return true;
  }
  //根據元素尋找下標
  indexOf(element:T){
    let current=this.head
    let index=0;
    while(current){
      if(current.value===element){
        return index;
      }
      current=current.next
      index++
    }
    return -1;
  }
   remove(element: T): T | null {
    const first = this.indexOf(element);
    //方法一：
    // if (first > 0) {
    //   let prev: Node<T> | null = null;
    //   let current = this.head;
    //   let index = 0;
    //   while (index++ < first && current) {
    //     prev = current;
    //     current = current.next;
    //   }
    //   prev!.next = current!.next ?? null;
    //   return true;
    // } else {
    //   return false;
    // }
    return this.removeAt(first);
  }
  isEmpty(): boolean {
    return this.size === 0 ? true : false;
  }
}

面試題反轉鏈表（棧結構實現）#

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;
  }
}
function reverseList(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  //只有一個節點
  if (!head.next) return head;
  //使用棧結構
  let stack: ListNode[] = [];
  while (head) {
    stack.push(head);
    head = head.next;
  }
  const newhead: ListNode = stack.pop()!;
  let newheadCurrent = newhead;
  while (stack.length) {
    const node = stack.pop();
    newheadCurrent.next = node!;
    newheadCurrent = newheadCurrent!.next;
  }
  newheadCurrent.next = null; //因為最後一個元素指向null，而不是前一個，否則會循環引用
  return newhead;
}
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;
  }
}
function reverseList(head: ListNode | null): ListNode | null {
 if(head===null ||!head.next) return head
 let newHead:ListNode|null=null
  while(head){
    
    let current:ListNode |null=head.next
    //讓第一個節點指向null，
    head.next=newHead
    //向後推進，依次類推
    newHead=head
    head=current
  }
  return newHead;
}

反轉鏈表（遞歸）#

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;
  }
}
function reverseList(head: ListNode | null): ListNode | null {
  if(head===null || head.next===null) return head
  const newhead=reverseList(head.next??null)
  head.next.next=head
  head.next=null
  return newhead
}

哈希表#

哈希表是基於數組實現的，但是區別於數組有許多優勢：

優點#

1. 提供非常快速的查找、刪除、插入操作
2. 無論多少數據，插入、刪除的時間都接近常量 O (1)，實際上只需要幾行機械指令即可。
3. 哈希表的速度比樹還要快，基本可以瞬間查到目標元素。
4. 哈希表比樹結構更容易編寫。

缺點#

1. 哈希表的數據結構是無序的，所以沒有一種固定的方式來遍歷元素。
2. 通常情況下，哈希表的 key 不能重複，不能放置相同的 key, 用於保存不同的元素。

本質#

它的結構就是數組結構，但是它的神奇之處在於數組下標值的變換，這種變換我們可以使用哈希函數，通過哈希函數獲取 hashCode。

比如存儲 50000 本圖書信息，數組：複雜度 o (n)，順序查找下標值索引，當然，可以利用二分將複雜度降到 O (logn)，但是利用哈希函數，可以提前將每一項圖書的每一項獲取到對應的下標即索引值，這個函數規則可以由我們自己來制定，
比如每本書對應存儲字符串 "abc"，按照 ascii 編碼得到一個規則下標 = 97+98+99,=== 該數組的下標值。

顯而易見，這種存儲方式的重複率極高，因此方案 b 可以解決這個問題 幂的連乘
比如 “abc"=271^3+272^3......
但是這樣做，還有弊端，雖然保持了唯一性，但是極其浪費數組空間，比如 “zzzzzzzzzzzzzzzzzzz”, 需要分配天文數字的存儲空間，這是不科學的。

因此 鏈地址法和 開放地址法

對關鍵字 key 計算哈希函數，獲得散列地址。
查看該散列地址，如果為空，則直接插入。
如果不為空，則檢查該地址上的鏈表中是否存在相同 key 的元素。
如果存在，則修改內容。如果不存在，則在該鏈表頭部插入一個新的元素。
插入新元素時，需要創建結點，並將新結點插入鏈表頭部。
查找元素時，需要遍歷鏈表，逐一比對關鍵字。
鏈地址法解決了衝突，但查找效率較低，需要遍歷鏈表。平均查找長度約為 O (1+α),α 是鏈表長度。