【JS算法】JS数据结构

JavaScript05

【JS算法】JS数据结构,第1张

数组: 是由相同类型的元素的集合所组成的数据结构,分配一块连续的内存来存储。知道第一个元素的内存地址,加上下标(偏移量)就能找到第2或N个。

数组随机访问的速度快,增加和删除则慢(因为删除index2,后面的3-n都要往前挪一位)

链表: 非连续存储的指向型存储,随机访问的速度慢(需一层层查找),增加和删除则快(不需要挪位)

树形结构、图形结构

树形结构又指向其他树点,就是图形结构

图结构,在webpack和vite中有用到,作用是,能找出是否有文件被重复加载

堆和栈

对象是数组+链表的结构

只要是树形结构,解答基本都可以用递归解决

在实际的工作和业务需求中,我们经常会碰到树形数据结构,比如公司组织架构、组织层级、省市县或者事物的分类等等数据。那么在JavaScript中如何将数组转为树形结构和树形结构转为数组,本文就详细的来探究一下。

先来看看给出了一组怎样的数据,转换为怎样的树形结构。

后台接口返回或者面试官给你的数据:

期望的处理后的数据:

如果后台给了一个这样的数据说让前端自己去转换为树形结构或者面试官给你一组这样的数据让你手写一个转换方法,你会怎么处理?

1、递归实现

2、Map对象实现

3、filter实现

这种方法很有意思,可能大多数人想不到,也是从大佬处学到的(读书人的是怎么能叫抄呢,应该叫“窃”)。

1、reduce取树行数据的所有子集

2、递归实现

3、广度优先遍历法

比较相邻的元素,如果前一个比后一个大,交换之。

第一趟排序第1个和第2个一对,比较与交换,随后第2个和第3个一对比较交换,这样直到倒数第2个和最后1个,将最大的数移动到最后一位。

第二趟将第二大的数移动至倒数第二位

......

因此需要n-1趟;

选择排序,从头至尾扫描序列,找出最小的一个元素,和第一个元素交换,接着从剩下的元素中继续这种选择和交换方式,最终得到一个有序序列

链表:存贮有序元素的集合,

但是不同于数组,每个元素是一个存贮元素本身的节点和指向下一个元素引用组成

要想访问链表中间的元素,需要从起点开始遍历找到所需元素

类似对象,以key,value存贮值

特点:每个节点最多有两个子树的树结构