signed

QiShunwang

“诚信为本、客户至上”

5-4 数据结构(队列、栈、链表、哈希表、树)

2021/4/26 22:28:16   来源:

之前用过的数据结构
1、数组
数组可以分为队列、栈等
2、哈希表
用来存储key-value

学习数据结构的好处

  • 知道哪一类问题应该用什么类型来解决

1.队列Queue

先进先出 FIFO(first-in-first-out) 的数组

1.题目

  • 实现一个餐厅叫号网页
  • 点击 [取号] 按钮生成一个号码
  • 点击 [叫号] 按钮显示 [请X号就餐]

2.代码

  • 首先选择队列queue作为数据结构
  • queue.push为入队/queue.shi为出队
  • 注意:做的所有网页都是手机上运行的
  • 记得练习一下call的用法
    所有的函数调用都可以用call

2.栈Stack

先进后厨 LIFO(Last-in-First-out) 的数组

1.举例
(类似于进电梯,先进的在里面,后进的在外面,电梯到了,后进的先出去)

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

2.代码

  • 压栈 push
  • 弹栈 pop

3.内存图里的栈内存和这个调用栈

  • 是什么关系?——关系很大
  • 是同一块内存吗?——有很大的重叠

链表 Linked List

一个链一个

1.实际使用

  • 原型链
  • 可以随时把链条中间的一个断掉,只需要让前一个链接到后一个,把需要断掉的跳过即可

2.创建链表(增删改查)

  • list = create(value)创建链表
  • node = get(index)创建对象
  • append(node,value)增加节点
  • remove(node)删除节点
  • travel(list,fn)遍历链表
const creatList = (value) => {
  //创建一个节点
  return creatNode(value);
};
const appendList = (list, value) => {
  //添加一个节点
  const node = creatNode(value);
  let x = list;
  while (x.next) {
    x = x.next;
  }
  x.next = node;
  return node;
};
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 travelList = (list, fn) => {
  //遍历链表
  let x = list;
  while (x !== null) {
    fn(x);
    x = x.next;
  }
};

const creatNode = (value) => {
  //创建一个对象
  return {
    data: value,
    next: null,
  };
};

const list = creatList(10);
const node2 = appendList(list, 20);
const node3 = appendList(list, 30);
travelList(list, (node) => {
  console.log(node.data);
});

3.链表的变形

  • 双向链表
    每个节点都有一个previous指向上一个节点
  • 循环链表
    最后一个节点的next指向头节点

哈希表

key-value pairs
哈希表的讲解

1.场景

  • 假设哈希表hash里有一万对key-value
  • 比如 name:‘frank’,age:18,p1:‘property1’,…
  • 如何使得读取hash[‘xxx’]速度最快

2.解决办法

  • 不做任何优化,hash[‘xxx’]需要遍历所有key,O(n)

  • 对key排序,使用二分法查找,O(log2n)
    二分法:每次找中间的,小了就往下,大了就往小

  • 用字符串对应的ASCII数字做索引,O(1)

  • 对索引做除法取余数,O(1)
    直接算到其对应的号码

  • 冲突了怎么办?冲突了就顺延

树 tree

一个链多个

1.实际应用

  • 中国的省市区,可以看成一棵树
  • 公司的层级结构
  • 网页中的节点

2.代码

  • let tree = creatTree(value)
  • let node = createNode(value)
  • addChild(tree,node2)
  • removeChild(node1,node2):删掉node1中的node2,这里的删掉不是删value,而是把地址也删掉
  • travel(tree)
const creatTree = (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 removeNode = (tree, node) => {
  //删除节点
  const siblings = node.parent.children; //找到node的兄弟姐妹
  let inde = 0; //数组只能通过下标删除元素
  for (let i = 1; i < siblings.length; i++) {
    if (siblings[i] === node) {
      index = i;
    }
  }
  siblings.splice(index, 1);
};

const tree = creatTree(30);
const node2 = addChild(tree, 20);
const node3 = addChild(tree, 30);
addChild(tree, 40);
const node5 = addChild(tree, 50);
addChild(node2, 201);
addChild(node3, 202);
console.log(tree);
//由于下面有了remove,这里打印出来的树也没有node5,这是Chrome的bug,点开即刷新页面
const fn = (node) => {
  console.log(node.data);
};
travel(tree, fn);

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