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

2022-09-26 17:12:22 浏览数 (1)
  • 数据结构介绍

-曾老湿, 江湖人称曾老大。

-多年互联网运维工作经验，曾负责过大规模集群架构自动化运维管理工作。 -擅长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创建项目：



代码语言：javascript复制
<!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>
代码语言：javascript复制
#screen{
    border: 1px solid black;
    width: 200px;
    height: 200px;
}

使用parcel启动页面：

代码语言：javascript复制
MacBook-Pro:queue-demo-1 driverzeng$ parcel src/index.html





代码语言：javascript复制
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



修改代码如下：

代码语言：javascript复制
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]的数组

生活中例子很少

代码语言：javascript复制
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创建项目

代码语言：javascript复制
<!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>
代码语言：javascript复制
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代码中有重复代码。

代码语言：javascript复制
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)

删除节点

代码语言：javascript复制
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)

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

代码语言：javascript复制
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 删除

代码语言：javascript复制
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 算法...

用代码实现树：





代码语言：javascript复制
<!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>



代码语言：javascript复制
const createTree = (value)  =>{
    return {
        data: value,
        children: null
    }
}

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

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

代码语言：javascript复制
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... 再生个孙子... 也不对。就是儿子生个儿子。

代码语言：javascript复制
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)



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

代码语言：javascript复制
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)



代码语言：javascript复制
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);



运维 node.js 自动化 ide 数据结构

0 人点赞