数据结构(上)

• 队列
• 栈
• 链表
• 哈希表
• 树

队列(Queue)(FIFO):First-In First-Out 先入先出

队列实例 : 取号先进叫号先出

//const : 常量块级作用域,很像使用let语句定义的变量。常量的值不能通过重新赋值来改变,并且不能重新声明
//document.querySelector() : 返回文档中与指定选择器或选择器匹配的第一个html元素element。如果找不
// 到匹配项,则返回null
//innerText : 属性表示一个节点及其后代的“渲染”文本内容
//JSON.stringify() ：方法将一个JavaScript值(对象或者数组)转换为一个JSON字符串,
//Array.prototype.push() : 方法是将一个或多个元素添加到数组的末尾,并返回数组的新长度

栈(stack)(LIFO):Last In First Out 后进后出

let result = 0
let recursion = numbers =>{
    if(numbers<=100){
      return recursion((result+=numbers,++numbers))
    }else{
      return result
    }
}
recursion(1)    //5050

//递归的步骤是怎么做的？调用函数时,在一个数组里进行压栈直到numbers等于101时。
//返回result并且把之前调用函数栈逐一释放,后进后出

链表(Linked List)

链表在 JS 里主要体现在对象里

什么时链表？ 答：在 JS 里的链表是由多个对象组成的,对象在链表里称为节点,第一个节点里必须有一个 next 属性该属性值必须是第二个节点以此类推

//创建一个单向链表,具有删除和遍历的函数。
const createList = value =>{  //创建第一个链表头
  return createNode(value)
}
const createNode = value =>{  //创建节点对象
  return {
    data:value,
    next:null
  }
}
const appendList = (list,value) =>{   //创建其他节点
  const node = createNode(value)
  let x = list
  while(x.next){
    x=x.next
  }
  x.next = node
  return node
}

const removeFromList = (list,node) =>{    //删除节点
  let x = list  //当前节点
  let p = null  //上一个节点
  while(x!==node){
    p = x
    x = x.next
  }
  p.next = x.next
}

const travelList = (list,fn)=>{
  let x = list
  while(x){
    fn(x)
    x = x.next
  }
}
const list = createList(1)
const node2 = appendList(list,2)
const node3 = appendList(list,3)
const node4 = appendList(list,4)
removeFromList(list,node3)    //删除第三个节点
console.log(list)  //data：3 的节点没了~

travelList(list,(node)=>{
  console.log(node.data)
})
/*
  输出:
      1
      2
      3
*/

哈希表(key-value pairs)

// 哈希表 在JS里是由对象存在的,对象里有多个 key - value

let key_value = {
    aaa:value,
    bbb:value,
    10000:value
}

//key-value 少的话访问速度可以忽略不计,

//如果key-value 有上万
let key_value = {
  //有上万个key-value
}

key_value['xxx']    //假设对象里key没排序.在找'xxx'时候假设它在10000 那就需要 O(n)

//假设 对象里的key已经排好序了 可以使用二分查找法  速度就是 O(log2 n)

//还能不能更快一点？ 做到 O(1)?

//当我们把key的转换成ascii数组做索引,在找的时候做除法取余数  就会达到o(1)

目前只是了解到这,以后有相关实例再来补充

树(tree)

结构的外形上相似于树,拿省市区县来说.一个中国有多少省?每个省有多少市？每个市有多少区？如果画出来是不是很想一棵树？

//树实例 :
const createTree = (value) =>{    //创建树的根节点
  return {
    data:value,
    children:null,
    parent:null
  }
}

const addChild = (node,value) =>{ //创建其他节点
  const newNode = {
    data:value,
    children:null,
    parent:node
  }
  node.children = node.children || []
  node.children.push(newNode)

  return newNode
}

const travel = (tree,fn) =>{    //遍历tree
  fn(tree)
  if(!tree.children){
    return
  }
  for(let i = 0;i<tree.children.length;i++){
    travel(tree.children[i],fn)
  }
}
const find = (tree,node) =>{      //find node
  if(tree === node){
    return tree
  }else if(tree.children){
    for(let i=0;i<tree.length;i++){
      let result = find(tree.children[i],node)
      if(result){
        return result
      }
    }
    return undefined
  }else{
    return undefined
  }
}
const removeNode = (tree,node) =>{  //remove node
  const siblings = node.parent.children
  let index = 0
  for(let i=1;i<siblings.length;i++){
    if(siblings[i] === node){
      index = i
    }
  }
  siblings.splice(index,1)
}
const tree = createTree(10)     //创建根节点
const node2 = addChild(tree,20) //根节点的儿子(2层)
addChild(node2,201) //节点(3层)
addChild(node2,202) //节点(3层)
addChild(node2,203) //节点(3层)
addChild(node2,204) //节点(3层)
const node3 = addChild(tree,30) //根节点的儿子(2层)
const node4 = addChild(tree,40) //根节点的儿子(2层)

travel(tree,(node)=>{         //遍历tree
  console.log(node.data)
  }
)


removeNode(tree,node3)  //删除一个节点

console.log(tree)