数据结构
数组结构
- 是一种线性结构
- 可以在数组的任意位置插入和删除数组
栈结构
- 一种受限的线性表，只允许在表的一端进行插入删除操作，这一端被称为栈顶，另一端称为栈底
- 后进先出（LIFO Last In First Out）
- 栈的封装
1.基于数组
function Stack() {
this.items = []
}
Stack.prototype.push = function (element) {
this.items.push(element)
}
Stack.prototype.pop = function () {
return this.items.pop()
}
Stack.prototype.peek = function () {
return this.items[this.items.length - 1]
}
Stack.prototype.isEmpty = function () {
return this.items.length === 0
}
Stack.prototype.size = function () {
return this.items.length
}
Stack.prototype.toString = function () {
let str = ''
for (let i = 0;i < this.items.length;i++){
str += this.items[i]
}
return str
}
队列结构
- 一种受限的线性表，只允许在表的前端进行删除操作，在表的后端进行插入操作
- 先进先出（FIFO First In First Out）
- 队列的封装
1.基于数组
function Queue() {
this.items = []
}
Queue.prototype.enqueue = function (element) {
this.items.push(element)
}
Queue.prototype.dequeue = function () {
return this.items.shift()
}
Queue.prototype.front = function () {
return this.items[0]
}
Queue.prototype.isEmpty = function () {
return this.items.length === 0
}
Queue.prototype.size = function () {
return this.items.length
}
Queue.prototype.toString = function () {
let str = ''
for (let i = 0;i < this.items.length;i++){
str += this.items[i]
}
return str
}
面试题：几个朋友一起玩一个游戏，围成一个圈，开始数数，数到规定数字的人自动淘汰，最后剩下的这个人会获得胜利，请问最后剩下的是原来在哪一个位置上的人
function passGame(nameList,num) { //nameList:玩游戏的人，num:规定的数字
const queue = new Queue()
//将nameList的每个人依次放入队列中
for (let i = 0;i < nameList.length;i++){
queue.enqueue(nameList[i])
}
//直到队列中的人数为1才停止
while (queue.size() > 1){
//开始数数，数到num之前的人都安全，依次从前端出来到队列的后端排队
for (let i = 0;i < num - 1;i++){
queue.enqueue(queue.dequeue())
}
//数到数字num，删除
queue.dequeue()
}
const winner = queue.front()
return nameList.indexOf(winner)
}
优先级队列
在插入一个元素的时候会考虑该数据的优先级，与队列中其他数据的优先级进行比较，比较完成后，可以得出该数据在队列中的正确位置
封装优先级队列的插入方法，其它方法与普通队列一样
function PriorityQueue() {
this.items = []
//内部再声明一个构造函数来表示队列元素的值和优先级
function QueueElement(element,priority) {
this.element = element
this.priority = priority
}
//插入方法
PriorityQueue.prototype.enqueue = function (element,priority) {
//创建queueElement实例
const queueElement = new QueueElement(element,priority)
//如果是首次插入不需要比较优先级直接插入
if (this.items.length === 0){
this.items.push(queueElement)
}else {
//设置元素是否插入得标志
let flag = false
//插入元素跟队列中元素比较优先级
for (let i = 0;i<this.items.length;i++){
if (queueElement.priority<this.items[i].priority){
this.items.splice(i,0,queueElement)
flag = true
break
}
}
//循环结束，如果元素还没找到正确位置，就放到末尾
if (!flag){
this.items.push(queueElement)
}
}
}
}
链表
链表和数组一样，可以用于存储一系列的元素，链表中的每一个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。
链表和数组的区别
1.数组的创建需要申请一段连续的内存空间，并且大小是固定的，当当前数组容量不能满足需求时，需要进行扩容（申请一个更大的数组，然后将原数组中的元素复制过去）；而链表中的元素在内存中不必是连续的空间，不用在创建时就确定大小，并且大小可以无限的延伸下去。
2.在数组的开头或中间位置插入删除元素的成本很高，因为需要进行大量元素的位移；链表在插入和删除数据时，时间复杂度可以到O（1），相对数组，效率高很多。
3.数组可以通过下标直接访问元素，而链表访问任何一个位置的元素时，都需要从头开始，一个一个访问。
封装单向链表
//封装单向链表
function LinkedList(){
this.head = null
this.length = 0
//元素节点构造函数
function Node(data) {
this.data = data
this.next = null
}
//append方法：向链表的末尾插入元素
LinkedList.prototype.append = function (data) {
//1.创建一个元素节点实例
const node = new Node(data)
//2.判断是不是首次插入
if (this.length === 0){
//2.1首次插入，将head指针指向该元素节点
this.head = node
}else {
//2.2不是首次插入，需要找到最后一个元素节点，将最后一个元素节点的指针指向该元素节点
let current = this.head
while (current.next){
current = current.next
}
//2.3找到最后一个元素节点，执行操作
current.next = node
}
//3.插入元素后，更新length
this.length++
}
//toString方法：将链表中的数据以字符串的方式返回
LinkedList.prototype.toString = function () {
let str = ''
let current = this.head
while (current){
str += current.data + ' '
current = current.next
}
return str
}
//insert方法：在指定位置插入数据
LinkedList.prototype.insert = function (position,data) {
//1.判断position是否越界
if (position<0 || position>this.length){
return false
}
//2.创建元素节点
const node = new Node(data)
//3.判断是不是插入到头部
if (position === 0){
//3.1插入到头部,将node元素的指针指向原来的head指针指向的元素节点，再把head指向node
node.next = this.head
this.head = node
}else{
//3.2其他情况，找到对应的位置，将node的指针指向当前位置的元素，前一个位置元素指针指向node
let index = 0
let current = this.head
let previous = null
while (index < position){
previous = current
current = current.next
index++
}
//3.3找到当前位置元素节点，将node指针指向它
node.next = current
//3.4找到前一个元素节点，将指针指向node
previous.next = node
}
//4.length+1
this.length++
}
//get方法：获取指定位置的元素
LinkedList.prototype.get = function (position) {
//1.position越界判断
if (position<0 || position>=this.length) return null
//2.取对应位置元素
let index = 0;
let current = this.head
while (index++ < position){
current = current.next
}
return current.data
}
//indexOf方法：返回指定元素所在链表中的位置，如果没有该元素则返回-1
LinkedList.prototype.indexOf = function (data) {
//1.循环链表，找到该元素
let index = 0
let current = this.head
while (index < this.length && current.data !== data){
current = current.next
index++
}
return current?index:-1
}
//update方法：修改指定位置的元素
LinkedList.prototype.update = function (position,newData) {
//1.越界判断
if (position<0 || position >= this.length) return false
//2.查找元素节点，替换data
let index = 0
let current = this.head
while (index++ < position){
current = current.next
}
current.data = newData
}
//removeAt方法：移除链表中指定位置的元素，并返回该元素
LinkedList.prototype.removeAt = function (position) {
//1.越界判断
if (position<0 || position >= this.length) return false
let current = this.head
//2.判断是否删除第一个元素
if (position === 0){
//2.1删除第一个元素，将head指向其下一个元素
this.head = current.next
}else {
//2.2找到要删除的元素，将其前一个元素的指针指向其后一个元素
let index = 0
let previous = null
while (index < position){
previous = current
current = current.next
index ++
}
previous.next = current.next
}
//3.长度减一
this.length--
return current.data
}
//remove方法：移除链表中指定的元素
LinkedList.prototype.remove = function (data) {
const position = this.indexOf(data)
return this.removeAt(position)
}
//isEmpty方法
LinkedList.prototype.isEmpty = function () {
return this.length === 0
}
//size方法
LinkedList.prototype.size = function () {
return this.length
}
}
双向链表
一个元素节点既有指向其前一个元素节点的指针，也有指向其后一个元素节点的指针
封装双向链表
//封装双向链表
function DoublyLinkedList() {
this.head = null
this.tail = null
this.length = 0
function Node(data) {
this.data = data
this.prev = null
this.next = null
}
//append方法：向链表的末尾插入元素
DoublyLinkedList.prototype.append = function (data) {
//1.创建元素节点
const node = new Node(data)
//2.判断是否是首次插入
if (this.length === 0){
this.head = node
this.tail = node
}else {
node.prev = this.tail
this.tail.next = node
this.tail = node
}
//3.length+1
this.length++
}
//toString方法：从前往后遍历转为字符串
DoublyLinkedList.prototype.toString = function(){
return this.backwardString()
}
//backwardString方法：从前往后遍历转为字符串
DoublyLinkedList.prototype.backwardString = function () {
let resultStr = ''
let current = this.head
while (current){
resultStr += current.data + ' '
current = current.next
}
return resultStr
}
//forwardString方法：从后往前遍历转为字符串
DoublyLinkedList.prototype.forwardString = function () {
let resultStr = ''
let current = this.tail
while (current){
resultStr += current.data + ' '
current = current.prev
}
return resultStr
}
//insert方法：在指定位置插入数据
DoublyLinkedList.prototype.insert = function (position,data) {
//1.position越界判断
if (position < 0 || position > this.length) return false
//2.创建元素节点
const node = new Node(data)
//3.判断是不是首次插入
if (this.length === 0){
//3.1首次插入，将head和tail指向该元素节点
this.head = node
this.tail = node
}else{
//3.2判断是否插入到头部
if (position === 0){
//插入到头部，将插入元素next指向原头部元素，原头部元素prev指向插入元素，head指向插入元素
node.next = this.head
this.head.prev = node
this.head = node
//3.3判断是否插入到尾部
}else if (position === this.length){
//插入到尾部，将插入元素prev指向原尾部元素，原尾部元素next指向插入元素，tail指向插入元素
node.prev = this.tail
this.tail.next = node
this.tail = node
}else {
//3.4其他情况，将当前位置元素的前一个元素的next指向插入元素，插入元素的prev指向前一个元素,
//插入元素的next指向当前位置元素，当前元素的prev指向插入元素
let index = 0
let current = this.head
while (index++ < position){
current = current.next
}
current.prev.next = node
node.prev = current.prev
node.next = current
current.prev = node
}
}
//4.length+1
this.length++
}
//get方法：获取指定位置的元素
DoublyLinkedList.prototype.get = function (position) {
//1.越界判断
if (position < 0 || position >= this.length) return null
let index = 0
let current = this.head
//如果position <= this.length / 2 从前往后遍历
if (position <= this.length / 2){
//2.找到指定位置元素并返回
while (index++ < position){
current = current.next
}
}else {
//如果position > this.length / 2 从后往前遍历
index = this.length - 1
current = this.tail
while (index-- > position){
current = current.prev
}
}
return current.data
}
//indexOf方法：返回指定元素所在链表中的位置，如果没有该元素则返回-1
DoublyLinkedList.prototype.indexOf = function (data) {
let index = 0
let current = this.head
while (index < this.length && current.data !== data){
current = current.next
index++
}
return current?index:-1
}
//update方法：修改指定位置的元素
DoublyLinkedList.prototype.update = function (position,newData) {
//1.越界判断
if (position < 0 || position >= this.length) return false
//2.找到指定位置元素并修改
let index = 0
let current = this.head
while (index++ < position){
current = current.next
}
current.data = newData
}
//removeAt方法：移除链表中指定位置的元素，并返回该元素
DoublyLinkedList.prototype.removeAt = function (position) {
//1.越界判断
if (position < 0 || position >= this.length) return null
let current = this.head
// 2.判断是否只有一个元素
if (this.length === 1) {
this.head = null
this.tail = null
//3.判断是否删除头部元素
}else if (position === 0){
//将head指向后一个元素，后一个元素的prev指向null
current.next.prev = null
this.head = current.next
//4.判断是否删除尾部元素
}else if (position === this.length - 1){
//将tail指向前一个元素，前一个元素的next指向null
current = this.tail
current.prev.next = null
this.tail = current.prev
}else { //5.其他情况
//5.1.找到该位置元素
let index = 0
while (index++ < position){
current = current.next
}
//5.2.将该位置元素的前一个元素的next指向该位置元素的后一个元素，后一个元素的prev指向前一个元素
current.prev.next = current.next
current.next.prev = current.prev
}
//6.length-1
this.length--
//7.返回该元素
return current.data
}
//remove方法：移除链表中指定的元素
DoublyLinkedList.prototype.remove = function (data) {
const position = this.indexOf(data)
return this.removeAt(position)
}
//isEmpty方法
DoublyLinkedList.prototype.isEmpty = function () {
return this.length === 0
}
//size方法
DoublyLinkedList.prototype.size = function () {
return this.length
}
//getHead方法：获取链表的第一个元素
DoublyLinkedList.prototype.getHead = function () {
return this.head.data
}
//getTail方法：获取链表的最后一个元素
DoublyLinkedList.prototype.getTail = function () {
return this.tail.data
}
}
集合
集合通常由一组无序的，不能重复的元素组成
（ES6中已经包含了Set，可以直接使用）
封装集合
//封装集合
function Set(){
this.items = {}
//add方法：向集合中添加新的元素
Set.prototype.add = function (value) {
if (this.has(value)) return false
this.items[value] = value
return true
}
//has方法：如果集合中有该元素，返回true，否则返回false
Set.prototype.has = function (value) {
return this.items.hasOwnProperty(value)
}
//remove方法：从集合中删除一个元素
Set.prototype.remove = function (value) {
if (!this.has(value)) return false
delete this.items[value]
return true
}
//clear方法：移除集合中的所有元素
Set.prototype.clear = function () {
this.items = {}
}
//size方法：返回集合中所有元素的个数
Set.prototype.size = function () {
return Object.keys(this.items).length
}
//values方法：返回包含所有元素的数组
Set.prototype.values = function () {
return Object.values(this.items)
}
//集合间的操作
//并集
Set.prototype.union = function (anotherSet) {
//1.创建一个新的集合
const unionSet = new Set()
//2.将当前集合中的所有数据添加到unionSet中
let values = this.values()
for (let i = 0;i < values.length;i++){
unionSet.add(values[i])
}
//3.将anotherSet中不重复的元素添加到unionSet中
values = anotherSet.values()
for (let i = 0;i < values.length;i++){
unionSet.add(values[i])
}
//4.返回unionSet
return unionSet
}
//交集
Set.prototype.intersection = function (anotherSet) {
//1.创建交集
const intersection = new Set()
//2.遍历集合中的元素是否同时存在于anotherSet中，如果存在，则添加
const values = this.values()
for (let i = 0;i < values.length;i++){
if (anotherSet.has(values[i])){
intersection.add(values[i])
}
}
//3.返回交集
return intersection
}
//差集 A-B
Set.prototype.subtraction = function (anotherSet) {
//1.创建差集
const subtraction = new Set()
//2.遍历A中元素，如果不存在于B中，则添加到新集合
const values = this.values()
for (let i = 0;i < values.length;i++){
if (!anotherSet.has(values[i])){
subtraction.add(values[i])
}
}
//3.返回交集
return subtraction
}
//判断集合A是否是集合B的子集
Set.prototype.isSubSet = function (anotherSet) {
//循环A集合中所有元素，只要有一个不再集合B中就返回false，否则返回true
const values = this.values()
for (let i = 0;i < values.length;i++){
if (!anotherSet.has(values[i])) return false
}
return true
}
}
字典（Map）
字典是由一一对应的键(key)值(value)对组成，key是不允许重复的，value允许重复,并且key是无序的
封装字典
// 封装字典结构
function Dictionary() {
//属性
this.items = {}
//方法
//set方法：向字典中添加键值对
Dictionary.prototype.set = function (key,value) {
this.items[key] = value
}
//has方法：判断字典中是否有某个key
Dictionary.prototype.has = function (key) {
return this.items.hasOwnProperty(key)
}
//remove方法：从字典中移除元素
Dictionary.prototype.remove = function (key) {
if (!this.has(key)) return false
delete this.items[key]
return true
}
//get方法：根据key值获取value
Dictionary.prototype.get = function (key) {
return this.has(key)?this.items[key]:undefined
}
//keys方法：获取所有的key
Dictionary.prototype.keys = function () {
return Object.keys(this.items)
}
//values方法：获取所有的方法
Dictionary.prototype.values = function () {
return Object.values(this.items)
}
//size方法：获取字典的元素个数
Dictionary.prototype.size = function () {
return this.keys().length
}
//clear方法：清除字典
Dictionary.prototype.clear = function () {
this.items = {}
}
}
哈希表
通过哈希函数将字符串转为下标值，通过下标值查找操作数据的效率就会变得很高
哈希表通常是基于数组进行实现的，但是相对数组又有很多优势
- 它可以提供非常快速的插入-删除-查找操作
- 哈希表的速度比树还要快，基本可以瞬间查找到想要的元素
- 哈希表相对于树来说编码要容易很多
哈希表相对于数组的一些不足 - 哈希表中的数据是没有顺序的，所以不能以一种固定的方式（比如从小到大）来遍历其中的元素
- 通常情况下，哈希表中的key是不允许重复的
哈希化：将大数字转化成数组范围内下标
哈希函数：将字符串转成大数字，大数字再进行哈希化的代码实现
哈希表：最终将数据插入到的这个数组，对整个结构的封装
经过哈希化后的下标值可能会发生重复，这种情况称为冲突
解决冲突的方法：
链地址法（拉链法）
每个数组单元中存储的不再是单个数据，而是一个数组或链表，一旦发现重复，将重复的元素插入到数组或链表的首端或者末端。当查询时，先根据哈希化后的下标值找到相应的位置，再取出该位置的链表，依次查询需要查找的数据。
开放地址法
寻找空白的位置来放置冲突的数据项
寻找空白位置的三种方法
- 线性探测
线性的查找空白单元
插入：
在插入时，如果发现该位置已有数据，就从index+1开始依次向后查找空的位置来存放该数据
查询：
查询经过哈希化得到的index位置的数据是否是要找的数据，如果是就返回，如果不是,从index+1开始依次向后查找，当查询到空位置时就停止，说明没有该数据
删除：
跟插入查询比较类似，但是删除一个数据项时，不能把该位置元素内容设为null（否则，查询操作时可能会出现未查找到该元素就停止的错误）可以将它进行特殊处理（比如说设为-1）当我们看到-1时就知道查询操作要继续，可以在该位置插入数据
线性探测的问题：聚集
聚集就是连续填充单元，会影响哈希表的性能，因为在插入重复数据的时候，会发现连续的单元都不能用来存放，需要探测很长的距离。 - 二次探测
对线性探测的优化，主要优化的是探测的步长，比如从下标值x开始，x+12,x+22...，这样就可以一次性探测比较长的距离，避免了聚集带来的影响
二次探测的问题：
比如我们连续插入的是22-132-82-92-112，他们依次累加的时候步长是相同的，会造成步长不一的一种聚集，还是会影响效率（但这种可能性比连续的数字小） - 再哈希法
为了解决线性探测和二次探测带来的问题
把大数字用另外一个哈希函数再做一次哈希化，用这次哈希化的结果作为步长
第二次哈希化需要具备如下特点：
1.和第一个哈希函数不同
2.不能输出为0，否则每次探测都是原地踏步，算法进入死循环
计算机专家已经设计出一种工作很好的哈希函数
链地址法封装哈希表
function HashTable() {
this.storage = [] //存放数据
this.count = 0 //数据个数
this.limit = 7 //哈希表容量：最好为质数，这样数据能更均匀分布
//哈希函数
HashTable.prototype.hashFunc = function (str) {
//1.定义hashCode
let hashCode = 0
//2.霍拉算法，将字符串转为较大的数字hashCode
//str.charCodeAt(i):将字符转为unicode编码
for (let i = 0;i < str.length;i++){
hashCode = 37 * hashCode + str.charCodeAt(i)
}
//3.将hashCode转为数组范围内下标值返回
return hashCode % this.limit
}
//put方法：插入&修改数据
HashTable.prototype.put = function (key,value) {
//1.根据key获取索引值
const index = this.hashFunc(key)
//2.判断该位置是否为空，如果是需要在该位置创建数组容器
let bucket = this.storage[index]
if (bucket === null){
bucket = []
this.storage[index] = bucket
}
//3.判断是插入操作还是修改操作
for (let i = 0;i < bucket.length;i++){
if (bucket[i][0] === key){
//3.1修改操作
bucket[i][1] = value
return
}
}
//3.2插入操作
//3.2.1创建一个数组存放插入数据
const tuple = [key,value]
//3.2.2将数据存放到单元数组容器中
bucket.push(tuple)
//3.2.3 数据个数加一
this.count++
//判断是否需要扩容，当loadFactor>0.75时就需要扩容
if (this.count > this.limit * 0.75){
const newSize = this.limit * 2
this.resize(this.getPrime(newSize))
}
}
//get方法：获取数据
HashTable.prototype.get = function (key) {
//1.根据key获取索引值
const index = this.hashFunc(key)
//2.判断当前索引位置是否有值，如果没有返回null，如果有遍历查找
const bucket = this.storage[index]
if (bucket === null){
return null
}
for (let i = 0;i < bucket.length;i++){
const tuple = bucket[i]
if (tuple[0] === key){
return tuple[1]
}
}
//3.如果遍历完数组容器还没找到，就返回null
return null
}
//remove方法：删除数据
HashTable.prototype.remove = function (key) {
//1.根据key获取对应的下标值
const index = this.hashFunc(key)
//2.根据index获取该位置的数组容器
const bucket = this.storage[index]
//3.如果bucket不存在，返回null
if (bucket === null) return null
//4.如果存在，线性查找并删除
for (let i = 0;i < bucket.length;i++){
const tuple = bucket[i]
if (tuple[0] === key){
bucket.splice(i,1)
this.count--
//判断是否需要缩容，当loadFactor < 0.25时就需要缩容
if (this.count < this.limit * 0.25){
const newSize = Math.floor(this.limit / 2)
this.resize(this.getPrime(newSize))
}
return tuple[1]
}
}
//5.如果还是没有找到，就返回null
return null
}
//其他方法
//判断哈希表是否为空
HashTable.prototype.isEmpty = function () {
return this.count === 0
}
//获取哈希表中元素的个数
HashTable.prototype.size = function () {
return this.count
}
//哈希表修改容量的方法
HashTable.prototype.resize = function (newLimit) {
//1.定义一个变量指向原哈希表数据
const oldStorage = this.storage
//2.重置当前哈希表属性
this.storage = []
this.count = 0
this.limit = newLimit
//3.遍历原哈希表中的数据，存放到新的哈希表中
for (let i = 0;i < oldStorage.length;i++){
const bucket = oldStorage[i]
//如果bucket为空，跳出本次循环
if (bucket === null) continue
//如果存在bucket，遍历bucket中的数据
for (let j = 0;j < bucket.length;j++){
const tuple = bucket[i]
this.put(tuple[0],tuple[1])
}
}
}
//判断一个数是否是质数
HashTable.prototype.isPrime = function (num) {
/**质数：在大于1的自然数中，只能被1和自己整除的数
* 一个数如果能被因式分解，那么分解得到的两个数，一定是一个大于等于这个数开平方，一个小于等于这个数开平方
* 所以我们判断一个数是否是质数时，只需要判断从2到这个数的平方根是否能整除这个数就行了
* */
const sqrt = Math.floor(Math.sqrt(num))
for (let i = 2;i <= sqrt;i++){
if (num % i === 0){
return false
}
}
return true
}
//获取质数的方法
HashTable.prototype.getPrime = function (num) {
while (!this.isPrime(num)){
num++
}
return num
}
}
树
树是非线性的，可以表示一对多的关系
树的常用术语
二叉树
- 完美二叉树
- 完全二叉树
- 二叉搜索树
封装二叉搜索树
//封装二叉搜索树
function BinarySearchTree() {
//定义指向根节点的索引
this.root = null
//节点构造函数
function Node(key,value) {
this.key = key
this.value = value
this.left = null
this.right = null
}
//insert方法：插入数据
BinarySearchTree.prototype.insert = function (key,value) {
//1.创建新节点
const newNode = new Node(key,value)
//2.判断是否存在根节点
if (this.root === null){
this.root = newNode
}else {
this.insertNode(this.root,newNode)
}
}
//内部使用的比较节点并插入的递归方法
BinarySearchTree.prototype.insertNode = function (node,newNode) {
if (newNode.key < node.key){ //向左查找
if (node.left === null){
//如果左子节点不存在，就插入
node.left = newNode
}else {
//如果左子节点存在，再进行递归比较
this.insertNode(node.left,newNode)
}
}else { //向右查找
if (node.right === null){
node.right = newNode
}else {
this.insertNode(node.right,newNode)
}
}
}
//树的遍历方法
//1.先序遍历
BinarySearchTree.prototype.preOrderTraversal = function (handler) {
this.preOrderTraversalNode(this.root,handler)
}
//内部调用的先序遍历的递归方法
BinarySearchTree.prototype.preOrderTraversalNode = function (node,handler) {
//判断节点是否存在
if (node !== null){
//处理节点
handler(node.value)
//遍历左子节点
this.preOrderTraversalNode(node.left,handler)
//遍历右子节点
this.preOrderTraversalNode(node.right,handler)
}
}
//2.中序遍历
BinarySearchTree.prototype.midOrderTraversal = function (handler) {
this.midOrderTraversalNode(this.root,handler)
}
//中序遍历的递归方法
BinarySearchTree.prototype.midOrderTraversalNode = function (node,handler) {
//1.判断该节点是否存在
if (node !== null){
//中序遍历左子树
this.midOrderTraversalNode(node.left,handler)
//处理该节点
handler(node.value)
//中序遍历右子树
this.midOrderTraversalNode(node.right,handler)
}
}
//3.后序遍历
BinarySearchTree.prototype.postOrderTraversal = function (handler) {
this.postOrderTraversalNode(this.root,handler)
}
//后序遍历的递归方法
BinarySearchTree.prototype.postOrderTraversalNode = function (node,handler) {
if (node !== null){
//后序遍历左子树
this.postOrderTraversalNode(node.left,handler)
//后序遍历右子树
this.postOrderTraversalNode(node.right,handler)
//处理节点
handler(node.value)
}
}
//min方法：查找最小值
BinarySearchTree.prototype.min = function() {
let node = this.root
while(node.left !== null){
node = node.left
}
return node.value
}
//max方法：查找最大值
BinarySearchTree.prototype.max = function() {
let node = this.root
while(node.right !== null){
node = node.right
}
return node.value
}
//search方法：查找元素节点，如果存在返回value，如果不存在返回false
BinarySearchTree.prototype.search = function (key) {
let node = this.root
while (node && node.key !== key){
if (node.key < key){
node = node.right
}else {
node = node.left
}
}
return node?node.value:false
}
//remove方法：删除元素节点
BinarySearchTree.prototype.remove = function (key) {
//1.通过key查找到该节点
let current = this.root
let parentNode = null //定义父节点
let isLeftChild = true //定义该节点是否是左子节点
while (current){
if (current.key < key){
parentNode = current
current = current.right
isLeftChild = false
}else if (current.key > key){
parentNode = current
current = current.left
isLeftChild = true
}else {
//2.找到该节点
//2.1如果该节点是叶子节点，直接删除，将其父节点指向null
if (!current.left && !current.right){
//2.1.1判断是否删除的是根节点
if (!parentNode) this.root = null
else {
//判断该节点是否是左子节点
if (isLeftChild) parentNode.left = null
else parentNode.right = null
}
return current.value
}
//2.2如果该节点有两个子节点
else if (current.left && current.right){
/**
* 如果删除的节点有两个子节点，可以找其前驱节点或者后继节点来替换该节点的位置，这里我找的后继节点
* 封装一个找后继节点的内部调用方法successor
*/
//2.2.1找到该节点的后继节点
let successor = this.successor(current)
//2.2.2用后继节点替换当前节点
successor.left = current.left
successor.right = current.right
//2.2.3判断是否删除根节点
if (!parentNode) this.root = successor
else {
//2.2.4不是根节点
if (isLeftChild) parentNode.left = successor
else parentNode.right = successor
}
return current.value
}
//2.3如果该节点只有一个子节点，将其父节点直接指向其子节点
else {
//2.3.1判断该节点是否是根节点
if (!parentNode){
if (current.left) this.root = current.left
else this.root = current.right
}else { //不是根节点的情况
if (isLeftChild){
//如果删除的是是左子节点，将其父节点的左子节点指向其子节点
if (current.left) parentNode.left = current.left
else parentNode.left = current.right
}else {
//如果删除的是右子节点，将其父节点的右子节点指向其子节点
if (current.left) parentNode.right = current.left
else parentNode.right = current.right
}
}
return current.value
}
}
}
//3.没有找到，返回null
return null
}
//successor方法：供内部调用的查找后继节点的方法
BinarySearchTree.prototype.successor = function (node) {
let successor = node.right
let parentNode = node
while (successor.left){
parentNode = successor
successor = successor.left
}
//判断successor是否直接是该节点的右子节点
if (successor === node.right){
parentNode.right = null
}else {
//如果后继节点有右子树,将后继节点的父节点指向其右子树
if (successor.right) {
parentNode.left = successor.right
}else {
parentNode.left = null
}
}
return successor
}
}
树的遍历方式：
-
先序遍历
-
中序遍历
-
后续遍历
二叉搜索树的缺陷
当插入的数据是连续的时候，树的深度会变得很深，插入删除数据项时效率会变得很低
平衡树（二叉搜索树的优化）
- AVL树
删除/删除操作的效率相对于红黑树较低，所以整体效率低于红黑树 - 红黑树
现在平衡树的应用基本都是红黑树
红黑树除了符合二叉搜索树外的基本规则外，还有一些自己的特性：
1.节点是红色或黑色
2.根节点是黑色
3.每个叶子节点都是黑色的空节点（NIL节点）
4.每个红色节点的子节点都是黑色的（从每个叶子到根的所有路径上不可能出现两个连续的红色节点）
5.从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点
前面的约束，确保了红黑树的关键特性：从根到叶子的最长路径不会超过最短路径的两倍
插入一个新节点时，有可能树不再平衡，可以通过三种方式的变换，使树保持平衡
-
变色
新插入的节点默认都是红色的 -
左旋转
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子
-
右旋转
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子
插入操作
设要插入的节点为N,其父节点为P，其祖父节点为G，其父节点的兄弟节点为U
1.情况一：
新节点N位于树的根上，没有父节点
操作：直接将红色变换为黑色即可
2.情况二：插入节点的父节点P是黑色的
操作：不需要变换
3.情况三：P为红色，U也为红色
操作：将P和U变换为黑色，并且将G变为红色
4.情况四：P为红色，U为黑色，且N是作为左孩子
操作：P变为黑色，G变为红色，G、P进行右旋转
5.情况五：P为红色，U为黑色，且N是作为右孩子
操作：
1.P、N进行左旋转（旋转后将P作为新插入的红色节点考虑即可，继续情况四操作）
2.N变为黑色，G变为红色，G、N进行右旋转
图论
图结构是一种与树结构有些相似的数据结构
图论是数学的一个分支，在数学的概念上，树是图的一种
它以图为研究对象，研究顶点和边组成的图形的数学理论和方法
主要研究的目的是事物之间的关系，顶点代表事物，边代表两个事物间的关系
图的常用术语
- 顶点：表示图中的一个节点
- 边：表示顶点和顶点之间的连线
- 相邻顶点：由一条边连接起来的顶点称为相邻顶点
- 度：一个顶点的度是其相邻顶点的数量
- 路径：一串连续的顶点序列
- 简单路径：不包含重复的顶点
- 回路：第一个顶点和最后一个顶点相同的路径称为回路
- 无向图：所有的边都没有方向的图称为无向图
- 有向图：图中的边是有方向的
- 无权图：边没有携带权重
- 带权图：边有一定的权重
图的表示
顶点可以抽象成ABCD...（或1234...），可以使用一个数组存储所有的顶点
边的表示：
- 邻接矩阵
邻接矩阵让每个顶点和一个整数相关联，该整数作为数组的下标值
用一个二维数组来表示顶点的连接
邻接矩阵的问题：
邻接矩阵有一个比较严重的问题，就是如果图是一个稀疏图，那么矩阵中将存在大量的0，这意味着我们浪费了计算机的存储空间来表示根本不存在的边。 - 邻接表
邻接表由图中每个顶点以及和顶点相邻的顶点列表组成
这个列表有很多种方式来存储：数组、链表、字典、哈希表等都可以
邻接表的问题：
邻接表计算出度比较简单，但如果需要计算有向图的入度，是一件非常麻烦的事情。它必须构造一个“逆邻接表”，才能有效的计算入度，但是在开发中入度用的比较少。
（出度：指向别人的数量；入度：指向自己的数量）
图的遍历方法
- 广度优先搜索（Breadth-First Search，简称BFS）
基于队列，入队列的顶点先被探索 - 深度优先搜索（Depth-First Search，简称DFS）
基于栈或使用递归，通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问
两种算法都需要明确指定第一个被访问的顶点
为了记录顶点是否被访问过，我们使用三种颜色来反应他们的状态
1.白色：表示该顶点还没有被访问
2.灰色：表示改顶点被访问过，但没有被探索过
3.黑色：表示该顶点被访问过也被完全探索过
封装图结构
需要引入字典结构和队列结构
//使用邻接法封装图结构
function Graph() {
//属性：顶点（数组）边（字典）
this.vertexes = [] //顶点
this.edges = new Dictionary() //边
//方法
//添加方法
//1.添加顶点的方法
Graph.prototype.addVertex = function (v) {
this.vertexes.push(v)
this.edges.set(v,[])
}
//2.添加边的方法
Graph.prototype.addEdge = function (v1,v2) {
//默认是处理无向图
this.edges.get(v1).push(v2)
this.edges.get(v2).push(v1)
}
//toString方法：打印出图结构
Graph.prototype.toString = function () {
let resultStr = ''
this.vertexes.forEach( item => {
let edges = ''
this.edges.get(item).forEach( item => {
edges+=item+' '
})
resultStr += item + '->' + edges + '
'
})
return resultStr
}
//初始化顶点颜色的方法
Graph.prototype.initinalizeColor = function () {
const colors = []
this.vertexes.forEach(item => {
colors[item] = 'white'
})
return colors
}
//广度优先搜索,基于队列实现
Graph.prototype.bfs = function (initV,handler) {
//initV--第一个被访问的顶点，handler--回调函数
//1.初始化顶点颜色
const colors = this.initinalizeColor()
//2.初始化一个队列
const queue = new Queue()
//3.访问第一个顶点并放入队列中
queue.enqueue(initV)
//4.访问后颜色变为灰色
colors[initV] = 'gray'
//5.判断队列是否为空
while (queue.size()){
//5.1取出队列中第一个元素
const v = queue.dequeue()
//5.2探索该顶点的相邻顶点并放入队列中
const vList = this.edges.get(v)
vList.forEach(item => {
//判断该元素从未被访问过才放入队列中，防止重复访问
if (colors[item] === 'white'){
queue.enqueue(item)
colors[item] = 'gray'
}
})
//5.3将该元素颜色设置为黑色
colors[v] = 'black'
//5.4处理该元素
handler(v)
}
}
//深度优先搜索，使用递归实现
Graph.prototype.dfs = function (initV,handler) {
//1.初始化颜色
const colors = this.initinalizeColor()
this.dfsVisit(initV,colors,handler)
}
//深度优先搜索的递归方法
Graph.prototype.dfsVisit = function (v,colors,handler) {
//1.访问该顶点
handler(v)
//2.将该顶点颜色设为灰色
colors[v] = 'gray'
//3.探索该顶点的相邻顶点
const vList = this.edges.get(v)
vList.forEach(item => {
//3.1判断该顶点是否被访问过
if (colors[item] === 'white'){
this.dfsVisit(item,colors,handler)
}
})
//4.处理完成，将该顶点颜色设为黑色
colors[v] = 'black'
}
}
算法
大O表示法
时间复杂度的大O表示法
排序算法
简单排序:冒泡排序、选择排序、插入排序
高级排序：希尔排序、快速排序
冒泡排序
冒泡排序算法相对于其他排序算法运行效率较低，但是排序算法中最简单的
冒泡排序的思路：
对未排序的元素从头到尾依次比较相邻的两个元素，将较大的元素放到右边，直到所有的元素都排序好
function bubbleSort(list){
for (let i = list.length;i > 0;i--){
for(let j = 0;j < i-1;j++){
if (list[j] > list[j+1]){
//如果当前元素大于后一个元素，就交换位置
let temp = list[j]
list[j] = list[j+1]
list[j+1] = temp
}
}
}
}
冒泡排序的效率：
比较次数时间复杂度：O(n^2)
交换次数时间复杂度：O(n^2)
选择排序
选择排序思路：
从未排序的元素中找出最小的元素交换到最左边，直到所有的元素都排序好
function selectionSort(list){
//获取数组的长度
const length = list.length
for (let i = 0;i < length;i++){
//定义一个变量保存最小值的下标
let min = i
for (let j = min+1;j < length;j++){
if (list[min] > list[j]){
min = j
}
}
//将最小值换到最左边
let temp = list[i]
list[i] = list[min]
list[min] = temp
}
}
选择排序的效率：
比较次数时间复杂度：O(n^2)
交换次数时间复杂度：O(n)
插入排序
插入排序思路（核心：局部有序）
依次将待排序的数据插入到前面已经排好序的有序序列中，直到所有数据都排好序
//插入排序
function insertionSort(list) {
//获取list长度
const length = list.length
//循环向前插入数据
for (let i = 1;i < length;i++){
//取出当前要插入的数据
const current = list[i]
let j = i
//循环比较有序序列
while (j>=1 && list[j-1] > current){
list[j] = list[j-1]
j--
}
//找到合适的位置，插入当前数据
list[j] = current
}
}
插入排序的效率：
效率高于冒泡排序和选择排序
希尔排序
希尔排序是插入排序的一种高效改进版，效率高于插入排序
希尔排序的思想：
将序列按照一定的增量进行分组，对每组进行插入排序，直至增量减为1
增量的选择：
- 希尔原稿
N/2 - Hibbard 增量序列
2^k - 1，也就是1，3，5，7... - Sedgewick 增量序列
94^i - 9*2^i + 1 或者是 4^i - 32^i + 1
function shellSort(list) {
//获取数组长度
const length = list.length
//获取增量
let gap = Math.floor(length/2)
while (gap > 0){
//进行快速排序
for (let i = gap;i < length;i++){
//取出当前要插入的数据
const current = list[i]
let j = i
while (j >= gap && list[j-gap] > current){
list[j] = list[j-gap]
j = j - gap
}
//找到正确的位置插入
list[j] = current
}
gap = Math.floor(gap/2)
}
}
希尔排序的效率：
希尔排序的效率大多数情况下都高于简单排序
快速排序
快速排序几乎是目前所有排序算法中最快的一种
快速排序思想（核心：分而治之）
在一次递归中，找出某个元素的正确位置，并且该元素之后不需要任何移动
枢纽（每次递归中，选出的某个元素）的选择：
取头中尾的中位数
//快速排序
function quickSort(list) {
quick(list,0,list.length-1)
}
//交换位置的函数
function swap(list,i,j) {
let temp = list[i]
list[i] = list[j]
list[j] = temp
}
//选择枢纽的函数
function median(list,head,tail) {
//获取中间位置的下标
const center = Math.floor((head+tail)/2)
if (list[head] > list[center]){
swap(list,head,center)
}
if (list[center] > list[tail]){
swap(list,center,tail)
}
if (list[head] > list[center]){
swap(list,head,center)
}
//将枢纽放置到tail-1位置
swap(list,center,tail-1)
return list[tail-1]
}
//递归函数
function quick(list,head,tail) {
//1.递归结束条件
if (head >= tail) return
//2.获取枢纽
const pivot = median(list,head,tail)
//3.定义两个指针分别指向要进行比较的数据
let left = head
let right = tail - 1
//4.循环比较数据并进行交换
while (left < right){
while (list[++left] < pivot){}
while (list[--right] > pivot){}
if (left < right){
swap(list,left,right)
}
}
//5.将枢纽放置到正确的位置
swap(list,left,tail-1)
//6.递归处理左边的序列
quick(list,head,left-1)
//7.递归处理右边的序列
quick(list,left+1,tail)
}