什么是数据结构？
所谓数据结构就是计算机组织存储数据的方式。
通俗的讲就是将数据以怎样的结构存储到计算机里面。
JS中最常见的数据结构就是数组，这种数据结构将多个数据有序的排列到一起，形成组合。
除此之外，还有ES6新增加的数据结构集合Set、映射Map等。
八种常见的数据结构
1：列表
概述：
列表很简单，如待办事项列表、购物清单、最佳十名榜单等。
所谓的简单并不是指形式上的简单，而是指操作复杂度的简单。
适用情况：
● 数据结构相对简单
● 不需要在一个长列表中进行查找或者排序
JS实现列表：
一个列表应具有以下属性：
● 元素项
● 元素个数：列表长度
● 当前元素位置
● 插入
● 删除
● 清空
● 移动
● 查找
2：栈
概述：
栈是一种特殊的列表，栈中的元素只能通过栈的一端进行删除或添加，这一端被称为栈顶。这样的操作速度很快。比如我们现实中的一叠盘子，放入在顶部，取盘子也是从顶部取。这样就形成了一个很明显的特征：先入后出、后入先出。
适用情况：
● 满足先入后出或后入先出条件的，优先考虑栈。
用JS实现栈：
3：队列
概述：
队列也是一种列表，在列表的尾部添加元素，列表头部删除元素。
比如我们生活中常见的排队。先入先出，后入后出。
适用情况：
● 满足先入先出，后入后出的特点，优先考虑队列。
● 消息机制，进程调度等。
用JS实现队列：
4：链表
概述：
链表由一系列结点组成，每一个结点包含一个存储数据的数据域和存储下一个结点地址的指针域。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
链表类型：
● 单向链表
链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。
最后一个指向NULL的指针。
● 双向链表
它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。最后一个指向NULL的指针。
● 循环链表
表中最后一个结点的指针域指向头结点，整个链表形成一个环。
JS实现单向链表：
5：字典
概述：
以键值对形式存储数据的数据结构，如JS中的对象类就是按字典的形式设计的。
用JS实现字典：
6：散列表
散列表概述：
散列表即Hash Table，又叫做哈希表。
是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表的查找过程基本上和造表过程相同，一些关键码可通过散列函数转换的地址直接找到。另一些关键码在散列函数得到的地址上产生冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突的查找依然是给定值与关键码进行比较的过程，所以对散列表查找效率的质量度依然用平均查找长度（装填因子α的函数）来衡量。
查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：
1. 散列函数是否均匀；
2. 处理冲突的方法；
3. 散列表的装填因子α = 数据元素个数 / 散列表表长
Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。
散列函数概述：
Hash, 一般翻译为散列、杂凑，音译为哈希。
特点是把任意长度的输入通过散列算法变换成固定长度的输出。该输出就是散列值。
这种转换是一种压缩映射，也就是说，散列值的空间通常远小于输入空间。
不同的输入有可能得到相同的输出，所以不能通过散列值来确定唯一的输入值。
简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。
碰撞（冲突）：
两个不同的输入，经过散列后得到一样的输出，这种情况就是碰撞。
Hash算法是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。
常用的散列算法有：
①：直接寻址法
取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）
②：数字分析法
分析数据中数字，找出规律，尽可能的利用这些数据来构造冲突几率较小的散列地址。
例如：我们要存储一个班上学生的身份证号码，已知这个班级的学生出生年份、出生地区相同，这就意味着他们身份证号码的前几位相同。那么我们就取后身份证的后5位（假设后五位不同）来代表地址。
③：平方取中法
取关键字平方后的中间几位作为散列地址。
如果关键字的每一位都有某些数字重复出现频率很高的现象，可以先求关键字的平方值，通过平方扩大差异，而后取中间数位作为存储地址。
例如：
key=1234 1234^2=1522756 取227作hash地址
key=4321 4321^2=18671041 取671作hash地址
这种方法适合事先不知道数据并且数据长度较小的情况
④：折叠法
将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
例如：
key = 124 778 912 345
每三位一组，然后叠加和为2159，取后三位159作为最终存储地址。
⑤：随机数法
选择一随机函数，取关键字的随机值作为散列地址，即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合。
⑥：除留余数法
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。
对p的选择很重要，使得数据元素集合中每一个关键字通过该哈希函数映射到内存单元的任意地址上的概率相等，从而尽可能减少发生哈希冲突的可能性。
一般取素数（即质数）或m，且p最好取1.1n～1.7n之间的一个素数（n为存在的数据元素个数）。
如：当n=7时，p最好取11、13等素数。
例题：key = 13、58、17、33、24、61、10；表长为13；我们取13作为p，那么最终存储如下：
处理冲突的常用方法：
①：开放寻址法
Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key）为散列函数，m为散列表长，di为增量序列，可有下列三种取法：
☀. di=1,2,3，…，m-1，称线性探测再散列；
☀. di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k<=m/2）称二次探测再散列；
☀. di=伪随机序列，称伪随机探测再散列。
②：再散列法
Hi=RHi(key),i=1,2，…，k
RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
③：链地址法
在哈希表每一个单元中设置链表，某个数据项对的关键字还是像通常一样映射到哈希表的单元中，而数据项本身插入到单元的链表中。
例题：key = 13、58、17、26、23、33、24、61、10；表长为13；我们取13作为p，用链地址法解决冲突后存储结构如下图：
④：建立公共溢出区
为所有冲突的关键字记录建立一个公共的溢出区来存放。在查找时，对给定关键字通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表进行顺序查找。如果相对于基本表而言，在有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。
还是之前那个例子
7：二叉树及二叉查找树
二叉树概述：
在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树 和二叉堆。
一棵深度为k，且有(2^k)-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2^(k-1)个叶子结点，至多有(2^k)-1个结点。(^代表乘方)
平衡二叉树概述：
平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
对一棵查找树（search tree）进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。
二叉查找树概述：
又叫二叉排序树，亦称二叉搜索树。
一颗空树或者满足以下性质的二叉树就是二叉查找树。
● 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
● 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
● 左、右子树也分别为二叉排序树；
● 没有键值相等的结点。
堆（一类特殊数据结构的统称）
概述：
堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。
堆总是满足下列性质：
● 堆中某个节点的值总是不大于或不小于其父节点的值；
● 堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆。
根节点最小的堆叫做最小堆或小根堆。
常见的堆有二叉堆、斐波那契堆等。
二叉堆其实就是满足堆性质的完全二叉树。
堆是非线性数据结构，相当于一维数组，有两个直接后继。
索引i的规律(n是元素个数)
● 如果i = 0, 它是根节点。
● 如果i > 0, 它是父节点的索引为floor((i - 1) / 2)。
● 如果2i + 1 <= n - 1, 它的左子节点索引为2i + 1。
● 如果2i + 1 > n - 1, 它无左子节点。
● 如果2i + 2 <= n - 1, 它的右子节点索引为2i + 2。
● 如果2i + 2 > n - 1, 它无右子节点。
斐波那契堆：
斐波那契堆(Fibonacci heap)是计算机科学中最小堆有序树的集合。它和二项式堆有类似的性质，但比二项式堆有更好的均摊时间。堆的名字来源于斐波那契数，它常用于分析运行时间。
参考：https://www.cnblogs.com/junyuhuang/p/4463758.html
二叉树遍历的方法
具体实现方式
8：图
概述：
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
图的存储结构除了要存储图中的各个顶点本身的信息之外，还要存储顶点与顶点之间的关系，因此，图的结构也比较复杂。常用的图的存储结构有邻接矩阵和邻接表等。
网友评论