《学习Javascript数据结构和算法》--读书笔记

2021年11月28日

学习数据结构和算法十分重要。首要原因是数据结构和算法可以很高效地解决常见问题，这对你今后所写代码的质量至关重要（也包括性能；要是用了不恰当的数据结构或算法，很可能会产生性能问题）。其次，对于计算机科学，算法是最基础的概念。

第 4 章栈

栈是一种遵循后进先出原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，称作栈顶，另一端叫做栈底。栈也被用在编程语言的编译器和内存中保存变量、方法调用等，也被用于浏览器历史记录（浏览器的返回按钮）

基于 JavaScript 对象的 Stack 类

class Stack {
  constructor() {
    this.count = 0;
    this.items = {}; // 选择对象来保存栈中元素
  }

  // 入栈
  push(element) {
    this.items[this.count] = element;
    this.count++;
  }

  size() {
    return this.count;
  }

  isEmpty() {
    return this.count === 0;
  }

  // 出栈
  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

  peek() {
    //返回栈顶的元素
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }

  clear() {
    this.items = {};
    this.count = 0;
  }

  toString() {
    if (this.isEmpty()) {
      return "";
    }
    let objString = `${this.items[0]}`;
    for (let i = 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}

这里为什么使用对象来保存栈中元素？

因为在使用数组时，大部分方法的时间复杂度是 O(n)。
并且数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间。

保护数据结构内部元素

采用下划线命名约定，这种方式只是一种约定，并不能保护数据，而且只能依赖于使用我们代码的开发者所具备的常识。
ES2015 新增了一种叫作 Symbol 的基本类型，它是不可变的，可以用作对象的属性。因为 ES2015 新增的 Object.getOwnPropertySymbols 方法能够取到类里面声明的所有 Symbols 属性。也不能保护内部元素
有一种数据类型可以确保属性是私有的，这就是 WeakMap。采用这种方法，代码的可读性不强，而且在扩展该类时无法继承私有属性。

const items = new WeakMap();
class Stack {
  constructor() {
    items.set(this, []); // {2}
  }
  push(element) {
    const s = items.get(this); // {3}
    s.push(element);
  }
  pop() {
    const s = items.get(this);
    const r = s.pop();
    return r;
  }
  // 其他方法
}

典型应用场景进制转换

function decimalToBinary(num, base) {
  const arr = [];
  const digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  let res = "";
  if (base < 2 || base > 36) {
    return "";
  }
  while (num > 0) {
    arr.push(Math.floor(num % base)); // 把余数取整存入数组
    num = Math.floor(num / base); // 对商取整
  }
  while (arr.length > 0) {
    res += digits[arr.pop()]; // 反向输出数组
  }
  return res;
}

第 5 章队列和双端队列

队列是遵循先进先出原则的一组有序的项，队列在尾部添加新元素，并从顶部移除元素。新添加的元素必须排在队列的队尾

class Queue {
  constructor() {
    this.count = 0; // 控制队列的大小
    this.lowestCount = 0; // 追踪第一个元素
    this.items = {};
  }
  // 入队列
  enqueue(element) {
    // 添加到队尾
    this.items[this.count] = element;
    this.count++;
  }

  // 出队列
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    // 获取队头元素
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }

  //返回队列第一个元素
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }
  isEmpty() {
    return this.count === this.lowestCount;
  }
  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }
  size() {
    return this.count - this.lowestCount;
  }
  toString() {
    if (this.isEmpty()) {
      return "";
    }
    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}

Queue 类和 Stack 类非常类似。主要的区别在于 dequeue 方法和 peek 方法，这是由于先进先出和后进先出原则的不同所造成的。

双端队列

双端队列允许我们同时从前端和后端添加和删除元素的特殊队列

class Deque {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

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

  addBack(element) {
    this.items[this.count] = element;
    this.count++;
  }

  removeFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }

  removeBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

  peekFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }

  peekBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }

  isEmpty() {
    return this.count === this.lowestCount;
  }
  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }
  size() {
    return this.count - this.lowestCount;
  }
  toString() {
    if (this.isEmpty()) {
      return "";
    }
    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}

