【算法与数据结构03】数据结构（上）

队列和栈

队列`Queue`

「先进先出FIFO」的数组

题目

请实现一个餐厅叫号网页

点击「取号」按钮生成一个号码

点击「叫号」按钮显示请X号就餐

手写队列`Queue`

首先选择队列Queue作为数据结构
queue.push()为入队，queue.shift()为出队
用call()来调用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


const divScreen = document.querySelector('#screen')
const btnCreateNumber = document.querySelector('#createNumber')
const btnCallNumber = document.querySelector('#callNumber')
    /* 取到 当前号码对应的span */
const spanNewNumber = document.querySelector('#newNumber')
const spanQueue = document.querySelector('#queue') // 取到 当前队列

/* 监听用户取号
 ** 声明一个号 n = 0 默认无人排队
 ** 声明队列数组 queue
 */
let n = 0
let queue = []

/* 点击取号时显示 当前号码 */
btnCreateNumber.onclick = () => {
    n += 1
    queue.push.call(queue, n) // 将取得的好记录下来 // queue.push(n)
    spanNewNumber.innerHTML = n
        // spanQueue.innerText = queue.toString() // spanQueue.innerText = queue.toString()  只能显示字符串，会用逗号连接 不美观 1,2,3,4,5 变为字符串格式的[]
        /* JSON.stringify 将对象变为带有原对象格式的字符串  */
    spanQueue.innerText = JSON.stringify(queue)
}

/* 点击叫号时 出队 */
btnCallNumber.onclick = () => {
    /* 排除叫完号 出现 m === undefined */
    if (queue.length === 0) {
        divScreen.innerText = `取号完毕`
        return;
    }
    //const m = queue.shift()
    const m = queue.shift.call(queue)
    divScreen.innerText = `请 ${m} 号就餐`
    spanQueue.innerText = JSON.stringify(queue) // 队列更新，再次打印到span里 放到span里
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


<!doctype html>
<html lang="ZH-chs">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>队列示例</title>
    <link rel="stylesheet/scss" lang="scss" href="./style.scss">
    <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>

样式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


* {
    box-sizing: border-box;
    margin: 0;
    padding: 0;
}

#screen {
    border: 1px solid #000;
    width: 200px;
    height: 200px;
}

队列：类似数组的结构，只提供入队queue.push(n)，和出队queue.shift()两个操作

实现示例的仓库

栈`Stack`

「后进先出LIFO」的数组

栈的例子

坐电梯
JS函数的调用栈call stack就是一个栈
假设f1调用了f2，f2又调用了f3
那么f3结束后应该回到f2，f2结束后应该回到f1

栈的代码

1
2
3
4


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

画压栈、出栈的过程

栈：类似数组的结构，只提供入队queue.push(n)，和出队queue.pop()两个操作

思考：内存图里的栈内存和此处调用栈的关系、是否占据同一块内存

链表`Linked List`

一个链一个，X体蜈蚣

手写链表`Linked List`

1
2
3
4
5
6
7
8


let array = [1, 2, 3]
array.__proto__ === Array.prototype
Array.prototype.__proto__ === Object.prototype
// JS原型链是一种链表，JS的每一个对象都是属于链表

/* 可以跳链 即将原型重新指向 */
array.__proto__ = Object.prototype
array.push // undefined

实例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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

/* 增加节点 */
const appendList(list, value)=>{
    const node = {
        data: value,
        nestL null
    }
    list.next = node
    return node
}
/* 在控制台看数据结构 */
console.log("node")
console.log(node)
console.log("list")
console.log(list)

合并，缩减代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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 node2 = appendList(list, 20)
const node3 = appendList(list, 30)

修改appendList，使增加的node加到最后一个节点上

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


const appendList = (list, value) => {
    const node = createNode(value);
    /* 使 x 是最后一个节点 */
    let x = list;
    while (x.next) { // x 非空 即不是最后一个节点
        x = x.next;
    }
    // x.next === null; // x 是最后一个节点
    x.next = node;
    return node;
};

删除节点的思路

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


