数据结构

2020-10-16
4 min read

目前我们用过的数据结构
数组(选择排序、归并排序、快速排序)
数组可以分为队列、栈等
哈希表(计数排序)
用来存储key-value对

数据结构一:队列Queue

队列Queue:一种特殊的数组,先进先出的数组 在这里插入图片描述 在这里插入图片描述

什么是队列数据结构?
队列数据结构就是个类似数组的东西,但是它只提供push()入队和shift()出队2个操作。你提供这样的结构和这样的2个操作,你就是队列。 队列专门用来解决排队的问题。

用call改写

//queue.push(n)
queue.push.call(queue, n)

//const m = queue.shift()
const m = queue.shift.call(queue)

数据结构二:栈Stack

后进先出的数组 例子:坐电梯超重时,后进先出。 在这里插入图片描述

2个操作:压栈push()、弹栈pop()

Queue和Stack都是用数组做的数据结构。

数据结构三:链表Linked List

一个链一个 在这里插入图片描述

在这里插入图片描述

JS的每个对象实际上就是链表。
这导致array能够直接访问数组原型的方法,比如说array.push()。 它也可以访问到对象原型上有的方法,比如说array.hasOwnProperty 这是一种非常简洁的实现继承的一种机制。

链表的好处:可以随时把中间的某个链条给断掉。
如何做到断掉数组原型?
array.__proto__指向对象原型,它就不会再有push这个方法了。
对于修改东西比较方便。

在这里插入图片描述

创建链表

如何创建链表,在链表上增删改查?

1.创建只含有一个节点的link_list

const createList = (value) => { //创建只含有一个节点的link_list
    return {
        data: value,
        next: null
    }
}
const list = createList(10)
console.log(list)
运行:parcel src/linked_list.html

在这里插入图片描述

2.新增其它节点

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)

在这里插入图片描述

3.删除节点

怎么删掉节点2呢?

将第1个节点指向第3个节点,那么第2个节点会因没人使用从而被浏览器自动回收掉,从而实现删除节点2

那怎么找到上一个节点呢?遍历list

每个节点只有2个数据data:value;next:null;

解析:每次都是判断节点 是否= node,然后让左边的=右边的next。

const removeFromList = (list, node) => {
  if (list === node) {
  //如果删除的是第1个节点
  //list指向第2个节点
    list = node.next; //list是第1个节点
  } else {
  //如果删除的是第2个节点
  //第1个节点.next=第2个节点.next
    if (list.next === node) {
    //第1个节点.next直接指向第3个节点,从而实现删除节点2 !
      list.next = node.next
    } else {
    //如果删除的是第3个节点
    //第2个节点.next=第3个节点.next
      if (list.next.next === node) {
        list.next.next = node.next
      } else {
      //如果删除的是第4个节点
      //第3个节点.next=第4个节点.next
        if (list.next.next.next === node) {
          list.next.next.next = node.next
        }
      }
    }
  }
}
removeFromList(list, list)//删除第1个节点

4.改写为while循环,通过遍历找当前节点的上一个节点。

解析:while循环会一直等表达式里的值不成立才跳出。

代入,假设x是10、node是30,进入循环。一直循环到x=30、node=30才跳出执行p.next = x.next

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===null x是最后一个节点
    x.next = node
    return node
}
const createNode = value => {
    return {
        data: value,
        next: null
    }
}
const removeFromList = (list, node) => {
 //debugger
    let x = list;
    let p = node;
    while (x !== node && x !== null) { 
    //如果node不在list中,x就可能为null
     //一直循环直到x=node,比如x=30、node=30
    //说明x就是我们要找的那个节点
        p = x;
        x = x.next;
    }
    if (x === null) { //false表示无法删除不在list里的节点
        return false
    } else if (x === p) { //删除第一个节点
        p = x.next
        return p
        //把新list的头节点p返回给外面,即newList=removeFromList(list, list)
    } else {
        p.next = x.next;
        return list // 如果删除的不是第一个节点,返回原来的list
    }
};
//删第一个节点
const list = createList(10);
const node = list // node 就是 list 的第一个节点了现在
const newList = removeFromList(list, node) // 必须用 newList 获取返回值才能拿到删除了第一个节点的新 list

//删其它节点
//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)

debugger看代码的执行过程。

5.travel遍历,打印list的每一项

解析:对每一项进行fn操作,直到x !== null