击鼓传花游戏

/**
 * @param {Array：参加游戏的人员} elementsList
 * @param {number：每次击鼓的次数} num
 */
function hotPotato(elementsList, num) {
  // 引入 queue.js 创建 Queue 实例
  const queue = new Queue();
  const elimitatedList = [];

  for (let i = 0; i < elementsList.length; i++) {
    // 把参加的人列入队列中
    queue.enqueue(elementsList[i]);
  }

  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      // 把队列的第一个人放入队尾循环队列
      queue.enqueue(queue.dequeue());
    }
    // 把淘汰的人放入 elimitatedList 数组中
    elimitatedList.push(queue.dequeue());
  }

  return {
    eliminated: elimitatedList, // 淘汰的人
    winner: queue.dequeue(), // 胜利者
  };
}
// 简易版
function hotPotato(arr, nums) {
  const disuse = [];
  while (arr.length > 1) {
    for (let i = 0; i < nums; i++) {
      arr.push(arr.shift());
    }
    disuse.push(arr.shift());
  }
  return arr[0];
}

第 6 章链表

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。链表就是线性表的链式存储方式。链表的内存是不连续的

链表基本操作方法有：

push(element)：向链表尾部添加一个新元素。
insert(element, position)：向链表的特定位置插入一个新元素。
getElementAt(index)：返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回 undefined。
remove(element)：从链表中移除一个元素。
indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。
removeAt(position)：从链表的特定位置移除一个元素。
isEmpty()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false。
size()：返回链表包含的元素个数，与数组的 length 属性类似。
toString()：返回表示整个链表的字符串。由于列表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。

class Node<T> {
  constructor(public element: T, public next?: Node<T>) {}
}
class LinkedList<T> {
  protected count = 0; // 存储链表中元素数量
  protected head: Node<T> | undefined; // 头指针

  push(element: T) {
    const node = new Node(element);
    let current: Node<T>;
    if (this.head) {
      current = this.head;
      // 遍历链表
      while (current.next && current.next !== null) {
        current = current.next;
      }
      // 将current的next指针指向新节点
      current.next = node;
    } else {
      this.head = node;
    }
    this.count++;
  }
  // 根据下标查找节点
  getElementAt(index: number) {
    if (index >= 0 && index < this.count) {
      let node = this.head;
      for (let i = 0; i < index && node !== null; i++) {
        node = node?.next;
      }
      return node;
    }
    return undefined;
  }
  //从链表中移除元素
  removeAt(index: number) {
    // 越界检查
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        //头节点
        this.head = current?.next;
      } else {
        // 中间节点
        const previous = this.getElementAt(index - 1); // 当前节点的前节点引用
        if (previous) {
          current = previous.next;
          // 跳过current节点 从而将其删除
          previous.next = current?.next;
        }
      }
      this.count--;
      return current?.element;
    }
    return undefined;
  }
  // 链表中间插入节点
  insert(element: T, index: number) {
    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.getElementAt(index - 1);
        if (previous) {
          const current = previous.next;
          node.next = current;
          previous.next = node;
        }
      }
      this.count++;
      return true;
    }
    return false;
  }
  // 返回一个元素的位置
  indexOf(element: T) {
    let current = this.head;
    for (let i = 0; i < this.count && current !== null; i++) {
      if (element === current?.element) {
        return i;
      }
      current = current?.next;
    }
    return -1;
  }
  // 从链表中移除元素
  remove(element: T) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }
  size() {
    return this.count;
  }
  isEmpty() {
    return this.size() === 0;
  }
  toString() {
    if (this.head === null) {
      return "";
    }
    let objString = `${this.head?.element}`;
    let current = this.head?.next;
    for (let i = 1; i < this.size() && current !== null; i++) {
      objString = `${objString},${current?.element}`;
      current = current?.next;
    }
    return objString;
  }
}

双向链表

双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接；而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素

class DoublyNode<T> extends Node<T> {
  constructor(
    public element: T,
    public next?: DoublyNode<T>,
    public prev?: DoublyNode<T>
  ) {
    super(element, next);
  }
}