const createList = (value)=>{
    return createNode(value)
}
const appendList = (list, value) => {
    const node = createNode(value);
    /* 使 x 是最后一个节点 */
    let x = list;
    while (x.next) { // x 非空 即不是最后一个节点
        x = x.next;
    }
    // x.next === null; // x 是最后一个节点
    x.next = node;
    return node;
};
/* 节点跳链 */
const removeFromList = (list, node)=>{
    // 遍历
    if(list === node){
    // 如果删除的是第1个节点
        list = node.next
        // 第一个节点 自动被回收
    }else{
    // 如果删除的是第2个节点
    // 就让第1个节点.next = 第2个节点.next
        if(list.next === node){
            list.next = node.next
            // 第2个节点 自动被回收
        }else{
            // 开始递归了
    // 如果删除的是第3个节点
    // 就让第2个节点.next = 第3个节点.next
            if(list.next.next === node){
                (list.next).next = node.next
            }
        }
    }
}
/* 优化 去掉重复代码 抽像 */
const createNode = (value)=>{
    return {
        data: value,
        next: null
    }
}
const list = createList(10)
const node2 = appendList(list, 20)
const node3 = appendList(list, 30)

用递归或循环来删除节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


const createNode = (value)=>{
    return {
        data: value,
        next: null
    }
}
const createList = (value)=>{
    return createNode(value)
}
const appendList = (list, value) => {
    const node = createNode(value);
    /* 使 x 是最后一个节点 */
    let x = list;
    while (x.next) { // x 非空 即不是最后一个节点
        x = x.next;
    }
    // x.next === null; // x 是最后一个节点
    x.next = node;
    return node;
};
/* 用循环实现 删除节点 */
const removeFromList = (list, node) => {
    let x = list;
    let p = null; // 上一个节点 默认是空
    while (x !== node) { // x 不等于 node， 先记下 x 给 p，让下一个节点赋值给 x
        p = x; //  先记下 x 给 p
        x = x.next
    }
    // console.log(p === null || p /* x 的上一个节点 */);
    // console.log(x === node || x === null);
    p.next = x.next;
    if (list === node) { // 如果删除的是第一个节点
        // list 指向 第二个节点
        list = node.next //即删除传入的节点
    }
};
const list = createList(0);
const node1 = appendList(list, 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

Sources里一步步运行步进代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


const createNode = (value)=>{
    return {
        data: value,
        next: null
    }
}
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) => {
    debugger;
    let x = list;
    let p = null;
    while (x !== node) {
        p = x;
        x = x.next
    }
    p.next = x.next;
    if (list === node) {
        list = node.next
    }
};
const list = createList(0);
const node1 = appendList(list, 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);

遍历操作节点 travel

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


/* 遍历操作节点 `travel` */
const travelList = (list,fn) => {
    let x = list;
    while (x !== null) {
        fn(x); // 操作节点
        x = x.next
    }
};
travelList(list, node => {
    console.log(node.data);
});

查找第几个节点

1
2
3


node = get(index)
// 遍历 1 次 记个1；
// 遍历 index 次 返回节点

removeFromList 存在 bug

那就是无法删除第一个节点，示例如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


const list = createList(10);
const node = list // node 就是 list 的第一个节点了现在
removeFromList(list, node) // 你会发现 list 没有任何变化
const newList = removeFromList(list, node) // 就算获取返回值也没有用，因为根本就没返回新 list
/*  Uncaught TypeError: Cannot set property 'next' of null
*   at removeFromList (<anonymous>:71:12)
*   at <anonymous>:1:1
*   removeFromList @ VM343:71
*   (anonymous) @ VM658:1
*   null 不存在任何属性 也不能添加任何属性
*/

正确的实现方法为：

（P.S. 当然还有其他更优雅的实现方法，比如将头指针改为头结点，不过有点超纲，就不说了）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


