27·灵魂前端工程师养成-数据结构

2019-05-13 分类:JavaScript, 前端开发 阅读(29) 评论(0)

-曾老湿, 江湖人称曾老大。
-笔者QQ:133411023、253097001
-笔者交流群:198571640
-笔者微信:z133411023


-多年互联网运维工作经验,曾负责过大规模集群架构自动化运维管理工作。
-擅长Web集群架构与自动化运维,曾负责国内某大型金融公司运维工作。
-devops项目经理兼DBA。
-开发过一套自动化运维平台(功能如下):

1)整合了各个公有云API,自主创建云主机。
2)ELK自动化收集日志功能。
3)Saltstack自动化运维统一配置管理工具。
4)Git、Jenkins自动化代码上线及自动化测试平台。
5)堡垒机,连接Linux、Windows平台及日志审计。
6)SQL执行及审批流程。
7)慢查询日志分析web界面。


数据结构介绍


队列

队列:Queue

特点:先进先出[FIFO]的数组

题目:请实现一个餐厅叫号网页

点击 [取号]按钮,生成一个号码
点击 [叫号]按钮,显示 请X号就餐

在JS中,入队:queue.push / 出队:queue.shift

使用vscode创建项目:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>队列示例</title>
    <link rel="stylesheet" href="./style.css">
</head>
<body>
    <div id="screen"></div>
    <div class="actions">
        <button id="createNumber">取号</button>
        <button id="callNumber">叫号</button>
    </div>
    <div>
        当前号码<span id="newNumber"></span>
    </div>
    <div>
        当前队列<span id="queue"> </span>
    </div>
    <script src="./main.js"></script>
</body>
</html>
#screen{
    border: 1px solid black;
    width: 200px;
    height: 200px;
}

使用parcel启动页面:

MacBook-Pro:queue-demo-1 driverzeng$ parcel src/index.html 

const divScreen = document.querySelector("#screen")
const btnCreateNumber = document.querySelector("#createNumber")
const btnCallNumber = document.querySelector("#callNumber")
const spanNewNumber = document.querySelector("#newNumber")
const spanQueue = document.querySelector("#queue")

let n = 0
let queue = []

btnCreateNumber.onclick = () => {
    n += 1
    queue.push(n)
    spanNewNumber.innerText = n
    spanQueue.innerText = JSON.stringify(queue)
}

btnCallNumber.onclick = () => {
    const m =  queue.shift()
    divScreen.innerText =  `请${m}号就餐`
    spanQueue.innerText = JSON.stringify(queue) 
}

但是上面的代码是有bug的,当你把号都叫完后,页面会变成undefined

修改代码如下:

const divScreen = document.querySelector("#screen")
const btnCreateNumber = document.querySelector("#createNumber")
const btnCallNumber = document.querySelector("#callNumber")
const spanNewNumber = document.querySelector("#newNumber")
const spanQueue = document.querySelector("#queue")

let n = 0
let queue = []

btnCreateNumber.onclick = () => {
    n += 1
    queue.push(n)
    spanNewNumber.innerText = n
    spanQueue.innerText = JSON.stringify(queue)
}

btnCallNumber.onclick = () => {
    const m =  queue.shift()
    if(m === undefined){
        alert("叫个锤子叫,都没人了")
        return;
    }
    divScreen.innerText =  `请${m}号就餐`
    spanQueue.innerText = JSON.stringify(queue) 
}


栈:Stack

特点:后进先出[LIFO]的数组

生活中例子很少

function f1(){let a=1; return a+f2() }
function f2(){let b=2; return b+f3() }
function f3(){let c=3; return c }

链表

链表:Linked List

特点:一个链一个

使用vscode创建项目

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>链表数据示例</title>
</head>
<body>
    <script src="./list.js"></script>
</body>
</html>
const createList = value =>{
    return {
        data: value,
        next: null
    }
}
const appendList = (list,value) =>{
    const node = {
        data: value,
        next: null
    }
    list.next = node
    return node
}

const list = createList(10)
const node = appendList(list,20)
console.log('node')
console.log(node)
console.log('list')
console.log(list)

代码可以优化,上面的JS代码中有重复代码。

const createList = value =>{
    return createNode(value)
}
const appendList = (list,value) =>{
    const node = createNode(value)
    list.next = node
    return node
}

const createNode = (value) =>{
    return {
        data: value,
        next: null
    }
}

const list = createList(10)
const node = appendList(list,20)
console.log('node')
console.log(node)
console.log('list')
console.log(list)

删除节点

const createList = value =>{
    return createNode(value)
}
const appendList = (list,value) =>{
    const node = createNode(value)
    list.next = node
    return node
}

const createNode = (value) =>{
    return {
        data: value,
        next: null
    }
}