class DoublyLinkedList<T> extends LinkedList<T> {
  protected head: DoublyNode<T> | undefined;
  protected tail: DoublyNode<T> | undefined;

  constructor() {
    super();
  }

  push(element: T) {
    const node = new DoublyNode(element);

    if (this.head == null) {
      this.head = node;
      this.tail = node; // NEW
    } else {
      // attach to the tail node // NEW
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }
    this.count++;
  }

  insert(element: T, index: number) {
    if (index >= 0 && index <= this.count) {
      const node = new DoublyNode(element);
      let current = this.head;

      if (index === 0) {
        if (this.head == null) {
          // NEW
          this.head = node;
          this.tail = node;
        } else {
          node.next = this.head;
          this.head.prev = node; // NEW
          this.head = node;
        }
      } else if (index === this.count) {
        // last item // NEW
        current = this.tail; // {2}
        current.next = node;
        node.prev = current;
        this.tail = node;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        node.next = current;
        previous.next = node;

        current.prev = node; // NEW
        node.prev = previous; // NEW
      }
      this.count++;
      return true;
    }
    return false;
  }

  removeAt(index: number) {
    if (index >= 0 && index < this.count) {
      let current = this.head;

      if (index === 0) {
        this.head = this.head.next; // {1}
        // if there is only one item, then we update tail as well //NEW
        if (this.count === 1) {
          // {2}
          this.tail = undefined;
        } else {
          this.head.prev = undefined; // {3}
        }
      } else if (index === this.count - 1) {
        // last item //NEW
        current = this.tail; // {4}
        this.tail = current.prev;
        this.tail.next = undefined;
      } else {
        current = this.getElementAt(index);
        const previous = current.prev;
        // link previous with current's next - skip it to remove
        previous.next = current.next; // {6}
        current.next.prev = previous; // NEW
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }

  indexOf(element: T) {
    let current = this.head;
    let index = 0;

    while (current != null) {
      if (element === current.element) {
        return index;
      }
      index++;
      current = current.next;
    }

    return -1;
  }

  getHead() {
    return this.head;
  }

  getTail() {
    return this.tail;
  }

  clear() {
    super.clear();
    this.tail = undefined;
  }

  toString() {
    if (this.head == null) {
      return "";
    }
    let objString = `${this.head.element}`;
    let current = this.head.next;
    while (current != null) {
      objString = `${objString},${current.element}`;
      current = current.next;
    }
    return objString;
  }

  inverseToString() {
    if (this.tail == null) {
      return "";
    }
    let objString = `${this.tail.element}`;
    let previous = this.tail.prev;
    while (previous != null) {
      objString = `${objString},${previous.element}`;
      previous = previous.prev;
    }
    return objString;
  }
}

第 7 章集合

集合是一组无序且唯一(没有重复的)的项组成的

class Set<T> {
  private items: any;
  constructor() {
    this.items = {}; // 这里用对象来实现
  }
  has(element: T) {
    return Object.prototype.hasOwnProperty.call(this.items, element);
  }
  add(element: T) {
    if (!this.has(element)) {
      this.items[element] = element; // 同时作为键和值保存，因为这样有利于查找该元素。
      return true;
    }
    return false;
  }
  delete(element: T) {
    if (this.has(element)) {
      delete this.items[element];
      return true;
    }
    return false;
  }
  clear() {
    this.items = {};
  }
  size() {
    return Object.keys(this.items).length;
  }
  values() {
    return Object.values(this.items);
  }
  // 并集
  union(otherSet: Set<T>) {
    const unionSet = new Set();
    this.values().forEach((value) => unionSet.add(value));
    otherSet.values().forEach((value) => unionSet.add(value));
    return unionSet;
  }
  // 交集
  intersection(otherSet: Set<T>) {
    const intersectionSet = new Set<T>();
    const values = this.values();
    const otherValues = otherSet.values();

    let biggerSet = values;
    let smallerSet = otherValues;

    if (otherValues.length - values.length > 0) {
      biggerSet = otherValues;
      smallerSet = values;
    }

    // 只需要遍历最少元素的集合
    smallerSet.forEach((value) => {
      if (biggerSet.includes(value)) {
        intersectionSet.add(value);
      }
    });

    return intersectionSet;
  }
  // 差集
  difference(otherSet: Set<T>) {
    const differenceSet = new Set<T>();
    this.values().forEach((value) => {
      if (!otherSet.has(value)) {
        differenceSet.add(value);
      }
    });
    return differenceSet;
  }
  // 子集
  isSubsetOf(otherSet: Set<T>) {
    if (this.size() > otherSet.size()) {
      return false;
    }
    return this.values().every((value) => otherSet.has(value));
  }
}

第 8 章字典和散列表

字典以[键，值]的形式存储元素，字典也称作映射，关联数组

class ValuePair<K, V> {
  constructor(public key: K, public value: V) {}

  toString() {
    return `[#${this.key}: ${this.value}]`;
  }
}
class Dictionary<K, V> {
  private table: { [key: string]: ValuePair<K, V> };

  constructor() {
    this.table = {};
  }
  private toStrFn(item: any): string {
    if (item === null) {
      return "NULL";
    } else if (item === undefined) {
      return "UNDEFINED";
    } else if (typeof item === "string" || item instanceof String) {
      return `${item}`;
    }
    return item.toString();
  }
  set(key: K, value: V) {
    if (key != null && value != null) {
      //由于 JavaScript 不是强类型的语言，我们不能保证键一定是字符串。
      //我们需要把所有作为键名传入的对象转化为字符串
      const tableKey = this.toStrFn(key);
      this.table[tableKey] = new ValuePair(key, value);
      return true;
    }
    return false;
  }

  get(key: K): V {
    const valuePair = this.table[this.toStrFn(key)];
    return valuePair == null ? undefined : valuePair.value;
  }

  hasKey(key: K) {
    return this.table[this.toStrFn(key)] != null;
  }

  remove(key: K) {
    if (this.hasKey(key)) {
      delete this.table[this.toStrFn(key)];
      return true;
    }
    return false;
  }

  values(): V[] {
    return this.keyValues().map(
      (valuePair: ValuePair<K, V>) => valuePair.value
    );
  }

  keys(): K[] {
    return this.keyValues().map((valuePair: ValuePair<K, V>) => valuePair.key);
  }

  keyValues(): ValuePair<K, V>[] {
    return Object.values(this.table);
  }

  forEach(callbackFn: (key: K, value: V) => any) {
    const valuePairs = this.keyValues();
    for (let i = 0; i < valuePairs.length; i++) {
      const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
      if (result === false) {
        break;
      }
    }
  }

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

  size() {
    return Object.keys(this.table).length;
  }

  clear() {
    this.table = {};
  }

  toString() {
    if (this.isEmpty()) {
      return "";
    }
    const valuePairs = this.keyValues();
    let objString = `${valuePairs[0].toString()}`;
    for (let i = 1; i < valuePairs.length; i++) {
      objString = `${objString},${valuePairs[i].toString()}`;
    }
    return objString;
  }
}

散列表（哈希表）

class ValuePair<K, V> {
  constructor(public key: K, public value: V) {}

  toString() {
    return `[#${this.key}: ${this.value}]`;
  }
}
class HashTable<K, V> {
  protected table: { [key: string]: ValuePair<K, V> };
  constructor() {
    this.table = {};
  }
  private toStrFn(item: any): string {
    if (item === null) {
      return "NULL";
    } else if (item === undefined) {
      return "UNDEFINED";
    } else if (typeof item === "string" || item instanceof String) {
      return `${item}`;
    }
    return item.toString();
  }
  // 散列函数
  private djb2HashCode(key: K) {
    const tableKey = this.toStrFn(key);
    let hash = 5381;
    for (let i = 0; i < tableKey.length; i++) {
      hash = hash * 33 + tableKey.charCodeAt(i);
    }
    return hash % 1013;
  }
  hashCode(key: K) {
    return this.djb2HashCode(key);
  }
  put(key: K, value: V) {
    if (key !== null && value !== null) {
      const hash = this.hashCode(key); // hash是索引
      this.table[hash] = new ValuePair(key, value); // 将键值对存入
      return true;
    }
    return false;
  }
  get(key: K) {
    const hash = this.hashCode(key);
    const valuePair = this.table[hash];
    return valuePair == null ? undefined : valuePair.value;
  }
  remove(key: K) {
    const hash = this.hashCode(key);
    const valuePair = this.table[hash];
    if (valuePair !== null) {
      delete this.table[hash];
      return true;
    }
    return false;
  }
  size() {
    return Object.keys(this.table).length;
  }
  getTable() {
    return this.table;
  }
  isEmpty() {
    return this.size() === 0;
  }
  clear() {
    this.table = {};
  }
  toString() {
    if (this.isEmpty()) {
      return "";
    }
    const keys = Object.keys(this.table);
    let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
    for (let i = 1; i < keys.length; i++) {
      objString = `${objString},{${keys[i]} => ${this.table[
        keys[i]
      ].toString()}}`;
    }
    return objString;
  }
}
const hash = new HashTable();
hash.put("Gandalf", "gandalf@email.com");
hash.put("John", "johnsnow@email.com");
hash.put("Tyrion", "tyrion@email.com");
console.log(hash.hashCode("Gandalf") + " - Gandalf");
console.log(hash.hashCode("John") + " - John");
console.log(hash.hashCode("Tyrion") + " - Tyrion");
console.log(hash.get("Gandalf")); // gandalf@email.com
console.log(hash.get("Loiane")); // 不存在于表中 返回undefined
console.log(hash.toString());

处理散列表中的冲突

处理冲突有几种方法：分离链接、线性探查和双散列法

第 9 章递归

递归是一种解决问题的方法，它从解决问题的各个小部分开始，直到解决最初的大问题。递
归通常涉及函数调用自身
每个递归函数都必须有基线条件，即一个不再递归调用的条件（停止点），以防
止无限递归。

迭代阶乘

function factorialIterative(number) {
  if (number < 0) return undefined;
  let total = 1;
  for (let n = number; n > 1; n--) {
    total = total * n;
  }
  return total;
}

递归阶乘

function factorial(n) {
  if (n === 1 || n === 0) {
    // 基线条件
    return 1;
  }
  return n * factorial(n - 1); // 递归调用
}

迭代求斐波那契数

function fibonacciIterative(n) {
  if (n < 1) return 0;
  if (n <= 2) return 1;
  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) {
    // n >= 2
    fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}

递归求斐波那契数

function fibonacci(n) {
  if (n < 1) return 0;
  if (n <= 2) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

记忆化斐波那契数

function fibonacciMemoization(n) {
  const memo = [0, 1];
  const fibonacci = (n) => {
    if (memo[n] != null) return memo[n];
    return (memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo));
  };
  return fibonacci;
}

原文链接: https://jesse121.github.io/blog/articles/2021/11/28.html

版权声明: 转载请注明出处.

前端之路

路漫漫其修远兮，吾将上下而求索

《学习Javascript数据结构和算法》--读书笔记

第 4 章栈

基于 JavaScript 对象的 Stack 类

保护数据结构内部元素

典型应用场景进制转换

第 5 章队列和双端队列

双端队列

第 6 章链表

双向链表

第 7 章集合

第 8 章字典和散列表

散列表（哈希表）

处理散列表中的冲突

第 9 章递归

迭代阶乘

递归阶乘

迭代求斐波那契数

递归求斐波那契数

记忆化斐波那契数

文章目录

第 4 章 栈

基于 JavaScript 对象的 Stack 类

保护数据结构内部元素

典型应用场景 进制转换

第 5 章 队列和双端队列

双端队列

第 6 章 链表

双向链表

第 7 章 集合

第 8 章 字典和散列表

散列表（哈希表）

处理散列表中的冲突

第 9 章 递归

迭代阶乘

递归阶乘

迭代求斐波那契数

递归求斐波那契数

记忆化斐波那契数

文章目录

第 4 章栈

典型应用场景进制转换

第 5 章队列和双端队列

第 6 章链表

第 7 章集合

第 8 章字典和散列表

第 9 章递归