//list.js
const removeFromList = (list, node) => {
  let x = list;
  let p = node; // 课堂里将 p 初始化为 null，这里改为 node
  while (x !== node && x !== null) { // 课堂里忘了对 null 进行处理，如果 node 不在 list 中，x 就可能为 null
    p = x;
    x = x.next;
  }
  if(x === null){ // 若 x 为 null，则不需要删除，直接 return， 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

链表代码小结

1
2
3
4
5
6


/* 创建链表 增删改查 */
list = create(value)
node = get(index)
append(node, value)
remove(node)
travel(list, fn)

链表的变形

双向链表

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

循环链表

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

链表的代码，注意看代码里的注释

哈希表`key-value pairs`

「哈希表」是什么？有哪些常用的解决冲突（碰撞）的方法？

程序员必须掌握哪些算法？

哈希表的难点

存的越多，读得越慢

场景

假设哈希表 hash 里有一万对key-value，比如name:'xxx', age:'18', p1:'property1'...

如何使得读取hash['xxx']速度最快

解决办法

不作任何优化，hash['xxx']需要遍历所有key，复杂度O(n)，成本太大
对key排序，使用二分查找，复杂度O(log2 n)
用字符串对应的ASCII码数字做索引，存入数组，复杂度O(1)
项目多的时候，数组下标太大
对索引做除法去余数（除以1000，长度为1000的数组）.复杂度O(1)
冲突了就顺延（或叠在一起，“立体”，开链表法）

手写哈希表`key-value pairs`

1

hashTable["yyy"]

树`tree`

一个链多个，链表的扩充

画图

实际使用场景

省市区
层级结构
网页节点DOM

控制台Elements里按Alt收缩所有节点

代码

手写

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


const createTree = value => {
    return {
        data: value,
        children: null
    }
};
/* 增加节点 */
const addChild = (node, value) => { // 每次在一个节点上 加一个孩子（值）
    const newNode = {
        data: value,
        children: null
    };
    /* 父节点 有可能是空 也有可能是数组 保底值 */
    node.children = node.children || [];
    node.children.push(newNode);
    /* 将加了子节点的新节点 返回 */
    return newNode
};
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);

遍历树的一种实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


// 紧接前面的代码
/* 删除节点的过程中，必须先遍历节点，先确保要删除的节点存在于当前父节点中 */
const travelTree = (tree, fn) => { // 所谓遍历，就是把每一个节点的值打出来
    // debugger;
    /* 首先 打印 tree上的每一个值，先遍历根节点 */
    fn(tree);
    /* 其次 再打印 tree上的每一个节点的值，可用 forEach遍历数组 children
    * // children 如果为空 就不应该被遍历 所以要加判断
    *  */
    if (!tree.children) {
        return;
    }
    for (let i = 0; i < tree.children.length; i++) {
        travelTree(tree.children[i], fn)// 把子节点作为一个树，再遍历一下
    }
};

/* 为打断点 */
const fn = node => {
    // debugger;
    console.log(node.data);
};
travelTree(tree, fn);

先打出根，再把左边打出来，再打出右边
即先根遍历

删除节点

思路

先找到被要删除children的属性所在的数组
从保存属性的数组那里删除节点
哪个节点保存了要删除节点的属性
找到这个节点的父亲（找子节点容易找父节点难）
用类似双向链表，在属性中记录父节点parent: node;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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
};

实现查找节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


/* 抽象一个查找函数 find()
* 判断一棵树里是否有要查找的节点
* 即查找这棵树的子树里是否存在 要查找的节点
* 当前节点是否匹配 子节点里遍历查找
*  */
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 // 未找到
    }
};
console.log('找到了');
console.log(find(tree, node2));

实现删除节点（需要遍历）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


/* 删除节点 */
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
        }
    }
    // 得到要删除节点的下标index
    siblings.splice(index, 1)
};
console.log(tree);
removeNode(tree, node5);
console.log(tree);

注意chrome控制台点开刷新对象的bug
删除一个节点的本质就是删除这个节在树里的地址
不能把sibling[i] = null，树中还存在地址，任然占位

树的小结

1
2
3
4
5


let tree =  createTree(value)
let node = createNode(value)
addChild(tree, node)
removeChild(node1, node2)
travel(tree)

遍历一棵树，简单的递归

参考文章

数据结构(上)

作者： Joel
文章链接：
版权声明
非自由转载-非商用-非衍生-保持署名
河掘思知简

【算法与数据结构03】数据结构（上）

文章目录

目录

队列和栈

队列`Queue`

题目

手写队列`Queue`

栈`Stack`

栈的例子

栈的代码

画压栈、出栈的过程

链表`Linked List`

手写链表`Linked List`

控制台打断点，debugger

链表代码小结

链表的变形

双向链表

循环链表

哈希表`key-value pairs`

哈希表的难点

场景

解决办法

手写哈希表`key-value pairs`

树`tree`

画图

实际使用场景

代码

参考文章

相关文章

文章目录

目录

队列和栈

队列Queue

题目

手写队列Queue

栈Stack

栈的例子

栈的代码

画压栈、出栈的过程

链表Linked List

手写链表Linked List

控制台打断点，debugger

链表代码小结

链表的变形

双向链表

循环链表

哈希表key-value pairs

哈希表的难点

场景

解决办法

手写哈希表key-value pairs

树tree

画图

实际使用场景

代码

参考文章

相关文章

队列`Queue`

手写队列`Queue`

栈`Stack`

链表`Linked List`

手写链表`Linked List`

哈希表`key-value pairs`

手写哈希表`key-value pairs`

树`tree`