你真的知道数据结构吗？

2019-03-11  本文已影响0人  沐雨芝录

前言：

普及一下顺序存储结构与链表存储结构。对应八大数据结构的数组和链表。

1）顺序存储结构的内存地址一定是连续的。
优点：存储密度大（＝1），存储空间利用率高。
缺点：插入或删除元素时不方便。

2）链表存储结构的内存地址不一定是连续的。
优点：插入或删除元素时很方便。
缺点：存储密度小（<1），存储空间利用率低。

八大数据结构：

const arr = new Aarray(100);
arr[0] = 1;

优点：
1、按照索引查询元素速度快
2、按照索引遍历数组方便

缺点：
1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加，删除的操作慢，因为要移动其他的元素。

适用场景：
频繁查询，对存储空间要求不大，很少增加和删除的情况。

链表的优点：
不需要初始化容量，可以任意加减元素；
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

缺点：
因为含有大量的指针域，占用空间较大；
查找元素需要遍历链表来查找，非常耗时。

适用场景：
数据量较小，需要频繁增加，删除操作的场景

a. 栈的特点是：先进先出。
b. 适用于多线程阻塞队列管理中。

a. 栈的特点是：先进后出。
b. 栈的插入称为进栈push。栈的删除称为出栈pop。
c. 栈常应用于实现递归功能方面的场景，例如斐波那契数列。

\color{blue}{一般我们都用二叉树，特点如下：}
相对本节点较小的值保存在左节点，相对本节点较大的值保存在右节点。

\color{blue}{完全二叉树：}
对于一个树高为h的二叉树，如果其第0层至第h-1层的节点都满。如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边。

\color{blue}{平衡二叉树：}
左子树高度 - 右子树高度 <=1 。(ps:子树高度计算，取最大节点数即可)。
当节点的平衡因子大于2时，说明是左子树深度偏大，此时需要右旋或者左右旋。小于2则反之。

定义：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)。

特点：
a. 堆是一棵完全二叉树
b. 从树根到子树数据分为从大到小（大顶堆），或者从小到大（小顶堆）

上一篇 下一篇

猜你喜欢

热点阅读