JavaScript Data Structures and Algorithms

javascript数据结构与算法

数据结构是计算机为了高效地利用资源而组织数据的一种方式，数据结构与算法是解决一切编程问题的基础

TypeScript

interface

data type 数据类型

interface Person {
  name: string
  age: number
}

const printName = (person: Person) => {
  console.log(person.name)
}

implements 合约

interface Compareble {
  conpareTo(b): number
}

class MyObject implements Compareble {
  peivate age: number = 0
  
  compareTo(b): number {
    if (this.age === b.age) {
      return 0
    }
    return this.age > b.age ? 1 : -1
  }
}

T 泛型

控制接口传入的参数类型，表示泛型，用来控制比较相同的对象

interface Compareble<T> {
  conpareTo(b: T): number
}

class MyObject implements Compareble {
  peivate age: number = 0
  
  compareTo(b: MyObject): number {
    if (this.age === b.age) {
      return 0
    }
    return this.age > b.age ? 1 : -1
  }
}

Stack

栈是一种遵循LIFO（后进先出）规则的有序集合，新元素靠近栈顶，旧的元素靠近栈底

常用于浏览器历史记录

只能从栈顶获取或者删除元素

constructor() {
  this.count = 0
  this.items = {}
}

stack.push()
stack.pop()
stack.toString()

Queue

Queue 队列

队列是一种遵循FIFO（先进先出）规则的有序集合，新元素靠近栈底，旧的元素靠近栈顶

常用于排队、消息队列

只能从队列底移除元素队列顶添加元素

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

queue.enqueue()
queue.dequeue()
queue.peek()

Deque (double-ended-queue) 双端队列

双端队列是一种允许同时从前端和后端添加或移除元素的特殊队列

常用于计算机存储撤销操作

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

queue.addFront()
queue.addBack()
queue.removeFront()
queue.removeBack()

LinkedList

LinkedList 链表

链表存储有序元素的集合，每个元素由一个元素本身的节点和一个指向下一个元素的引用组成

相较于数组，再链表中添加或删除元素不需要移动其他元素

constructor(equalsFn = defaultEquals) {
  this.count = 0
  this.head = undefined
  this.equalsFn = equalsFn
}

linkedList.push(element)
linkedList.insert(element, index)
linkedList.removeAt(index)
linkedList.remove(element)
linkedList.indexOf(element)
linkedList.getElementAt(index)
linkedList.toString()

DoublyLinkedList 双向链表

双向链表是一种特殊的链表，在元素中的链接是双向的，一个指向前一项元素，一个指向下一个元素

双向链表提供了两种迭代方式，从前向后或从后向前

exptends LinkedList

constructor(equalsFn = defaultEquals) {
  super(equalsFn)
  this.tail = undefined
}

doublyLinkedList.insert(element, index)
doublyLinkedList.removeAt(index)

CircularLinkdList 循环链表

双向链表是一种特殊的链表，最后一个元素指向下一个元素的指针不是undefined，而是指向第一个元素

循环链表与双向链表相同，可以提供两种迭代方式

exptends LinkedList

constructor(equalsFn = defaultEquals) {
  super(equalsFn)
}

doublyLinkedList.insert(element, index)
doublyLinkedList.removeAt(index)

Set

集合是一个由无序且唯一的项组成的，集合是一种不允许重复的顺序数据结构。

constructor() {
  this.items = {}
}

set.add(element)
set.delete(element)
set.has(element)
set.clear()
set.size()
set.values()

集合运算

union 并集

const arrA = []
const arrB = []

const result = new Set([...arrA, ...arrB])

intersection 交集

const setA = new Set()
const setB = new Set()

const result = new Set([...setA].filter(x => setB.has(x)))

difference 差集

const setA = new Set()
const setB = new Set()

const result = new Set([...setA].filter(x => !setB.has(x)))

Graph

图是一组用边连接的顶点，从数据结构的角度来说，有多种表示图的方式，根据实际问题进行选择，常用的包括邻接矩阵和邻接表两种

邻接矩阵

用二维数组来表示顶点之间的连接，如果索引为i的节点和索引为j的节点相邻则array[i][j] = 1否则 = 0

	A	B	C	D	E	F	G	H
A	0	1	1	1	0	0	0	0
B	1	0	0	1	1	0	0	0
C	1	0	0	1	0	0	1	0
D	1	0	1	0	0	1	1	0
E	0	1	0	0	0	0	0	1
F	0	1	0	1	0	0	0	0
G	0	0	1	1	0	0	0	0
H	0	0	0	0	1	0	0	0

邻接表

由图中每个顶点的相邻点列表组成，存在多种方式实现，包括但不限于数组，链表等。邻接表可能对大多数问题来说都是更好的选择。

A => B C D

B => A D E F

C => A D G

D => A B C F G

E => B

F => B D

G => C D

H => E

 constructor(isDirected = false) {
   // 是否有向
   this.isDirected = isDirected
   // 顶点列表
   this.vertices = [];
   // 邻接表
   this.adjList = new Map();
}

graph.addVertex(v)
graph.addEdge(v, w)

	A	B	C	D	E	F	G	H
A	0	1	1	1	0	0	0	0
B	1	0	0	1	1	0	0	0
C	1	0	0	1	0	0	1	0
D	1	0	1	0	0	1	1	0
E	0	1	0	0	0	0	0	1
F	0	1	0	1	0	0	0	0
G	0	0	1	1	0	0	0	0
H	0	0	0	0	1	0	0	0

	A	B	C	D	E	F	G	H
A	0	1	1	1	0	0	0	0
B	1	0	0	1	1	0	0	0
C	1	0	0	1	0	0	1	0
D	1	0	1	0	0	1	1	0
E	0	1	0	0	0	0	0	1
F	0	1	0	1	0	0	0	0
G	0	0	1	1	0	0	0	0
H	0	0	0	0	1	0	0	0

tmg0 / data-structures Goto Github PK

data-structures's Introduction