js数据结构和算法
2021-08-17 本文已影响0人
易路先登
队列
FIFO(first in first out): 先入后厨
队列的实现
class Queue{
constructor(){
this.container = []
}
enQueue(value){
this.container.push(value)
}
deQueue(){
return this.container.shift()
}
size(){
return this.container.length
}
}
案例问题
1.首先，我们先来了解一下什么是约瑟夫环问题：
讲一个比较有意思的故事：约瑟夫是犹太军队的一个将军，在反抗罗马的起义中，他所率领的军队被击溃，只剩下残余的部队40余人，他们都是宁死不屈的人，所以不愿投降做叛徒。一群人表决说要死，所以用一种策略来先后kill所有人。
于是约瑟夫建议：每次由其他两人一起kill一个人，而被kill的人的先后顺序是由抽签决定的，约瑟夫有预谋地抽到了最后一签，在kill了除了他和剩余那个人之外的最后一人，他劝服了另外一个没死的人投降了罗马。
我们这个规则是这么定的：
在一间房间总共有n个人（下标0～n-1），只能有最后一个人活命。
按照如下规则去排除人：
所有人围成一圈
顺时针报数，每次报到q的人将被排除掉
被排除掉的人将从房间内被移走
然后从被kill掉的下一个人重新报数，继续报q，再清除，直到剩余一人
你要做的是：当你在这一群人之间时，你必须选择一个位置以使得你变成那剩余的最后一人，也就是活下来。
let first = new Queue()
//入队40人
for(let i = 0;i < 40;i++){
first.enQueue(i+1)
}
let number=0;
let result = []
while(first.size()>3){
let outPerson = first.deQueue()
number++
if(number===9){
number=0
result.push(outPerson)
}else{
first.enQueue(outPerson)
}
}
console.log(first,result)
链表
单向链表
//[1,'2',3,8,4,5]
//数组的变量名其实是一个地址值，指向内存中该数组的第一个元素
//& 具体取值时是怎么计算的呢 首地址+宽度*索引
//链表
//{{value:1,next:obj1}} var obj1 = {value:3,next:obj2}
class LinkNode{
constructor(value,next){
this.value = value;
this.next = next
}
}
class MyLink{
constructor(){
this.head = null;
this.size = 0;
}
appendChild(value){
if(this.head===null){
this.head = new LinkNode(value,null)
this.size++
}else{
this.findNode(this.size).next = new LinkNode(value,null)
this.size++;
}
}
insertNode(index,value){
if(index===1){
this.head = new LinkNode(value,this.head)
}else{
let pre = this.findNode(index-1)
pre.next = new LinkNode(value,pre.next)
}
this.size++
}
findNode(index){
if(index < 1 || index > this.size){
throw new Error('索引不存在')
}
var current = this.head;
for(let i = 0;i < index - 1;i++){
current = current.next
}
return current;
}
setNode(index,value){
this.findNode(index).value = value
}
}
let first = new MyLink()
first.appendChild(5)
first.appendChild(6)
first.appendChild(7)
first.insertNode(2,5.5)
console.log(first,'链表')
console.log(first.findNode(2))
链表实现约瑟夫环
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
<style>
html,body,#container{
width:100%;
height:100%;
}
</style>
</head>
<body>
<div id="container">
</div>
<script>
//[1,'2',3,8,4,5]
//数组的变量名其实是一个地址值，指向内存中该数组的第一个元素
//& 具体取值时是怎么计算的呢 首地址+宽度*索引
//链表
//{{value:1,next:obj1}} var obj1 = {value:3,next:obj2}
class LinkNode{
constructor(value,next){
this.value = value;
this.next = next
}
}
class MyLink{
constructor(){
this.head = null;
this.tail = null;
this.current = null;
this.size = 0;
}
appendChild(value){
if(this.head===null){
this.current = this.tail = this.head = new LinkNode(value,null)
this.size++
}else{
this.tail = this.findNode(this.size).next = new LinkNode(value,this.head)
this.size++;
}
}
insertNode(index,value){
if(index===1){
this.tail.next = this.head = new LinkNode(value,this.head)
this.current = this.head;
}else{
let pre = this.findNode(index-1)
pre.next = new LinkNode(value,pre.next)
}
this.size++
}
deleteNode(index){
let temp = this.findNode(index)
let next = temp.next
if(index===1){
this.tail.next = this.head = this.head.next
}else if(index===this.size){
this.tail = this.findNode(this.size-1)
this.tail.next = this.head
}else{
let pre = this.findNode(index-1)
pre.next = pre.next.next
}
if(temp === this.current){
this.current = next;
}
this.size--
}
deleteNodeByValue(value){
let index = 1;
let current = this.head
while(current.value!=value){
index++
if(index>this.size){
index = -1
break;
}
if(this.tail.value===current.value){
break;
}
current = current.next
}
if(index>0){
this.deleteNode(index)
}
}
findNode(index){
if(index < 1 || index > this.size){
throw new Error('索引不存在')
}
var current = this.head;
for(let i = 0;i < index - 1;i++){
current = current.next
}
return current;
}
setNode(index,value){
this.findNode(index).value = value
}
next(){
this.current = this.current.next;
}
}
let first = new MyLink()
/*
40个人 每9 杀一个 剩2结束
*/
for(let i = 1;i < 41;i++){
first.appendChild(i)
}
while(first.size>2){
new Array(8).fill(0).forEach(item => {
first.next()
});
first.deleteNodeByValue(first.current.value)
}
console.log(first,'链表')
</script>
</body>
</html>
二叉树
增加节点与查询节点方法
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
<style>
html,body,#container{
width:100%;
height:100%;
}
</style>
</head>
<body>
<div id="container">
</div>
<script>
//BST binary search tree
class BSTNode{
constructor(left,value,right){
this.left = left;
this.value = value;
this.right = right
}
}
class BSTree{
constructor(){
this.root = null;
this.size = 0;
}
addChild(value){
if(this.root === null){
this.root = new BSTNode(null,value,null)
this.size++
}else{
this.root = this.addChildFromNode(this.root,value)
}
}
addChildFromNode(node,value){
if(value < node.value){
if(node.left===null){
node.left = new BSTNode(null,value,null)
this.size++
return node
}
node.left = this.addChildFromNode(node.left,value)
return node
}else if(value > node.value){
if(node.right===null){
node.right = new BSTNode(null,value,null)
this.size++
return node
}
node.right = this.addChildFromNode(node.right,value)
return node
}
}
hasValue(value){
return this.hasValueFromNode(this.root,value)
}
hasValueFromNode(node,value){
if(value < node.value){
if(node.left === null){
return false
}
return this.hasValueFromNode(node.left,value)
}
else if(value > node.value){
if(node.right===null){
return false
}
return this.hasValueFromNode(node.right,value)
}else{
return true
}
}
}
let first = new BSTree();
first.addChild(89)
first.addChild(80)
first.addChild(100)
first.addChild(79)
console.log(first.hasValue(101))
</script>
</body>
</html>
二叉树相比数组搜索效率数量级提升
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
<style>
html,body,#container{
width:100%;
height:100%;
}
</style>
</head>
<body>
<div id="container">
</div>
<script>
//BST binary search tree
class BSTNode{
constructor(left,value,right){
this.left = left;
this.value = value;
this.right = right
}
}
class BSTree{
constructor(){
this.root = null;
this.size = 0;
}
addChild(value){
if(this.root === null){
this.root = new BSTNode(null,value,null)
this.size++
}else{
this.root = this.addChildFromNode(this.root,value)
}
}
addChildFromNode(node,value){
if(value < node.value){
if(node.left===null){
node.left = new BSTNode(null,value,null)
this.size++
return node
}
node.left = this.addChildFromNode(node.left,value)
return node
}else if(value > node.value){
if(node.right===null){
node.right = new BSTNode(null,value,null)
this.size++
return node
}
node.right = this.addChildFromNode(node.right,value)
return node
}
}
hasValue(value){
return this.hasValueFromNode(this.root,value)
}
hasValueFromNode(node,value){
if(value < node.value){
if(node.left === null){
return false
}
return this.hasValueFromNode(node.left,value)
}
else if(value > node.value){
if(node.right===null){
return false
}
return this.hasValueFromNode(node.right,value)
}else{
return true
}
}
}
let first = new BSTree();
let result = []
while(result.length<10000){
let number = Math.floor(Math.random()*100000)
if(result.indexOf(number)<0){
result.push(number)
}
}
result.forEach((item)=>{
first.addChild(item)
})
let start1 = new Date().getTime()
for(let j = 0;j < 10000;j++){
let number = Math.floor(Math.random()*100000)
for(let i = 0;i < result.length;i++){
if(number===result[i]){
break;
}
}
}
let end1 = new Date().getTime()
let start2 = new Date().getTime()
for(let j = 0;j < 10000;j++){
let number = Math.floor(Math.random()*100000)
first.hasValue(number)
}
let end2 = new Date().getTime()
console.log(end1-start1)
console.log(end2-start2)
// first.addChild(89)
// first.addChild(80)
// first.addChild(100)
// first.addChild(79)
// console.log(first.hasValue(101))
</script>
</body>
</html>
二叉树的删除方法
删除节点100前
删除节点100后
代码：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
<style>
html,body,#container{
width:100%;
height:100%;
}
</style>
</head>
<body>
<div id="container">
</div>
<script>
//BST binary search tree
class BSTNode{
constructor(left,value,right){
this.left = left;
this.value = value;
this.right = right
}
}
class BSTree{
constructor(){
this.root = null;
this.size = 0;
}
addChild(value){
if(this.root === null){
this.root = new BSTNode(null,value,null)
this.size++
}else{
this.root = this.addChildFromNode(this.root,value)
}
}
addChildFromNode(node,value){
if(value < node.value){
if(node.left===null){
node.left = new BSTNode(null,value,null)
this.size++
return node
}
node.left = this.addChildFromNode(node.left,value)
return node
}else if(value > node.value){
if(node.right===null){
node.right = new BSTNode(null,value,null)
this.size++
return node
}
node.right = this.addChildFromNode(node.right,value)
return node
}
}
deleteValue(value){
this.root = this.deleteFromNode(this.root,value)
}
deleteFromNode(node,value){
if(value < node.value){
node.left = this.deleteFromNode(node.left,value)
return node
}else if(value > node.value){
node.right = this.deleteFromNode(node.right,value)
}else if(value === node.value){
//该节点为叶子节点
if(node.left===null&&node.right===null){
this.size--
return null
}
//只有左节点
if(node.left!=null&&node.right===null){
this.size--
return node.left
}
//只有右节点
if(node.left===null&&node.right!=null){
this.size--
return node.right
}
//有两个子节点
if(node.left!=null && node.right!=null){
let minNode = this.getMinFromNode(node.right)
node.value = minNode.value
node.right = this.deleteFromNode(node.right,minNode.value)
return node;
}
}
return node
}
hasValue(value){
return this.hasValueFromNode(this.root,value)
}
hasValueFromNode(node,value){
if(value < node.value){
if(node.left === null){
return false
}
return this.hasValueFromNode(node.left,value)
}
else if(value > node.value){
if(node.right===null){
return false
}
return this.hasValueFromNode(node.right,value)
}else{
return true
}
}
getMin(){
return this.getMinFromNode(this.root)
}
getMinFromNode(node){
if(node.left===null){
return node
}else{
return this.getMinFromNode(node.left)
}
}
}
let first = new BSTree();
first.addChild(89)
first.addChild(80)
first.addChild(100)
first.addChild(79)
first.addChild(95)
first.addChild(120)
first.addChild(91)
first.addChild(101)
first.addChild(121)
first.deleteValue(100)
console.log(first)
</script>
</body>
</html>
二叉树的前中后序遍历层级遍历深度获取
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
<style>
html,body,#container{
width:100%;
height:100%;
}
</style>
</head>
<body>
<div id="container">
</div>
<script>
class MyQueue{
constructor(){
this.container = []
}
enQueue(value){//入队
this.container.push(value)
}
deQueue(){
return this.container.shift()
}
size(){
return this.container.length
}
}
//BST binary search tree
class BSTNode{
constructor(left,value,right){
this.left = left;
this.value = value;
this.right = right
}
}
class BSTree{
constructor(){
this.root = null;
this.size = 0;
}
addChild(value){
if(this.root === null){
this.root = new BSTNode(null,value,null)
this.size++
}else{
this.root = this.addChildFromNode(this.root,value)
}
}
addChildFromNode(node,value){
if(value < node.value){
if(node.left===null){
node.left = new BSTNode(null,value,null)
this.size++
return node
}
node.left = this.addChildFromNode(node.left,value)
return node
}else if(value > node.value){
if(node.right===null){
node.right = new BSTNode(null,value,null)
this.size++
return node
}
node.right = this.addChildFromNode(node.right,value)
return node
}
}
deleteValue(value){
this.root = this.deleteFromNode(this.root,value)
}
deleteFromNode(node,value){
if(value < node.value){
node.left = this.deleteFromNode(node.left,value)
return node
}else if(value > node.value){
node.right = this.deleteFromNode(node.right,value)
}else if(value === node.value){
//该节点为叶子节点
if(node.left===null&&node.right===null){
this.size--
return null
}
//只有左节点
if(node.left!=null&&node.right===null){
this.size--
return node.left
}
//只有右节点
if(node.left===null&&node.right!=null){
this.size--
return node.right
}
//有两个子节点
if(node.left!=null && node.right!=null){
let minNode = this.getMinFromNode(node.right)
node.value = minNode.value
node.right = this.deleteFromNode(node.right,minNode.value)
return node;
}
}
return node
}
hasValue(value){
return this.hasValueFromNode(this.root,value)
}
hasValueFromNode(node,value){
if(value < node.value){
if(node.left === null){
return false
}
return this.hasValueFromNode(node.left,value)
}
else if(value > node.value){
if(node.right===null){
return false
}
return this.hasValueFromNode(node.right,value)
}else{
return true
}
}
getMin(){//寻找最小值
return this.getMinFromNode(this.root)
}
getMinFromNode(node){
if(node.left===null){
return node
}else{
return this.getMinFromNode(node.left)
}
}
getMax(){//寻找最大值
return this.getMaxFromNode(this.root)
}
getMaxFromNode(node){
if(node.right===null){
return node
}else{
return this.getMaxFromNode(node.right)
}
}
getDep(){//求二叉树的深度（即层数）
return this.getDepFromNode(this.root)
}
getDepFromNode(node){
let left;
if(node.left===null){
left = 0
}else{
left = this.getDepFromNode(node.left)
}
let right;
if(node.right===null){
right = 0
}else{
right = this.getDepFromNode(node.right)
}
return Math.max(left,right)+1
}
preErgodic(fn){//前序遍历
this.preErgodicFromNode(this.root,fn)
}
preErgodicFromNode(node,fn){
fn(node)
if(node.left){
this.preErgodicFromNode(node.left,fn)
}
if(node.right){
this.preErgodicFromNode(node.right,fn)
}
}
midErgodic(fn){//中序遍历
this.midErgodicFromNode(this.root,fn)
}
midErgodicFromNode(node,fn){
if(node.left){
this.midErgodicFromNode(node.left,fn)
}
fn(node)
if(node.right){
this.midErgodicFromNode(node.right,fn)
}
}
nextErgodic(fn){//中序遍历
this.nextErgodicFromNode(this.root,fn)
}
nextErgodicFromNode(node,fn){
if(node.left){
this.nextErgodicFromNode(node.left,fn)
}
if(node.right){
this.nextErgodicFromNode(node.right,fn)
}
fn(node)
}
storeyErgodic(fn){
let myQueue = new MyQueue()
myQueue.enQueue(this.root)
let tmp;
while(myQueue.size()>0){
tmp = myQueue.deQueue()
fn(tmp)
if(tmp.left){
myQueue.enQueue(tmp.left)
}
if(tmp.right){
myQueue.enQueue(tmp.right)
}
}
}
}
let first = new BSTree();
first.addChild(89)
first.addChild(80)
first.addChild(100)
first.addChild(79)
first.addChild(95)
first.addChild(120)
first.addChild(91)
first.addChild(101)
first.addChild(121)
first.deleteValue(100)
//console.log(first.getDep())
first.preErgodic((node)=>{
console.log(node.value)
})
console.log('----------------------------------------------')
first.midErgodic((node)=>{
console.log(node.value)
})
console.log('----------------------------------------------')
first.nextErgodic((node)=>{
console.log(node.value)
})
console.log('----------------------------------------------')
first.storeyErgodic((node)=>{
console.log(node.value)
})
</script>
</body>
</html>
