JavaScript数据结构与算法

25次阅读
没有评论

共计 7736 个字符，预计需要花费 20 分钟才能阅读完成。

数组结构

参考：https://aboss.top/post/173/

栈结构

栈 (stack) 又名堆栈，是一种运算受限的线性表，限定仅在表尾进行插入和删除操作。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素称作进栈，从一个栈删除元素称作出栈。

特点：后进先出，即 Last in First out (LIFO)。

class Stack {#items = [] //# 符号声明私有属性，ES13 新特性

  pop() {return this.#items.pop() // 出栈
  }

  push(data) {return this.#items.push(data) // 进栈
  }

  peek() {return this.#items.at(-1) // 栈顶
  }

  isEmpty() {return this.#items.length === 0}

  size() {return this.#items.length}

  clear() {this.#items = []
  }

  toString() {return this.#items.join(" ")
  }
}

// 十进制转 2 8 16 进制
function convert(decNumber, base) {let remStack = new Stack()
  let number = decNumber
  let string = ""
  let baseString = "0123456789ABCDEF"

  while (number > 0) {remStack.push(number % base)
    number = Math.floor(number / base)
  }

  while (!remStack.isEmpty()) {string += baseString[remStack.pop()]
  }

  return string
}

convert(500, 16)

队列结构

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾（入队），进行删除操作的端称为队头（出队）。队列中没有元素时，称为空队列。

特点：先进先出，即 First in First out(FIFO)。

封装与应用

class Queue {#items = {}
  #lowCount = 0
  #count = 0

  dequeue() {if (this.isEmpty()) {return undefined}

    let res = this.#items[this.#lowCount]
    delete this.#items[this.#lowCount]
    this.#lowCount++
    return res // 出队
  }

  enqueue(data) {this.#items[this.#count] = data // 入队
    this.#count++
  }

  front() {return this.#items[this.#lowCount] // 队头
  }

  isEmpty() {return this.size() === 0
  }

  size() {return this.#count - this.#lowCount}

  clear() {this.#items = {}
    this.#count = 0
    this.#lowCount = 0
  }

  toString() {
    let str = ""
    for (let i = this.#lowCount; i < this.#count; i++) {str += `${this.#items[i]} `
    }

    return str
  }
}

// 击鼓传花游戏
function game(list, num) {let queue = new Queue()
  for (let i = 0; i < list.length; i++) {queue.enqueue(list[i])
  }

  while (queue.size() > 1) {for (let i = 0; i < num; i++) {queue.enqueue(queue.dequeue())
    }

    console.log(queue.dequeue(), " 淘汰了 ")
  }

  return queue.dequeue() + " 获胜 "}

game([" 张三 ", " 李四 ", " 王五 ", " 赵六 ", " 孙七 "], 7)

双端队列

class DeQueue {#items = {}
  #lowCount = 0 // 队头索引
  #count = 0

  removeFront() {if (this.isEmpty()) {return undefined}

    let res = this.#items[this.#lowCount]
    delete this.#items[this.#lowCount]
    this.#lowCount++

    return res
  }

  removeBack() {if (this.isEmpty()) {return}

    this.#count--
    const res = this.#items[this.#count]
    delete this.#items[this.#count]

    return res
  }

  addFront(data) {if (this.isEmpty()) {this.addBack(data)
    } else {if (this.#lowCount > 0) {
        this.#lowCount--
        this.#items[this.#lowCount] = data
      } else {
        // #lowCount=0
        for (let i = this.#count; i > 0; i--) {this.#items[i] = this.#items[i - 1]
        }
      }
    }
  }

  addBack(data) {this.#items[this.#count] = data
    this.#count++
  }

  peekFront() {return this.#items[this.#lowCount]
  }

  peekBack() {return this.#items[this.#count - 1]
  }

  isEmpty() {return this.size() === 0
  }

  size() {return this.#count - this.#lowCount}

  clear() {this.#items = {}
    this.#count = 0
    this.#lowCount = 0
  }

  toString() {
    let str = ""
    for (let i = this.#lowCount; i < this.#count; i++) {str += `${this.#items[i]} `
    }

    return str
  }
}

// 回文字符串检查
function test(str) {const lowstr = str.toLocaleLowerCase().split(" ").join("")
  let dequeue = new DeQueue()

  for (let i = 0; i < lowstr.length; i++) {dequeue.addBack(lowstr[i])
  }

  let isEqual = true
  while (dequeue.size() > 1) {if (dequeue.removeFront() != dequeue.removeBack()) {
      isEqual = false
      break
    }
  }

  return isEqual
}

test(" 上海自来水来自海上 ")

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点 (链表中每一个元素称为结点) 组成，结点可以在运行时动态生成。每个结点包括两个部分: 一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表的特点

  1. 插入、删除数据效率高 O(1)级别 (只需更改指针指向即可)，随机访问效率低 O(n) 级别(需要从链头至链尾进行遍历)
  2. 和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

单链表

每个节点只包含一个指针，即后继指针。

class Node {constructor(element) {
    this.element = element
    this.next = null
  }
}

class LinkedList {constructor() {
    this.count = 0
    this.head = null
  }

  push(element) {const node = new Node(element)

    if (this.head === null) {this.head = node} else {
      let current = this.head

      while (current.next !== null) {current = current.next}

      current.next = node
    }

    this.count++
  }

  getNodeAt(index) {if (index >= 0 && index < this.count) {
      let node = this.head
      for (let i = 0; i < index; i++) {node = node.next}

      return node
    }

    return
  }

  // 指定位置删除
  removeAt(index) {if (index >= 0 && index < this.count) {
      let current = this.head
      if (index === 0) {this.head = this.head.next} else {let previous = this.getNodeAt(index - 1)
        current = previous.next
        previous.next = current.next
      }

      this.count--
      return current.element
    }

    return
  }

  equalFn(a, b) {return JSON.stringify(a) === JSON.stringify(b)
  }

  indexOf(element) {
    let current = this.head
    for (let i = 0; i < index; i++) {if (this.equalFn(element, current.element)) {return i}
      current = current.next
    }

    return -1
  }

  // 指定元素删除
  remove(element) {const index = this.indexOf(element)
    return this.removeAt(index)
  }

  insert(element, index) {if (index >= 0 && index <= this.count) {const node = new Node(element)
      if (index === 0) {
        const current = this.head
        node.next = current
        this.head = node
      } else {const previous = this.getNodeAt(index - 1)
        const current = previous.next

        node.next = current
        previous.next = node
      }

      this.count++
      return true
    }

    return false
  }

  isEmpty() {return this.size() === 0
  }

  size() {return this.count}

  getHead() {return this.head}
}

// 回文字符串检查
function test(str) {const lowstr = str.toLocaleLowerCase().split(" ").join("")
  let sll = new LinkedList()

  for (let i = 0; i < lowstr.length; i++) {sll.push(lowstr[i])
  }

  let isEqual = true
  while (sll.size() > 1) {if (sll.removeAt(0) !== sll.removeAt(sll.size() - 1)) {
      isEqual = false
      break
    }
  }

  return isEqual
}

test(" 上海自来水来自海上 ")

击鼓传花游戏使用单链表：

// 击鼓传花游戏
function game(list, num) {let queue = new LinkedList()
  for (let i = 0; i < list.length; i++) {queue.push(list[i])
  }

  while (queue.size() > 1) {for (let i = 0; i < num; i++) {queue.push(queue.removeAt(0))
    }

    console.log(queue.removeAt(0), " 淘汰了 ")
  }

  return queue.removeAt(0) + " 获胜 "
}

game([" 张三 ", " 李四 ", " 王五 ", " 赵六 ", " 孙七 "], 7)

十进制转 2 8 16 进制：

// 十进制转 2 8 16 进制
function convert(decNumber, base) {let remStack = new LinkedList()
  let number = decNumber
  let string = ""
  let baseString = "0123456789ABCDEF"

  while (number > 0) {remStack.push(number % base)
    number = Math.floor(number / base)
  }

  while (!remStack.isEmpty()) {string += baseString[remStack.removeAt(remStack.size() - 1)]
  }

  return string
}

convert(500, 16)

双链表

class DoublyNode extends Node {constructor(element) {super(element)
    this.prev = null
  }
}

class DoublyLinkedList extends LinkedList {constructor() {super()
    this.tail = null
  }

  push(element) {const node = new DoublyNode(element)
    if (this.head === null) {
      this.head = node
      this.tail = node
    } else {
      this.tail.next = node
      node.prev = this.tail
      this.tail = node
    }

    this.count++
  }

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

  insert(element, index) {if (index >= 0 && index <= this.count) {const node = new DoublyNode(element)
      let current = this.head
      if (index === 0) {if (this.head === null) {
          this.head = node
          this.tail = node
        } else {
          node.next = this.head
          this.head.prev = node
          this.head = node
        }
      } else if (index === this.count) {
        current = this.tail
        current.next = node
        node.prev = current
        this.tail = node
      } else {const previous = this.getNodeAt(index - 1)
        current = previous.next

        node.next = current
        current.prev = node
        previous.next = node
        node.prev = previous
      }

      this.count++
      return true
    }

    return false
  }

  removeAt(index) {if (index >= 0 && index < this.count) {
      let current = this.head
      if (index === 0) {
        this.head = current.next
        if (this.count === 1) {this.tail = null} else {this.head.prev = null}
      } else if (index === this.count - 1) {
        current = this.tail
        this.tail = current.prev
        this.tail.next = null
      } else {let previous = this.getNodeAt(index - 1)
        current = previous.next
        previous.next = current.next
        current.next.prev = previous
      }

      this.count--
      return current.element
    }

    return
  }

  getHead() {return this.head}

  getTail() {return this.tail}
}

循环链表

循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针 (tail.next) 不是 undefined，而是指向第一个元素(head)。

class CircularLinkedList extends LinkedList {constructor() {super()
  }

  push(element) {const node = new Node(element)
    let current
    if (this.head === null) {this.head = node} else {current = this.getNodeAt(this.size() - 1)
      current.next = node
    }

    node.next = this.head
    this.count++
  }

  insert() {if (index >= 0 && index <= this.count) {const node = new Node(element)
      let current = this.head
      if (index === 0) {if (this.head === null) {
          this.head = node
          node.next = this.head
        } else {
          node.next = current
          this.head = node

          current = this.getNodeAt(this.size() - 1)
          current.next = this.head
        }
      } else {const previous = this.getNodeAt(index - 1)
        node.next = previous.next
        previous.next = node
      }

      this.count++
      return true
    }

    return false
  }

  removeAt(index) {if (index >= 0 && index < this.count) {
      let current = this.head
      if (index === 0) {if (this.size() === 1) {this.head = null} else {let last = this.getNodeAt(this.size() - 1)
          this.head = this.head.next
          last.next = this.head
        }
      } else {const previous = this.getNodeAt(index - 1)
        current = previous.next
        previous.next = current.next
      }

      this.count--
      return current.element
    }

    return
  }
}

正文完
post-qrcode
JavaScript
发表至： 编程
2023-08-29
 0
三毛
版权声明：本站原创文章，由 三毛 于2023-08-29发表，共计7736字。
转载说明：除特殊说明外本站文章皆由CC-4.0协议发布，转载请注明出处。
Python数据分析
网络基础知识
Python实现21点纸牌游戏
PHP字符串相关函数
评论（没有评论）