const travelList = (list, fn) => {
    let x = list
    while (x !== null) {
        fn(x) //fn(node)
        x = x.next
    }
}
const list = createList(10)
const node2 = appendList(list, 20)
const node3 = appendList(list, 30)
travelList(list, (node) => {
    console.log(node.data)
})

在这里插入图片描述

链表的变形

双向链表

每个节点有一个previous指向上一个节点

循环链表

最后一个节点的next指向头节点

双向链表:每个节点除了保存上个节点还保存了下个节点,那么这种链表就叫双向链表。

const createNode = value => {
    return {
        data: value,
        next: null,
        //previous:xxx
    }
}

循环列表 :最后一项不指向null而是指向第1项,每个链表的最后一项又回到第1项,这就是循环列表。

数据结构四:哈希表key-value pairs

哈希表是什么?

假设我们要找车,有3种方法:(n就是key的值)

解决办法

1’ 不做任何优化。一个一个找,hash[‘xxx’]需要遍历所有key,复杂度O(n)

2’ 对key排序。使用二分查找,每次从中间找。复杂度为O(log2 n)

3’ 对字符串对应的ASCII数字做索引。对索引做除法取余数。复杂度为O(1)

对每个字符串进行编号,比如a的ASCII是97,aaa编号后就是979797。 缺点:979797前的数字都用不到

处理方法: 对索引做除法取余数。979797除以1000得到就是0~999,就需要准备个长度为一千的容器容纳它就可以了。有冲突就放2个或者顺延。

哈希表的难点

哈希表难点在于,如何让你读出来时比较快。

数据结构五:树Tree

树 Tree 一个链多个 在这里插入图片描述

在这里插入图片描述

1.创建树,添加节点

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 tree = createTree(10)
const node2 = addChild(tree, 20)
addChild(tree, 30)
addChild(tree, 40)
addChild(tree, 50)
addChild(node2, 201)
addChild(node2, 202)
addChild(node2, 203)
addChild(node2, 204)
console.log(tree)

parcel src/linked_list.html

在这里插入图片描述

2.travel遍历节点

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)//对每个儿子再进行travel
    }
}
const tree = createTree(10)
const node2 = addChild(tree, 20)
const node3 = addChild(tree, 30)
addChild(tree, 40)
addChild(tree, 50)
addChild(node2, 201)
addChild(node2, 202)
addChild(node2, 203)
addChild(node2, 204)
console.log(tree)

travel(tree, node =>
    console.log(node.data)
)

3.查找节点

逻辑: 如果找到了就return tree。

如果有儿子就return儿子里的结果,如果儿子里都找不到就return undefind。 如果既不是我又不是我的儿子就return undefined。

const find = (tree, node) => {
    if (tree === node) {//找到了。如果有就return tree
        return tree
    } else if (tree.children) {//如果有儿子就return儿子里的结果
        for (let i = 0; i < tree.children.length; i++) {
            const result = find(tree.children[i], node)
            if (result) { return result }
        }
        return undefined //如果儿子里都找不到就return undefind
    } else { //如果既不是我又不是我的儿子就return undefined
        return undefined
    }
}
console.log(find(tree, node2))

在这里插入图片描述

4.删除节点

假设要删节点30,那就应该把存节点30的地址删掉。

找到哪个节点的children包含了要删掉的节点

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)
const node4 = addChild(tree, 40)
removeNode(tree, node4)
console.log(tree)

数组里只能支持下标删除

逻辑: 找到它的爸爸的儿子们,看它在爸爸的儿子们排第几。再从数组里把它删掉。 删除节点的主要目的,不是把这个节点搞没,而是把节点在这个树里的地址搞没。

在这里插入图片描述

以上就是数据结构:发明一个数据结构,然后看下怎么对它进行增删改查。

课后题

请问a是什么数据结构:

const a = []
a.push(1)
a.push(2)
a.push(3)
const item = a.pop() //1.栈
const item = a.shift() //2.队列

const a = { //3.哈希表
    name: 'frank',
    age: 18
}

const a = { //4.链表
  value: 1,
  next: {
      value: 2, 
      next: {
          value: 3,
          next: null
      }
  }
}

const a = { //5.树
  value: 1,
  children: [{value: 2, children: null}, {value:3, children: [
      {value:4, children: null}
  ]}]
}

总结

队列:先进先出

栈:先进后出

哈希表:用来存储key-value对

链表:一个链一个

树:

const a = {
  value: 1,
  children: [{value: 2, children: null}, {value:3, children: [
      {value:4, children: null}
  ]}]
}