数据结构和数据存储结构

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

数据结构和数据存储结构

数据结构和数据存储结构是不同的：一个是逻辑概念上的一个是真实存储在计算机上的

数据的存储结构：顺序、链式、索引、散列
数据的存储结构是针对计算机来说的，指的是数据的逻辑结构在计算机中的表示，也就是说这些数据存储在计算机中到底是怎么存储的

而对于计算机来说数据元素之间的关系只有两种不同的表示方法：顺序映像和非顺序映像
顺序存储方法：把逻辑上相邻的结点存储在物理位置相邻的存储单元里，
链式存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。

还有两种数据的存储结构：索引存储结构和散列存储结构
索引存储结构：可以理解成是顺序存储结构和链式存储结构的结合
散列存储结构：选取某个函数，依照改函数来计算元素的存储位置，形成函数值和存储位置之间的一一对应，例如hash函数

数据的逻辑结构：集合、线性结构、树形结构、图形结构
线性结构和树形结构是最常用的两种高效数据结构
数据结构和数据存储结构是不同的：一个是逻辑概念上的一个是真实存储在计算机上的
数据的存储结构：顺序、链式、索引、散列
数据的存储结构是针对计算机来说的，指的是数据的逻辑结构在计算机中的表示，也就是说这些数据存储在计算机中到底是怎么存储的
而对于计算机来说数据元素之间的关系只有两种不同的表示方法：顺序映像和非顺序映像
顺序存储方法：把逻辑上相邻的结点存储在物理位置相邻的存储单元里，
链式存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。
还有两种数据的存储结构：索引存储结构和散列存储结构
索引存储结构：可以理解成是顺序存储结构和链式存储结构的结合
散列存储结构：选取某个函数，依照改函数来计算元素的存储位置，形成函数值和存储位置之间的一一对应，例如hash函数

数据的逻辑结构：集合、线性结构、树形结构、图形结构
线性结构和树形结构是最常用的两种高效数据结构
线性数据结构：数组、链表、队列、栈
列表：普通的数组形式、链表形式
队列：先进先出，删除在队首，添加在队尾
栈：后进先出，添加和删除都在栈顶实现
线性的数据结构的主要特点是首无前驱，尾无后继，中间的元素有唯一的前驱和后继

数组的时间复杂度：访问O(1)、查找（不知道在哪）O（n）、插入和删除O（n）

单链表的时间复杂度：查找、插入和删除都是O（n），但其优势在于当我们知道要插入、删除的位置之后，我们的插入删除都是O(1)

队列：分为普通队列（容易出现假上溢）和循环队列（一般常用）
一般队列是放在一个向量空间（又称线性空间）里面的，在这一段连续的存储空间中，由一个队列头指针和一个尾指针表示这个队列，当头指针和尾指针指向同一个位置时，队列为空，也就是说，队列是由两个指针中间的元素构成的。在队列中，入队和出队并不是象现实中，元素一个个地向前移动，走完了就没有了,而是指针在移动，当出队操作时，头指针向前(即向量空间的尾部)增加一个位置，入队时，尾指针向前增加一个位置，在某种情况下，比如说进一个出一个，两个指针就不停地向前移动，直到队列所在向量空间的尾部，这时再入队的话，尾指针就要跑到向量空间外面去了，仅管这时整个向量空间是空的，队列也是空的，却产生了”上溢”现象，这就是假上溢。

为了克服这种现象造成的空间浪费，我们引入循环向量的概念，就好比是把向量空间弯起来，形成一个头尾相接的环形，这样，当存于其中的队列头尾指针移到向量空间的上界(尾部)时，再加1的操作(入队或出队)就使指针指向向量的下界，也就是从头开始。这时的队列就称循环队列。
a) 如果只有头指针，且含头结点
1. 出队: O(1)，因为只要把头结点的下一个结点删除就好了
2. 入队: O(n)，要把新的结点插入到队尾，必须把队列历遍，找到队尾，才能插入
b) 如果只有头指针，不含头结点
1. 出队: O(n)，要把头结点删除，必须历遍队列，找到队尾，才能更新头指针 (循环单链的缘故，如果仅仅是普通单链，则本操作也是O(1) )
2. 入队: O(n)，同 (a).2
c) 如果只有尾指针
1. 出队: O(1)，只要把尾指针的下一个结点(没有头结点的情况)或者下下个结点(有头结点的情况)删除即可
2. 入队: O(1)，只要在尾指针的后面插入新的结点，并更新尾结点，所以是O(1)

栈数据结构：栈的数据操作只能在线性表的一端进行，例如子弹夹，Word等的撤销操作等，但是明显有很多的限制
因此其时间空间复杂度都是O(1)

二叉树
基础：
数据的逻辑结构：集合、线性结构、树形结构、图形结构
线性结构和树形结构是最常用的两种高效数据结构
现行
二叉树就是每个结点最多有两个子树的树结构，通常子树称为左子树和右子树
二叉树的度：
子树就是二叉树的分支，度就是分支的数目
没有分支的二叉树结点其度就是0度，如果一个结点只有一个分支就是一度，而两个分支就是两度，二叉树不存在度大于2的结点
二叉树在查找上有着巨大的先天优势，其查找，插入和删除的算法时间复杂度可以控制在log2n级别，
而数组链表：
数组的时间复杂度：访问O(1)、查找（不知道在哪）O（n）、插入和删除O（n）

二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：
1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
2. 树的结点无左、右之分，而二叉树的结点有左、右之分。

叶子结点：除了根节点其他所有的结点都是其父结点的子结点，但是最底层的无子结点的结点也称为叶子结点，很形象吧，树上的叶子就是数的最外面

满二叉树：
除最后一层无任何子结点外，每一层的所有结点都有两个子结点的二叉树

如图：
很形象，就是二叉树所有的位置都被填满，因为要求次底层的所有结点都必须有两个子结点，所以最底层也是被填满的

完全二叉树：
只有最下面的两层结点，其度能够小于2，并且最下面一层的结点都集中在该层的最左边的若干位置的二叉树，如图：

如此图：
最下面的结点不用说其结点必然为0，不然就不是最下面一层，而其上面一层如果其度也都是二，那也太巧了，而且不能再向里面放数据了，所以允许其度是1或者0。而且所有你想要向其中放数据的时候，因为其规则只能放在左子树那边，因此遍历的时候效率最高，
注意完全二叉树是由满二叉树引出来的，满二叉树和完全二叉树的唯一区别就是完全二叉树的最底层是没有填满的，而且缺失的集中在最右边
完全二叉树的特点：
1、完全二叉树通常采用数组而不是链表存储
2、注意上图中二叉树结点的顺序：每一层的顺序，都是从左向右依次递增，而且是逐层递增
3、只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；
4、对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个
计算完全二叉树的叶子结点数的算法：
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数
则 ①n= n0+n1+n2 （其中n为完全二叉树的结点总数）；这个好理解
又因为一个度为2的结点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他结点都有父结点，所以②n= 1+n1+2*n2 ；这个你要结合上图来理解，2*n2指的是从下往上遍历：每个度为2的结点都有两个子结点，依次累加向上到根结点，这样就把除了根结点之外的所有度为2 的结点以及其子结点都计数了一次。然后二叉树中就剩下了根结点，以及度为1的结点的子结点个数没有统计了，于是得出公式：②n= 1+n1+2*n2
由①、②两式把n2消去得：n= 2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。
简便来算，就是 n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=1）。可根据完全二叉树的结点总数计算出叶子结点数。