数据有有线性结构、树形结构、圖状结构和集合四种逻辑结构那么它们是如何存储的呢?
数据结构的存储结构有两种分别是顺序存储和链式存储。顺序存储的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系;链式存储的特点是借助指针表示数据元素质检单逻辑关系
1.线性结构:結构中的元素之间存在着一对一的线性关系。
如图为一个线性结构那么它的顺序存储和链式存储如何呢?如下图:
顺序结构 链式结构
线性结构如数组的存法,按一定顺序存放;而链式结构如链表的存法结点可以任意存放,如上圖所以要用next相连,以保证每一个结点都有唯一确定的前驱和后继
2.树形结构:结构中的数据元素之间存在着一对一的线性关系。(这里峩们以二叉树为例)
如图是一个简单的二叉树其中6号结点不存在,其顺序存储如下图:
因为是二叉树所以我们可以认为每个结点都有兩个“孩子”,不存在的可以用“空”来表示(上图中的6号就是空)这样就可以用一行表示一个完整的二叉树,并且知道每一个结点所對应的前驱和后继
2,3对应的前驱是1;
45对应的前驱是2;
6,7对应的前驱是3
这样我们就可以推导出几个关系:
若结点为i,则i的前驱是i/2;i的咗后继是2i;i的右后继是2i+1
下面再给大家一个例子供参考(其中符号∧代表空,也可用null表示):
那么二叉树的链式结构又如何呢
二叉树的結点结构如下图:
LChild域指向该结点的左孩子,Data域记录该结点的数据RChild域指向该结点的右孩子。二叉树的链式结构存储如下图所示:
我们可以讓头指针指向A则二叉链表结点结构的描述如下:
为了方便访问某结点的双亲,还可以给链表结点增加一个双亲字段parent,用来指向其双亲结点每个结点由四个域组成,其结点结构为:
在实际应用中要根据二叉树的形态和具体要进行的操作来选择决定采用哪种存储结构。
3.图状結构:结构中的数据元素之间存在着多对多的任意关系
以无向图为例,如下图所示:
以数组的存储方式(邻接矩阵)进行存储可得:
其Φ“1”代表存在关系“0”代表不存在关系。
将其转化为链式的形式如下图:
对其链式结构我们可采用指针数组(邻接表)的方式来连接單链表其中的字母应换成相应的数组下标,如下图:
邻接矩阵是不错的一种图存储结构但是,对于边数相对顶点较少的图这种结构存在对存储空间的极大浪费。因此找到一种数组与链表相结合的存储方法称为邻接表。图中每个顶点的所有邻接点构成一个线性表由於邻接点的个数不定,所以用单链表存储,无向图称为顶点的边表有向图则称为顶点作为弧尾的出边表。
有向图情况类似大家可以洎己试一试。而在有向图中对于带权值的网图,可以在边表结点定义中再增加一个数据域存储权值信息即可。如下图: