元素与元素的关系是怎样的,数据结构分哪些形式

Admin 2022-06-11 群英技术资讯

关于“元素与元素的关系是怎样的,数据结构分哪些形式”的知识有一些人不是很理解,对此小编给大家总结了相关内容,具有一定的参考借鉴价值,而且易于学习与理解,希望能对大家有所帮助,有这个方面学习需要的朋友就继续往下看吧。

逻辑结构反映的是数据元素之间的关系,它们与数据元素在计算机中的存储位置无关,是数据结构在用户面前所呈现的形式。根据不同的逻辑结构来分,数据结构可分为集合、线性结构、树形结构和图形结构4种形式,接下来分别进行简要介绍。

1)集合

在集合中,数据元素都属于这个集合,但数据元素之间并没有什么关系。它类似于数学中的集合,如图所示。

集合
集合

2)线性结构

线性结构中的元素具有一对一的关系,通过前一个结点可以找到后一个结点,图1-1的学生信息表就是一个线性结构,数据元素逐个排列。线性结构中前后两个结点互有联系。

线性结构分为顺序存储和链式存储两种。

顺序存储是由一段地址连续的空间来存储元素;链式存储是由分散的单元空间来存储元素,存储单元由指针相连接。简单的线性结构如图所示。

线性结构链式储存

在线性结构中,除头尾结点外,可以通过前一个结点来寻找后一个结点,也可以通过后一个结点来寻找前一个结点。

3)树形结构

树形结构中,数据元素之间存在一对多的层次关系。图1-4为一棵普通的树。除根结点外,树形结构的每一个结点都必须有一个且只有一个前驱结点,但可以有任意个后继结点。这些数据元素有自顶向下的层次关系。

树形结构

4)图形结构

图形结构中的数据元素存在多对多的关系,每个结点的前驱和后继结点都可以是任意个,如图1-5所示。

图形结构
按照逻辑结构,数据结构可以分为上述4种类型,在后续的深入学习中,本书会逐一详细讲解。

2.存储结构

数据结构除了按照逻辑结构来分,还可以按照存储结构来分。

存储结构反映的是数据元素在计算机中的存储形式,如何在计算机中正确地描述数据元素之间的逻辑关系,才是数据结构的关键与重点。常用的存储结构有顺序存储结构、链式存储结构、索引存储结构和散列表4种,接下来分别进行简要介绍。

1)顺序存储结构

顺序存储结构是把逻辑上相邻的结点存储在地址连续的存储单元里,数据元素之间的关系由存储单元是否相邻来体现。这种存储结构通常用高级语言上的数组来描述,数据的逻辑关系与物理关系是一致的。以数组inta[5]={100,20,3,56,266}为例,其中的元素a[0]~a[4]在逻辑上是连续的,在存储器中的物理地址也是连续的,如图1-6所示。

顺序结构

使用顺序存储结构存储数据时,系统为数据元素分配一段连续的地址空间。顺序存储结构可以提高空间利用率,而且对于随机访问元素,其效率非常高,因为逻辑上相邻的数据元素,其存储地址也是紧邻的,所以可以按元素序号来快速查找到某一个元素。

但也正因如此,如果要对顺序存储结构实现元素的插入和删除,效率则非常低。因为如果要插入一个元素,需要将这个位置之后的所有元素都向后移动一个位置;同样,如果要删除一个元素,需要将这个位置之后的所有元素都向前移动一个位置。

顺序存储结构在使用时有空间限制,当需要存取元素的个数多于预先分配的空间时,会出现“溢出”问题;当元素个数少于预先分配的空间时,又会造成空间浪费。

2)链式存储结构

链式存储结构在空间上是一些不连续的存储单元,这些存储单元的逻辑关系通过附加的指针字段来表示,例如C/C++语言中的指针类型,通过这些指针的指向来表明结点之间的联系。图1-3(b)为链式存储结构的示意图,但在此图中没有标明指针的指向。在链式存储结构中,可以有指向后继元素的指针字段,也可以有指向前驱元素的指针字段,如图1-7和图1-8所示。


插入元素T

这样在插入元素时不必移动任何一个元素,高效简洁。同理,当删除某一个元素时,只需将其前后两个元素连接起来即可,也无须移动其他元素。

但链式存储结构无法进行元素的随机访问。

对链式存储结构而言,空间利用率也较低,因为分配的内存单元有一部分被用来存储结点之间的逻辑关系。但链式存储在存储元素时没有空间限制,顺序存储与链式存储都是按需分配,只是链式存储可以在需要时方便地分配新空间,不会造成空间不足或者浪费。

3)索引存储结构

这种存储结构主要是为了方便查找数据,它通常是在存储结点信息的同时,还建立附加的索引表。索引表中的每一项称为索引项,它由两个字段组成:关键字与地址。其中关键字唯一标识一个结点,地址是指向结点的指针。这种结构类似于人们常用的字典,如图所示。

索引储存结构

索引存储结构

这种索引表一个索引项对应一个结点,叫作稠密索引。如果索引表中一个索引项对应一组结点,叫作稀疏索引,稀疏索引表如图1-11所示。

稀疏索引
稀疏索引

索引表可以快速地对数据进行随机访问。又因为在进行数据的插入和删除时,只需要更改索引表中的地址值,不必移动结点,所以在数据更改方面也具有较高的效率。但是索引存储结构在建立结点时会额外分配空间来建立一个索引表,因此降低了空间利用率。

4)散列存储结构

散列(hash)存储又称为哈希存储,是一种力图将数据元素的存储位置与关键字之间建立确定对应关系的查找技术。它的基本思想是通过一定的函数关系(散列函数,也称为哈希函数)计算出一个值,将这个值作为元素的存储地址。

散列存储的访问速度是非常迅速的,只要给出相应结点的关键字,它会立即计算出该结点的存储地址。因此它是一种非常重要的存储方法。数据存储的几种方式各有其优点,也各有其用途,不能说哪一种存储结构就比另一种好。在使用时,它们既可以单独使用,也可以组合起来使用,具体要根据操作和实际情况来决定采取哪一种方式,或者哪几种方式结合使用。



上述内容具有一定的借鉴价值,感兴趣的朋友可以参考,希望能对大家有帮助,想要了解更多"元素与元素的关系是怎样的,数据结构分哪些形式"的内容,大家可以关注群英网络的其它相关文章。

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:[email protected]进行举报,并提供相关证据,查实之后,将立刻删除涉嫌侵权内容。

猜你喜欢

成为群英会员,开启智能安全云计算之旅

立即注册
专业资深工程师驻守
7X24小时快速响应
一站式无忧技术支持
免费备案服务
免费拨打  400-678-4567
免费拨打  400-678-4567 免费拨打 400-678-4567 或 0668-2555555
在线客服
微信公众号
返回顶部
返回顶部 返回顶部