const removeFromList = (list,node) =>{
    if(list === node){
        // 如果是删除第一个节点
        list = node.next
    }else{
        // 如果是删除第二个节点
        // 第一个节点.next = 第三个节点 (第一个节点.next = 第二个节点.next)
        if(list.next === node){
            list.next = node.next
        }else{
            // 如果删除的是第三个节点
            // 第二个节点.next = 第三个节点.next
            if(list.next.next === node){
                (list.next).next = node.next
            }else{
                // 如果删除的是第四个节点
                // 第三个节点.next = 第四个节点.next
                if(list.next.next.next === node){
                    (list.next.next).next = node.next
                }
            }
        }
    }
}
const list = createList(10)
const node = appendList(list,20)
console.log('node')
console.log(node)
console.log('list')
console.log(list)

可以看到上面代码中的规律,所以我们需要使用循环

const createList = value =>{
    return createNode(value)
}
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 createNode = (value) =>{
    return {
        data: value,
        next: null
    }
}

const list = createList(10)
const node2 = appendList(list,20)
const node3 = appendList(list,30)
console.log('list')
console.log(list)

我们添加 node2 node3 node4 然后我们把node3 删除

const createList = value =>{
    return createNode(value)
}
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 createNode = (value) =>{
    return {
        data: value,
        next: null
    }
}

const list = createList(10)
const node2 = appendList(list,20)
const node3 = appendList(list,30)
const node4 = appendList(list,40)
removeFromList(list, node3)
console.log('list')
console.log(list)


哈希表

什么是hash?hash的原理是什么?hash碰撞如何解决?

请看知乎的一篇文章:TP

hash的做法,会让数据读取的比较快,但是存储的时候比较难。


针对于树的数据类型,用的比较多

比如中国的行政区域。

比如公司的层级结构。

比如网页中的节点。

比如 MySQL中的 Btree 算法...

用代码实现树:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>树 示例</title>
</head>
<body>
    <script src="./tree.js"></script>
</body>
</html>

const createTree = (value)  =>{
    return {
        data: value,
        children: null
    }
}

const tree = createTree(10)
console.log(tree)

没有儿子,怎么办,我们要给他加儿子...生猴子

const createTree = (value)  =>{
    return {
        data: value,
        children: null
    }
}

const addChild = (node,value) => {
    const newCode = {
        data: value,
        children: null
    }
    node.children = node.children || []
    node.children.push(newCode)
}

const tree = createTree(10)
addChild(tree,20)
addChild(tree,30)
addChild(tree,40)
addChild(tree,50)
console.log(tree)

给 儿子 再生个儿子... 噗,什么鬼。emmmm... 再生个孙子... 也不对。就是儿子生个儿子。

const createTree = (value)  =>{
    return {
        data: value,
        children: null
    }
}

const addChild = (node,value) => {
    const newCode = {
        data: value,
        children: null
    }
    node.children = node.children || []
    node.children.push(newCode)
    return newCode
}

const tree = createTree(10)
const node2 = addChild(tree,20)
addChild(tree,20)
addChild(tree,30)
addChild(tree,40)
addChild(tree,50)
addChild(node2,120)
addChild(node2,130)
addChild(node2,140)
addChild(node2,150)
console.log(tree)

删除节点,首先我们要遍历这棵树,每一个节点,包括子节点上的数据

const createTree = (value)  =>{
    return {
        data: value,
        children: null
    }
}

const addChild = (node,value) => {
    const newCode = {
        data: value,
        children: null
    }
    node.children = node.children || []
    node.children.push(newCode)
    return newCode
}

// 遍历树

const travel = (tree , fn) => {
    fn(tree)
    if(!tree.children){
        return
    }
    for(let i = 0;i<tree.children.length;i++){
        travel(tree.children[i],fn)
    }
}

const tree = createTree(10)
const node2 = addChild(tree,20)
addChild(tree,20)
addChild(tree,30)
addChild(tree,40)
addChild(tree,50)
addChild(node2,120)
addChild(node2,130)
addChild(node2,140)
addChild(node2,150)
console.log(tree)

const fn = node =>{
    console.log(node.data)
}

travel(tree,fn)

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) => {
  fn(tree);
  if (!tree.children) {
    return;
  }
  for (let i = 0; i < tree.children.length; i++) {
    travel(tree.children[i], fn);
  }
};

const find = (tree, node) => {
  if (tree === node) {
    return tree;
  } else if (tree.children) {
    for (let i = 0; i < tree.children.length; i++) {
      const result = find(tree.children[i], node);
      if (result) {
        return result;
      }
    }
    return undefined;
  } else {
    return undefined;
  }
};

const removeNode = (tree, 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);
const node3 = addChild(tree, 30);
addChild(tree, 40);
const node5 = addChild(tree, 50);
addChild(node2, 201);
addChild(node2, 202);
addChild(node2, 203);
addChild(node2, 204);
console.log(tree);

const fn = node => {
  console.log(node.data);
};

removeNode(tree, node5);
console.log(tree);

关于 曾老湿
我只是一个躲在角落里瑟瑟发抖的小运维,随时准备给大佬端茶递水。
WeChat:z133411023
QQ:133411023
欢迎新朋友你的到来!
还没有人抢沙发呢~
昵称
邮箱
网站
切换注册

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

切换登录

注册